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

h1, b1, r1, s1 = map(R, samples)
h2, b2, r2, s2 = map(R, samples)

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)
d = r1^-1 * (s1*k1(*roots) - h1)
print(d)
``````

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 = ...

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