Comment by loup-vaillant

Do note thought that X25519 and Ed25519 were designed so they wouldn’t need those checks at all. It’s only when you’re trying to design fancier protocols on top of Curve25519 or Edwards25519 that you can run into subgroup issues.

And for those use cases, I personally try my best to just reproject everything back into the prime order subgroup whenever possible. Monocypher has a number of such fancy functions:

  crypto_x25519_dirty_fast()
  crypto_x25519_dirty_small()
  crypto_elligator_map()
  crypto_elligator_rev()
  crypto_elligator_key_pair()

The dirty functions explicitly produce public keys that cover the entire curve, so that random such keys are truly indistinguishable from random when converted with `crypto_elligator_rev()`. But instead of just removing the clamp operation, I instead add random low-order point, so that when we later use the point in an X25519 key exchange, the shared secret is exactly the same as it would have been for a genuine X255119 key.

That’s where I thank DJB for designing a key exchange protocol that project the shared secret to the prime order subgroup, even when the public key it processes is not. The original intent may have been to make checks easier (low order keys all end up yielding zero), but a nice side effect is how it enabled a nice API for Mike Hamburg’s Elligator2.

> Accepting points outside the prime-order subgroup can quietly undermine higher-level assumptions, even if no immediate exploit is obvious.

If on the other hand we can prove that all computed results are low-order-component-independent (as is the case for X25519), then we know for sure we’re safe. In the end, Ristretto is only really needed when we can’t tweak the protocol to safely reproject to the prime order subgroup.

Don’t get me wrong, having a prime order group abstraction does help. But if someone is qualified to design a protocol that may require this, they’re qualified to try and make it work with a non-trivial cofactor as well — that, or prove it cannot be done.