Instantly share code, notes, and snippets.

# hellman/0_writeup.md

Last active April 10, 2019 08:56
Show Gist options
• 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.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 from sage.all import * flag = "XXXXXXXXXXXXXXXXXXXXXXXXX" p = 257 k = len(flag) + 1 F = GF(p) FF. = 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 flag = "XXXXXXXXXXXXXXXXXXXXXXXXX" p = 257 k = len(flag) + 1 def prover(secret, beta=107, alpha=42): F = GF(p) FF. = 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]