jedisct1 / libsodium

A modern, portable, easy to use crypto library.
https://libsodium.org
Other
12.06k stars 1.72k forks source link

Add _noclamp versions of curve25519 scalarmult operations #1216

Closed ldr709 closed 1 year ago

ldr709 commented 1 year ago

The curve25519 function crypto_scalarmult always clears the low 3 bits of the scalar, so it always outputs a point in the prime-order subgroup of the elliptic curve. As a default this is fine (though small subgroup attacks are often more important for protocols that would typically be implemented with ed25519 instead), but it conflicts with ciphertext pseudorandomness, a property required by some applications of key exchange. I have coauthored a couple papers that use ciphertext pseudorandomness for oblivious transfer and private set intersection. For implementation, we used a trick due to Möller that provides ciphertext pseudorandomness by randomly choosing between curve25519 and its quadratic twist. As part of the implementation, I patched libsodium to add _noclamp versions of the curve25519 scalar multiplication functions, and I was hoping to be able to upstream these functions. Documentation PR is here.

jedisct1 commented 1 year ago

A slightly different implementation was committed in 8b2cbb0d02396027017e9b4ae4273aba8ce2d767

But I'm not sure that having this is a good thing, at least as-is.

First, because unclamped operations are already available over edwards25519 and ristretto255. So, protocols can already use these. Implementing the same thing over curve25519 doesn't enable anything that couldn't be done already. It just adds extra code that virtually no one is going to use.

Also what is the scalar? For edwards25519 and ristretto255, the range is well defined, and the API offers everything to generate scalars, do modular arithmetic, etc.

In X25519, the scalar is documented everywhere as a random 32 byte sequence. Clamping is an opaque protocol detail. So, unless we bring the entire set of functions for modular arithmetic on scalars to the curve25519 namespace, things can be quite confusing.

As a workaround, we should handle unclamped scalar multiplication over 256 bits, not silently discard one bit. That would be consistent with Curve25519.mul() in Zig. lDoing so introduces quite a lot of ugliness in the code.

At the end of the day, what do we get. Another way to do something that we could already do, just with incompatible outputs and without the ability to perform arithmetic on scalars (even for the tests, using functions from edwards25519 was required, which doesn't really make sense from an API perspective). And if curve25519 is really required for interop, we already have functions mapping curve25519 points to edwards25519 points.

We could add the full scalar functions to scalarmult_curve25519_* but that would add a lot of code having to be maintained forever, add burden to people writing bindings, and I doubt these functions would be used much in the real world.