SuSeC CTF 2020 – Inaction Writeup (ppc)
Below is the writeup for a programming challenge in SuSec CTF 2020.
The source code is given as follow:
import re, sys, os, signal, string, random from hashlib import * from secret import flag p = 2**2281 - 1 s = 2**228 pad = 2228 def idle_square(x, toil, pad): for i in range(toil): x = pow(x ^ pad, 2, p) return x def gen_chall(toil): x = random.randint(1, s) return [x, toil, pad] def main(): pr("-"*72) pr("|" + " hi all, in each level try to solve given challenge ".center(70) + "|") pr("-"*72) stage = 40 for i in range(stage): x, toil, pad = gen_chall(stage) y = idle_square(x, toil, pad) pr('y =', y) pr('please send solution:') ans = sc() try: ans = int(ans) except: die('Sorry, the given answer is not integer! Bye!!') if ans == x: if i == 39: die('Congratz! You got the flag:', flag) else: pr('Great! Please solve the next level :P') else: die('Your answer is not correct, try again, Bye!')
Basically all the operation is happening in idle_square funcion. In 40 rounds, the chosen x (which we have to find its value) will first get XOR-ed by a constant (pad) and then is powered by 2 in the field of another constant(p).
This part of the problem is a typic in cryptographic called modular square root which is solvable using Shanks algorithm. However, since the power is 2 there should be two possible answers for each round unless the Shanks algorithm fails. So there would be at most 2**40 possible answers for this challenge. I’ve traced the code manually and found out in first step (which we have the initial value of x) the x is slightly smaller than other possible answers.
I’ve modified this Shanks implementation a little to work with large numbers and put the function in the back-track algorithm. Hopefully in many places, the Shanks algorithm fails (meaning there is not a valid step to go further) and this will dramatically reduce our calculations.
p = 2**2281 - 1 s = 2**228 pad = 2228 all = [] def solve(y, stage): if stage <= 0: all.append(y) return possible_current_stage_answers = prime_mod_sqrt(y, p) for possible_current_stage_answer in possible_current_stage_answers: x = (possible_current_stage_answer ^ pad) % p solve(x, stage - 1) solve(y, 40) x = min(all)
Now, all is left is to connect to server and repeat these steps. We have to repeat these steps 40 times and provide valid X to get flag. Whole code is attached for readabily:
from pwn import * def legendre_symbol(a, p): """ Legendre symbol Define if a is a quadratic residue modulo odd prime http://en.wikipedia.org/wiki/Legendre_symbol """ ls = pow(a, (p - 1)//2, p) if ls == p - 1: return -1 return ls def prime_mod_sqrt(a, p): """ Square root modulo prime number Solve the equation x^2 = a mod p and return list of x solution http://en.wikipedia.org/wiki/Tonelli-Shanks_algorithm """ a %= p # Simple case if a == 0: return [0] if p == 2: return [a] # Check solution existence on odd prime if legendre_symbol(a, p) != 1: return [] # Simple case if p % 4 == 3: x = pow(a, (p + 1)//4, p) return [x, p-x] # Factor p-1 on the form q * 2^s (with Q odd) q, s = p - 1, 0 while q % 2 == 0: s += 1 q //= 2 # Select a z which is a quadratic non resudue modulo p z = 1 while legendre_symbol(z, p) != -1: z += 1 c = pow(z, q, p) # Search for a solution x = pow(a, (q + 1)//2, p) t = pow(a, q, p) m = s while t != 1: # Find the lowest i such that t^(2^i) = 1 i, e = 0, 2 for i in range(1, m): if pow(t, e, p) == 1: break e *= 2 # Update next value to iterate b = pow(c, 2**(m - i - 1), p) x = (x * b) % p t = (t * b * b) % p c = (b * b) % p m = i return [x, p-x] p = 2**2281 - 1 s = 2**228 pad = 2228 all = [] def solve(y, stage): global all if stage <= 0: all.append(y) return possible_current_stage_answers = prime_mod_sqrt(y, p) for possible_current_stage_answer in possible_current_stage_answers: x = (possible_current_stage_answer ^ pad) % p solve(x, stage - 1) s = remote('66.172.27.57', 3114) for i in range(1,41): y = int(s.recvline_contains('y = ')[4:]) s.recvline_contains("please send solution:\n") print("[*] ------- Step {} ------- ".format(i)) print("[*] Got new y: {}".format(y)) solve(y, 40) x = min(all) all = [] print("[*] Valid x : {}".format(x)) s.sendline(str(x)) s.interactive()
And after a while, we get the flag:
Congratz! You got the flag: SUSEC{5m4Rt___p0W___cH4lL3n93}
1
Write a Reply or Comment