pbctf 2020

December 06, 2020

I didn’t have much free time this weekend, but pbctf turned out to the perfect opportunity to use my coppersmith script in the field. Check it out!

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:

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

where b is the leak and a,c are unknown 40 bit values. Now let’s consider the overall signature equations modulo the generator’s order.

s == inv(k)*(h + r*d)
s*k == h + r*d

We have three unknowns, one being d and the other two from k. Fortunately, we can eliminate d by combining two samples.

s1*k1 == h1 + r1*d -> inv(r1)*s1*k1 - inv(r1)*h1 == d
s2*k2 == h2 + r2*d -> inv(r2)*s2*k2 - inv(r2)*h2 == d
inv(r1)*s1*k1 - inv(r2)*s2*k2 - inv(r1)*h1 + inv(r2)*h2 == 0

So we have a multivariate equations with small unknowns, which means it’s time for Coppersmith’s! Some back-of-the-envelope calculation to justify the solution: we have four unknowns for a total of 160 bits, well underneath the modulus’s 256 bits. The Sage code can explain the rest.

n = 115792089237316195423570985008687907852837564279074904382605163141518161494337
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 - r2^-1*s2*k2 - r1^-1*h1 + r2^-1*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, so I’ll only explain it once. We get an RSA key where d is short - not to mention we’re given everything except its 120 LSBs. This gives us a good approximation d0, where d-d0 <= 2^120.

Let’s recall the Boneh-Durfee attack on small d. The important idea is ed == 1 mod φ, which we can lift to ed == 1 + kφ over the integers. Reducing modulo e, we get

1 + kφ == 0

Note that k := (ed-1)/phi is small - about the size of d given that e and φ are comparable. Also, note that φ == (p-1)(q-1) == N+1-(p+q), where p+q is about half the bit-length of N. Rewriting the equation:

1 + kφ == 0
1 + k(N+1 - p+q) == 0

One optimization people like doing is factoring out 2 from N-1 - p+q, since it’s guaranteed to be even. This gives the bivariate polynomial

1 + 2k((N+1)/2 - s) == 0

where s == (p+q)/2. Assuming small k, Coppersmith’s will work. Unfortunately for us, d is way too big for Boneh-Durfee. However, what we can do instead is approximate k!

The idea is that ed0/n is very close to k == (ed-1)/φ. In particular, they differ by around 2^120:

(ed-1)/φ ~ ed/n ~ ed0/n + e(d-d0)/n ~ ed0/n + (d-d0)

This lets us construct a similar equation to Boneh-Durfee, but now our unknown is simply the difference between k and ed0/n. The Sage code explains the rest.

N, e, gift = ...
d0 = gift << 120

R = Integers(e)
P.<x, s> = PolynomialRing(ZZ)
bounds = (2^120, 2^512)
f = 1 + 2*(x+e*d0//N)*((N+1)//2 - 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, since the approximation remains equally powerful. The one issue is that I had to increase Coppersmith parameters to d=5 (not sure why). Also, change the elif I.dimension() == 0: clause in coppersmith.sage to the following:

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

It uses resultants to solve polynomials instead of Sage’s built-in methods, which were dying (took 10 minutes on my laptop). I’ll probably make a generic resultant method in the future.