# pbctf 2020

December 6, 2020

I didn’t have much free time this weekend, but pbctf ended up being the perfect opportunity to field-test my coppersmith script!

## LeaK

We get thirty ECDSA signatures along with their partially leaked nonces, although I ended up only using two. The challenge’s twist is that each leak is the middle 176 bits of a 256 bit nonce, leaving 40 unknown bits on each side. As a mathematical expression, we have

``````k = 2^216 a + 2^40 b + c
``````

where `a` is an unknown, `b` is the leak, and `c` is another unknown. Recall that in ECDSA we have the following signature equations:

``````s = inv(k) (h + r d)
d = inv(r) (s k - h)
``````

Using two signatures, we can eliminate the private key entirely:

``````inv(r1) (s1 k1 - h1) - inv(r2) (s2 k2 - h2) = 0
``````

This is a multivariate equation with small roots, which means it’s time for Coppersmith’s method! Some back-of-the-envelope calculation to justify the approach: we have four unknowns for a total of 160 bits, which is well below 256-bit modulus. The roots allow us to recover the nonces, and hence the private key.

``````n = ...
R = Integers(n)

h1, b1, r1, s1 = map(R, samples[0])
h2, b2, r2, s2 = map(R, samples[1])

P.<a1, c1, a2, c2> = PolynomialRing(R)
bounds = (2^40, 2^40, 2^40, 2^40)

k1 = a1*2^216 + b1*2^40 + c1
k2 = a2*2^216 + b2*2^40 + c2
f = r1^-1 * (s1*k1 - h1) - r2^-1 * (s2*k2 - h2)

roots = small_roots(f, bounds, m=2, d=2)[0]
d = r1^-1 * (s1*k1(*roots) - h1)
print(d)
``````

This solution works for both Special Gift and Special Gift Revenge. We get an RSA public key where the private key `d` is relatively small, around `N^0.4`. This is too large to use the Boneh-Durfee attack, but fortunately we also get a partial leak of `d`, namely all but the lower 120 bits. In other words, we have an approximation `d0` such that `d - d0` is 120 bits.

Recall that in the Boneh-Durfee attack, we lift `ed = 1` modulo `phi` to be `ed = 1 + k phi` over the integers, where `k = (ed - 1) / phi` is unknown. Reducing modulo `e`, we get

``````1 + k phi = 0
1 + k (N + 1 + s) = 0
``````

where `s = p + q` is also unknown. Notice that `k` is approximately the same size as `d`. The Boneh-Durfee attack solves for `k` and `s` using Coppersmith’s method, but in this challenge `k` is too big. Fortunately, we have an approximation! Let `k0 = e d0 // N`. Then `k - k0` is 120 bits, and we can solve for this unknown instead.

``````N, e, gift = ...

R = Integers(e)
P.<x, s> = PolynomialRing(ZZ)
bounds = (2^120, 2^512)

k0 = e*d0 // N
f = 1 + (k0 + x) * (N + 1 - s)

x, s = small_roots(f.change_ring(R), bounds, m=3, d=4)[0]
ed = f(x.lift(), s.lift())
d = ed // e
print(d)
``````

The same idea works for Special Gift Revenge, except I called `small_roots(..., d=5)`. Also, instead of using `I.variety` to compute roots (took ~10 minutes on my laptop), I suggest modifying `small_roots` to use polynomial resultants.

``````roots = []
h1, h2 = I.change_ring(f.parent()).gens()
for y, _ in h1.resultant(h2).univariate_polynomial().roots():
for x, _ in h1.subs({h1.variable(1): y}).univariate_polynomial().roots():
roots.append((R(x), R(y)))
return roots
``````