Scalar arithmetic is inconsistent with point multiplication most of the time

[rozbb]

What's wrong

Scalars in various curve25519-based schemes are considered as integers to be multiplied with a curve point. This is fine. In other protocols, scalars are considered as integers mod ℓ to be multiplied with curve points in the prime ℓ-order subgroup.
This is also fine.

A problem arises when you mix these two interpretations of scalars. It doesn't matter if you use s or s + 3ℓ to multiply by a point in the prime-order subgroup (since they're the same mod ℓ). But it does matter when the point is not in the prime-order subgroup. Concretely, the following assert fails most of the time:

// Make a random clamped scalar
let s = {
    let mut bytes = [0u8; 32];
    rng.fill_bytes(&mut bytes);
    Scalar::from_bits_clamped(bytes)
};

// Make a random point
let point = {
    let mut bytes = [0u8; 32];
    rng.fill_bytes(&mut bytes);
    CompressedEdwardsY::from_slice(&bytes)
        .unwrap()
        .decompress()
        .unwrap()
};

assert_eq!(s * point, s.reduce() * point);

In other words, scalar mod ℓ arithmetic is incompatible with most of the points on the curve. Here's a demonstration that the distributive property is violated. This assert fails most of the time:

// Make two random scalars that are reduced mod l
let (s1, s2) = {
    let mut bytes1 = [0u8; 32];
    let mut bytes2 = [0u8; 32];
    rng.fill_bytes(&mut bytes1);
    rng.fill_bytes(&mut bytes2);
    (
        Scalar::from_bytes_mod_order(bytes1),
        Scalar::from_bytes_mod_order(bytes2),
    )
};

// Make a random point
let point = {
    let mut bytes = [0u8; 32];
    rng.fill_bytes(&mut bytes);
    CompressedEdwardsY::from_slice(&bytes)
        .unwrap()
        .decompress()
        .unwrap()
};

assert_eq!((s1 + s2) * point, s1 * point + s2 * point);

What to do

You don't need arithmetic for Scalar almost ever. I propose removing the Add and Mul traits for Scalar. To keep functionality, there should be a new type, ScalarFieldElem which has these traits and is guaranteed to always be reduced mod ℓ.

The arithmetic (Add, Mul) functionality from Scalar should be split off to a new type, ScalarFieldElem, which is guaranteed to always be reduced mod ℓ. This way, you can still use Scalar::from_bits_clamped as in the most common case, and if you need arithmetic, you're nudged towards the more correct type.

Further, ScalarFieldElem should not be allowed to be multiplied with any point outside the prime-order subgroup. To this end, there should probably be a PrimeOrderGroupElem type (or something less wordy) which is guaranteed to have no 8-torsion component.

Issues

This interacts not great with how ed25519-dalek batching currently works. Recall, in batch verification you have to compute zᵢkᵢ * Aᵢ for each i. As we know from above, and from all previous talk on batch verification, this is not well-defined. We can make an escape hatch for this operation if we want.

Another option is to adopt the mul-by-cofactor batch equation. This requires computing 8zᵢkᵢ * Aᵢ, which is well defined because 8Aᵢ is in the prime-order subgroup. The API described above doesn't really capture this, but an easyish solution would be to make special case these particular linear equations that have an 8 * out front.

Questions

What do we name the new types? How are we gonna expose the ill-defined mul-by-fieldelem method? What is the feature flag gonna be named?

cc @tarcieri

[jrose-signal]

libsignal's poksho uses Scalar addition and multiplication for its Schnorr protocol (but doesn't run into problems because it stays in the Ristretto subgroup). I don't think we'd have a problem using a separate ScalarFieldElem type for this operation, or explicitly-named functions, but just wanted to point out that it does have a use.

[str4d]

(but doesn't run into problems because it stays in the Ristretto subgroup)

To clarify, ristretto255 is not a subgroup of Curve25519. It is a separate group that has the same order as the prime-order subgroup of Curve25519, and can use Curve25519 point arithmetic to implement its group operations. But there is nothing that forces ristretto255 elements to only internally use a subgroup of Curve25519 points as internal representatives for arithmetic; it is entirely possible that encoding and then decoding a ristretto255 element results in a different Curve25519 internal representative.

For ristretto255, having a scalar type that implements integers mod ℓ with addition and multiplication, and doesn't inherit any of the other scalar weirdness, would be ideal.

[Sc00bz]

You don't need arithmetic for Scalar almost ever.

This is needed for an OPRF. You have to calculate the inverse of a scalar. Also sometimes this can be used to replace a*(b*G) with (a*b)*G. One of these cases is some doubly augmented PAKEs, when the password is provided vs using the stored client data.

Anyway to preserve the zeroing of the cofactor, all the scalar operations could be modulo 8*ℓ. This can be used to simplify the implementation of scalar invert while preserving the clamp (ie clampedInvert(clamp(scalar)) == clamp(clampedInvert(clamp(scalar)))). Note that a clamped invert can fail but it's like a 1 in 2^121 chance.

---

I suggest either no change or make scalar operations modulo 8*ℓ instead of ℓ.

[rozbb]

@Sc00bz I think I might have miscommunicated my proposal. See the new paragraph. Also, could you point to a representative PAKE impl? It'd be great to have a reference when making the change, so as to break as little as possible.

[burdges]

We need 0 = 8*(R - (s*B - c*A)) to be the preferred non-batched verificatoin for ed25519, aka remove the cofactor last not first, right? You found the distributive property being violated creates issues for ed25519 batch verification or more half-aggregation even with this approach?

[str4d]

Further, ScalarFieldElem should not be allowed to be multiplied with any point outside the prime-order subgroup. To this end, there should probably be a PrimeOrderGroupElem type (or something less wordy) which is guaranteed to have no 8-torsion component.

I introduced a SubgroupPoint type in #473, which is needed for the ff traits (which explicitly handle this issue). If a ScalarFieldElem type is introduced then we can change the Group::Scalar associated type in #473 to be that.

[tarcieri]

I think this can be closed after #519?