dalek-cryptography / curve25519-dalek

A pure-Rust implementation of group operations on Ristretto and Curve25519
Other
850 stars 416 forks source link

Implementation of ed25519-dalek::VerifyingKey::verify_strict seemingly inconsistent with documentation #663

Open fspreiss opened 2 weeks ago

fspreiss commented 2 weeks ago

There is a seeming discrepancy between the documentation of ed25519-dalek::VerifyingKey::verify_strict and its implementation.

The documentation of verify_strict suggests that verify_strict uses the verification equation with the cofactors (i.e., [8][S]B = [8]R + [8][k]A'), while the implementation uses the verification equation without the cofactors (i.e., [S]B = R + [k]A'). This is because the documentation says: "This method performs both of the above signature malleability checks", where "both" refers to a "Scalar Malleability" check and a "Point malleability" check, where the documentation of the latter suggests that the actual check is done through the use of the equation with the cofactors.

While one could argue there is some ambiguity in the documentation on "Point malleability" as to whether the equation with or without the cofactors is used, the belief that the one with the cofactors is used is further strengthened by @isislovecruft (one of the original library authors) stating the following in https://github.com/dalek-cryptography/ed25519-dalek/issues/115#issuecomment-720803926:

Note that we currently multiply by the cofactor in verify_strict()

Possibly the latter was true at some point, but it doesn't seem to be the case any more.

That all verification functions (e.g., verify and verify_strict) use the equation without the cofactors was also pointed out earlier in https://github.com/dalek-cryptography/ed25519-dalek/issues/20#issuecomment-570742436 and https://github.com/dalek-cryptography/ed25519-dalek/issues/115#issue-569181785.

Note that verify_strict does fail verification if signature_R.is_small_order() || self.point.is_small_order(). However, as pointed out in https://github.com/dalek-cryptography/ed25519-dalek/issues/20#issuecomment-570742436, this is not equivalent to using the verification equation with the cofactors.

Do you see it as option to adapt verify_strict so that it actually uses the verification equation with the cofactors as (somewhat) suggested by the documentation and as stated by one of the original library authors?

In any case, it would make sense to remove the ambiguity from the documentation of verify_strict's "Point malleablity" section by making clear which of the two mentioned equations is used in the implementation.