Description

During the audit, a number of test vectors were ported to verify the ECDSA signature verification module Secp256r1.sol. One of these test vectors was test case ID 345: extreme value for k and s^-1 from Project Wycheproof. The parameters in this test picks values such that the inverse of s is very high and verifies that the signature still passes the check. This test case fails for this module.

To verify that the signature is indeed correct, we tested all the parameters in SageMath with the following script,

# Curve parameters
p256 = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a256 = p256 - 3
b256 = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
gx = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
gy = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
qq = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
FF = GF(p256)
E = EllipticCurve([FF(a256), FF(b256)])
E.set_order(qq)
G = E(FF(gx), FF(gy))
# Test parameters
pubx = 0xc6a771527024227792170a6f8eee735bf32b7f98af669ead299802e32d7c3107
puby = 0xbc3b4b5e65ab887bbd343572b3e5619261fe3a073e2ffd78412f726867db589e
r    = 0x7cf27b188d034f7e8a52380304b51ac3c08969e277f21b35a60b48fc47669978
s    = 0xb6db6db6249249254924924924924924625bd7a09bec4ca81bcdd9f8fd6b63cc
h    = 0xbb5a52f42f9c9261ed4361f59422a1e30036e7c32b270c8807a419feca605023
s1   = inverse_mod(s, E.order())
assert ((h * s1) * G + (r*s1)*E(pubx, puby)).xy()[0] == r

which passes with no issues. A similar test failure raised concerns in the fastecdsa project↗ and got assigned CVE-2020-12607↗ at a very high severity level (though this CVE score is disputed).

Impact

The full impact is hard to classify without more knowledge about the root cause of the bug, but the most likely effect will be that some valid signatures will be rejected --- but rarely. The mentioned CVE-2020-12607↗ claims that this is not merely a usability problem, so depending on the root cause, it could be dangerous.

Recommendations

The likely culprit is lack of consideration for the point at infinity when adding or doubling with modified Jacobians. The code comments link to the website Point-at-Infinity↗ where the optimized algorithm used in the code is broken down. Some of the conditionals, where an early return POINT_AT_INFINITY is reached, are missing from the contract code. These checks should be implemented properly to check if the point at infinity occurs during calculations.

We also strongly recommend to implement comprehensive test cases that go beyond test vectors but also target edge cases in the calculations.

Remediation

Following the completion of this audit, Zellic conducted a separate review of Secp256r1, the details of which can be accessed here↗.