Difficult Ed25519 implementations have made hundreds of cryptography packages vulnerable to attacks. Ed25519 is a common digital signature method.

Cryptographer Konstantinos Chalkias of MystenLabs, who found and disclosed the flaw, claims that hackers might use it to steal private keys from cryptocurrency wallets.

The susceptible technologies have been patched to some extent, but not all of them.

Where’s your Ed at?

As a more recent alternative to the Elliptic Curve Digital Signature Algorithm, Ed25519 is frequently utilised (ECDSA). Ed25519 has gained a lot of popularity across many industries, especially blockchain and cryptocurrency platforms, because it is more open, secure, and quick than ECDSA.

The key advantages of ECDSA, according to Chalkias, are that EdDSA signatures are predictable and users don’t need [access to] a secure Random Number Generator [RNG] to sign a transaction.

“How does this help? due to the possibility that a user’s laptop or Internet of Things device won’t have a strong source of entropy or support a strong RNG function.

Numerous security occurrences have demonstrated that bad random generation can lead to private key leaks or thefts. One significant instance was the PlayStation 3’s ECDSA algorithm-based technology’s private key breaches.

Pre-computing public keys

Giving the algorithm a message and a private key is required by the Ed25519 message signing specification. The computation of the public key and message signing will be done by the function using the private key. A message signing function that is offered by some libraries has an additional input argument that accepts the pre-generated public key. The use of this strategy has various advantages.

“Recalculating the public key each time would result in a slower algorithm (it adds an additional scalar to elliptic curve point multiplication to generate the public key, which reduces the speed by approximately two times, potentially making it even slower than ECDSA),” Chalkias stated.

Additionally, it’s generally advisable in cryptography to refrain from repeatedly obtaining the private key. It follows that we must access it twice—once to sign and again to derive the public key—if we permit the public key to be derived on each signing invocation.

However, the modification also creates a security loophole in the library.

According to Chalkias, certain libraries accept any public key as an input without verifying that it matches the input private key. This flaw allows an attacker to utilise the signing function as an Oracle, conduct crypto-analysis, and eventually obtain secrets. For instance, an attacker who lacks access to the private key but has access to the signature mechanism via an API call could utilise a number of public keys and messages to progressively gain knowledge of the private key parameters.

Libraries at risk

26 libraries were first identified as being at risk by Chalkias. Later, 40 libraries were added to the list. A financial API was among the web services that the security researcher discovered to be susceptible to the same kind of attack.

When keyGen fails in some applications or a clean-up process deletes the privKey for this user, the software typically tries keyGen again. The database, however, continued to store the old userID, pubKeyOld> for a brief period of time, creating a small window for race condition attacks before the database was updated with the new pubKey (a situation that, surprisingly, we were able to exploit with a high probability). Chalkias made this observation.

Since his report, several libraries have implemented fixes and workarounds, including ed25519-elisabeth, PASETO, and Trezor wallet. “A few libraries [have] already provided either fixes (if they were vulnerable) or proactively added extra checks that the stored pub key corresponds to the private keys,” Chalkias concluded.