Incorrect signatures %1 of the time

[conorpp]

We already talk about this, but opening here to stay organized. Signatures seem to be invalid deterministically about 1% of the time. One of the vectors that causes a bad signature is the following.

ed25519  Secret / seed = 5C 8A 90 83 8D 10 55 24 FE 8D F6 5A 9D AF D9 9C C4 08 53 7B 6C A3 1B 39 91 0B 71 75 35 55 74 15 
ed25519  public key = E7 0E 8F C5 4B 8E 9E 35 67 ED 82 D9 CE 98 A8 DA 06 BD 06 C4 A3 83 F4 36 C3 BA 05 5D C8 48 A8 04

signing data = BF AB C3 74 32 95 8B 06 33 60 D3 AD 64 61 C9 C4 73 5A E7 F8 ED D4 65 92 A5 E0 F0 14 52 B2 E4 B5 01 00 00 0B 0E 31 32 33 34 35 36 37 38 39 61 62 63 64 65 66 30 31 32 33 34 35 36 37 38 39 61 62 63 64 65 66 30

(incorrect) signature = 45 13 8A 44 1F B8 D0 C5 6B 1F F7 E5 7E 75 99 38 49 12 17 99 F1 58 E0 DE 56 F7 29 29 70 EA 93 9C FA 56 EF EE 50 AD DF 2A 80 4F AA 46 41 9D 37 D8 4C C4 7B 93 AE 96 9E F0 39 2C B7 F2 00 E5 36 10

[nickray]

It seems that this is not an incorrect signature: https://colab.research.google.com/drive/1ZDRWkO9o9YVbo6HLl7Weo3G35c4ccIID

So I assume the error is in the signing data vis-a-vis what CTAP/python-fido2 expect.

[nickray]

The issue turns out to be that SUPERCOP (and hence python-ed25519) skip the malleability check S < l, whereas OpenSSL (and hence cryptography, which python-fido2 uses) run it.

libsodium added the check too: jedisct1/libsodium#125

An online reference for more information: dalek-cryptography/ed25519-dalek#20 (comment).

Adjusting the signature in this issue by subtracting L from S fixes things.

Will PR a change, although strangely the code indicates we do actually reduce S mod L.

UPDATE: "reduce_modulo_ell" actually just subtracts L once. In some cases, one has to do this twice.

[nickray]

This is fixed.