DEV Community

Erhan Tezcan
Erhan Tezcan

Posted on

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;
  }
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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;
  });
});
Enter fullscreen mode Exit fullscreen mode

Fun fact: I was the author of this puzzle!

Top comments (0)