Processing math: 100%

Tags: coppersmith lcg 

Rating:

BBBB Writeup

DiceCTF 2023 - crypto 199 - 31 solves

i prefer LCGs over QCGs to be honest... based off BBB from SECCON CTF 2022

bbbb.py

Analysis

Below is the problem logic.

  • Step 1: Key Generation
    • The challenge first initializes lcg as the form Xn+1=f(Xn)=aXn+bmodp, where X is the sequence of random values and p is 1024 bit prime. b and p are given, and we have power to control a.
    • Let k in range(5).
    • Five RSA public key pairs Nk,ek are generated. Public modulus Nk is 2048 bits. Each ek is generated using the lcg, asking the attacker to input seed X0 for lcg. lcg state advances t = randint(10, 100) times, and the final output Xt will be the public exponent ek for RSA each. Denote each seed as sk.
    • Generated ek must be greater than 10.
  • Step 2: Encryption
    • FLAG is read from file, asserting that the length is less than 50.
    • Random padding PAD = urandom(4) is right-appended to FLAG.
    • For each five RSA public keys, again random padding 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.
    • Each (nk,ek,rk,ck) pair is given to the attacker.

Control seed and a to fix e=11

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+2Xi+1=a(Xi+1Xi)

Xi+3Xi+2=a(Xi+2Xi+1)

Xi+4Xi+3=a(Xi+3Xi+2)

XiXi+4=a(Xi+4Xi+3)

Xi+1Xi=a(XiXi+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

Coppersmith Attack

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: xec=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 69len("dice{")len(r)=69516=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/20482.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)ec=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

Original writeup (https://github.com/pcw109550/write-up/tree/master/2023/Dice/BBBB).