Proof of Concept of the Chalkias Ed25519 Implementation Vulnerability in Python

Proof of Concept of the Chalkias Ed25519 Implementation Vulnerability in Python

Konstantinos Chalkias from MystenLabs has reported a major vulnerability in the implementation of the Ed25519 (EdDSA) signature method on a range of libraries [2, 3]. It should be noted the Ed25519 is a highly secure method, but it has been let down by the implementation of the method in around 40 libraries. This is a MAJOR implementation vulnerability and could allow attackers to steal private keys from wallets. It could also allow for the impersonation attacks using forged signatures.

So, let’s actually implement a proof of concept for this.

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. The code for this is here:

https://asecuritysite.com/eddsa/ed01

Proof of Concept for Poor Implementation of Ed25519

Now, if we can get the same message signed with the same private key, but with different public keys, we can actually recover the private key signing element (sk). In the previous derivation we had:

Bob is able to determine:

and so we have:

Now, if we can generate two signatures from different public keys we get [1]:

and:

If we now subtract these we get:

Converting to find sk:

And, that’s it! Bob can recover Alice’s private key, by taking the two signatures, and then also generating the e values for each signature.

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
    e=Hint(R_bytes + pk + m) 
    return R_bytes, S,e,a

We see that the return is R, S, e and a (and where a is the private key element that we want to recover.) The code we need now is:

R1,S1,e1,a1 = signature(m,sk1,vk1)
R2,S2,e2,a2= signature(m,sk1,vk2)

q=pow(2,555)-19
e_inv=invmod(e1-e2,q)
val=((S1-S2)*e_inv) %q

And with a sample run we see we can recover the private key element:

Message: Hello
Secret key 1:  ddf7becfcbb6add34bd7dbf377b1de0f6c09e71c07dda720faca027905e61172
Verifing key 1:  41c1829f965c5bc8b89af365aa23831ce13b43a124f0cb0ba9a99ec44894b519
Secret key 2:  83158153e01eff5c7db3b911e613939f292fc4fa45659466a7750a3079e76a04
Verifing key 2:  0453090d566cfd4a9a213c7aecb9a843dcf9b36d8c0d645006d529474e4990c8

Recovered private key element:  42153319604559151050509664631610125740601183589956076291747165775958039011104
Actual Private key element:  42153319604559151050509664631610125740601183589956076291747165775958039011104

Private key signing element has been recovered

The coding is here:

https://asecuritysite.com/eddsa/ed03

and here is the code:

Conclusions

It must be said that the Ed25519 is a highly secure method, and it is the implementation of the method that is major problem here. Developers should thus always generate the public key from the private key when creating the signature. Please, also note, that the Schnorr signature method is also vulnerable to this implementation vulnerability.

References

[1] Does changing the random number selected for each message increase security in Schnorr’s scheme?, https://crypto.stackexchange.com/questions/13129/does-changing-the-random-number-selected-for-each-message-increase-security-in-s

[2] https://github.com/MystenLabs/ed25519-unsafe-libs

[3] Analysis On Ed25519 Use Risks: Your Wallet Private Key Can Be Stolen, https://blog.safeheron.com/blog/safeheron-originals/analysis-on-ed25519-use-risks-your-wallet-private-key-can-be-stolen