07.Lockbox2
2023-07-26 18:43:30 # 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);
}


}