tulpan257

by goulov

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

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\).
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.
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.