CCCamp CTF 2023 - Baby RSA

This is the solution of the challenge “Baby RSA” from CCCamp 2023. It was a RSA whitebox implementation in Python with a left to right windowed exponentiation.

Description

I stumbled across this weird RSA implementation. However, it seems like it still works correctly. Can you figure out how? The flag is contained in one of the prime factors of N!

Challenge Files: babyrsa.zip

Details

Category: Crypto

Difficulty: Medium

Author: floesen

Solution

The implementation is quite compact. The encryption function is a standard RSA encryption with $N$ being 4094 bits and $e=65537$. We did not have any ciphertext nor plaintext since we could compute them ourselves. It directly indicated that the private key is encoded in the rsa_decrypt function. The goal was clearly to recover the private exponent $d$ or to factor $N$. In the first part, we have a binomial expansion and thus, $s$ is a vector containing $s[i] = m_1^i (b+ac^h)^i$ for $i = 0,..,32$. Note that the computations do not happen on the ciphertext $c$ but on $c^h$. Then we have a linear combination of the vector $s$ with the matrix $M$ and a correction term to eliminate the term in degree 32. To convince myself that it is a cancelling term I computed:

1
2

sage: R(m1^32*M[0][32]) == -v[0]
True

Finally, the last part was hard to guess but I could understand it is a left to right k-ary exponentiation with window of 5 bits: I figure out that by seeing that $l$ is 819 elements long containing value on 5 bits wich make a total of $5\times 819 = 4095$ bits. Another clue is that the product is computed with a serie of power of 32 which is $2^5$. The final computation can be written as: $$m = m_2 \prod_i u[l[819-i-1]]^{32^i}$$ However, because of the linear step with matrix $M$ we cannot recover directly the bits of the private exponent bits of $d$ directly in $l$. Basically during the CTF I was stuck there.

Afterwards, a message in the Discord channel gave me the solution. The idea is to use symbolic computation of the first step of the precomputation in sage to guess how the bits are mixed but using an unknown $x=c^h$ to avoid complexity explosion during computation. That’s what I did:

1
2
3
4
5
6

R = Integers(N)
P = PolynomialRing(R, "x")
x = P(x)
M = matrix(A)
s = vector([m1^i * sum([binomial(i, j) * a^j * x^(j) * b^(i - j) for j in range(i + 1)]) for i in range(M.ncols())])
u = M * s + a^(M.nrows()) * x^(M.nrows()) * vector(v)

It works, the coponements of u where only monomial on $x$ meaning that the depends only on a single power of $x$:

1
2

sage: u[0]
19110896700346878729...584446*x^28

So we know that u is simply a substitution of the precomputed values and we can reconstruct the private exponent bits in the correct order:

1
2
3
4
5
6
7
8

sage: sub = [u[i].degree() for i in range(len(u))]
sage: d_list = [sub[l[i]] for i in range(len(l))]
sage: d_bin = ""

sage: for w in d_list:
....:    d_bin+= f"{w:05b}"

sage: d = int(d_bin,2) * h

Note that we must mutiply the result by h to have the correct value of $d$ since we substitue it in $x$. Now we can check everything is correct:

1
2

sage: (R(2)^e)^d
2

We have to compute the factorization of $N$ from $d$ with a well known method. With my full script solve.sage I got the flag:

1
2

$ sage solve.sage
b'ALLES!{c0ngr4tZ_y0u_br0K3_A_Wh1t3b0x_RSA_1mpL3m3nt4t10n}\xb7\xaa\xd1\xddl;\xe5\xa0\x89J\xed\x03\xb4\x85J7\x8f\xd2\x03x7~\xee#\xe6Kk\xbe4H\x13\xab\x1d\x9a\xa0x\x7fB\xc4c\xd8\x14\x9fq\x1a\xf4\x90{\xf3R+\x01\x82\xbfU\x17\xa8Ah&\xc2\xe9\x80\xb7%\x97\x87\xf9S\xb0/Rr\x0bf\xb2\t\x96*\xb5\x824B\x1d\xaa\x08\x94\xad\x0f\xed\xb4&b(\x01$\xc7x?\x89\xa9\xd3\xdf\xf1\x94BDI\x1a\xc8\x93\xa1\x17\xb4I8\x18{7FJ\xfd\xf5i\xee\x86\xfdAF\x92\xbd\x89{\x8a\xad\xf05\xe2\x12\xc7\xa3g#\xf0H\xc1\xeb\xe8E7svr\xee>\xe4\xd3A\xb5\xc5\xa5\xf9\xde\x10{\xc1A4d\xd5\x83\xbc\x92\xf6N\xdbE.56\xf1N\xb6\x00D7\x16\x05B\x90\xa1]OL\xe8\xd1u\xba\xda;'