EllipticCurve.validateSignature accepts rs[1] >= n

[code423n4]

Lines of code

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

Vulnerability details

Impact

EllipticCurve.validateSignature might accepts invalid signatures because rs[1] >= n is valid for current implementation but in fact, they are invalid.

Proof of Concept

EllipticCurve.validateSignature doesn't check if rs[1] < n. If we uncomment the following line, it will be good, but currently there is no validation about rs[1] < n.

        if (rs[0] == 0 || rs[0] >= n || rs[1] == 0) {
            // || rs[1] > lowSmax)
            return false;
        }

As a result, if rs[1] >= n and (rs[0], rs[1] - n) is a valid signature, EllipticCurve.validateSignature will accept (rs[0], rs[1]) as a valid signature.

But in the original Elliptic Curve Digital Signature Algorithm, rs[1] >= n is invalid as you can see here in wikipedia.

Tools Used

Manual Review

Recommended Mitigation Steps

We should add validation rs[1] < n.

    function validateSignature(
        bytes32 message,
        uint256[2] memory rs,
        uint256[2] memory Q
    ) internal pure returns (bool) {
        // To disambiguate between public key solutions, include comment below.
 -      if (rs[0] == 0 || rs[0] >= n || rs[1] == 0) { 
 +      if (rs[0] == 0 || rs[0] >= n || rs[1] == 0 || rs[1] >= n) { 
            // || rs[1] > lowSmax)
            return false;
        }

[c4-pre-sort]

thereksfour marked the issue as primary issue

[c4-sponsor]

Arachnid marked the issue as sponsor confirmed

[c4-judge]

dmvt marked the issue as selected for report

[trust1995]

The issue does not specify an attack path or describe conditions of some scenario where the consequence of the bug is detrimental to the protocol. For these reasons, it does not meet the requirements of the C4 severity constitution.

[d3e4]

Wikipedia is misleading. It doesn't matter security-wise that we can use congruent values. We only require that r and s not equal 0 mod n. The code checks that for r. But if rs[1] == n then the implementation of the modular inverse gives sInv == 0, which leads to P being the identity. So we fail the identity check and would also need that rs[0] == 0 which is disallowed. Therefore this is not exploitable and not an issue. But I suppose it would look more reassuring with the normal sanity check in the beginning.

[auditor0517]

My estimation was wrong, only one of rs[1] >= n is accepted, so impact is not huge. QA is fair.

[c4-judge]

dmvt changed the severity to QA (Quality Assurance)

[c4-judge]

dmvt marked the issue as grade-b

[c4-judge]

dmvt marked the issue as not selected for report

[c4-judge]

dmvt marked the issue as grade-a