Implementation of sqrt() is incorrect, used in pricing

[c4-bot-2]

Lines of code

https://github.com/code-423n4/2024-03-abracadabra-money/blob/1f4693fdbf33e9ad28132643e2d6f7635834c6c6/src/mimswap/libraries/Math.sol#L29

Vulnerability details

Description

MIMswap uses the following square root implementation in Math:

function sqrt(uint256 x) internal pure returns (uint256 y) {
    uint256 z = x / 2 + 1;
    y = x;
    while (z < y) {
        y = z;
        z = (x / z + z) / 2;
    }
}

It is the babylonian method taken from DODO. However there is an incorrect result when the input is 2:

contract Test {
    function sqrt(uint256 x) external pure returns (uint256 y) {
        uint256 z = x / 2 + 1;
        y = x;
        while (z < y) {
            y = z;
            z = (x / z + z) / 2;
        }
    }
}

Calling sqrt(2) -> 2 Note that sqrt(1) -> 1, sqrt(3) -> 1, so the result is breaking the invariant that sqrt(x) < sqrt(y) if x < y. The Uniswap implementation handles it correctly:

        } else if (y != 0) {
            z = 1;
        }

The sqrt() function is used in _SolveQuadraticFunctionForTrade()

// calculate sqrt
uint256 squareRoot = DecimalMath.mulFloor((DecimalMath.ONE - k) * 4, DecimalMath.mulFloor(k, V0) * V0); // 4(1-k)kQ0^2
squareRoot = sqrt((bAbs * bAbs) + squareRoot); // sqrt(b*b+4(1-k)kQ0*Q0)
// final res
uint256 denominator = (DecimalMath.ONE - k) * 2; // 2(1-k)
uint256 numerator;
if (bSig) {
    numerator = squareRoot - bAbs;
    if (numerator == 0) {
        revert ErrIsZero();
    }
} else {
    numerator = bAbs + squareRoot;
}

When the value being calculated would be 2, the invariant breaking would lead to unexpected results and wrong calculations.

Impact

Wrong pricing calculations when calculating the sqrt() of 2.

Tools Used

Manual audit

Recommended Mitigation Steps

Use the UniswapV2 sqrt() implementation.

Assessed type

Math

[c4-pre-sort]

141345 marked the issue as primary issue

[c4-pre-sort]

141345 marked the issue as sufficient quality report

[0xCalibur]

Ack. Fix is here https://github.com/Abracadabra-money/abracadabra-money-contracts/pull/151

[c4-sponsor]

0xCalibur (sponsor) acknowledged

[c4-judge]

thereksfour marked the issue as satisfactory

[c4-judge]

thereksfour marked the issue as selected for report

[blutorque]

This findings should be low, due its zero impact in current in the scope contracts and very low likelihood, warden assumed;

When the value being calculated would be 2, the invariant breaking would lead to unexpected results and wrong calculations.

uint256 s1= DecimalMath.mulFloor((DecimalMath.ONE - k) * 4, DecimalMath.mulFloor(k, V0) * V0); // 4(1-k)kQ0^2
squareRoot = sqrt((bAbs * bAbs) + s1); // sqrt(b*b+4(1-k)kQ0*Q0)

*First squareRoot renamed as s1 for convenience

The sqrt() uses s1 for its calculation. It can be checked that the value of this s1 more likely result in the same decimal as V0, since V0 is directly mulitplied to DecimalMath.mulFloor(k,V0). This V0 is either quote or base target, which has the same decimal as its respective token.

So even if we consider tokens with lowest decimal places(e.g. 6), the chances of s1 being eq 2 is same as 1/1e6, which is one in million. Also the severity categorization suggest it to be low, since assets are not at risk directly or indirectly.

[thereksfour]

Agree with the low likelihood, but it seems to affect key functions in PMMPricing that are used to calculate the swap amount of tokens, so the impact would be considered to high, and this finding would be considered M severity

[blutorque]

hey @thereksfour , In Math.sol, sqrt() is used at places L97, L99, other than this, it is used in above snippet that warden has provided(explanation of this part I'd given above),

97:            _sqrt = sqrt(((ki * delta) / V1) + DecimalMath.ONE2); <@ 
98:        } else {
99:            _sqrt = sqrt(((ki / V1) * delta) + DecimalMath.ONE2); <@ 
100:        }

since, ONE2(1e36) is added, reaching sqrt(2) is just an imaginary.

That's it. No where else the sqrt() is being in used in current of scope of the contracts. I request the judges to please reconsider this, its would be completely unfair to other warden to grant this medium severity when its cannot even stand to it.

[thereksfour]

After reconsidering, I think that even if there is a miscalculation, i.e. incorrectly calculating sqrt(2) as 2 instead of 1, the impact is very minimal.

Consider the case where squareRoot is 2 and 1 in the following calculation. The numerator will be 1 bigger than the correct calculation. Its impact is essentially eliminated by divCeil. The maximum impact will make the _SolveQuadraticFunctionForTrade() is 1 less than correct. This also means a loss of 1 wei when swapping tokens. In summary, consider QA.

        squareRoot = sqrt((bAbs * bAbs) + squareRoot); // sqrt(b*b+4(1-k)kQ0*Q0)

        // final res
        uint256 denominator = (DecimalMath.ONE - k) * 2; // 2(1-k)
        uint256 numerator;
        if (bSig) {
            numerator = squareRoot - bAbs;
            if (numerator == 0) {
                revert ErrIsZero();
            }
        } else {
            numerator = bAbs + squareRoot;
        }

        uint256 V2 = DecimalMath.divCeil(numerator, denominator);
        if (V2 > V1) {
            return 0;
        } else {
            return V1 - V2;
        }

[c4-judge]

thereksfour changed the severity to QA (Quality Assurance)

[c4-judge]

thereksfour marked the issue as not selected for report