Sign Wars

The most painful task unless you have a lot of ready-made code for it. And on a 24-hour CTF this packed with tasks it’s either a tooling-check or a number-of-team-memebers-check.

Task is basically:

from secret import msg1, msg2, flag

# P-384 curve
G = ...
order = ...

flag = pad(flag, 96)
flag1 = flag[:48]
flag2 = flag[48:]

for b in msg1:
  assert b >= 0x20 and b <= 0x7f
z1 = bytes_to_long(msg1)
assert z1 < 2^128

for b in msg2:
  assert b >= 0x20 and b <= 0x7f
z2 = bytes_to_long(msg2)
assert z2 < 2^384

# prequel trilogy
def sign_prequel():
  d = bytes_to_long(flag1)
  sigs = []
  for _ in range(80):
    # normal ECDSA. all bits of k are unknown.
    k1 = random.getrandbits(128)
    k2 = z1
    k3 = random.getrandbits(128)
    k = (k3 << 256) + (k2 << 128) + k1
    kG = k*G
    r, _ = kG.xy()
    r = Z_n(r)
    k = Z_n(k)
    s = (z1 + r*d) / k

  return sigs

# original trilogy
def sign_original():
  d = bytes_to_long(flag2)
  sigs = []
  for _ in range(3):
    # normal ECDSA
    k = random.getrandbits(384)
    kG = k*G
    r, _ = kG.xy()
    r = Z_n(r)
    k = Z_n(k)
    s = (z2 + r*d) / k

  return sigs

sigs1 = sign_prequel()
sigs2 = sign_original()

We get 80 signatures with some fuckery going on with the nonce, which smells of lattices already.

I did actually attempt this problem when I woke up in the wee morning before the CTF ended. I “woke up with the solution,” as sometimes happens, but it turns out this is far from infallible… The dreams had corrupted the problem in my mind, because I fully believed we got 80 samples of both types of signatures, and that the problem was some sort of Mersenne Twister thing where we could align a lot of samples just-so to induce a bias in the bits of the ks, (approximating -linearity with something -linear, somehow, magically,) and “there’s our lattice…” Unfortunately the dream didn’t include the details, just the idea. “But man,” I thought, “this seems like a really tough problem, doesn’t MT’s output tempering kind of fuck us? How on Earth… Is it Google-the-paper?” But once I realized my mistake and that everything I thought was wrong and that I had wasted a good and precious time on being an idiot, I was like ah fuck me, and panic-switched to other, less time-intensive problems.

Ahh. But now, dear hearts, without the time pressure, we can remain calm and collected and pretend to be as clever as we want. We can use words like “trivial” and “easy” to mask our crippling insecurity and self-doubt, because the only thing that is certain is our own stupidity and failings1.

Anyway, back to this easy problem. So trivial, pah, hardly worth the words I waste on it.

There’s two twists on the standard partially-revealed-nonce setup:

  • we don’t know the “hash” (z1). This is fine though, because it’s given to be small, so we can just set it up as an extra row in our lattice.

  • it’s not known-prefix nor known-suffix, but known-middle-bits (kinda), which, from my experience, is a real pain in the ass for lattice solves, because now we kind of want to do some Coppersmith polynomial shit instead, and ugh.

However — here’s the clever trick — because the order of the group is close to a power of two, we can overflow the nonce and still end up with a “small” number.

>>> (random.getrandbits(128)*2**384 % order).bit_length()

Now, there’s our lattice.

I ended up with something like this:

def matrix_for(sigs, scale=(1,1,1)):
  B = Z_n(2)^128
  N = matrix.identity(len(sigs)) * order
  S = matrix(ZZ, [
    for r,s in sigs]).T

  V = matrix.diagonal([2^scale[2], 2^scale[1]])
  Z =, 2)

  return matrix.block([
    [S*2^scale[0], V],
    [N*2^scale[0], Z],
  ], subdivide=False)

scale_d = 0
scale_k = 384-318
scale_z = 384-128
M = matrix_for(sp, (scale_k, scale_d, scale_z))

And it works and we get…

>>> any_to_bytes(v[-1])

half the flag? Ah fuck, right, I forgot.

So now it’s actually a MT reverse problem, but it’s an easy one and just a tooling-check because we recover the ks from the first signature set, which is 2 more than needed for Python’s MT’s full state. There’s no tricks or gotchas, just plug-and-play:

  1. half of you, dear non-existent reader, will have no idea what I’m talking about: you also have no idea how much I envy you.