Closed stevieraykatz closed 6 months ago
This PR fixes unicity in the representation of a point. While it is not a vulnerability as such, but rather malleability, it is correct that unexpected uses of malleability can lead to disaster. Thanks for the update.
I don't think this change is needed and instead a different one should be made. The current change protects against cases where x=2p, 3p, ...
or y=2p, 3p, ...
but this never happens since 2p, 3p, ...
won't fit in the uint256
type and therefore the type system will protect against it. The only reason that you might want to do this change is if mod operation is more efficient than checking against 0 and p.
The description of the PR is correct in pointing out that the code accepts x
and x+p < 2^256
(and similarly y
and y+p < 2^256
) as valid while it should only accept x
and y
. I believe the fix should be adding an additional check that validates if x < p && y < p
. Putting it all together, I think the following change should be made:
if (x >= p || y >= p || ((x == 0) && (y == 0))) {
return false;
}
@rdubois-crypto what do you think?
@stevieraykatz I think Arash's point here makes sense and we should probably just open a new PR. I do not think the x+p
issue is mitigated by the modulo check.
In
FCL_Elliptic_ZZ.ecAff_isOnCurve
where x and y are the coordinates of the public key we first validate that the point is not at infinity (0,0) and then verify that the points are not equivalent to the prime field modulus.Today, this check fails to consider the case where x and y are some higher multiple of p. The remainder of the check whether the point is on the curve, as well as all subsequent curve calculations, are all done mod p, so these are equivalent representations of the (0,0) identity element but pass this critical, initial check. This means that an attacker can create a key pair such that for any single message with signature he can produce up to three additional public keys which will all be validated by
ecdsa_verify
.This can be fixed by changing the logic to the following:
The following PoC demonstrates the vulnerability:
A similar issue was reported in this biconomy audit.