https://github.com/minaminao/tokyo-payload
"minaminao" made a very interesting and hard blockchain challenge of which length is short in SECCON CTF 2023 Quals.
I felt like solving pwnable because I had to chain the payload like ROP.
I wasted a lot of time and effort during/after the competition and the reason was very trivial.
That was the difference of bytecode between my local and the server environment.
I used Remix IDE which provides CLI and has a default compiler option of "no optimize, --evm-version shanghai".
However, "forge build" of the server environment has "--optimize" and "--evm-version paris".
I rewrote my payload four times until I found out this and recognized that the bytecode was different after seeing the excessive transaction gas usage.
I think everyone who solves this problem has a different payload.
My payload is complicated and long, so I recommend you look at other payloads.
Background
Through this challenge, I learned so much interesting something about EVM and Solidity.
Let's assume that optimization is not applied.
EVM is a state machine using Stack, Memory, PC, etc.
When we call a function, we pass function arguments and return value through the stack and memory.
https://www.evm.codes/?fork=shanghai
Calling a function within the contract means that we move Program Counter to staring point of the corresponding function opcode via JUMP.
Only JUMPDEST is allowed as the destination of JUMP, otherwise it reverts.
We can find the destnation index through deployed bytecode.
The caller should push JUMPDEST to return, JUMPDEST to go, and arguments to the stack.
The callee should clean the space they used. e.g. If they received some arguments from the caller, they should pop them.
without argument
function fun1() public {
fun2();
}
function fun2() public {
}tag 4 function fun1() public {\r\n ...
JUMPDEST function fun1() public {\r\n ...
PUSH [tag] 7 function fun1() public {\r\n ...
PUSH [tag] 8 function fun1() public {\r\n ...
JUMP function fun1() public {\r\n ...
tag 7 function fun1() public {\r\n ...
JUMPDEST function fun1() public {\r\n ...
STOP function fun1() public {\r\n ...
tag 8 function fun1() public {\r\n ...
JUMPDEST function fun2() public {\r\n ...
JUMP
PC => JUMP
stack[0] = destination addr
stack[1] = return addr
...
with arguments
function fun1() public {
fun2(0x8, 0x9);
}
function fun2(uint a, uint b) public {
}tag 6 function fun1() public {\r\n ...
JUMPDEST function fun1() public {\r\n ...
PUSH [tag] 12 fun2(0x8, 0x9)
PUSH 8 0x8
PUSH 9 0x9
PUSH [tag] 10 fun2
JUMP fun2(0x8, 0x9)
tag 12 fun2(0x8, 0x9)
JUMPDEST fun2(0x8, 0x9)
JUMP function fun1() public {\r\n ...
tag 10 function fun2(uint a, uint b) ...
JUMPDEST function fun2(uint a, uint b) ...
POP function fun2(uint a, uint b) ...
POP function fun2(uint a, uint b) ...
JUMP function fun2(uint a, uint b) ...PC => JUMP
stack[0] = destination addr
stack[1] = arg0
stack[2] = arg1
stack[3] = return addr
...
without return
function fun1() public {
fun2();
}
function fun2() public {
}tag 4 function fun1() public {\r\n ...
JUMPDEST function fun1() public {\r\n ...
PUSH [tag] 7 function fun1() public {\r\n ...
PUSH [tag] 8 function fun1() public {\r\n ...
JUMP function fun1() public {\r\n ...
tag 7 function fun1() public {\r\n ...
JUMPDEST function fun1() public {\r\n ...
STOP function fun1() public {\r\n ...
tag 6 function fun2() public {\r\n ...
JUMPDEST function fun2() public {\r\n ...
JUMP function fun2() public {\r\n ...
tag 8 function fun1() public {\r\n ...
JUMPDEST function fun1() public {\r\n ...
PUSH [tag] 11 fun2()
PUSH [tag] 6 fun2
JUMP fun2()
tag 11 fun2()
JUMPDEST fun2()
JUMP function fun1() public {\r\n ...PC = JUMP
stack[0] = ret addr
...
with return
function fun1() public {
fun2();
}
function fun2() public returns(uint, uint) {
return (0x8, 0x9)
}tag 4 function fun1() public {\r\n ...
JUMPDEST function fun1() public {\r\n ...
PUSH [tag] 9 function fun1() public {\r\n ...
PUSH [tag] 10 function fun1() public {\r\n ...
JUMP function fun1() public {\r\n ...
tag 9 function fun1() public {\r\n ...
JUMPDEST function fun1() public {\r\n ...
STOP function fun1() public {\r\n ...
tag 6 function fun2() public returns...
JUMPDEST function fun2() public returns...
PUSH 0 uint
DUP1 uint
PUSH 8 0x8
PUSH 9 0x9
SWAP2 return (0x8, 0x9)
POP return (0x8, 0x9)
SWAP2 return (0x8, 0x9)
POP return (0x8, 0x9)
SWAP1 function fun2() public returns...
SWAP2 function fun2() public returns...
JUMP function fun2() public returns...
tag 10 function fun1() public {\r\n ...
JUMPDEST function fun1() public {\r\n ...
PUSH [tag] 13 fun2()
PUSH [tag] 6 fun2
JUMP fun2()
tag 13 fun2()
JUMPDEST fun2()
POP fun2()
POP fun2()
JUMP function fun1() public {\r\n ...
PC = JUMP
stack[0] = ret addr
stack[1] = ret1
stack[2] = ret0
...
+ if the caller does not receive return values, they will be popped.
array layout
storage
dynamic array:
storage[slot] = length
arr[i] = sha3(i, slot)
fixed array:
arr[i] = slot + i
memory
dynamic array:
mem[ptr] = length
arr[i] = ptr + 1 + i
fixed array
arr[i] = ptr + i
memory layout
https://docs.soliditylang.org/en/latest/internals/layout_in_memory.html
[0x00: 0x40]: scratch space
[0x40: 0x60]: currently allocated memory size
[0x60: 0x80]: zero slot
The zero slot is used as initial value for dynamic memory arrays and should never be written to (the free memory pointer points to 0x80 initially).
tokyoPayload():: function()[] memory funcs;
resetGasLimit():: uint256[] memory arr;
Since dynamic memory arrays are used without allocation, zero-slot(0x60) represents them.
Analysis
A user must set solved as true, but it seems that there is no functionality to change slot 0 inside TokyoPayload.
We can easily come up with the idea of calling a logic contract that turns slot 0 into true through delegatecall().
Unfortunately, delegatecall() has two constraints, one of which is checking for msg.sender and the other is gas option.
It is natural that we cannot find the private key whose public key is 0xCAFE.
So we need a method of bypass for require statement.
Assuming we bypass require statement, we need to increase gasLimit by at least 20000 because sstore opcode consumes 20000 gas.
As the name of resetGasLimit() shows, it resets gasLimit.
In resetGasLimit(), uint256[] memory arr is declared as a dynamic array but it is not allocated, resulting arr.length is zero
As I mentioned above, not-allocated dynamic array is represented by zero slot that occupies memory [0x60:0x80).
If we change zero slot, we can control gasLimit.
tokyoPayload() provides a user with the chance to overwrite memory using calldatacopy.
If we call resetGasLimit() continuously before tokyoPayload() finishes its procedure, the memory is retained.
Additionally, it has a function pointer array and calls one of those, allowing us to chain calling function!!
We are aware that calling functions is equal to jumping to JUMPDEST within the deployed bytecode.
In the solidity code, if-else, require statement, calling functions create a branch, meaning that the code that is not the entry point of the function can be JUMPDEST.
For example, delegatecall() opcode follows as:
We can easily bypass require statement through tag 50.
To summarize, we must
1. control memory[0x60:0x80) using calldatacopy
2. bypass the require statement using JUMP
the calldata of tokyoPayload() consists of
function signature=hex'000040c3'(4-byte) + x(32-byte) + y(32-byte) + additonal data(length we want)
Maybe everyone's solution is different from here.
I chose x as 0x7b, which makes memory[0x60:0x80) = 0x40c300.
Then 0x40c300 && 0xffff = 0xc300 is more than 20000, gas is enough to use sstore opcode.
At this point, we note that the range of x should be [0x40: 0x79].
Before funcs[z]() is called, array boundary check exists.
Since funcs is not allocated, it compares the value stored at zero slot with the index called.
PUSH 60 function()[] memory funcs
PUSH 0 uint256 z
DUP3 y
SWAP1 uint256 z = y
POP uint256 z = y
PUSH [tag] 43 funcs[z]()
DUP3 funcs
DUP3 z
DUP2 funcs[z]
MLOAD funcs[z]
DUP2 funcs[z]
LT funcs[z]
By the way, we don't need to care about that because zero slot has 0xc300.
Which JUMPDEST should we choose?
1. tokyoPayload(x, y)
2. load(i)
3. createArray(length)
4. resetGasLimit()
5. delegatecall(addr)
When we encounter JUMP opcode, stack follows as:
stack[0] => next JUMPDEST
stack[1] => ret addr => finish this call of tokyoPayload()
stack[2] => z
stack[3] => funcs zero slot: 0x60
stack[4] => y
stack[5] => x
stack[6] => 0x97 => stop opcode
stack[7] => tokyoPayload function signature
As we learned above Background, the function's arguments are passed through stack.
If next function has
1. no argument
there is no change due to the type of funcs
stack[0] => next JUMPDEST
stack[1] => ret addr
stack[2] => z
stack[3] => funcs zero slot: 0x60
stack[4] => y
stack[5] => x
stack[6] => 0x97 => stop opcode
stack[7] => tokyoPayload function signature
2. one argument
stack[0] => next JUMPDEST
stack[1] => ret addr => next function's argument
stack[2] => z => ret addr
stack[3] => funcs zero slot: 0x60
stack[4] => y
stack[5] => x
stack[6] => 0x97 => stop opcode
stack[7] => tokyoPayload function signature
3. two arguments
stack[0] => next JUMPDEST
stack[1] => ret addr => next function's second argument
stack[2] => z => next function's first argument
stack[3] => funcs zero slot: 0x60 => ret addr
stack[4] => y
stack[5] => x
stack[6] => 0x97 => stop opcode
stack[7] => tokyoPayload function signature
In order to control execution flow, I must choose one argument case.
As a result, we will call sequentially tokyoPayload() -> funcs[z]() -> z().
stack[0] => next JUMPDEST => first call
stack[1] => ret addr => first function's argument
stack[2] => z => first ret addr => second call
stack[3] => funcs zero slot: 0x60
stack[4] => y
stack[5] => x
stack[6] => 0x97 => stop opcode
stack[7] => tokyoPayload function signature
It would be better to look at load() for pushing some values we want to the stack.
Having three return values is identical to pushing three values into the stack.
if the first call is load()
step i)
stack[0] => next JUMPDEST => first call => load()
stack[1] => ret addr => first call's argument => i
stack[2] => z => first ret addr => second call
stack[3] => funcs zero slot: 0x60
stack[4] => y
stack[5] => x
stack[6] => 0x97 => stop opcode
stack[7] => tokyoPayload function signature
step ii)
stack[0] => z => first ret addr => second call
stack[1] => c => third return value => second call's argument
stack[2] => b => second return value => third call
stack[3] => a => first return value
stack[4] => funcs zero slot: 0x60
stack[5] => y
stack[6] => x
stack[7] => 0x97 => stop opcode
stack[8] => tokyoPayload function signature
Test.sol
https://gist.github.com/kangsangsoo/fdbdb2815ffa6288e513ad4edd3b4278
payload.py
https://gist.github.com/kangsangsoo/d93036176b74d0e6898c0d3c3ca8ea29
I noted that load(i)'s third return value remains, allowing me to use it as any function argument.
So my idea is that I repeat this and then chain those like load() -> load() -> ... -> func1 -> func2 -> func3 => solved!!
Actually, func1, func2, and func3 are determined above.
func1 => resetGasLimit()
func2 => delegatecall(addr)
We will set load()'s third value in detail. Now we just set a value for easy identification in the debugger.
Due to optimize option, we have to take a look at resetGasLimit() opcodes.
resetGasLimit() could be called from two places:
i. just call resetGasLimit()
ii. inside tokyoPayload()
They have different opcodes at the end.
i) case cannot be used in our payload because it has a STOP opcode.
tag 5 function resetGasLimit() publi...
JUMPDEST function resetGasLimit() publi...
PUSH [tag] 11 function resetGasLimit() publi...
PUSH 60 uint256[] memory arr
MLOAD arr.length
PUSH 1 gasLimit
SSTORE gasLimit = arr.length
JUMP function resetGasLimit() publi...
tag 11 function tokyoPayload(uint256 ...
JUMPDEST function tokyoPayload(uint256 ...
STOP function tokyoPayload(uint256 ...
We have no choice but to go to ii).
As we know, tokyoPayload() would make the stack:
stack[0] => next JUMPDEST
stack[1] => ret addr => finish this call of tokyoPayload()
stack[2] => z
stack[3] => funcs zero slot: 0x60
stack[4] => y
stack[5] => x
...
some value I pushed
...
stack[?] => 0x97 => stop opcode
stack[?] => tokyoPayload function signature
That means scenario ii) spoils stack[0:5] to be used for chaining.
As we think of ROP, pop-pop-pop-pop-ret gadget also exists in deployed bytecode?
The answer is yes.
tag 43 funcs[z]()
JUMPDEST funcs[z]()
POP {\n require(x >= 0x40);...
POP {\n require(x >= 0x40);...
POP function tokyoPayload(uint256 ...
POP function tokyoPayload(uint256 ...
JUMP function tokyoPayload(uint256 ...
Thanks to pop4-ret gadget
stack[0] => next JUMPDEST => p4-ret gadget
stack[1] => ret addr => will be popped
stack[2] => z => will be popped
stack[3] => funcs zero slot: 0x60 => will be popped
stack[4] => y => will be popped
stack[5] => x => next call! => delegatecall()
...
some value I pushed
...
stack[?] => 0x97 => stop opcode
stack[?] => tokyoPayload function signature
PoC
Test.sol
https://gist.github.com/kangsangsoo/58bb7322d958323793f11e795a1139b0
payload.py
https://gist.github.com/kangsangsoo/3da37c9c95053436e74da8a9f98dfcfe
0x1a3 is JUMPDEST bypassing require statement within delegatecall(addr)
0xcccc..cc would be logic contract address.
0xbbb.bbb would be delegatecall(addr) return address.
To finish this chaining, I put JUMPDEST which has STOP opcode.
In fact, 0xaaa..aaa was unnecessary so I could have reduced the number of calling load().
In conclusion, we went through the following flow:
tokyoPayload -> load -> load -> load -> resetGasLimit -> POP4-RET -> delegatecall -> STOP
Solve
solve.sol
https://gist.github.com/kangsangsoo/b8ddc278c2ec33db4eb27d7238a17bab
payload.py
https://gist.github.com/kangsangsoo/052286df7061cbdc62793cd32c9b4ac0
'writeups' 카테고리의 다른 글
| GlacierCTF 2023 - smartcontract (0) | 2023.11.26 |
|---|---|
| N1CTF 2023 - blockchain(pool by sec3) (0) | 2023.10.23 |
| whitehat 2023 - blockchain (0) | 2023.09.19 |
| SekaiCTF 2023 - Blockchain(The Bidding, Play for Free, Re-Remix) (0) | 2023.08.28 |
| flashbot mev-share ctf (0) | 2023.08.08 |