Cofactored verification of Ed25519 signatures

[CedarMist]

Re: https://github.com/oasisprotocol/oasis-core/blob/b0e6bc88be7a3fe051ea1d35b06e8d33691d5aec/runtime/src/common/crypto/signature.rs#L123-L128

https://github.com/oasisprotocol/oasis-core/blob/b0e6bc88be7a3fe051ea1d35b06e8d33691d5aec/runtime/src/common/crypto/signature.rs#L173

---

8.8. Multiplication by Cofactor in Verification

The given verification formulas for both Ed25519 and Ed448 multiply points by the cofactor. While this is not strictly necessary for security (in fact, any signature that meets the non-multiplied equation will satisfy the multiplied one), in some applications it is undesirable for implementations to disagree about the exact set of valid signatures. Such disagreements could open up, e.g., fingerprinting attacks.

---

Note that the ed25519-dalek verify_strict method doesn't use cofactored verification.

https://github.com/dalek-cryptography/ed25519-dalek/blob/02001d8c3422fb0314b541fdb09d04760f7ab4ba/src/verifying.rs#L349

---

From my notes:

• With cofactored verification, signatures are malleable. An attacker can multiply a point in the signature by the cofactor to create a new valid signature.
• Cofactor-less verification: This stricter method only accepts signatures using points in the main subgroup. It's considered more secure in some contexts.
• Security-critical systems, especially those where signature malleability could be exploited, might prefer cofactor-less verification.

---

Are we sure that we want to use cofactored verification? Under normal circumstances signing libraries will never produce signatures outside of the main subgroup.

I feel that ed25519_dalek::verify_strict could be used unless there are compelling reasons. The comments in Oasis signature.rs are confusing and don't specify the intent for allowing signature malleability by using cofactored verification.

ADR-009 does though: https://github.com/oasisprotocol/adrs/blob/5acd39c3491e72bb6692818641f8585b54783ae2/0009-ed25519-semantics.md?plain=1#L68C1-L79C12

Cofactored Verification Equation

There are two forms of the Ed25519 verification equation commonly in use, [S]B = R + [k]A (cofactor-less), and [8][S]B = [8]R + [8][k]A (cofactored), which are mutually incompatible in that it is possible to produce signatures that pass with one and fail with the other.

The cofactored verification equation is explicitly required by FIPS 186-5, and is the only equation that is compatible with batch signature verification. Additionally, the more modern lattice-reduction based technique for fast signature verification is incompatible with existing implementations unless cofactored.

https://eprint.iacr.org/2020/1244.pdf provides more insight

Essentially, providing a batch signature to a cofactorless verification routine will fail.

---

ADR-064 specifies block validation by batching signatures.

[kostko]

This is probably a question for @Yawning, I would assume that the Rust implementation is consistent with the Go one. But note that changing any of this is very likely consensus-breaking.

[CedarMist]

Am still digging into this, will update notes above.

[CedarMist]

I'm going to close this ticket for now, but it was worth making a note of.