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 kk). The r.coeffs() output has length 2626, so this means that k=26k=26.

Now the hard part was recovering the polynomial masked - if I knew that, I could just multiply by the multiplicative inverse of rr in the ring GF(p)[x]/(xk+1)GF(p)[x]/(x^k+1) (which fortunately exists). The known output y is obtained by evaluating masked at the positions 0,1,,1060,1,\ldots,106 - however, with random chance of 42107\frac{42}{107}, a random output modulo pp is chosen instead. I also know that masked is a polynomial of degree k1k-1 - so if I just knew kk 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 21062\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(a1),p(a2),,p(an))p is a polynomial over F of degree k}\{(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,ai=i1,k=26,F=GF(p)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 r1r^{-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