Tags: coppersmith lcg
Rating:
i prefer LCGs over QCGs to be honest... based off BBB from SECCON CTF 2022
Below is the problem logic.
range(5)
.t = randint(10, 100)
times, and the final output Xt will be the public exponent ek for RSA each. Denote each seed as sk.FLAG
is read from file, asserting that the length is less than 50.PAD = urandom(4)
is right-appended to FLAG
.r_k = urandom(16)
is right-appended to plaintext. The final plaintext form is mk = FLAG + PAD + r_k
, which has max length as 49+4+16=69. Note that PAD
is fixed for every plaintext, but r differs. The final plaintext is encrypted using kth RSA public key, resulting in ciphertext as ck.Becaue all public modulus nk differs, it seems that the only way to get flag is using Hastad's Broadcast Attack. To apply this, we must make all public keys share the same public exponent e, and e must be small.
The smallest value we can use is e=11. We can control a and seed sk to make the final rng state be e=11 by high probability. Let Xi,Xi+1,Xi+2,Xi+3,Xi+4 be consecutive lcg states for some non-negative integer i. If we meticulously choose a to make a cycle: f(Xi+4)=Xi for every non-negative integer i, and set seed sk to be these vertices, we can get final state be e in 100%/5 = 20% probability. Final state will be randomly selected in these five elements because of the number of lcg state advancement is random(t = randint(10, 100)
). This is all possible because lcg is a permutation(every indegree and outdegree is 1).
<p align="center"> <img src="./asset/graph.png" alt="graph" width="200" /> </p>
We derive a by following formula.
Xi+1=aXi+b
Xi+2=aXi+1+b
Xi+3=aXi+2+b
Xi+4=aXi+3+b
Xi=aXi+4+b
Pair up each equations to get rid of b:
Xi+2−Xi+1=a(Xi+1−Xi)
Xi+3−Xi+2=a(Xi+2−Xi+1)
Xi+4−Xi+3=a(Xi+3−Xi+2)
Xi−Xi+4=a(Xi+4−Xi+3)
Xi+1−Xi=a(Xi−Xi+4)
Assuming that Xi,Xi+1,Xi+2,Xi+3,Xi+4 is distinct, a satisfies the following equation.
a5=1modp
We use sagemath's roots()
method to calculate a. The method usually finds the roots of polynomials, but not always. If we fail, get new parameters a and p by reinitiating the connection. Below is the sagemath code to get a. We ignore the trivial root 1.
We derive seeds using a,b,p. Seeds will be elements Xi=e,Xi+1,Xi+2,Xi+3,Xi+4. Advance four times from initial state e, and store the output state as seeds.
Below is the relevant logic implemented to get a and seeds sk from b and p.
def gen_cycle(p, b):
e = 11
R.<x> = PolynomialRing(Zmod(p), "x")
eq = x**5 - 1
roots = eq.roots()
for root, _ in roots:
if root == 1:
continue
a = root
seeds = [e]
for i in range(4):
seeds.append(rng(a, seeds[-1], b, p))
if len(set(seeds)) != len(seeds):
continue
assert rng(a, seeds[-1], b, p) == seeds[0]
return a, seeds
assert False
We supply a and seeds sk to fix ek as e=11, each with probability as 20%. We have five public keys, so in order to fix every key, the expected trials to set all public exponents as e=11 will be 55=3125. This is too much.
We need to calculate the minimum number T of (nk,ek,rk,ck) pairs. Each pair gives at most 2048(1/e−ϵ) information to find hidden bits, by applying Coppersmith attack. e will be the degree of monic polynomial: xe−c=0modN.
Lets revisit the final plaintext form: mk = FLAG + PAD + r_k
, which having max length as 49+4+16=69. We know the value of rk, and also know the prefix of FLAG
is dice{
. By using prefix info, the hidden bytes x to recover is at most 69−len("dice{")−len(r)=69−5−16=48, or 384 bits. We get the following inequality:
Hidden information max length=384<T×2048e=\# of pt-ct pairs×information recovered per pair
T>384e/2048≃2.0625. We can feasibly recover FLAG
by using the Coppersmith attack using T=3. The expected trials to set only three public exponent as e=11 will be 53=125, which is much more feasible then setting every e=11.
We now apply the Coppersmith attack. We do not know the exact length of the flag, so bruteforcing the FLAG
length L is required. Combine all information using Chinese remainder theorem. Combination process is somewhat related with generalization of Hastad's broadcast attack. Each pre-combined monic polynomial will be the following form.
(28×len(r)x+r+C)e−c=0modN
where C is the constant for taking care of the prefix dice{
.
Below is the relevant logic implemented to bruteforce over L and applying Coppersmith attack to recover flag:
def hastad(ns, rs, cs):
e = 11
# do not know the exact length of flag
for L in reversed(range(30, 44)):
pwn.log.info(f"{L = }")
X_len = 8 * (L + 4)
NUM = len(ns)
assert NUM == 3
C = bytes_to_long(b"dice{") << ((L + 4 + 16) * 8)
P.<x> = PolynomialRing(Zmod(prod(ns)))
ts = [crt([int(i == j) for j in range(NUM)], ns) for i in range(NUM)]
gs = [
(ts[i] * ((x * (1 << (16 * 8)) + rs[i] + C) ** e - cs[i]))
for i in range(NUM)
]
g = sum(gs)
g = g.monic()
beta = e * 8 * (L + 4) / (2048 * NUM)
epsilon = 1 / 32
pwn.log.info(f"beta = {float(beta)}")
pwn.log.info(f"epsilon = {float(epsilon)}")
set_verbose(2)
roots = g.small_roots(X=2**X_len, beta=beta, epsilon=epsilon)
set_verbose(0)
for root in roots:
flag_cand = Integer(root)
FLAG_cand = long_to_bytes(flag_cand)[:-4]
return FLAG_cand
We get flag when L=42.
dice{r3s0rt_t0_LCG_4ft3r_f41l1ng_t0_m4k3_ch4ll}
Problem src: bbbb.py
exploit driver code: solve.sage