Collatz Puzzle is a Solidity CTF challenge from QuillCTF.
Solution
In this contract, there is only 1 solidity file. CollatzPuzzle.sol. Contract is not deployed on any test network.
Objective of CTF is
Make a successful call to the callMe function.
You should be the deployer of the contract at the given addr parameter!
To solve this question we have to call callMe() function with an address parameter and that address should belong to a solidity contract. There are 2 conditions in that callMe function. First one is size of the contract should be between 0 and 32 and in each loop it should pass the require(p == q, "result mismatch!"); statement.
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
interface ICollatz {
function collatzIteration(uint256 n) external pure returns (uint256);
}
contract CollatzPuzzle is ICollatz {
function collatzIteration(uint256 n) public pure override returns (uint256) {
if (n % 2 == 0) {
return n / 2;
} else {
return 3 * n + 1;
}
}
function callMe(address addr) external view returns (bool) {
// check code size
uint256 size;
assembly {
size := extcodesize(addr)
}
require(size > 0 && size <= 32, "bad code size!");
// check results to be matching
uint p;
uint q;
for (uint256 n = 1; n < 200; n++) {
// local result
p = n;
for (uint256 i = 0; i < 5; i++) {
p = collatzIteration(p);
}
// your result
q = n;
for (uint256 i = 0; i < 5; i++) {
q = ICollatz(addr).collatzIteration{gas: 100}(q);
}
require(p == q, "result mismatch!");
}
return true;
}
}
Second require statement is easy to solve. We just need to implement a function named collatzIteration and it should return exactly the same as the original collatzIteration. If we try to write an attack contract which does the same thing in solidity it should pass the second require statement but it will fail on the first one.
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
contract AttackSolidity {
function collatzIteration(uint256 n) public pure returns (uint256 res) {
res = (n % 2 == 0) ? n / 2 : 3 * n + 1;
}
}
If we deploy it and check the size we will see
>>> attack_contract = AttackSolidity.deploy({'from': attacker})
Transaction sent: 0xd87a4af421a6b01027c5e79164478bfb5d5d864428ba33dc87a854ff2377cf84
Gas price: 0.0 gwei Gas limit: 12000000 Nonce: 1
AttackSolidity.constructor confirmed Block: 2 Gas used: 129109 (1.08%)
AttackSolidity deployed at: 0x602C71e4DAC47a042Ee7f46E0aee17F94A3bA0B6
TypeError: 'str' object is not callable
>>> test.testSize(attack_contract)
352
And the testSize function is
function testSize(address addr) public view returns(uint256 size){
// check code size
assembly {
size := extcodesize(addr)
}
}
So it is not possible to solve this question by writing pure solidity code. Instead, we can write a YUL code or direct OPCode. Yul (previously also called JULIA or IULIA) is an intermediate language that can be compiled to bytecode for different backends.
In .yul code we should write an assembly. Normal structure of YUL is like this
object "Contract" {
// This is the constructor code of the contract.
code {
// Deploy the contract
datacopy(0, dataoffset("runtime"), datasize("runtime"))
return(0, datasize("runtime"))
}
object "runtime" {
code {
// Protection against sending Ether
if gt(callvalue(), 0) {
revert(0, 0)
}
// Dispatcher
switch selector()
case 0x6d4ce63c {
returnUint(get())
}
case 0x371303c0 {
inc()
}
case 0xb3bcfa82 {
dec()
}
default {
revert(0, 0)
}
// ABI
function get() -> counter {
counter := sload(counterSlot())
}
function inc() {
sstore(counterSlot(), add(get(), 1))
}
function dec() {
sstore(counterSlot(), sub(get(), 1))
}
// Helpers
function selector() -> s {
s := div(calldataload(0), 0x100000000000000000000000000000000000000000000000000000000)
}
function returnUint(v) {
mstore(0, v)
return(0, 0x20)
}
// Slots
function counterSlot() -> s { s := 0 }
}
}
}
This piece of code is taken from Evm Playground
So we can see that there is a object "ContractName" and that code returns the code under object "runtime" So we have to modify this object "runtime" it in a way that works for us. To do that we can check OPCODES FOR THE EVM.
01 ADD 3 a, b a + b (u)int256 addition modulo 2**256
02 MUL 5 a, b a * b (u)int256 multiplication modulo 2**256
04 DIV 5 a, b a // b uint256 division
06 MOD 5 a, b a % b uint256 modulus
15 ISZERO 3 a a == 0 (u)int256 iszero
35 CALLDATALOAD 3 idx msg.data[idx:idx+32] read word from msg data at index idx
52 MSTORE 3* ost, val . mem[ost:ost+32] := val write a word to memory
F3 RETURN 0* ost, len . return mem[ost:ost+len-1]
All of those opcodes will be enough for us to build our YUL code. Our algorithm is
take a parameter n. return n/2 if n is even, return 3n+1 if n is odd
So if x is our parameter, our algorithm will be like this
let res := add(mul(x,3),1)
if iszero(mod(x, 2)) {
res := div(x, 2)
}
like python:
res = 3*x+1
if x % 2 == 0:
res = x/2
That algorithm should be fine. We just need to take the given parameter and assign it to x and then we need to return x. For example from evm playground it can be seen that
function returnUint(v) {
mstore(0, v)
return(0, 0x20)
}
To return value x, we first store it and then return that offset. The mstore instruction takes two arguments: the first argument is the address in memory where the value should be stored, and the second argument is the value to be stored. The value is stored in a 256-bit word in memory. So if I write
mstore(0, res) it stores the value of res in memory at address 0. If I replace with 0x20 then the value of res will be stored at address 0x20 instead of 0.
So we can use the address we want.
For the return part we can write
let res := add(mul(x,3),1)
if iszero(mod(x, 2)) {
res := div(x, 2)
}
mstore(0x20, res)
return(0x20, 0x20)
And the second 0x20 in return specifies the length of res variable. Since its uint256 it is 32 bytes which is 0x20. We just need to get given parameter and assign it to x. calldataload instruction takes an offset as an argument and returns the value stored at that address. The first 4 bytes are special bytes for the function signature so if we take offset 0x4 we will be able to get our uint256 parameter. So the final code will be like this.
object "Attack" {
code {
datacopy(0, dataoffset("runtime"), datasize("runtime"))
return(0, datasize("runtime"))
}
object "runtime" {
code {
let x := calldataload(0x4)
let res := add(mul(x,3),1)
if iszero(mod(x, 2)) {
res := div(x, 2)
}
mstore(0x0, res)
return(0x0, 0x20)
}
}
}
POC
We can compile our yul contract with solc compiler.
> solc --strict-assembly .\collatz-puzzle\contracts\test.yul
======= collatz-puzzle/contracts/test.yul (EVM) =======
Pretty printed source:
object "Attack" {
code {
datacopy(0, dataoffset("runtime"), datasize("runtime"))
return(0, datasize("runtime"))
}
object "runtime" {
code {
let x := calldataload(0x4)
let res := add(mul(x, 3), 1)
if iszero(mod(x, 2)) { res := div(x, 2) }
mstore(0x20, res)
return(0x20, 0x20)
}
}
}
Binary representation:
6020600d60003960206000f3fe60043560016003820201600282066017576002820490505b80602052602080f3
So our binary representation is 6021600d60003960216000f3fe60043560016003820201600282066017576002820490505b8060005260206000f3 We can deploy this bytecode with the help of create function.
Solidity Attack Contract
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
contract Attack {
uint256 public global_size;
address public global_addr;
function deploy(bytes memory given_code) external returns(uint){
bytes memory code = given_code;
address addr;
uint size;
assembly{
addr := create(0, add(code, 0x20), mload(code))
size := extcodesize(addr)
}
global_addr = addr;
global_size = size;
}
}
Python Exploit Function
from brownie import *
from scripts.setup_general import console
def exploit():
admin = accounts[0]
attacker = accounts[1]
collatz = CollatzPuzzle.deploy({'from': admin})
attack_contract = Attack.deploy({'from': attacker})
new_data = bytes.fromhex('6020600d60003960206000f3fe60043560016003820201600282066017576002820490505b80602052602080f3')
console.yellow("Creating attack contract with compiled YUL binary code.")
attack_contract.deploy(new_data)
assert attack_contract.global_size() == 32
console.yellow("Calling -> collatz.callMe(attack_contract.global_addr(), {'from': attacker})")
val = collatz.callMe(attack_contract.global_addr(), {'from': attacker})
assert val == True
console.green("Return value of callMe: "+ str(val))
And the output is
>>> run('poc', 'exploit')
Running 'scripts\poc.py::exploit'...
Transaction sent: 0xf7b7a3ee3c3fa60d6cdc3db31b8f67f273ef3e3107978094854e0f100e2950f0
Gas price: 0.0 gwei Gas limit: 12000000 Nonce: 1
CollatzPuzzle.constructor confirmed Block: 4 Gas used: 243464 (2.03%)
CollatzPuzzle deployed at: 0x602C71e4DAC47a042Ee7f46E0aee17F94A3bA0B6
Transaction sent: 0x85b134eed594d6732e59b2324b2763f48ab27bbdc304101ca48d2c8107aa94ac
Gas price: 0.0 gwei Gas limit: 12000000 Nonce: 2
Attack.constructor confirmed Block: 5 Gas used: 289251 (2.41%)
Attack deployed at: 0xE92E591c9661fe380Bb0949D22d27432E9f5b7F6
- Creating attack contract with compiled YUL binary code.
Transaction sent: 0x1d39355b9959a7a1a4f1d3a08ec6213e84d26def90573a642ca97382d43bba97
Gas price: 0.0 gwei Gas limit: 12000000 Nonce: 3
Attack.deploy confirmed Block: 6 Gas used: 102772 (0.86%)
+ Calling -> collatz.callMe(attack_contract.global_addr(), {'from': attacker})
+ Return value of callMe: True