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

*Message: sctf.io*

*Signature:*

*Message: 2016 Q1*

*Signature:*

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

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

- There is a collision in SHA512, which is so unlikely that we can rule that out completely, or,
- 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 . The -part is computed as

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

and therefore,

So, we may obtain and, conquently, . To forge a signature for message , we now compute . Using the previously obtain and , we can compute . The signature becomes .

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