A self-contained definition of `verify_strict`

[AljoschaMeyer]

Hi,

I am looking for a precise definition of what exactly verify_strict does. I am not entirely confident in my understanding of the underlying math, but is the following sketch accurate?

• Adhere to RFC RFC8032, with the following modifications:
• In §5.1.7, step 1: reject the signature if S >= L.
• In §5.1.7, step 3: reject the signature if [8][S]B = [8]R + [8][k]A' does not hold.

This is what I get from the current doc comments. Is this alone sufficient to uniquely characterise the behaviour of verify_strict, or are there further requirements? According to the ZIP215 blogpost, there are additional sources of ambiguity:

• If the verification key is given as a byte array (as opposed to a curve point), whether its encoding is canonic.
• Whether R in the (unbatched) equality check [8][S]B = [8]R + [8][k]A' must have been encoded canonically.

How does verify_strict handle the canonicity requirements of A and R? Since from_bytes is infallible, am I right to assume that these checks are not performed?

I'd love to contribute an explicit definition to the API docs once I actually know what that definition would have to say =)

[tarcieri]

Since from_bytes is infallible, am I right to assume that these checks are not performed?

I would agree it does not appear to be checking that the Edwards y-coordinate is reduced/canonical. That follows ZIP-215 rules, but not RFC8032.

#833 attempts to address it.

[tarcieri]

It seems like this issue might be a duplicate of #663

[AljoschaMeyer]

Related, but not duplicate I'd say. #663 asks whether the equation meant for bulk verification is used. I was assuming that this is the case, and was instead looking for clarification on whether the signature bytes must be canonically encoded in order for verification to pass.

Taking a step back: the ZIP215 blogpost lists five points of potential divergence. My question was basically: does verify_strict implement the strictest possible configuration out of these points of divergence (which is uniquely defined when requiring the batch verification equation and forbidding any additional ad-hoc criteria).

The answer is no, if I understood you correctly. A follow-up question of mine would be whether the NIST full validation criteria together with the batch verification equation would yield that strictmost sensible signature verification function.

Framed yet another way: all I want are unique signatures, why is this so hard 😢

[tarcieri]

I believe if it were using the NIST full validation criteria, then it would be doing what the comments say it's doing.

It would be great to get #626 landed but it seems to have stalled.