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:

1. There is a collision in SHA512, which is so unlikely that we can rule that out completely, or,
2. 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/)