Has the ed25519 criteria changed?

[iquerejeta]

I might be missing a check wrt torsion elements somewhere, but doesn't the new verification criteria accept signatures with an R that contains a torsion component?

Before 42b4a29 we had:

    ge25519_double_scalarmult_vartime(&R, h, &A, sig + 32);
    ge25519_tobytes(rcheck, &R);

    return crypto_verify_32(rcheck, sig) | (-(rcheck == sig)) |
           sodium_memcmp(sig, rcheck, 32);

Therefore, we were checking that rcheck's byte representation was equivalent to that received in the signature. Given that rcheck comes from a value computed by the verifier, it will not have a torsion component. Therefore, if sig contained a torsion component, the check would fail.

However, in after that commit (and a later one, 0f767c7) it changed to:

    ge25519_double_scalarmult_vartime(&sb_ah_p2, h, &A, sig + 32);
    ge25519_p2_to_p3(&sb_ah, &sb_ah_p2);
    ge25519_p3_sub(&check, &expected_r, &sb_ah);

    return ge25519_has_small_order(&check) - 1;

In this case, expected_r might have a torsion component and, if that's the case, when subtracting by sb_ah the result will be the torsion component. However, the signature will accept that, as the torsion component has small order.

Is there any particular reason why this change is being applied?

[jedisct1]

Can you clarify why this is necessary?

R is part of the hash, and the Taming the many EdDSAs paper notes that rejecting small order R is not required for binding.

[jedisct1]

I might be missing a check wrt torsion elements somewhere

It's in the second commit you referenced:

libsodium/src/libsodium/crypto_sign/ed25519/ref10/open.c

Line 48 in ee00928

ge25519_has_small_order(&expected_r) != 0) {

but may eventually be removed.

[iquerejeta]

I'm not implying that is necessary for security, I just wanted to confirm whether signatures that were previously rejected may now be accepted (with the latest version of master).

And the check you shared only checks whether the expected_r has small order, but not whether it contains a torsion component. So we could still have that expected_r is not a small order point, but is not part of the prime order subgroup.

Just to clarify, I'm not saying this results in the verification algorithm being insecure, just that the set of accepted signature now changes.

[jedisct1]

Yes, the intent was to be consistent with Zig's standard library, and allow signatures checked individually to follow the same rules as batch verification.

Libsodium doesn't support batch verification yet, but that may be added next.

[iquerejeta]

Ok, so the goal is to support batch verification 👍 I did an implementation of batch_verification for a VRF variant here. Ed25519 batch verification would be very similar. If there is interest, I'd be happy in translating that to the ed25519 context and open a PR.
We had an audit on that code made by Taurus.