Updated Tue, 06 Sep 2022 16:11:51 GMT

Replacing Curve25519 with Ristretto255

Quoting Ristretto255 for the PHP Community,

Ristretto255 is Ristretto defined over Curve25519, which allows cryptographers to extend the Ed25519 signature scheme to support complex zero-knowledge proof protocols without having to deal with the cofactor.

(The cofactor in Ed25519 is what caused the multi-spend vulnerability in CryptoNote cryptocurrencies (n.b. Monero).)

It's not entirely clear to me, from this, what all would be involved with swapping out Curve25519 for Ristretto255.

Is crypto_scalarmult_ristretto255 a drop in replacement for crypto_scalarmult?

There's crypto_box_easy and crypto_box_easy_open, but they use X25519 - not Ristretto255. I'm not seeing a crypto_box_easy_ristretto255 function. Maybe it's not needed for that specific use case? Or maybe libsodium has such a function and I just missed it when I was reviewing the documentation?


The Monero vulnerability was related to "key images". When signing a transaction to spend an output, a unique EC point called a "key image" is produced as a result of the signature. This key image uniquely identifies the private key of the output being spent (without revealing which output in the ring that private key is associated with). Therefore, if the spender ever attempts to spend that output again in another ring signature, they will be forced to declare the same key image again, and the network will be able to see that there has been a double-spend attempt.

However, because Ed25519 (and Curve25519) have a co-factor, there are 8 large subgroups (because the co-factor is 8). This means that you could spend an output, nudge the key image into the wrong subgroup, and under certain circumstances pretend that a second signature has a different key image.

The fix for this was very easy - you just need to validate each key image to ensure it is in the correct large subgroup. To do this, you just multiply it by the group order and check that the result is the point at infinity (the "zero" point).

Therefore, if you are designing new EC schemes, Ristretto255 would be helpful to avoid the risk of forgetting to validate points in all necessary places.

The designers of X25519 were well aware of this issue, which is why X25519 clears the lower 3 bits of the private key used during key exchange. This forces the private key to be a multiple of 8, which means that the result of X25519 will be in the correct large subgroup even if it was provided with an invalid EC point in the wrong large subgroup.

The bottom line is that X25519 has already been designed to prevent the problem that Ristretto255 was designed to prevent. Since X25519 has been very widely examined for vulnerabilities, the risk of introducing a vulnerability by implementing a new form of ECDH in Ristretto255 would be higher than the risk of just using a widely used and audited X25519 implementation.

Is crypto_scalarmult_ristretto255 a drop in replacement for crypto_scalarmult?

Ristretto255 is not supposed to be interoperable with Curve25519. It is supposed to provide you with safe, equivalent methods while hiding implementation details from you and ensuring all safety checks are in place. Therefore, if you would normally use crypto_scalarmult for your own ECDH mechanism (or other EC scheme), you would now use crypto_scalarmult_ristretto255 instead.

Comments (3)

  • +2 – Great answer. I would add that just using crypto_scalarmult means you should concatenate the output/shared secret with both public keys before passing it through a KDF to prevent vulnerabilities and slightly improve the entropy. Some implementations don't do this, like Monocypher didn't, which led to the API being depreciated. Similarly, many implementations don't check for 'weak keys', which allows one party to force the shared secret to zero. crypto_kx should be preferred. — Aug 06, 2022 at 13:00  
  • +2 – @samuel-lucas6 That's a very interesting point about attempting to use knowledge of the shared secret to prove knowledge of a private key. Are you aware of any protocols that attempted to do this? — Aug 06, 2022 at 13:13  
  • +2 – The Matrix protocol for end-to-end encrypted messaging used X25519 to make an SAS scheme but only hashed the shared secret, which allowed an attacker to force the same SAS. This was apparently quickly fixed. It was mentioned in the book Real-World Cryptography by David Wong. — Aug 06, 2022 at 13:35