Fixed#safeMulDiv rounds incorrect when rounding mode is set to ROUND

[howlbot-integration]

Lines of code

https://github.com/code-423n4/2024-07-reserve/blob/3f133997e186465f4904553b0f8e86ecb7bbacbf/contracts/libraries/Fixed.sol#L561-L607

Vulnerability details

Impact

Fixed#safeMulDiv rounds incorrect when rounding mode is set to ROUND and functions closer to CEIL

Proof of Concept

function safeMulDiv(
    uint192 a,
    uint192 b,
    uint192 c,
    RoundingMode rounding
) internal pure returns (uint192 result) {
    if (a == 0 || b == 0) return 0;
    if (a == FIX_MAX || b == FIX_MAX || c == 0) return FIX_MAX;

    uint256 result_256;
    unchecked {
        (uint256 hi, uint256 lo) = fullMul(a, b);
        if (hi >= c) return FIX_MAX;
        uint256 mm = mulmod(a, b, c);
        if (mm > lo) hi -= 1;
        lo -= mm;
        uint256 pow2 = c & (0 - c);

        uint256 c_256 = uint256(c);
        // Warning: Should not access c below this line

        c_256 /= pow2; <- @audit c_256 is modified
        lo /= pow2;
        lo += hi * ((0 - pow2) / pow2 + 1);
        uint256 r = 1;
        r *= 2 - c_256 * r;
        r *= 2 - c_256 * r;
        r *= 2 - c_256 * r;
        r *= 2 - c_256 * r;
        r *= 2 - c_256 * r;
        r *= 2 - c_256 * r;
        r *= 2 - c_256 * r;
        r *= 2 - c_256 * r;
        result_256 = lo * r;

        // Apply rounding
        if (rounding == CEIL) {
            if (mm != 0) result_256 += 1;
        } else if (rounding == ROUND) {
            if (mm > ((c_256 - 1) / 2)) result_256 += 1; <- @audit modified c_256 used to check rounding
        }
    }
    if (result_256 >= FIX_MAX) return FIX_MAX;
    return uint192(result_256);
}

For rounding to be accurate the unmodified divisor must be used to check the remainder of the division. Above we see that c_256 is divided by pow2 before being used to check mm (the remainder). Take the following example of c = 1e18:

pow2 = c & (0 - c) = 1000000000000000000 & (0 - 1000000000000000000) = 524288

c_256 = c_256/524288 = 19073486328125

As we can see the final c_256 is significantly lower than it should be. In this scenario, values greater than 499999999999999999 should be rounded up however, due to the error in implementation, values greater than 9536743164062 will be rounded up. To put that in decimal terms, that is 0.499999999999999999 vs 0.000009536743164062 which is a staggering difference. This effectively turns ROUND into CEIL.

Although safeMulDiv is not used with the ROUND rounding in the in-scope contracts, this math library is used across the entire protocol and will presumably be used during future upgrades as well.

We all know that rounding error, although they seems insignificant have lead to some very nasty exploits in defi. Any future update which utilizes this function to round for distribution of asset, pricing or share evaluation could cause loss of funds. In such situation, the incorrect rounding direction could cause incremental advantage to an attacker who could repeatedly exploit the rounding error to drain funds from the protocol. This risk is exponentially greater due to these contracts being deployed on low cost chains like base and OP.

Tools Used

Forge fuzz testing

Recommended Mitigation Steps

Use c rather than c_256 for checking the round:

        if (rounding == CEIL) {
            if (mm != 0) result_256 += 1;
        } else if (rounding == ROUND) {
--          if (mm > ((c_256 - 1) / 2)) result_256 += 1;
++          if (mm > ((c - 1) / 2)) result_256 += 1;
        }

Assessed type

Error

[tbrent]

Confirming it works as described by the warden: Fixed.safeMulDiv() for ROUND rounds up too aggressively because the wrong c_256 value is used to compute the remainder.

Fortunately this does not impact any of the core contracts or live funds. However, the Fixed.sol library is specifically listed as in-scope for the competition. Under a "Speculation on future code" assumption, there could be a future impact that could put funds at risk.

However: (i) this future code would need to be developed even though we have no expectations for it today; and (ii) funds would need to become at-risk as a result -- but the magnitude of the rounding effect is very small (1 wei) so it is not clear this would necessarily be the case.

Electing to confirm the bug at L severity, pending Judge approval.

[thereksfour]

No clear impact, will downgrade to Low.
Similar judgment: code-423n4/2024-03-abracadabra-money-findings#228 (comment)

[c4-judge]

thereksfour changed the severity to QA (Quality Assurance)

[tbrent]

reserve-protocol/protocol#1187