code423n4 commented 1 year ago

Lines of code

https://github.com/code-423n4/2023-04-ens/blob/45ea10bacb2a398e14d711fe28d1738271cd7640/contracts/dnssec-oracle/algorithms/EllipticCurve.sol#L137-L140

Vulnerability details

Impact

EllipticCurve.isOnCurve returns false for x = 0, but there are valid points of SECP256R1 whose x coordinate is 0. If those points are used for public key in validateSignature, validateSignature will returns false for valid signatures.

Proof of Concept

EllipticCurve.isOnCurve returns false for x = 0 or x = p.

    function isOnCurve(uint256 x, uint256 y) internal pure returns (bool) {
        if (0 == x || x == p || 0 == y || y == p) {
            return false;
        }

But SECP256R1, which is the curve used here, has a point whose x coordinate is 0. Let us say

y0 = 0x66485C780E2F83D72433BD5D84A06BB6541C2AF31DAE871728BF856A174F93F4

y0 * y0 % p = b, so (0, y0) is on SECP256R1, and (0, p - y0) is also on SECP256R1.

These are valid points and there is no limitation about these points, so they can be used as public key, even though the probability to choose the corresponding private key is very low. For these valid public key points, isOnCurve will return false. In that case, validateSignature will return false for valid signatures.

        if (!isOnCurve(Q[0], Q[1])) {
            return false;
        }

I attached coded POC for isOnCurve, and we don't know the private key of (0, y0), so I skipped writing for validateSignature.

    function testIsOnCurve() external pure {
        uint x;
        uint y = 0x66485C780E2F83D72433BD5D84A06BB6541C2AF31DAE871728BF856A174F93F4;
        require(mulmod(y, y, p) == b, "y^2 = b, so (0, y) is on the curve");

        uint256 LHS = mulmod(y, y, p); // y^2
        uint256 RHS = mulmod(mulmod(x, x, p), x, p); // x^3

        if (a != 0) {
            RHS = addmod(RHS, mulmod(x, a, p), p); // x^3 + a*x
        }
        if (b != 0) {
            RHS = addmod(RHS, b, p); // x^3 + a*x + b
        }

        require(LHS == RHS, "double check - (0, y) is on the curve");
        require(!isOnCurve(0, y), "isOnCurve(0, y) returns false");
    }

Tools Used

Manual Review

Recommended Mitigation Steps

We should remove validation about x in isOnCurve.

function isOnCurve(uint256 x, uint256 y) internal pure returns (bool) {
 -      if (0 == x || x == p || 0 == y || y == p) {
 +      if (0 == y || y == p) {
            return false;