P-256 failing cases

[swojo]

Seeing an issue where the P-256 verify fails with certain inputs (which succeed when verified with a different library, eg wolfssl).

Eg. These set of inputs fail but are valid when run through a different library:
Curve: P-256r1
`/* public key (raw) */
{0x49, 0x5d, 0x14, 0x99, 0xb6, 0x62, 0x6e, 0xa9, 0x94, 0xaf, 0x76, 0x8f, 0xf9,
0x60, 0xac, 0xfa, 0xc3, 0xaf, 0x29, 0xf, 0x8c, 0x98, 0x16, 0xa1, 0x58,
0xa7, 0xee, 0x71, 0xbe, 0x89, 0x5e, 0x79, 0x2a, 0x16, 0x8a, 0xae, 0xb7,
0x97, 0xea, 0x66, 0x57, 0x86, 0x96, 0x63, 0x56, 0x71, 0x5b, 0xcb, 0x44,
0xcc, 0x51, 0xd7, 0x92, 0xf4, 0xbc, 0xd6, 0x32, 0xc, 0x37, 0xa, 0x73, 0x87,
0x1f, 0x69}

/* message */
{0xef, 0x79, 0x8c, 0xff, 0x4c, 0x93, 0x5d, 0xca, 0x6c, 0xc1, 0x93, 0x38,
0xf4, 0x8f, 0xfd, 0x61, 0x85, 0xa7, 0xeb, 0x46, 0x12, 0x16, 0x98, 0x5f,
0xc3, 0xd7, 0x25, 0x52, 0xf5, 0xb9, 0x18, 0x36}

/* signature (raw) */
{0x49, 0x5d, 0x14, 0x99, 0xb6, 0x62, 0x6e, 0xa9, 0x94, 0xaf, 0x76, 0x8f,
0xf9, 0x60, 0xac, 0xfa, 0xc3, 0xaf, 0x29, 0xf, 0x8c, 0x98, 0x16, 0xa1,
0x58, 0xa7, 0xee, 0x71, 0xbe, 0x89, 0x5e, 0x79, 0x6, 0x78, 0x35, 0x94,
0xbf, 0xe8, 0x92, 0xd4, 0xc1, 0xda, 0xa7, 0x97, 0xf9, 0xb4, 0x9d, 0x4c,
0x29, 0xb9, 0xf5, 0x13, 0x1f, 0x9a, 0x20, 0x3c, 0x71, 0x7c, 0x2, 0x24,
0x32, 0x9b, 0x18, 0xf9}`

With these inputs, rx is 0 at the end of the uECC_verify function, and fails the check against r.

[jojotds]

I see the same problem...
I can't verify the signature below using uECC_secp256r1
With these input rx also becomes = 0 during the uECC_verify process.
apply_z(tx, ty, z, curve); // Here tx becomes same value as rx so on the next line Z becomes 0 because rx and tx are equal
uECC_vli_modSub(tz, rx, tx, curve->p, num_words); /* Z = x2 - x1 */

I can verify the signature below with python using https://pypi.org/project/ecdsa/

HASH (SHA256): 797601B76D29603D167FA1062CC27B00BB0E39493BF3B7BBAFA610C2B24F4A20

Public Key:
7CF27B188D034F7E8A52380304B51AC3C08969E277F21B35A60B48FC4766997807775510DB8ED040293D9AC69F7430DBBA7DADE63CE982299E04B79D227873D1

Signature:
56CD9CF152BCCC3A64E41E2B2BF91ED0661E0821B14B50ABE93C05EA889AFED3F93452957106BAB410617E306D876BB58FA7D7B5A515AC6B6181D8D638651FC7

[Robloit]

@jojotds
I think the root cause is this line: uECC_vli_modMult_fast(z, z, tz, curve);
As soon as tz gets 0 once, it stays at 0 forever.

On a higher level, the issue is that this implementation is handling the identity element incorrectly. Let O be the identity element and P a point on curve. Usually O + P = P, but in this implementation O + P = O, which leads to the rejection of the signature.

In line 1579 to 1585, the point t is added to the point r. This point addition shows the above described behavior.
Probably this point addition algorithm has to be substituted with another algorithm, e.g. https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates

Please note this issue does not only exist for the inputs described above, but also for other inputs from test libraries (e.g. Wycheproof).

[CryptoManiac]

There seem to be an issue with the optimized uECC_vli_modMult_fast function. If you replace it with "slow" version then everything works fine.

[Robloit]

OMG, thanks for figuring this out. The slow version should be definitely the standard in the mainline and we should warn the user about this when using the faster version.

[CryptoManiac]

OMG, thanks for figuring this out. The slow version should be definitely the standard in the mainline and we should warn the user about this when using the faster version.

It wouldn't do any good since the generic version of MMod function is impractically slow to use. Like ten times slower or so. Anyway, this glitch is only relevant if you need to verify the signatures that have been made by different implementations. If you have a closed ecosystem then you can just ignore it. Because there is no problem with signatures made by uECC and the other implementations can verify the signatures generated by the uECC.