# 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
sigs.append((r,s))
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
sigs.append((r,s))
return sigs
sigs1 = sign_prequel()
print(sigs1)
sigs2 = sign_original()
print(sigs2)
```

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 `k`

s, (approximating
$Z$-linearity with something $F_{2}[X]$-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 failings^{1}.

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()
318
```

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, [
[B*(1-B*s)/Z_n(s),
B*r/Z_n(s),]
for r,s in sigs]).T
V = matrix.diagonal([2^scale[2], 2^scale[1]])
Z = matrix.zero(len(sigs), 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])
b'SECCON{New_STARWARS_Spin-Off_The_Book_Of_Boba_Fe'
```

… *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 `k`

s 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:

```
b'tt_Will_Premiere_On_December_29-107c360aab}\x05\x05\x05\x05\x05'
```

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