Skip to content

Instantly share code, notes, and snippets.

@hellman
Last active April 10, 2019 08:56
Show Gist options
  • Save hellman/e7cb757900bce3cdd4022c2e1c299bca to your computer and use it in GitHub Desktop.
Save hellman/e7cb757900bce3cdd4022c2e1c299bca to your computer and use it in GitHub Desktop.
Midnight Sun CTF 2019 Quals - Tulpan

In this challenge the flag is treated as a polynomial over GF(257), it is blinded by a random known polynomial, and then it is evaluated at 107 first integers. However, each result is corrupted with probability 43/108. The polynomial has degree 25, so we need 26 correct points to interpolate it. Observe that by choosing random 26 points from those given, we have a feasible probability of having an error-less set:

sage: math.log(binomial(108-43, 26) / binomial(108, 26), 2)
-22.716429556377932

That is, we need to try around 7 000 000 random subsets. This can be done in 10 minutes on 8 cores by a simple Sage code.

from sage.all import *
flag = "XXXXXXXXXXXXXXXXXXXXXXXXX"
p = 257
k = len(flag) + 1
F = GF(p)
FF.<x> = GF(p)[]
mod = (x**k+1)
# sage: prover(flag)
r = [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]
y = [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]
y = map(F, y)
r = sum(c*x**i for i, c in enumerate(map(F, r)))
ir = xgcd(r, x**k+1)[1]
assert r * ir % (x**k+1) == 1
y = list(enumerate(y))
itr = 0
while True:
itr += 1
if itr % 2**12 == 0:
# math.log(binomial(107-42, 26) / binomial(107, 26), 2) = -22.319094058832547
# need to print up to ~1260
print itr / 2**12
shuffle(y)
masked = FF.lagrange_polynomial(y[:26])
secret = (ir * masked) % mod
if 32 <= min(secret) <= max(secret) <= 127:
flag = "".join(chr(int(c)) for c in secret)
print `flag`
print
# N0p3_th1s_15_n0T_R1ng_LpN
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]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment