Paradigm CTF - SWAP

这大概是整个Paradigm CTF中难度最大的一道题，因为它同时考察两方面的内容，既考察你对於DEFI生态的理解，也考察你对於ABI编码和Solidity函数中的内存的理解。难度超乎想象 :funeral_urn:

题目分析：

这道题目还是尝试着自己做一下会更有意思一些。

首先查看setup合约中，解答该题目的条件是

swap.totalValue() < value / 100;

而在setup的构造函数中，value的值为：

value = swap.totalValue();

也就是说，我们需要改变swap.totalValue的值，让其比初始值小一百倍。现在我们再看下StableSwap合约中的totalValue方法：

function totalValue() public view returns (uint) {
    uint value = 0;
    for (uint i = 0; i < underlying.length; i++) {
        value += scaleFrom(underlying[i], underlying[i].balanceOf(address(this)));
    }
    return value;
}

简单来讲，scaleFrom就是把所有的value都换算成18为小数的值，而totalValue就是把swap中所有的抵押品数量按照单位换算后加和在一起得到的总的值。

那么swap池子里总共有多少种抵押品呢？一共有4中，分别通过swap.addCollateral添加。addCollateral只允许owner添加，做法是把抵押品添加到一个列表里，然后再在一个map里更新一个address=>bool的键值对，表明该collateral已经添加到池子里了。

function addCollateral(ERC20Like collateral) public {
    require(msg.sender == owner, "addCollateral/not-owner");
    underlying.push(collateral);
    hasUnderlying[address(collateral)] = true;
}

然后构造函数再通过swap.mint(amounts)方式，按照underlying token的顺序批量将对应的underlying token转账到swap池子里。

从而使得swap池子计算totalValue的时候即为amounts[i]的总和。

思路整理：

这道题肯定是从swap合约入手，swap合约中有三个比较感兴趣的函数：mint，burn，swap。也就是说作为攻击者，首先mint一部分underlying token，然后要么让其铸造出更多的StableSwap Token给我，从而去burn更多的underlying Token， 要么是不去mint，而是直接swap出更多underlying Token给我即可。两种思路。典型看觉得mint可能性更大一点。

首先看一下mint函数，其思路如下：

function mint(uint[] amounts) nonReentrant returns(uint)
第一步：构造一个结构体MintVars，类似于compound中的函数使用结构体，用于存放中间变量
第二步：将当前的StableSwapToken的总量记录到结构体的totalSupply中
第三步：执行for循环，针对每一种抵押品，分别执行如下：
第四步：把当前抵押品的地址放入v.token中
第五步：把swap合约中mint前拥有的当前抵押品的数量记录到v.preBalance里，即打一个快照
第六步：把msg.sender中拥有的当前抵押品的数量记录到v.has中
第七步：如果amounts[i]>v.has，说明用户拥有的token数量太少，取较少的值
第八步：把用户的token转移到swap合约中
第九步：再打一个快照，拿到此时swap合约中token的数量
第十步：通过前后两个快照的计算，计算出用户存入的token数量
第十一步：将第一个快照前合约swap中拥有的token的数量按照小数点放大后加到totalBalanceNorm上
第十二步：将用户存入的token数量按照小数点放大后加到totalInNorm上
第十三步：如果此时还未开始铸币，则总的铸币数量为totalInNorm,即用户deposit的总数；如果此时已经铸币了，则总的铸币数量为用户的累计deposit数量除以此前swap池子中的总的balance数量乘以totalSupply，即按照比例分配
第十四步：更新supply的值，并给用户记账，即v.amountToMint

总的来看mint思路很清晰，感觉没毛病。所以也是这道题难的点所在。samczsun说这道题目的问题在于mint的参数uint[]是一个动态数组，存在于内存中，而且mint函数里，用到了一个结构体，mintVar，该结构体也在内存里。看是否能够让这两个结构体在内存中的位置发生碰撞，从而实现控制的目的。

uint[] memory amounts在内存的排布为：

<- 32 bytes ->
OOOOO....OOOOO //loc
LLLLL....LLLLL //len
DDDDD....DDDDD //amount[0]
DDDDD....DDDDD //amount[1]
DDDDD....DDDDD //amount[2]
DDDDD....DDDDD //amount[3]

理论上来讲，mint是会首先把amounts这个动态数组放在free pointer指的内存位置，然后根据amounts的长度更新freepointer，然后再把mintvars放在freepointer指的内存位置。

Solidity uses what is known as a linear memory allocator (or arena-based allocator). This just means that Solidity will allocate new memory linearly along the block of total available memory. To allocate a new chunk, Solidity reads the free-memory pointer stored at 0x40 to determine where the next free address is, and moves it forward to reflect the fact that a new chunk of memory was just allocated. Notice that there are no checks to ensure that the amount of memory requested is not excessively large. This means that if one was to allocate a specific amount of memory, then the free memory pointer may overflow and begin re-allocating in-use memory. In this case, two calls to the pseudo-malloc might return pointers which alias each other.

查看文档可以看到：

0x00 - 0x3f (64 bytes): scratch space for hashing methods 0x40 - 0x5f (32 bytes): currently allocated memory size (aka. free memory pointer) 0x60 - 0x7f (32 bytes): zero slot - The zero slot is used as initial value for dynamic memory arrays and should never be written to (the free memory pointer points to 0x80 initially).

即使是bytes1[]数组，在内存中也是每个元素占据32bytes，如果是storage的化，这个bytes1会紧密排在一起。

为了保证碰撞，这里我们再看一下MintVars这一个结构体在内存中的排布：

struct MintVars {
<- 32 bytes ->
DDDDD....DDDDD    uint totalSupply;  
DDDDD....DDDDD    uint totalBalanceNorm;
DDDDD....DDDDD    uint totalInNorm;
DDDDD....DDDDD    uint amountToMint; => uint(-1)
DDDDD....DDDDD    ERC20Like token; //address
DDDDD....DDDDD    uint has;
DDDDD....DDDDD    uint preBalance;
DDDDD....DDDDD    uint postBalance;
DDDDD....DDDDD    uint deposited;
}

因为我们关心amountToMint，这个值是最后给用户记账的值，所以第一个思路肯定是把amountToMint这个值写成uint(-1)

但是v.amountToMint的值在mint函数中被更新过一次, 所以不能直接写amountToMint的值，这样可以选择的值有totalInNorm, totalSupply, totalBalanceNorm这三个值

if (v.totalSupply == 0) {
    v.amountToMint = v.totalInNorm;
} else {
    v.amountToMint = v.totalInNorm * v.totalSupply / v.totalBalanceNorm;
}

totalBalanceNorm这个值也被更新过，同时preBalance也被更新过

v.preBalance = v.token.balanceOf(address(this));
v.totalBalanceNorm += scaleFrom(v.token, v.preBalance);

totalSupply在一开始就被更新过：

v.totalSupply = supply;

totalInNorm也是被更新过：

v.preBalance = v.token.balanceOf(address(this));
v.postBalance = v.token.balanceOf(address(this));
v.deposited = v.postBalance - v.preBalance;
v.totalInNorm += scaleFrom(v.token, v.deposited);

这样看起来MintVars里的值都是要在函数内部更新的，是不是就没办法了呢？

这里使用的方式是让memory存储溢出，从而使得MintVars memory v与uint[] memory amounts两者在内存中分配到同一块内存上，即v=amounts.

然后通过构造的方式，让v的值变化成amounts[0-3]的值，实现内存变量的shadowing。

我们的目标是让amountToMint尽可能地大，也就是让totalInNorm大，totalSupply大，totalBalanceNorm小。

针对totalBalanceNorm, 我们可以先swap一下，把swap合约中的后三个token的数量都清空为0，只留下第一个token有数量，即DAI的数量。

这里的映射关系为：

v.totalSupply -> amounts[0]
v.totalBalanceNorm -> amounts[1]
v.totalInNorm -> amounts[2]
v.amountToMint -> amounts[3]

由于此时只有DAI是由余额的，为400，其他均为0；即DAI

Next, we'll purchase the right amount of DAI/TUSD/USDC such that when amounts[i] = v.has is executed, we'll write our desired values into v. The balance of DAI will be written to v.totalSupply, so we'll want to set this to a large number such as 10000e18. The balance of TUSD will be written to v.totalBalanceNorm, so we'll update that to 1. Finally, the balance of USDC will be written to v.totalInNorm so we'll also set that to 10000e18. There's no point manipulating the USDT balance because the value will be clobbered anyways.

if (amounts[i] > v.has) amounts[i] = v.has;

通过构造，使得v.has的数据可以写入amounts[i]中，即此时可以将Dai.balance写入totalSupply里。所以totalSupply的值应该是10000 ether

于是amountToMint是 10000 * 20000 / 1 = 2000000

为搞清楚ABI.encoding 和 struct的机制，构造如下Test合约：

pragma solidity 0.4.24;

contract Test {
    struct MintVars {
        uint totalSupply;
        uint totalBalanceNorm;
        uint totalInNorm;
        uint amountToMint;

        address token;
        uint has;
        uint preBalance;
        uint postBalance;
        uint deposited;
    }

    function mint(uint[] memory amounts) public returns (uint) {
        MintVars memory v;
        v.totalSupply = uint256(0);
        v.totalBalanceNorm = uint256(1);
        v.totalInNorm = uint256(2);
        v.amountToMint = uint256(3);
        v.token = address(this);
        v.has = uint256(5);
        v.preBalance = uint256(6);
        v.postBalance = uint256(7);
        v.deposited = uint256(8);

        return v.amountToMint;
    }
    function toCall(bytes memory data) public returns (uint) {
        address(this).call(data);

    }

}

第一步：设置mint参数为[0x02]

虽然设置了uint[] memory amounts, 其存储位置为memory，实际上还是会调用calldatacopy方法，将数据拷贝到内存中。其中，mstore(mload(0x40),len); mstore(add(mload(0x40)), amounts[0])

freepointer -> len
freepointer + 0x20 -> amounts[0]

当进入到函数内，MintVars memory v会首先在内存中初始化一段内存，起始点是更新后的freepointer指向的内容

第二步：调用call函数，设置其data为：

0xf8e93ef90000000000000000000000000000000000000000000000000000000000000020000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000020000000000000000000000000000000000000000000000000000000000000003

这里主要是判断3是否会被拷贝到内存中，从实际的截图看，其并不会拷贝到内存中，原因是调用了calldatacopy这个opcode，其含义为从calldta 中的u1位置处开始拷贝，长度为len，拷贝到内存u0处。所以上面data中的0x3并不会拷贝到内存中，对整个数据拷贝过程没有影响。

第三步：调用call函数，设置其data为：

0xf8e93ef900000000000000000000000000000000000000000000000000000000000000200800000000000000000000000000000000000000000000000000000000000000

这里主要是验证samczsun所说的线性分配内存，即其并不会检查len的大小，如果len的大小超过了整个内存池的长度，则会导致上溢出，从而使得free-pointer重新指向到已分配的内存中。这里主要是检查函数内部的变量v的开始位置在哪

从下图，可以确实的看到，free-pointer的位置在0xa0处，即整个MintVars memory v的指针完全与Amount部分重叠了。

那么是不是只有在编译器版本为0.4的时候才出现这个问题呢？如果是高版本会怎么样？

第四步：将编译器换成高版本，重新进行第三步：

当把编译器换成高版本的0.8.0时，发现该问题已经被修复，不存在内存shadow的现象了。