MidnightsunCTF Quals 2019

The following sage script was given:

flag = "XXXXXXXXXXXXXXXXXXXXXXXXX"
p = 257
k = len(flag) + 1

def prover(secret, beta=107, alpha=42):
    F = GF(p)
    FF.<x> = GF(p)[]
    r = FF.random_element(k - 1)
    masked = (r * secret).mod(x^k + 1)
    y = [
        masked(i) if randint(0, beta) >= alpha else
        masked(i) + F.random_element()
        for i in range(0, beta)
    ]
    return r.coeffs(), y

sage: prover(flag)
[141, 56, 14, 221, 102, 34, 216, 33, 204, 223, 194, 174, 179, 67, 226, 101, 79, 236, 214, 198, 129, 11, 52, 148, 180, 49]
[138, 229, 245, 162, 184, 116, 195, 143, 68, 1, 94, 35, 73, 202, 113, 235, 46, 97, 100, 148, 191, 102, 60, 118, 230, 256, 9, 175, 203, 136, 232, 82, 242, 236, 37, 201, 37, 116, 149, 90, 240, 200, 100, 179, 154, 69, 243, 43, 186, 167, 94, 99, 158, 149, 218, 137, 87, 178, 187, 195, 59, 191, 194, 198, 247, 230, 110, 222, 117, 164, 218, 228, 242, 182, 165, 174, 149, 150, 120, 202, 94, 148, 206, 69, 12, 178, 239, 160, 7, 235, 153, 187, 251, 83, 213, 179, 242, 215, 83, 88, 1, 108, 32, 138, 180, 102, 34]

It doesn’t work quite as given - prover() must be given a polynomial, not a string. I figured that this polynomial was probably just using the flag string as coefficients, and just tried to recover that secret polynomial first (under the assumption that it was of degree $k$ ). The r.coeffs() output has length $26$ , so this means that $k=26$ .

Now the hard part was recovering the polynomial masked - if I knew that, I could just multiply by the multiplicative inverse of $r$ in the ring $GF(p)[x]/(x^k+1)$ (which fortunately exists). The known output y is obtained by evaluating masked at the positions $0,1,\ldots,106$ - however, with random chance of $\frac{42}{107}$ , a random output modulo $p$ is chosen instead. I also know that masked is a polynomial of degree $k-1$ - so if I just knew $k$ correct points, I could simply construct the Lagrange Polynomial through these points.

With the output containing errors I had two choices:

Guessing: If I just guess 26 points that had the correct output, I could recover the original polynomial. A quick calculation shows that this has about chance $2\cdot 10^{-6}$ of happening - and it is easy to detect, as some random polynomial through 26 of the points will match y in far less places than the correct one. Having now tried it after the CTF, it works very well.
Using someone elses work: My first instinct however was to search for a more elegant algorithm for the problem. In retrospect, just using brute force would probably have saved me some time - but this variant was at least quite educational.

I knew that problems of the type “given a set of discrete equations, find a solution that satisfies a high number of them” were quite typical for Coding theory, so I started looking at well-known error-correcting codes. After a little reading, the Reed-Solomon Code jumped out to me - Wikipedia gives the codewords of a Reed-Solomon Code as $\{(p(a_1), p(a_2), \ldots, p(a_n))\mid p \text{ is a polynomial over } F \text{ of degree } k\}$ . Setting $n=107, a_i=i-1, k=26, F=GF(p)$ , this is exactly the kind of output we are dealing with. So now I just needed to decode the codeword given to me in y to one that lies in that Reed-Solomon Code. Fortunately, sage has builtin functions for everything:

sage: p, k = 257, 26
sage: F = GF(p)
sage: FF.<x> = F[]
sage: from sage.coding.grs import *
sage: C=GeneralizedReedSolomonCode([F(i) for i in range(107)],26)
sage: D=GRSBerlekampWelchDecoder(C)
sage: D.decode_to_message(vector(y,F))
DecodingError: Decoding failed because the number of errors exceeded the decoding radius
sage: D.decoding_radius()
40

Whoops - it seems there are just a few errors too many in the output for the BerlekampWelchDecoder to handle. All the other decoders seemed to have the same problem… until I somehow managed to find the Guruswami-Sudan decoder. It conveniently takes a parameter tau that specifies (within limits) the number of errors it will be able correct:

sage: from sage.coding.guruswami_sudan.gs_decoder import *
sage: D=GRSGuruswamiSudanDecoder(C,45)
sage: masked=D.decode_to_message(vector(y,F))[0]
sage: masked
136*x^25 + 181*x^24 + 158*x^23 + 233*x^22 + 215*x^21 + 95*x^20 + 235*x^19 + 76*x^18 + 133*x^17 + 199*x^16 + 105*x^15 + 46*x^14 + 53*x^13 + 123*x^12 + 150*x^11 + 28*x^10 + 87*x^9 + 122*x^8 + 59*x^7 + 177*x^6 + 174*x^5 + 200*x^4 + 143*x^3 + 77*x^2 + 65*x + 138

Finally it’s just a matter of multiplying by $r^{-1}$ :

sage: R = FF.quo(x^k+1)
sage: flag = R(masked)*R(r)^(-1)
sage: "".join([chr(i) for i in flag]) # iterates over coefficients
'N0p3_th1s_15_n0T_R1ng_LpN\x00'

Lessons learned

Coding theory has all kinds of useful stuff for “out of n relations, only k hold, but we don’t know which”-type situations
If a builtin function of sage isn’t quite good or general enough, there is probably a better one somewhere
Don’t waste time on elegant solutions if you can just guess