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

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)) &amp; 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) &amp; 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'

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