# tulpan257

by majo

Points: 451 (Dynamic, 24 solves)

Description:

We made a ZK protocol with a bit of HFS-flair to it! announcement 2019-04-05 16:33:51 UTC tulpan257 Correction of description, prover does not take a string, but a polynomial

Given: chall.sage

# Solution:

## TLDR

1. The zero-knowledge being implemented works in the quotient ring $$\mathcal{R} = \mathbb{F} _ p[x]/(x^k + 1)$$. A secret $$s \in \mathcal{R}$$ is masked by a polynomial $$r \in \mathcal{R}$$, as $$m = r \cdot s$$.

2. We are given the polynomial $$r$$ and the polynomial $$m$$ evaluated at some points. However, $$0.4$$ of the points are random, and only $$0.6$$ are good points, i.e. actual evaluations of the polynomial $$m$$, obviously we don’t know which ones.

3. Since the fraction of the points given is large enough (considering the low degree of the polynomial $$s$$), we can keep trying to interpolate $$k$$ points until we find a combination of all good points, and recover the secret (aka the FLAG).

## Description

We are in a presence of a zero-knowledge protocol. In this protocol, there are several parameters and variables:

• $$\mathcal{R} = \mathbb{F} _ p[x]/(x^k + 1)$$ – Quotient ring for the ZK protocol, where $$p = 257$$ and $$k = 26$$.

• $$s \in \mathcal{R}$$ – Secret polynomial, i.e. the FLAG.

• $$r \in \mathcal{R}$$ – Hiding polynomial. Masks $$s$$.

• $$m = r \cdot s$$ – Hidden secret.

• $$(\alpha=42,\beta=107)$$ – $${\alpha}/{\beta}$$: Ratio of points, given from evaluating the polynomial $$m$$, or random.

First, $$r$$ is sampled at random from $$\mathcal{R}$$, and is mixed with $$s$$ to obtain $$m$$. Then, the polynomial $$m$$ is evaluated at points $$\{0,\dots,\beta-1\}$$. Finally, for each of these $$\beta$$ points, with probability $${\alpha}/{\beta}$$ a random element of the ring is added to that point (which makes it random). This new set of mixed good and bad points is referred to as $$y$$.

We are given the hiding polynomial $$r$$, and $$y$$. (As well as the length of the flag $$k$$, but we could have guessed this from the degree of $$r$$.)

### Probability of getting all good points

We are given a set of $$\beta$$ points. We don’t know which, or how many, of these are good and bad points. However, we know that in expectation $\#\text{good} = \text{Pr[good]}\cdot \beta = (1 - \alpha/\beta) \cdot \beta = \beta - \alpha$ points will be good. So, we have $$\binom{\beta - \alpha}{k}$$ good choices, from a total of $$\binom{\beta}{k}$$ possible choices. Thus, the probability of choosing $$k$$ points which are all good is $\text{Pr[choose $$k$$ good points]} = \dfrac{\binom{\beta - \alpha}{k}}{\binom{\beta}{k}} \approx 2\cdot 10^{-7}.$ This is high enough for solving using bruteforce.

### Inverting $$r \in \mathcal{R}$$

Since $$\mathcal{R}$$ is not a field, it could have been the case that $$r$$ had no inverse in $$\mathcal{R}$$. Notwithstanding, by computing the polynomial gcd, $$\mathsf{gcd}(r, x^k+1) = 1$$, we verify that both polynomials are coprime, and so using xgcd (or effortlessly writing in Sage $$r^{-1}$$) we can compute $$r^{-1}$$, such that $$r\cdot r^{-1} = 1$$ in $$\mathcal{R}$$.

### The attack

Given the inverse of $$r$$ in $$\mathcal{R}$$, we can keep sampling $$k$$ points and interpolating them, hoping that we get all good points. (We need $$k$$ points, as the degree of the polynomial is $$k-1$$.) If that is the case, multiplying by $$r^{-1}$$ yields the FLAG, and testing for ASCII characters in the coefficients of the candidate for the secret polynomial $$s$$ is enough for, after a little time, discover

midnight{N0p3_th1s_15_n0T_R1ng_LpN}


I am not sure if this is the intended solution. But I would be very interested in knowing that one in case this was not the intended path.

# Resources:

The solution code can be found in sol.sage.