Documentation for PublicKey::verify_strict() is misleading

[abacabadabacaba]

The documentation for PublicKey::verify_strict() method states that it verifies a signature in a way that eliminates signature malleability. Unfortunately, this is not what it actually does.

The first point in the documentation talks about scalar malleability. As it says, both verify and verify_strict check that a scalar is encoded canonically. However, if legacy_compatibility feature is enabled, this check is loosened for both verify and verify_strict. A user can expect verify_strict to remain strict even if legacy_compatibility feature is used, but this is not what happens.

The second point, which talks about point malleability of R, is more misleading. First, being able to add a small-order component to R is not a source of signature malleability at all: because the value of R is hashed (together with the message and the public key), any change to R, even the addition of a torsion component, will invalidate the signature. So, anyone who is not in possession of a private key cannot change R while keeping the signature valid, just as they can't change the message. And anyone who is in possession of a private key can generate any number of distinct valid signatures of the same message by generating r randomly rather than deterministically.

By the way, the README file is also misleading in this regard. It states that "doing so allows for signature malleability, meaning that there may be two different and "valid" signatures with the same key for the same message, which is obviously incredibly dangerous", but a key holder can generate any number of such signatures that will pass even the most strict checks.

What the function does (and which is not mentioned in the documentation) is rejecting a signature if the key or R consist exclusively of a small-order torsion component. This is because they check those points using is_small_order() method. Is this intended? It looks like is_torsion_free() is more relevant here.

Also, verify_strict() doesn't check that the encoding of R is canonical. verify() does this implicitly, by computing the encoding of the expected value of R and comparing is with the encoding of R byte-wise. Unlike verify(), verify_strict() compares unpacked points, so a point that is encoded non-canonically may go undetected (but this doesn't lead to signature malleability, see above).

[isislovecruft]

Hi @abacabadabacaba! Thanks for creating this issue.

The first point in the documentation talks about scalar malleability. As it says, both verify and verify_strict check that a scalar is encoded canonically. However, if legacy_compatibility feature is enabled, this check is loosened for both verify and verify_strict. A user can expect verify_strict to remain strict even if legacy_compatibility feature is used, but this is not what happens.

I've clarified this in ad2e75f.

The second point, which talks about point malleability of R, is more misleading. First, being able to add a small-order component to R is not a source of signature malleability at all: because the value of R is hashed (together with the message and the public key), any change to R, even the addition of a torsion component, will invalidate the signature. So, anyone who is not in possession of a private key cannot change R while keeping the signature valid, just as they can't change the message. And anyone who is in possession of a private key can generate any number of distinct valid signatures of the same message by generating r randomly rather than deterministically.

Yes, this is misleading, as it only applies to the batch verification equation and isn't relevant here. For that to occur, a torsion component must also be added to the public key, and the signature will probablistically falsely satisfy the batch equation.

I've fixed this in 0206d0a.

What the function does (and which is not mentioned in the documentation) is rejecting a signature if the key or R consist exclusively of a small-order torsion component.

Clarified in 87731f1.

This is because they check those points using is_small_order() method. Is this intended? It looks like is_torsion_free() is more relevant here.

Yes, I agree. This check is slower and there has been some discussion of this in #20 and #115.

Also, verify_strict() doesn't check that the encoding of R is canonical. verify() does this implicitly, by computing the encoding of the expected value of R and comparing is with the encoding of R byte-wise. Unlike verify(), verify_strict() compares unpacked points, so a point that is encoded non-canonically may go undetected (but this doesn't lead to signature malleability, see above).

This is a fair point, and I think we should be checking for non-canonical Rs. There are 26 non-canonical byte representations of the y-coodinate and sign bit which can decompress to valid curve points, so it might actually be faster to check that the compressed bytes aren't equal to any of them, rather than dealing with compression and decompression. However, if we switched to checking that R is torsion-free (and checking that it's not the identity element) then this would be redundant.

[rozbb]

Agreed that we need better documentation around malleability and verify_strict. This is a must-do before 2.0 release.

I explored this in #259 and wrote up my findings.

Closing as a dupe of #20