Tapioca DAO - nadin's results

Lines of code

https://github.com/Tapioca-DAO/tapioca-periph-audit/blob/023751a4e987cf7c203ab25d3abba58f7344f213/contracts/Swapper/libraries/FullMath.sol#L7-L123

Vulnerability details

Impact

The Fullmatch library in tapioca-periph-audit/contracts/Swapper/libraries/FullMath.sol doesn't correctly handle the case when an intermediate value overflows 256 bits. This happens because an overflow is desired in this case but it's never reached.

Proof of Concept

• In UniswapV3Swapper.sol : OracleLibrary.getQuoteAtTick() ---> FullMath.mulDiv
• The FullMath library which doesn't use an unchecked block:

File: tapioca-periph-audit/contracts/Swapper/libraries/FullMath.sol
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.18;


/// @title Contains 512-bit math functions
/// @notice Facilitates multiplication and division that can have overflow of an intermediate value without any loss of precision
/// @dev Handles "phantom overflow" i.e., allows multiplication and division where an intermediate value overflows 256 bits
library FullMath {
    /// @notice Calculates floor(a×b÷denominator) with full precision. Throws if result overflows a uint256 or denominator == 0
    /// @param a The multiplicand
    /// @param b The multiplier
    /// @param denominator The divisor
    /// @return result The 256-bit result
    /// @dev Credit to Remco Bloemen under MIT license https://xn--2-umb.com/21/muldiv
    function mulDiv(
        uint256 a,
        uint256 b,
        uint256 denominator
    ) internal pure returns (uint256 result) {
        // 512-bit multiply [prod1 prod0] = a * b
        // Compute the product mod 2**256 and mod 2**256 - 1
        // then use the Chinese Remainder Theorem to reconstruct
        // the 512 bit result. The result is stored in two 256
        // variables such that product = prod1 * 2**256 + prod0
        uint256 prod0; // Least significant 256 bits of the product
        uint256 prod1; // Most significant 256 bits of the product
        assembly {
            let mm := mulmod(a, b, not(0))
            prod0 := mul(a, b)
            prod1 := sub(sub(mm, prod0), lt(mm, prod0))
        }


        // Handle non-overflow cases, 256 by 256 division
        if (prod1 == 0) {
            require(denominator > 0);
            assembly {
                result := div(prod0, denominator)
            }
            return result;
        }


        // Make sure the result is less than 2**256.
        // Also prevents denominator == 0
        require(denominator > prod1);


        ///////////////////////////////////////////////
        // 512 by 256 division.
        ///////////////////////////////////////////////


        // Make division exact by subtracting the remainder from [prod1 prod0]
        // Compute remainder using mulmod
        uint256 remainder;
        assembly {
            remainder := mulmod(a, b, denominator)
        }
        // Subtract 256 bit number from 512 bit number
        assembly {
            prod1 := sub(prod1, gt(remainder, prod0))
            prod0 := sub(prod0, remainder)
        }


        // Factor powers of two out of denominator
        // Compute largest power of two divisor of denominator.
        // Always >= 1.
        uint256 twos = denominator & (~denominator + 1);
        // Divide denominator by power of two
        assembly {
            denominator := div(denominator, twos)
        }


        // Divide [prod1 prod0] by the factors of two
        assembly {
            prod0 := div(prod0, twos)
        }
        // Shift in bits from prod1 into prod0. For this we need
        // to flip `twos` such that it is 2**256 / twos.
        // If twos is zero, then it becomes one
        assembly {
            twos := add(div(sub(0, twos), twos), 1)
        }
        prod0 |= prod1 * twos;


        // Invert denominator mod 2**256
        // Now that denominator is an odd number, it has an inverse
        // modulo 2**256 such that denominator * inv = 1 mod 2**256.
        // Compute the inverse by starting with a seed that is correct
        // correct for four bits. That is, denominator * inv = 1 mod 2**4
        uint256 inv = (3 * denominator) ^ 2;
        // Now use Newton-Raphson iteration to improve the precision.
        // Thanks to Hensel's lifting lemma, this also works in modular
        // arithmetic, doubling the correct bits in each step.
        inv *= 2 - denominator * inv; // inverse mod 2**8
        inv *= 2 - denominator * inv; // inverse mod 2**16
        inv *= 2 - denominator * inv; // inverse mod 2**32
        inv *= 2 - denominator * inv; // inverse mod 2**64
        inv *= 2 - denominator * inv; // inverse mod 2**128
        inv *= 2 - denominator * inv; // inverse mod 2**256


        // Because the division is now exact we can divide by multiplying
        // with the modular inverse of denominator. This will give us the
        // correct result modulo 2**256. Since the precoditions guarantee
        // that the outcome is less than 2**256, this is the final result.
        // We don't need to compute the high bits of the result and prod1
        // is no longer required.
        result = prod0 * inv;
        return result;
    }


    /// @notice Calculates ceil(a×b÷denominator) with full precision. Throws if result overflows a uint256 or denominator == 0
    /// @param a The multiplicand
    /// @param b The multiplier
    /// @param denominator The divisor
    /// @return result The 256-bit result
    function mulDivRoundingUp(
        uint256 a,
        uint256 b,
        uint256 denominator
    ) internal pure returns (uint256 result) {
        result = mulDiv(a, b, denominator);
        if (mulmod(a, b, denominator) > 0) {
            require(result < type(uint256).max);
            result++;
        }
    }
}

• The FullMath library is currently used was designed in order to handle "phantom overflow" i.e., allows multiplication and division where an intermediate value overflows 256 bits.
• This means that the original library can handle statements like : FullMath.mulDiv(type(uint256).max / 2, 3, 111)) .
• This a feature of the library, as statements like this cannot be handled by solidity >0.8 directly as the execution will revert due to an overflow. Because the original library was created with solidity version <0.8.0 (which doesn't revert on overflows) this behaviour was allowed as the expected intermediatory overflow could be reached.
• However, due to the fact that the FullMath Library was ported to solidity version ^0.8.18, which is >0.8, this operation would revert as the intermediate calculations would overflow, meaning that it can't handle those multiplication and division where an intermediate value overflows the 256 bits.
• The fix is to mark the full body in an unchecked block, in order to leverage the fact that the original version was designed in order to allow the intermediate overflow.
• A modified version of the original Fullmath library that uses unchecked blocks to handle the intended overflow, can be found in the 0.8 branch of the Uniswap v3-core repo.

Tools Used

Manual Review

Recommended Mitigation Steps

• It is advised to put the entire function bodies of mulDiv and mulDivRoundingUp in an unchecked block. A modified version of the original Fullmath library that uses unchecked blocks to handle the overflow, can be found in the 0.8 branch of the Uniswap v3-core repo.
• Similar cases consider adding unchecked block in case of FullMatch in twAML.sol for optimization.

Assessed type

Under/Overflow