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.
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
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
This gives us the flag
(Image inspired by https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/)