Ed25519 is Great, But …

“You can lead a horse to water, but you can’t make it drink”
Photo by Mukesh Naik on Unsplash

Ed25519 is Great, But …

“You can lead a horse to water, but you can’t make it drink”

Sometimes, you feel that some software developers struggle to properly secure their code. For example, a recent survey showed by some developers struggled to know the difference between encoding methods (such as Base 64), hashing methods (such as SHA-1) and encryption methods (such as AES).

One of the most important function 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”. And, so, now Konstantinos Chalkias from MystenLabs has reported a major vulnerability in the implementation of the Ed25519 (EdDSA) signature method, and which could allow attackers to steal private keys from wallets.

Ed25519

With digital signatures, we create a key pair: a private (or secret) key and a public (or verifier) key. We can store this key pair in our wallet, and then use the private key when we have to sign for something. Basically for a signature, we take a hash of a message and then apply our private key to produce the signature. This is typically in the form of an R and an s value (R,s). These values can then be used with the public key and the message to verify the signature.

With Ed25519, we use the well-known Curve 25519 elliptic curve, and convert it into a digital signature method. This uses 256-bit values for the private and public key and gives us 128-bit equivalent security. Overall it uses a prime number of:

2²⁵⁵-19

With Ed25519, Bob first generates a 256-bit random number for his private key (priv) and then creates his public key with:

pub=H(priv)[:32]⋅B

and where B is the base point on the curve, and where H() is a hashing function (SHA-512). In this case, we take the lower 32 bytes of the SHA-512 hash. Normally, we just define this as the y coordinate of the point. The public key is thus 32 bytes long (256 bits). To compute the signature, we generate:

r=H_int(H(priv)[32:]||M)(mod l)

and where H_int() is a hash function (SHA-512) and converted to an integer value. In this case, we take the upper 32 bytes for the calculation. The value of l is the order of the curve. Then M is the byte value of the message. With “||” we append the bytes together. We then convert this to a point on the curve with:

R=r⋅B

Next, we compute:

h=Hint(R||pub||M)(mod l)

and:

s=H_int(priv))[:32]

S=(r+h⋅s)(modl)

The signature is then (R,S). Bob sends M, R, S and pub to Alice. Alice then computes:

k=H(R||pub||M)(mod l)

P1=S⋅B

P2=R+k⋅pub

and if P1 is equal to P2, the signature verifies. This works because:

P1=S⋅B=(r+h⋅s(mod l))⋅B=r⋅B+h⋅s⋅B=R+h⋅pub=P2

Note that l is the order of the curve (l=2252+27742317777372353535851937790883648493).

The great advantage of using Ed25519 over ECDSA is that we can aggregate signatures and public keys. Here is an overview of the maths involved:

There are three main modes [RFC 8032] that we can have: Ed25519 (pure EdDSA, as we have defined above), Ed25519Ph (where the message is hashed), and Ed25519Ctx (and where we add a context message):

  • Ed25519 (pure Ed25519). r=Hint(H(priv)[32:]||M)(mod l)
  • Ed25519Ph (with pre-hash). r=Hint(H(priv)[32:]||H(M))(mod l). In this case, the message will be hashed with SHA-512 before it is used.
  • Ed25519Ctx (with context). r=Hint(H(priv)[32:]||M||Ctx)(mod l) and where Ctx is a context string.

A range of implementation are here:

https://asecuritysite.com/eddsa

In RFC 8032, we should always create unique values for R and s for every signature. The s part uses the public key, but not the R element. An intruder could thus use a signing function to discover when the same message get the same R value, but will differ with the s value. If this can be found, it is fairly easy to recover the private key (defined here).

The Chalkias Vulnerability

Ed25519 has many advantages over ECDSA, including not requiring a strong source of randomness. It is also faster, and less complex in its implementation. The discovered weakness relates some implementations setting up pre-computed public keys, and which speeds up their operation. Thus, when a user signs for a transaction, we would normally access the private key twice: to sign the transaction; and to generate the public key. But some libraries do not check that the public key actually relates to a corresponding key, and thus do not check the signature. This approach could allow an attacker to inject a range of public keys and messages, into the signature method, and eventually discover parts of the private key. It should be remembered that even if one bit is discovery it reduces the security by a half, and two bits by a quarter, and so on.

Konstantinos initially found 26 libraries that were vulnerable were posted on Twitter [here]:

This number has since increased to 40. Since the post a few libraries have been fixed, but many are still vulnerable.

Conclusions

Sometimes, just sometimes, it’s performance over security, and that is often not a good focus when you are protecting critical assets, such as your digital wallet.