07.Lockbox2
2023-09-18 11:09:48 # 14.Paradigm CTF 2022

Lockbox2

分析

1.任务

任务是让lockbox2.locked()值设置为false

1
2
3
function isSolved() external view returns (bool) {
       return !lockbox2.locked();
   }

然后我们看Lockbox2.sol合约可以知道，需要成功调用solve()，其实也就是通过5个stage的检验，调用方式为：外部进行call调用，输入：solve()函数选择器 + msg.data

1
2
3
4
5
6
7
8
9
10
function solve() external {
    bool[] memory successes = new bool[](5);
    (successes[0],) = address(this).delegatecall(abi.encodePacked(this.stage1.selector, msg.data[4:]));
    (successes[1],) = address(this).delegatecall(abi.encodePacked(this.stage2.selector, msg.data[4:]));
    (successes[2],) = address(this).delegatecall(abi.encodePacked(this.stage3.selector, msg.data[4:]));
    (successes[3],) = address(this).delegatecall(abi.encodePacked(this.stage4.selector, msg.data[4:]));
    (successes[4],) = address(this).delegatecall(abi.encodePacked(this.stage5.selector, msg.data[4:]));
    for (uint256 i = 0; i < 5; ++i) require(successes[i]);
    locked = false;
}

2.通过5个stage

2.1stage1

1
2
3
function stage1() external {
    require(msg.data.length < 500);
}

第一个条件很容易满足，只需要我们的msg.data不要太长即可

2.2stage2

1
2
3
4
5
6
7
8
function stage2(uint256[4] calldata arr) external {
    for (uint256 i = 0; i < arr.length; ++i) {
        require(arr[i] >= 1); 
        for (uint256 j = 2; j < arr[i]; ++j) { 
            require(arr[i] % j != 0);
        }
    }
}

可以看出，第二个条件是将我们的msg.data分成了uint256[4]，也就是说每32个字节一份。然后要求：

  • 数组的每个数值必须是大于或等于1的素数
  • 由于for (uint256 j = 2; j < arr[i]; ++j)，因此我们的素数不能很大，不然会造成gas不足或者达到区块的gaslimit限制，我们无法知道某个素数花了多少gas，因此选择的素数越小越好

2.3stage3

1
2
3
4
5
function stage3(uint256 a, uint256 b, uint256 c) external {
    assembly { mstore(a, b) }
    (bool success, bytes memory data) = address(uint160(a + b)).staticcall("");
    require(success && data.length == c);
}

  • assembly { mstore(a, b) }：将内存位置a之后的32字节的值设置为b，暂时没啥用

    1
    2
    3
    4
    mstore(p,v): mem[p..(p+32)] := v
    | offset | value | ===> 
    memory[offset:offset+32] = value
    writes a (u)int256 to memory

  • (bool success, bytes memory data) = address(uint160(a + b)).staticcall("");

    • 将a和b的和作为地址，然后进行staticcall()，由于stage2的限制，a和b必须尽可能的小，因此a加b所得到的地址也会很小，那么就会得到一个包含很多0的地址。由于这样的地址用CREATE2几乎不可能做到，因此此地址包含的code一定是空的，返回来的值一定为：success=true，data=空。

  • require(success && data.length == c);

    • success一定为true，没问题。

    • 因为data一定为空，因此data.length一定为0，此时c的值就只能为0。但是0不是素数，因此无法通过条件2，我们必须做些什么。

      1. 注意到，stage3包含了内联汇编，并且有mstore可以操作内存中的数值，我们还得知道，solidity保留了 4 个 32 字节槽，其中一个32字节槽为0x60 - 0x7f，这个槽位用来定义程序的 “零” 是什么，也就是说程序如果返回 “零”值，那么回到这个槽来取值，默认情况下 ”零“的值为0。

      2. 知道了这些，我们可以这么操作：当staticcall()返回 “零“值的时候，回到内存0x60 - 0x7f的位置去取值，如果我们将0x60 - 0x7f的值修改为一个数X，c的值也设置为X，那么就可以通过检验了！同时因为c要尽可能的小，0x60 - 0x7f的值要尽可能小

      3. 让我们开始操作：输入的a、b、c必须是素数，a是存入内存的位置，并且操作的大小为32字节，那么能操作到 “零“值的a范围是：( 0x60-0x20, 0x7f ]，也就是( 0x40, 0x7f ]，其中可用的素数为43,47,47,4f,53,59,61,65,67,6b,6d,71,7f。同时设置的值b是32字节的低位，如图，比如用操作内存0x61的位置，那么在0x80那一段就会多出来一部分，b从蓝色部分开始往前开始存储。从图里面可用看出，如果a太小，就会是覆盖方式1，这就会操作 “零”值特别大，也就是c要特别大，不行；如果a太大，就会是覆盖方式2，这样就需要b要特别大才能触碰到0x60~0x7f的位置修改 ”零“值。因此，a和b的值要选择好，不大也不小

      4. 最终，我们选择了这样一个值：a=0x61，b=0x0101。此时内存中的结果为如下。这样，我们就做到了a为0x61, b为0x0101，c为0x01，都不大，都为素数

        1
        2
        [0x60~0x7f]	0000000000000000000000000000000000000000000000000000000000000001 
        [0x80~0x9f]	0100000000000000000000000000000000000000000000000000000000000000

因此，此时输入的solve()函数选择器 + msg.data暂时为如下：

1
2
3
4
890d6908 // 函数选择器
0000000000000000000000000000000000000000000000000000000000000061 // 00
0000000000000000000000000000000000000000000000000000000000000101 // 20
0000000000000000000000000000000000000000000000000000000000000001 // 40

2.4stage4

1
2
3
4
5
6
function stage4(bytes memory a, bytes memory b) external {
    address addr;
    assembly { addr := create(0, add(a, 0x20), mload(a)) }
    (bool success, ) = addr.staticcall(b);
    require(tx.origin == address(uint160(uint256(addr.codehash))) && success);
}
  • 分析代码
    • assembly { addr := create(0, add(a, 0x20), mload(a)) }：输入a作为bytecode来创建一个合约
    • (bool success, ) = addr.staticcall(b);：将b输入到该合约，结合下一行代码可知必须执行成功
    • require(tx.origin == address(uint160(uint256(addr.codehash))) && success);：输入该合约的bytecode经过哈希之后，要等于调用此方法的EOA账户。由此可知，我们部署的bytecode也就是a，必须是消息调用者的公钥，因为公钥经过hash之后才会等于tx.origin地址。但是由于上一步staticcall()，他会执行runtimecode，如果我们无法控制runtimecode，就会乱执行，很可能调用失败，所以对bytecode要一定要求。有一个很好的想法，我们可以选择00开头的runtimecode，因为00是STOP的操作码，执行了就成功执行并退出了，那么我们的bytecode（也就是initCode）的工作就是返回这个符合要求的runtimecode
    • 所以我们需要做的就是生成一个EOA账户，其公钥是00开头，一个合适的bytecode，然后用这个账户进行调用该方法

我们用下面的代码可以生成我们想要的EOA账户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import random
from Crypto.Util.number import isPrime
from ecdsa import ecdsa

g = ecdsa.generator_secp256k1

while True:
    private_key = random.randint(0, 1 << 256 - 1)
    public_key = private_key * g
    x = str(hex(public_key.x())[2:])
    x = ("00" * 32 + x)[-32 * 2:]
    y = str(hex(public_key.y())[2:])
    y = ("00" * 32 + y)[-32 * 2:]
    public_key_hex = x + y
    if public_key_hex[:2] == "00":
        print("private_key",private_key)
        print("public_key_hex",public_key_hex)
        break

然后我执行的结果为：

1
2
private_key 53696799650805905702178748833560284763518490362681353450771033938641345485772
public_key_hex 00c71a98df7527e420247f8e4baa7a5e8c66108c63107c3d1c9a4cf49574cffc4f37e410c847198bafb557e5fe8ba61fa1b61a55724ebac021acf438a3961cf5

最后，我们就可以构造bytecode了，作用是将我们的公钥返回，思路大概如下。

1
2
3
4
5
6
7
PUSH1 0x40              6040
DUP1                    80
PUSH1 0x0b              600B
PUSH1 0x0               6000
CODECOPY                39
PUSH1 0                 6000
RETURN                  f3

得到604080600B6000396000f3，然后拼接我们的公钥，最终bytecode为：

1
604080600B6000396000f300c71a98df7527e420247f8e4baa7a5e8c66108c63107c3d1c9a4cf49574cffc4f37e410c847198bafb557e5fe8ba61fa1b61a55724ebac021acf438a3961cf5

让我们看回我们构造的msg.data，意思是会到内存61的位置选取32字节的内容作为数据长度，然后再获取这个长度的实际数据，由于这个位置也需要是一个合适的素数，因此我们将其[ // 60 ]设置为1，那么选取32字节的数据长度就是0x100，也就是256字节

1
2
3
4
5
6
890d6908 // 函数选择器
0000000000000000000000000000000000000000000000000000000000000061 // 00
0000000000000000000000000000000000000000000000000000000000000101 // 20
0000000000000000000000000000000000000000000000000000000000000001 // 40
0000000000000000000000000000000000000000000000000000000000000001 // 60
00

然后拼接我们的bytecode，因为要256字节，所以后面补0即可。因此，此时输入的solve()函数选择器 + msg.data暂时为如下：

1
2
3
4
5
6
7
8
9
10
890d6908 // 函数选择器
0000000000000000000000000000000000000000000000000000000000000061 // 00
0000000000000000000000000000000000000000000000000000000000000101 // 20
0000000000000000000000000000000000000000000000000000000000000001 // 40
0000000000000000000000000000000000000000000000000000000000000001 // 60
00
// bytecode
604080600B6000396000f300c71a98df7527e420247f8e4baa7a5e8c66108c63107c3d1c9a4cf49574cffc4f37e410c847198bafb557e5fe8ba61fa1b61a55724ebac021acf438a3961cf5
// 补0
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

2.5stage5

1
2
3
4
5
6
function stage5() external {
       if (msg.sender != address(this)) {
           (bool success,) = address(this).call(abi.encodePacked(this.solve.selector, msg.data[4:]));
           require(!success);
       }
   }

意思是会回调当前合约的solve函数，但要返回失败，即：第一遍成功，第二遍失败。由于只能在本合约中操作，无法通过我们自己的合约进行控制，那么我们只可以用gas限制这个土方法，那么需要寻找一个合适的gas。同时，我们的solve()函数选择器 + msg.data就已经确定下来了，就是stage4的那个，此stage5只是要找一个合适的gas，不会影响我们的calldata。

我们可以在执行前后看看花了多少gas

1
2
3
4
5
6
7
8
9
10
11
12
function test_isSolved() public{
    console.log(lockbox2.locked());
    // 用私钥选择msg.sender
    vm.startBroadcast(53696799650805905702178748833560284763518490362681353450771033938641345485772);
    
    console.log(gasleft());    
    address(lockbox2).call(hex"890d6908000000000000000000000000000000000000000000000000000000000000006100000000000000000000000000000000000000000000000000000000000001010000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000100604080600B6000396000f300c71a98df7527e420247f8e4baa7a5e8c66108c63107c3d1c9a4cf49574cffc4f37e410c847198bafb557e5fe8ba61fa1b61a55724ebac021acf438a3961cf500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
    console.log(gasleft());  
    console.log(lockbox2.locked());
    vm.stopBroadcast();
    assertEq(level.isSolved(),true);
}

得到结果，相减得到差值，知道花了315585

1
9223372036854741483 - 9223372036854425898 = 315585

那么接下来爆破，我们操作这个最多花315585，并且选取一个gas否则我怕第一次调用solve()都不成功，200000试试看，当然更小可以，只是爆破时间更长：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function test_isSolved() public{
    console.log(lockbox2.locked());
    // 用私钥选择msg.sender
    vm.startBroadcast(53696799650805905702178748833560284763518490362681353450771033938641345485772);
    for(uint i = 200000; i <= 315585;i++){
        address(lockbox2).call{gas:i}(hex"890d6908000000000000000000000000000000000000000000000000000000000000006100000000000000000000000000000000000000000000000000000000000001010000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000100604080600B6000396000f300c71a98df7527e420247f8e4baa7a5e8c66108c63107c3d1c9a4cf49574cffc4f37e410c847198bafb557e5fe8ba61fa1b61a55724ebac021acf438a3961cf500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");

        if(lockbox2.locked()== false){
            emit log_uint(i);
            break;
        }

    }
    console.log(lockbox2.locked());
    vm.stopBroadcast();
}

爆破出结果：289126

1
2
3
4
5
6
7
8
9
10
function test_isSolved() public{
    console.log(lockbox2.locked());
    // 用私钥选择msg.sender
    vm.startBroadcast(53696799650805905702178748833560284763518490362681353450771033938641345485772);
    
    address(lockbox2).call{gas:289126}(hex"890d6908000000000000000000000000000000000000000000000000000000000000006100000000000000000000000000000000000000000000000000000000000001010000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000100604080600B6000396000f300c71a98df7527e420247f8e4baa7a5e8c66108c63107c3d1c9a4cf49574cffc4f37e410c847198bafb557e5fe8ba61fa1b61a55724ebac021acf438a3961cf500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
    console.log(lockbox2.locked());
    vm.stopBroadcast();
    assertEq(level.isSolved(),true);
}

完成

解题

calldata

1
890d6908000000000000000000000000000000000000000000000000000000000000006100000000000000000000000000000000000000000000000000000000000001010000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000100604080600B6000396000f300c71a98df7527e420247f8e4baa7a5e8c66108c63107c3d1c9a4cf49574cffc4f37e410c847198bafb557e5fe8ba61fa1b61a55724ebac021acf438a3961cf500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
pragma solidity >=0.5.0;

import "forge-std/Test.sol";
import "../src/Setup.sol";

contract lockbox2Test is Test{

    Setup level;
    Lockbox2 lockbox2;

    function setUp() public {
        level = new Setup();
        lockbox2 = level.lockbox2();
    }

    // function test_isSolved() public{
    //     console.log(lockbox2.locked());
    //     // 用私钥选择msg.sender
    //     vm.startBroadcast(53696799650805905702178748833560284763518490362681353450771033938641345485772);
    //     for(uint i = 200000; i <= 315585;i++){
    //         address(lockbox2).call{gas:i}(hex"890d6908000000000000000000000000000000000000000000000000000000000000006100000000000000000000000000000000000000000000000000000000000001010000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000100604080600B6000396000f300c71a98df7527e420247f8e4baa7a5e8c66108c63107c3d1c9a4cf49574cffc4f37e410c847198bafb557e5fe8ba61fa1b61a55724ebac021acf438a3961cf500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");

    //         if(lockbox2.locked()== false){
    //             emit log_uint(i);
    //             break;
    //         }

    //     }
    //     console.log(lockbox2.locked());
    //     vm.stopBroadcast();
    // }

    function test_isSolved() public{
        console.log(lockbox2.locked());
        // 用私钥选择msg.sender
        vm.startBroadcast(53696799650805905702178748833560284763518490362681353450771033938641345485772);
        
        address(lockbox2).call{gas:289126}(hex"890d6908000000000000000000000000000000000000000000000000000000000000006100000000000000000000000000000000000000000000000000000000000001010000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000100604080600B6000396000f300c71a98df7527e420247f8e4baa7a5e8c66108c63107c3d1c9a4cf49574cffc4f37e410c847198bafb557e5fe8ba61fa1b61a55724ebac021acf438a3961cf500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
        console.log(lockbox2.locked());
        vm.stopBroadcast();
        assertEq(level.isSolved(),true);
    }


}
Prev
2023-09-18 11:09:48 # 14.Paradigm CTF 2022
Next