Dozens of cryptography libraries vulnerable to private key theft

Signing mechanism security shortcomings exposed

A poor implementation of Ed25519, a popular digital signature algorithm, has left dozens of cryptography libraries vulnerable to attacks.

According to Konstantinos Chalkias, a cryptographer at MystenLabs who discovered and reported the vulnerability, attackers could exploit the bug to steal private keys from cryptocurrency wallets.

Some but not yet all of the vulnerable technologies have been patched.

Where’s your Ed at?

Ed25519 is often used as a modern replacement for the Elliptic Curve Digital Signature Algorithm (ECDSA). Ed25519 is more open, secure, and faster than ECDSA, which is why it has become very popular in many sectors, especially in blockchain and cryptocurrency platforms.

“The main benefits against ECDSA is that EdDSA sig[nature]s are deterministic and users don’t need [access to] a secure Random Number Generator [RNG] to sign a transaction,” Chalkias told The Daily Swig. “Why is this useful? because a user’s laptop or IoT device might not have a good source of entropy or support a weak RNG function.”

Numerous security incidents have shown that poor random generation can result in private keys being leaked or stolen. One notable example was the private key leaks of PlayStation 3, whose technology relies on the ECDSA algorithm.

Pre-computing public keys

The standard specification of Ed25519 message signing involves providing the algorithm with a message and private key. The function will use the private key to compute the public key and sign the message. Some libraries provide a variant of the message signing function that also takes the pre-computed public key as an input parameter. There are some benefits to this implementation.

“Recomputing the public key each time would result in a slower algorithm (it adds an extra scalar to elliptic curve point multiplication to derive the public key, which reduces the speed by almost 2x, potentially making it even slower than ECDSA),” Chalkias said.

“And generally, in cryptography, it’s good hygiene to avoid accessing the private key many times. If we allowed the public key derivation on each signing invocation, then this implies we need to access it twice, once to sign, and once to derive the public key.”

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

Chalkias found that some libraries were allowing arbitrary public keys as inputs without checking if the input public key corresponds to the input private key. This shortcoming means that an attacker could use the signing function as an Oracle, perform crypto-analysis and ultimately get at secrets. For example, an attacker who can’t access the private key but can access the signing mechanism through an API call could use several public keys and messages to gradually build up insights into private key parameters.

Libraries at risk

Chalkias initially found 26 libraries that were vulnerable to the attack. The list was later extended to 40 libraries. The security researcher also found several online services that were vulnerable to the same kind of attack, including a fintech API.

“In some applications when keyGen fails or a clean-up process deletes the privKey for this user, then the app usually retries keyGen. But in the meantime and for a few sec[ond]s, the DB [database] still stored the old <userID, pubKeyOld>, and this allowed a narrow window for race condition attacks before the DB gets updated with the new pubKey (a scenario that, surprisingly, we managed to exploit with significant probability),” Chalkias noted.

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.