pbctf 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)

samples = eval(open('output').readline())
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)

Special Gift

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 = ...
d0 = gift << 120

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