QuillCTF: 6. Collatz Puzzle

Objective of CTF:

Make a successful call to the ctf function.
You should be the deployer of the contract at the given addr parameter!

Target contract:

// 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 ctf(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;
  }
}

Solution

The important part here is obviously is the code size constraint. Writing a contract would incur a huge code size, so we have to dive hands-dirty into EVM level. We want to implement a function with the signature collatzIteration(uint256) in which a Collatz iteration takes place.

Runtime Code

We don't need to care about the function signature actually, we can just ignore the selector bytes, and do the process on whatever argument we get! This will save some bytes. First, let us write our runtime code that handles the Collatz iteration logic:

Code Size	Section	Instruction	Stack	Explanation
`0x02`	`entry` ⚪	`PUSH1 0x04`	`0x4`	skip 4-byte selector
`0x03`	`entry` ⚪	`CALLDATALOAD`	`n`	load argument from calldata
`0x04`	`entry` ⚪	`DUP1`	`n n`	duplicate `n`
`0x06`	`entry` ⚪	`PUSH1 0x01`	`0x1 n n`	check parity by AND'ing with 1
`0x07`	`entry` ⚪	`AND`	`i n`	get the last bit `i = 0x1 & n`
`0x09`	`entry` ⚪	`PUSH1 0x13`	`0x13 i n`	push destination to `odd`
`0x0A`	`entry` ⚪	`JUMPI`	`n`	conditional jump to `odd`
`0x0C`	`even` 🟢	`PUSH1 0x1`	`0x1 n`	add `1` to shift once
`0x0D`	`even` 🟢	`SHR`	`m`	find `n/2`, as shifting right once divides by 2. denote as `m`
`0x0F`	`even` 🟢	`PUSH1 0x17`	`0x17 m`	push destination to `return`
`0x10`	`even` 🟢	`JUMP`	`m`	go to `return`
`0x11`	`odd` 🔵	`JUMPDEST`	`n`	destination for `odd` subroutine
`0x13`	`odd` 🔵	`PUSH1 0x3`	`0x3 n`	push 3 for multiplication
`0x14`	`odd` 🔵	`MUL`	`3n`	find `3n`
`0x16`	`odd` 🔵	`PUSH1 0x1`	`0x1 3n`	push 1 for addition
`0x17`	`odd` 🔵	`ADD`	`m`	find `3n+1`, denote as `m`
`0x18`	`return` ⚫	`JUMPDEST`	`m`	destination for `return` subroutine
`0x1A`	`return` ⚫	`PUSH1 0x80`	`0x80 m`	push `0x80`, the first free memory slot
`0x1B`	`return` ⚫	`MSTORE`	`-`	store the result at `0x80` in memory
`0x1D`	`return` ⚫	`PUSH1 0x20`	`0x20`	to return an `uint256`, we need 32 bytes
`0x1F`	`return` ⚫	`PUSH1 0x80`	`0x80 0x20`	position to return the data in memory
`0x20`	`return` ⚫	`RETURN`	`-`	returns 32 bytes from `0x80` in memory

We have given section names and colors to make it more clear how the code is structured. The entry section simply retrieves the input argument (32-byte argument, ignoring the 4-byte function selector). Then, we do bitwise-AND operation on the input number with 1, which will return the last bit. If the last bit is 0, the number is even; 1 otherwise. The conditional jump activates when the top of the stack is non-zero, so it will only JUMP to the odd section if the number is odd. The even and odd sections do the n/2 and 3n+1 operations respectively. Also note that there is an additional jump at the end even section, to go directly to the return section.

Here is the code in copy-paste-friendly format:

// entry
PUSH1 0x04
CALLDATALOAD
DUP1
PUSH1 0x01
AND
PUSH1 0x10
JUMPI // ═════════════════╗
                       // ║
// even                // ║
PUSH1 0x01             // ║
SHR                    // ║
PUSH1 0x17             // ║
JUMP // ════════════╗     ║
                 // ║     ║
// odd           // ║     ║
JUMPDEST // <═══════║═════╝
PUSH1 0x3        // ║
MUL              // ║
PUSH1 0x1        // ║
ADD              // ║
                 // ║
// return        // ║
JUMPDEST // <═══════╝
PUSH1 0x80
MSTORE
PUSH1 0x20
PUSH1 0x80
RETURN

You can copy-paste the code above to play around with it at https://www.evm.codes/playground. Try calling with 0x112233440000000000000000000000000000000000000000000000000000000000000003. This inputs means n = 3 and the returned value will be a 32-byte value 3*3+1 = 10 = 0x000..00A. The bytecode for this code is 0x6004358060011660105760011c6017565b6003026001015b60805260206080f3 (you can retrieve this from the playground link above) and it is exactly 32 bytes! This is just enough to match our constraint of 0 < codeSize <= 32.

Initialization Code

Now we can write the initialization code, which is tasked with copying the runtime code above into the memory. It will do so via CODECOPY instruction, and must later return the code from memory. The instructions are as follows:

Code Size	Section	Instruction	Stack	Explanation
`0x02`	`init` 🔴	`PUSH1 0x20`	`0x20`	runtime code is `32 = 0x20` bytes
`0x04`	`init` 🔴	`PUSH1 0x0C`	`0x0C 0x20`	runtime code starts at `12 = 0x0C`
`0x06`	`init` 🔴	`PUSH1 0x00`	`0x00 0x0C 0x20`	runtime code should be written to slot 0
`0x07`	`init` 🔴	`CODECOPY`	`-`	copy the runtime code from calldata to memory
`0x09`	`init` 🔴	`PUSH1 0x20`	`0x20`	runtime code is `32 = 0x20` bytes
`0x0b`	`init` 🔴	`PUSH1 0x00`	`0x00 0x20`	runtime code is written to slot 0
`0x0c`	`init` 🔴	`RETURN`	`-`	32-bytes are returned from the memory

Again, in copy-paste friendly format:

PUSH1 0x20 // 32 bytes
PUSH1 0x0C // position in bytecode of the runtime code
PUSH1 0x00 // write to memory position 0
CODECOPY   // copy the bytecode
PUSH1 0x20 // 32 bytes
PUSH1 0x00 // read from memory position 0
RETURN     // returns the code copied above

The bytecode is 0x6020600c60003960206000f3. This will deploy the runtime code above to the chain.

Deployment & Testing

The Hardhat test code to demonstrate this attack is given below. Contract types are generated via TypeChain.

describe('Custom: Collatz Puzzle', () => {
  let contract: CollatzPuzzle;
  let owner: SignerWithAddress;

  const initializationCode = '6020600c60003960206000f3';
  const runtimeCode = '6004358060011660105760011c6017565b6003026001015b60805260206080f3';

  before(async () => {
    [owner] = await ethers.getSigners();
    contract = await ethers.getContractFactory('CollatzPuzzle', owner).then(f => f.deploy());
    await contract.deployed();
  });

  it('should call `ctf` successfully', async () => {
    // deploy your contract
    const tx = await owner.sendTransaction({
      to: undefined, // contract creation
      data: '0x' + initializationCode + runtimeCode,
    });
    const receipt = await tx.wait();

    // get address from receipt
    const addr = receipt.contractAddress;
    expect(addr).to.be.properAddress;

    // run the ctf function
    expect(await contract.ctf(addr)).to.be.true;
  });
});

Fun fact: I was the author of this puzzle!

Blog

QuillCTF: 6. Collatz Puzzle

Erhan Tezcan

Solution

Runtime Code

Initialization Code

Deployment & Testing

Join Our Newsletter. No Spam, Only the good stuff.

Related