mayday-mayday

\( \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Z}{\mathbb{Z}} \)

An RSA challenge with leakage of MSB from the CRT exponents of the private key. The parameters allow an attack described in a paper by May (hinted by the title), Nowakowski and Sarkar leveraging the Coppersmith method to recover the key.

Challenge Description

The challenge setting is quite simple. We have a Crypto class defining some parameters:

1
2
3
4
self.bits = bits
self.alpha = 1/9
self.delta = 1/4
self.known = int(self.bits*self.delta)

The class then generates an RSA instance using CRT exponents:

1
2
3
4
5
6
7
8
9
10
11
12
while True:
    p, q = [getPrime(self.bits//2) for _ in '__']
    self.e = getPrime(int(self.bits*self.alpha))
    print(f'{self.e.bit_length() = }')
    φ = (p-1)*(q-1)
    try:
        dp = pow(self.e, -1, p-1)
        dq = pow(self.e, -1, q-1)
        self.n = p*q
        break
    except:
        pass

The challenge is run with bits = 2048 (which means p and q are both 1024 bits). We are given the public key together with a leak of the MSB of the CRT exponents:

1
2
dp = f'0x{(dp >> (rsa.bits//2 - rsa.known)):x}'
dq = f'0x{(dq >> (rsa.bits//2 - rsa.known)):x}'

Solution

The solution is explained in great detail here. This attack works in general, but is even more efficient for \(e \sim N^{1/12}\) (in our case is self.bits*self.alpha so roughly \(N^{1/9}\); this unusual choice is already extremely suspicious). First, we write

\[d_p = d_p^M 2^i + d_p^L\]

and the same for \(d_q\). We know \(d_p^M\) from the leak, and in our case \(i = 512\). Section 3.1 gives us a way to compute \(k\) and \(l\), where \(ed_p = k(p - 1) + 1\). First, we need to compute \(A\):

1
2
3
4
i = 512
dpM = dp
dqM = dq
A = (pow(2, 2*i) * pow(e, 2) * dpM * dqM)//N + 1

Then, notice that in our case (with the paper notation)

\[\delta = \frac{1}{4} < \frac{1}{2} - \frac{2}{9} \sim 0.27\]

so we are just inside the bounds. Then we can recover \(k\) and \(l\) as roots of the appropriate polynomial:

1
2
3
4
5
6
7
8
9
10
x = PolynomialRing(RationalField(), 'x').gen()
C = (1 - A*(N-1)) % e
f = x**2 - C*x + A
roots = f.roots()
if roots == []:
    f = x**2 - (C + e)*x + A
    roots = f.roots()
k = roots[0][0]
l = roots[1][0]
assert k*l == A

Finally, given \(k\), we can go to Section 3.3. Here a bit of trial and error is required, since we do not know if \(k\) is actually associated to \(d_p\) or \(d_q\), but this is not a big effort. Notice that we do our computation modulo \(kN\) (the paper mention \(kp\), which may be somewhat confusing). Here applying Coppersmith method for small roots we can find a factor for \(N\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
x = PolynomialRing(Zmod(k*N), 'x', implementation='NTL').gen()
# Assume k is the coefficient of dp
a_small = (e * dpM * (2**i) + k - 1) * inverse_mod(e, k*N)
a_small = int(a_small)
f = x + a_small
my_dpL = f.small_roots(X=2**i-1, beta=0.5)

# Is actually with dq
if my_dpL == []:
    a_small = (e * dqM * (2**i) + k - 1) * inverse_mod(e, k*N)
    a_small = int(a_small)
    f = x + a_small
    my_dqL = f.small_roots(X=2**i-1, beta=0.5)[0]
    p = gcd(f.subs(x=my_dqL), N)
    print(f'{p = }')

else:
    my_dpL = my_dpL[0]
    print(my_dpL == dpL)
    print(f'{p = }')

Finally, with the factorization we can decrypt the flag: HTB{f4ct0r1ng_w1th_just_4_f3w_b1ts_0f_th3_CRT_3xp0n3nts!https://eprint.iacr.org/2022/271.pdf}. With no surprise, it points again at the paper we’ve been using through all the challenge!

Solve Script

The full solution script can be found here


Stellar Vector is powered by the DistriNet research group and the KU Leuven.

© 2022-2023 All content published on this site are protected under copyright of the respective authors.