Ristretto

[kingsleyh]

Hi,

I'm looking at implementing multisig in SushiChain and since I moved to ED25519 I'm investigating Ristretto.

Libsodium already has support for ristretto - I was wondering if this is something you would consider including either in Monocypher or as an add-on.

[kingsleyh]

I guess I'm going to implement Ristretto in Crystal and if you decide in the future to support it in Monocypher - I'll switch to using it if it's better/faster

[kingsleyh]

This looks like an interesting C implementation

[fscoto]

Ristretto's a topic that Loup and I have been discussing for a while now in various contexts. My understanding of Loup's position is that he tends to prefer that the cofactor be handled upstack (i.e. at the protocol level); on the other hand, I'm 100% sold on Ristretto/Decaf being basically the be-all-end-all solution to making Edwards curves good and that cofactors are the worst thing since the invention of patents on cryptography.

Without speaking for Loup or Monocypher, I don't think that Ristretto will be included in Monocypher as-is for multiple reasons:

1. There is no space. Monocypher observes a limit of 2000 lines of source code being the limit, as determined by sloccount(1). And without some serious cheating, Ristretto is going to be a tight fit.
2. There's generally only one way to do things with Monocypher (compatibility optionals for IETF ChaCha20 and Ed25519 notwithstanding). Ristretto would add effectively provide a complete, low-level system to accomplish various tasks that exists in parallel and would require exposing raw scalar multiplication for Ed25519 as well to be of any use.

Similarly, however, it's unlikely that it'll make its way in as an add-on in the src/optional/ tree:

1. To properly encode and decode from Ristretto, you need to be able to access the guts of how elliptic curves are implemented. This is intentionally not exposed and changing that would be rather inelegant and might give rise to some rather bad ideas. In my personal opinion, Monocypher already has a surprisingly large amount of sharp edges and I'd be thankful if there weren't any more to come.
2. Now that Elligator is part of the core featureset of Monocypher, Ristretto and its interaction with both Elligator maps would require special special attention. It was tricky the first time already, and I don't think anyone wants to figure that part out right now.

Ignoring the Elligator issue, I don't think it would be too hard to implement (famous last words) given Monocypher's current state, but it's unlikely to get upstreamed. As far as I can tell, there's not much to it: You need to set up a Ristretto equivalent for ge_tobytes, ge_frombytes_vartime (or a constant-time version instead depending on what you need Ristretto for), both of which you can just 1:1 follow the explicit formulae on the website, new functions for 64-byte string to group element and point equality; hook that up to the a point addition and scalar multiplication functions and that's ristretto255. The current Internet Draft for ristretto255 spells out the functions you need to expose (encode, decode, equals, 64-byte string to group element) and gives you pseudocode that should map to internal functions Monocypher already has. You already have invsqrt() available, so the biggest challenge to shoehorning in Ristretto is already solved, really. This is not an endorsement for people to try and write it themselves. There are likely still subtle pitfalls that I'm not aware of. I would not trust myself to write a production-grade implementation even with Monocypher providing almost all the low-level tools.

I guess I'm going to implement Ristretto in Crystal and if you decide in the future to support it in Monocypher - I'll switch to using it if it's better/faster

I'm not sure how deeply you're into the whole elliptic curve swamp and Ristretto in particular. Ristretto (and Decaf) is ultimately a method of point compression, i.e. taking a set of coordinates (x, y) [affine coordinates] or (X : Y : T : Z) [extended homogeneous coordinates] and returning a bit string that is shorter than the bit length of the coordinates of the point appended to each other. However, the point compression works such that if you operate only on points you decoded from Ristretto, you can effectively ignore the cofactor and get a prime-order group.

However, this comes at some added complexity: Point equality checks require either a specific procedure or re-serialization to Ristretto and comparing the serialized points. More importantly, the (de)serialization procedures are somewhat more expensive. It's not a lot (see the explicit formulas for encoding and decoding to/from bytes and compare it to encoding and decoding for EdDSA; do note that you'll usually need two extra multiplications and one multiplicative inverse for that to go from extended homogeneous coordinates to affine coordinates), but it may well make a difference.

More to the point: It's not faster. But using it is safer and if you're faced with some arbitrary third-party protocol that requires a prime-order group, it's usually easier for the non-expert to take Ristretto than to figure out how to modify the protocol deal with the cofactor properly.

(And technically, serialized points Ristretto and Decaf are both two bits more compact than classic affine point compression as used in Ed25519 since the sign bit for the x coordinate can be omitted and the sign bit of y is always 0.)

[LoupVaillant]

Hi,

I agree with @fscoto, including the part where cofactors are ugly and evil. There are two things to keep in mind though.

First, Monocypher does not really care about compatibility with third parties. The choice of well known primitives were driven by safety and speed, not compatibility. Those third party protocols that require a prime order group? They probably have an equivalent that properly deals with the cofactor.

Second, a naive use of Monocypher already deals with the cofactor to a large extent:

• X25519 naturally absorbs the low order component, if any.
• So does crypto_x25519_inverse().
• Elligator works over the whole curve, and crypto_hidden_key_pair() does the right thing.
• EdDSA doesn't have a cofactor problem (and Monocypher prevents the other malleability problems).

The only remaining problem is that points on the curve (more accurately, equivalence classes with respect to the main subgroup) may have several representatives. To solve that, you generally just have to authenticate the whole transcript, and that's something protocol designers tend to do systematically, even if it's "just in case".

---

If I were to write Monocypher from scratch today, I would consider Ristretto. Now however I have users, and I'd rather not break compatibility with them. Monocypher is supposed to be stable, and 3 major versions in 3 years is not as stable as I'd like.

[kingsleyh]

Thanks for the detailed explanations :)