A vulnerability can exist in the implementation of Ed25519, and where the private key can be leaked. In this case we will sign two messages with the same private key, but with different public keys. The basics of Ed25519 using Python is [Here].
Ed25519 Vulnerabilty in Python |
Theory
With EdDSA, Alice will sign a message with her private key, and then Bob will use her public key to verify that she signed the message (and that the message has now changed):
Key generation
Alice generates a random 32-byte secret key (\(sk\)) and then creates a public key of:
\(pk=sk \cdot G\)
and where \(G\) is the base point of the curve.
Signing
Alice creates a SHA-512 hash of her private key:
\(h=\textrm{HASH}(sk)\)
Create \(r\) from the upper 32 bytes of hash and the message:
\( r = \textrm{HASH}(h[32:] \: || \: m))\)
And where "||" represents a concatenation of the byte array values. Next she matches \(r\) onto curve with:
\(R=r \cdot G\)
Next Alice computes \(s\) with:
\(s=r + (\textrm{HASH}(R \: || \: pk \: || \: m)) \cdot sk\)
The signature is (\(R,s\)). The values of \(R\) and \(s\) are 32 bytes long, and thus the signature is 64 bytes long.
Verifying
Bob creates \(S\) using \(R\), \(pk\) and \(m\):
\(S =\textrm{HASH}(R \: || \: pk \: || \: m) \)
And next creates two verification values:
\(v_1=s \cdot G\)
\(v_2=R+ pk \cdot S\)
If \(v_1==v_2\) the signature checks. This is because:
\(v_1=s.G = (r + (\textrm{HASH}(R \: || \: pk \: || \: m)) \cdot sk) \cdot G = rG + sk \cdot G \cdot (\textrm{HASH}(R \: || \: pk \: || \: m))= R+ pk \cdot S = v_2 \pmod q \)
The following is an outline of the code:
# https://asecuritysite.com/encryption/eddsa from pure25519.basic import (bytes_to_clamped_scalar, bytes_to_scalar, scalar_to_bytes, bytes_to_element, Base) import hashlib, binascii import os,sys def H(m): return hashlib.sha512(m).digest() def publickey(seed): # turn first half of SHA512(seed) into scalar, then into point assert len(seed) == 32 a = bytes_to_clamped_scalar(H(seed)[:32]) A = Base.scalarmult(a) return A.to_bytes() def Hint(m): h = H(m) return int(binascii.hexlify(h[::-1]), 16) def signature(m,sk,pk): assert len(sk) == 32 # seed assert len(pk) == 32 h = H(sk[:32]) a_bytes, inter = h[:32], h[32:] a = bytes_to_clamped_scalar(a_bytes) r = Hint(inter + m) R = Base.scalarmult(r) R_bytes = R.to_bytes() S = r + Hint(R_bytes + pk + m) * a return R_bytes + scalar_to_bytes(S) def checkvalid(s, m, pk): if len(s) != 64: raise Exception("signature length is wrong") if len(pk) != 32: raise Exception("public-key length is wrong") R = bytes_to_element(s[:32]) A = bytes_to_element(pk) S = bytes_to_scalar(s[32:]) h = Hint(s[:32] + pk + m) v1 = Base.scalarmult(S) v2 = R.add(A.scalarmult(h)) return v1==v2 def create_signing_key(): seed = os.urandom(32) return seed def create_verifying_key(signing_key): return publickey(signing_key) def sign(skbytes, msg): """Return just the signature, given the message and just the secret key.""" if len(skbytes) != 32: raise ValueError("Bad signing key length %d" % len(skbytes)) vkbytes = create_verifying_key(skbytes) sig = signature(msg, skbytes, vkbytes) return sig def verify(vkbytes, sig, msg): if len(vkbytes) != 32: raise ValueError("Bad verifying key length %d" % len(vkbytes)) if len(sig) != 64: raise ValueError("Bad signature length %d" % len(sig)) rc = checkvalid(sig, msg, vkbytes) if not rc: raise ValueError("rc != 0", rc) return True msg="Hello" if (len(sys.argv)>1): msg=str(sys.argv[1]) m = msg.encode() print("Message:",msg) sk1 = create_signing_key() vk1 = create_verifying_key(sk1) sk2 = create_signing_key() vk2 = create_verifying_key(sk2) print("Secret key 1: ",sk1.hex()) print("Verifing key 1: ",vk1.hex()) print("Secret key 2: ",sk2.hex()) print("Verifing key 2: ",vk2.hex()) sig1 = signature(m,sk1,vk1) sig2 = signature(m,sk1,vk2) print("Signature 1 (sk1, pk1): ",sig1.hex()) R1=sig1.hex()[:len(sig1.hex())//2] S1=sig1.hex()[len(sig1.hex())//2:] R2=sig2.hex()[:len(sig2.hex())//2] S2=sig2.hex()[len(sig2.hex())//2:] print("Now we will sign the message with sk1 and use pk1 to give Sig1") print("And sign the message with sk1 and use pk2 to give Sig2") print("\nR1=", R1) print("S1= ",S1) print("R2=", R2) print("S2= ",S2) rtn1=verify(vk1,sig1,m) if (rtn1==True): print("Signature Success") if (R1==R2): print("R1 is equal to R2!")
A sample run is:
Message: Hello Secret key: f85d5062036a7b7cfe4627e6978ab95ca2e2878f1c319a653a69439009b9ce53 Verifing key: be3c90fdf892123a53ebd29b96e09d3d30cf3f450e54619ae35e75c1d7d49729 Signature: 4c0d15b5f54e3e80e4bdba1386bfc30a3e648e3c6f286c565b5927e71fc0c3609d3d093d6c7fe683aa5b15c8eb63dcd47bca89ab62058fd72c0d68999013d600 R= 4c0d15b5f54e3e80e4bdba1386bfc30a3e648e3c6f286c565b5927e71fc0c360 S= 9d3d093d6c7fe683aa5b15c8eb63dcd47bca89ab62058fd72c0d68999013d600 Signature Success
The Chalkias Ed25519 Vulnerability
Now, hopefully, you understand the basics of the wonderful Ed25519 signature method. It is so much more secure and faster than ECDSA. So, what was the vulnerability that Konstantinos Chalkias found? Well, in the previous example, we use:
sig1 = signature(m,sk1,vk1)
And thus pass the secret key and the public key. Hopefully, these are matched, and that the public key relates to the secret key. What should happen is:
sig1 = signature(m,sk1)
and where the signature method derives the public key from the secret key. Unfortunately, Konstantinos has found up to 39 libraries did not do this checking, and basically allowed the caching of the public key, and for it then to probe for the correct secret key.
This we can simulate this by:
sig1 = signature(m,sk1,vk1) sig2 = signature(m,sk1,vk2)
and where we are using the same private key, and using an incorrect public key value. Now, we will modify our code to produce two signatures, and one uses the correct key pair, and the other has a different public key:
# https://asecuritysite.com/encryption/eddsa from pure25519.basic import (bytes_to_clamped_scalar, bytes_to_scalar, scalar_to_bytes, bytes_to_element, Base) import hashlib, binascii import os,sys def H(m): return hashlib.sha512(m).digest() def publickey(seed): # turn first half of SHA512(seed) into scalar, then into point assert len(seed) == 32 a = bytes_to_clamped_scalar(H(seed)[:32]) A = Base.scalarmult(a) return A.to_bytes() def Hint(m): h = H(m) return int(binascii.hexlify(h[::-1]), 16) def signature(m,sk,pk): assert len(sk) == 32 # seed assert len(pk) == 32 h = H(sk[:32]) a_bytes, inter = h[:32], h[32:] a = bytes_to_clamped_scalar(a_bytes) r = Hint(inter + m) R = Base.scalarmult(r) R_bytes = R.to_bytes() S = r + Hint(R_bytes + pk + m) * a return R_bytes + scalar_to_bytes(S) def checkvalid(s, m, pk): if len(s) != 64: raise Exception("signature length is wrong") if len(pk) != 32: raise Exception("public-key length is wrong") R = bytes_to_element(s[:32]) A = bytes_to_element(pk) S = bytes_to_scalar(s[32:]) h = Hint(s[:32] + pk + m) v1 = Base.scalarmult(S) v2 = R.add(A.scalarmult(h)) return v1==v2 def create_signing_key(): seed = os.urandom(32) return seed def create_verifying_key(signing_key): return publickey(signing_key) def sign(skbytes, msg): """Return just the signature, given the message and just the secret key.""" if len(skbytes) != 32: raise ValueError("Bad signing key length %d" % len(skbytes)) vkbytes = create_verifying_key(skbytes) sig = signature(msg, skbytes, vkbytes) return sig def verify(vkbytes, sig, msg): if len(vkbytes) != 32: raise ValueError("Bad verifying key length %d" % len(vkbytes)) if len(sig) != 64: raise ValueError("Bad signature length %d" % len(sig)) rc = checkvalid(sig, msg, vkbytes) if not rc: raise ValueError("rc != 0", rc) return True msg="Hello" if (len(sys.argv)>1): msg=str(sys.argv[1]) m = msg.encode() print("Message:",msg) sk1 = create_signing_key() vk1 = create_verifying_key(sk1) sk2 = create_signing_key() vk2 = create_verifying_key(sk2) print("Secret key 1: ",sk1.hex()) print("Verifing key 1: ",vk1.hex()) print("Secret key 2: ",sk2.hex()) print("Verifing key 2: ",vk2.hex()) sig1 = signature(m,sk1,vk1) sig2 = signature(m,sk1,vk2) print("Signature 1 (sk1, pk1): ",sig1.hex()) R1=sig1.hex()[:len(sig1.hex())//2] S1=sig1.hex()[len(sig1.hex())//2:] R2=sig2.hex()[:len(sig2.hex())//2] S2=sig2.hex()[len(sig2.hex())//2:] print("Now we will sign the message with sk1 and use pk1 to give Sig1") print("And sign the message with sk1 and use pk2 to give Sig2") print("\nR1=", R1) print("S1= ",S1) print("R2=", R2) print("S2= ",S2) rtn1=verify(vk1,sig1,m) if (rtn1==True): print("Signature Success") if (R1==R2): print("R1 is equal to R2!")
If we have a sample run, we see that the R values are the same, as the R value relies on the private key:
Message: Hello Secret key 1: 0d03912ed90dd2f37a6905abcaf93bedab69250c702ff4a9c3a80a78e0b1d9a5 Verifing key 1: 7f374d5d9fe3ee6a192b5178003716896449b5866939d797d38bdfa3f724d07d Secret key 2: 4d16a6c8776191ec09d8deeb2bb35fe6778fc8b2ce3606ecf2e1c69b589e449c Verifing key 2: f6890b5f67bdf17389ab436ef2a42559794f8eb993fba613478f0140810453e5 Signature 1 (sk1, pk1): 92e98ce46aca82de10dc856da9e17e7805bc33b824608e25a58424b5cdc3ee9d06ab9cf4234dc492e6f2a1de7ed9dafbb57682f29d1356a3379c3dd0aa677403 Now we will sign the message with sk1 and use pk1 to give Sig1 And sign the message with sk1 and use pk2 to give Sig2 R1= 92e98ce46aca82de10dc856da9e17e7805bc33b824608e25a58424b5cdc3ee9d S1= 06ab9cf4234dc492e6f2a1de7ed9dafbb57682f29d1356a3379c3dd0aa677403 R2= 92e98ce46aca82de10dc856da9e17e7805bc33b824608e25a58424b5cdc3ee9d S2= cde54d3a0ab2671bd942ea111974f681e185c9f045711b9701acacac83aa0f09 Signature Success R1 is equal to R2!
This approach leaks information about the private key, and Konstantinos defines the following method to reveal it [here]
And there you go. Basically what should happen, is that the signing function should only take the private key, and then generate the public key from this.