SCTF – Ed25519

This was a quite nice challenge about elliptic curves, giving 40 points. The problem is stated as follows:

Ed25519-sign the flag with the same private key and implementation flaw used to sign the messages below. The flag is the base64 representation of the signature.

Public key: \texttt{5bfcb1cd3938f3f6f3092da5f7d7a1bdb1d694a725d0585a99208787554e110d}

Message: sctf.io
Signature:
\begin{array}{l}\texttt{68299a51b6b592e2db83c26ca3594bdd81bdbb9f11c597a1deb823da7c8b9de8} \\ \texttt{e2224855125b1acbeab1468bf4860c1eeb05b6d2375e2214c55bdfe808a6c106}\end{array}

Message: 2016 Q1
Signature:
\begin{array}{l}\texttt{68299a51b6b592e2db83c26ca3594bdd81bdbb9f11c597a1deb823da7c8b9de8} \\  \texttt{25ad01a05a0cce69258d41d42ed046956e7d4586eb21ff031bf8ac03243d5e04}\end{array}

OK, so the two signatures have the same prefix \texttt{68299a51b6b592e2db83c26ca3594bdd81bdbb9f11c597a1deb823da7c8b9de8}. Hmm… let us first look at the Ed25519 signing algorithm and try to identify the flaw:

Skärmavbild 2016-04-13 kl. 10.49.16

 

Clearly, R is equal in for two different messages implying that either:

  1. There is a collision in SHA512, which is so unlikely that we can rule that out completely, or,
  2. R is independent of the message.

Now, we know that the implementation is flawed. It is rather obvious that the marked (see above image) connection from the message is missing.

First, define n =2^{252} + 27742317777372353535851937790883648493. The S-part is computed as r + a\cdot H(r,\text{pubkey},\text{message})  \bmod n

Since r does not differ in the flawed implementation, we have that

S_1 =r + a\cdot \underbrace{H(r,\text{pubkey},\text{message}_1)}_{h_1}, S_2 =r + a\cdot \underbrace{H(r,\text{pubkey},\text{message}_2)}_{h_2}

and therefore,

S_1 -S_2 =a\cdot \underbrace{(h_1-  h_2)}_{\text{known!}}.

So, we may obtain a =(S_1 - S_2) \cdot (h_1-  h_2)^{-1} \bmod n and, conquently, r = S_1-a \cdot h_1 \bmod n. To forge a signature for message \text{message}_3, we now compute h_3 = H(r,\text{pubkey},\text{message}_3). Using the previously obtain a and r, we can compute S_3 = r + a\cdot h_3 \bmod n. The signature becomes (R, S_3).

OK, so how does it look in code?


import ed25519, hashlib, libnum, binascii, base64

def bit(h,i): return (ord(h[i/8]) >> (i%8)) & 1

def Hint(m):
   h = hashlib.sha512(m).digest()
   return sum(2**i * bit(h,i) for i in range(2*256))

def decodeint(s): return sum(2**i * bit(s,i) for i in range(0,256))

def encodeint(y):
   bits = [(y >> i) & 1 for i in range(256)]
   return ''.join([chr(sum([bits[i * 8 + j] <<  j for j in range(8)])) for i in range(256/8)])

# modular field size
n = 2**252 + 27742317777372353535851937790883648493
pkey = b'5bfcb1cd3938f3f6f3092da5f7d7a1bdb1d694a725d0585a99208787554e110d'

# messages
message1 = 'sctf.io'
message2 = '2016 Q1'
message3 = 'the flag'

# provided test-case signatures
sig1 = b'68299a51b6b592e2db83c26ca3594bdd81bdbb9f11c597a1deb823da7c8b9de8e2224855125b1acbeab1468bf4860c1eeb05b6d2375e2214c55bdfe808a6c106'
sig2 = b'68299a51b6b592e2db83c26ca3594bdd81bdbb9f11c597a1deb823da7c8b9de825ad01a05a0cce69258d41d42ed046956e7d4586eb21ff031bf8ac03243d5e04'

# extract required data
rbin = binascii.unhexlify(sig1[:64])
pkbin = binascii.unhexlify(pkey)
s1 = decodeint(binascii.unhexlify(sig1[64:]))
s2 = decodeint(binascii.unhexlify(sig2[64:]))

# compute H(R,A,M)
hram1 = Hint(rbin+pkbin+message1)
hram2 = Hint(rbin+pkbin+message2)

# ok, now we got the information we need
a = (s1-s2)*libnum.modular.invmod(hram1-hram2,n) % n
r = (s1-hram1*a) % n

# compute new hram
hram = Hint(rbin+pkbin+message3)
s = (r+hram*a) % n

# this is our new fresh signature
flagsig = sig1[:64] + binascii.hexlify(encodeint(s))

Converting it to the correct format

base64.b64encode(binascii.unhexlify(flagsig))

This gives us the flag

sctf{aCmaUba1kuLbg8Jso1lL3YG9u58RxZeh3rgj2nyLneh12Mf7NAvaREdBikQrkpWSa3UT15wUmunsrceSa3CUCQ==}.

(Image inspired by https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s