Explaining The Chalkias Ed25519 Vulnerability

Explaining The Chalkias Ed25519 Vulnerability

One of the most important functions within a trusted infrastructure is the usage of a digital signature. In the past, ECDSA has been shown to have weaknesses, including where Sony used a private key of “9”. Many in the industry are moving to the more secure Ed25519 signature method, and which uses a Schnorr approach to generate a digital signature.

But, now Konstantinos Chalkias from MystenLabs has reported a major vulnerability in the implementation of the Ed25519 (EdDSA) signature method on a range of libraries. This vulnerability could allow attackers to steal private keys from wallets, and also allow for the impersonation attacks using forged signatures.

So, my early Saturday morning task is to explain this vulnerability. And, now, please bare with me here, as I outline the basic method used in Ed25519, and then I will show the vulnerability. So, I won’t use Rust or Golang, but stick to good old plain Python.

The Basics of Ed25519

My first task is to show how Ed25519 actually works. For this, Alice is going to sign something for Bob to check. She initially generates a random 32-byte secret key (sk) and then creates a public key of:

and where G is the base point of the curve. Alice then creates a SHA-512 hash of her private key:

The signature is made up of an r value and an s value. She create r from the upper 32 bytes of hash and the message (m):

And where “||” represents a concatenation of the byte array values. Next she matches r onto curve with:

Next Alice computes s with:

The signature is (R,s). The values of R and s are 32 bytes long, and thus the signature is 64 bytes long.

To verify, Bob creates S using R, pk and m:

And next creates two verification values:

If v1==v2 the signature checks. This is because:

I have coded this as simply as possible, so you can see the basic steps [here]:

A sample runs shows:

Message: Hello
Secret key:  1713eabb6764a316d0731ec0643b8fb5bea9e79d9ac61c76ccef3e30945e53eb
Verifing key:  9835c2338983071d65496eda2b487dab38d54a427daadf2b5a90033506b9f226
Signature:  3d13ee16209b5218ba385ea46e11de640343a80ffb377ddfdd7dab07bbbfbe9935a4366137ee64067e1919f961612eca8b7e912204d7e29aaf2d4d831a2b3c0a
R=  3d13ee16209b5218ba385ea46e11de640343a80ffb377ddfdd7dab07bbbfbe99
S=  35a4366137ee64067e1919f961612eca8b7e912204d7e29aaf2d4d831a2b3c0a
Signature Success

So, we see that we have a secret (private) key and a public (verifying) key, and which are the same length. This is a characteristic of Curve 25519. Each time we produce the signature, we will get a new signature value, and new values of R and S. You can try here:

https://asecuritysite.com/eddsa/ed01

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.

Thus 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 [here]:

You can run the code here:

https://asecuritysite.com/eddsa/ed02

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:

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.

You can view these code samples here:

https://asecuritysite.com/eddsa/ed01

and

https://asecuritysite.com/eddsa/ed02

You can read more about Konstantinos’ thoughts here: