How to cheat a crypto casino. Predicting random numbers in Ethereum smart contracts.

[Brother]

Ethereum has gained immense popularity as an ICO platform. But it is applicable not only for creating ERC-20 tokens. The Ethereum blockchain can be used in online roulette, lotteries and card games. Confirmed blockchain transactions cannot be faked - the technology is decentralized and transparent - but smart contract code can be vulnerable. One problem is vulnerable pseudo-random number generators, PRNGs. Let's take a look at the typical errors of PRNG implementation in Ethereum-based gambling.

Ethereum allows execution of Turing complete programs, usually written in the Solidity language, which is why the platform founders call it the "world supercomputer". Due to its transparency, Ethereum is very convenient to use in the field of online gambling, where user trust is very important.

However, the processes of the Ethereum blockchain are predictable, which creates difficulties for those who decide to write their own pseudo-random number generator - an integral part of any gambling game. We decided to investigate smart contracts in order to evaluate the reliability of PRNGs on Solidity and to identify common design errors that lead to vulnerabilities and thus make it possible to predict random numbers.

INFO​

In 2017, Positive Technologies specialists implemented projects to analyze security and protect against cybercriminals both the ICO procedure and the implementation of blockchain technologies. The results of the study turned out to be bleak: vulnerabilities in smart contracts were identified in 71% of projects, in 23% of projects flaws were identified that allow attacking investors. Each ICO project contained an average of five vulnerabilities. However, attackers only need one to embezzle investors' money.

Our research includes the following stages:

1. Collected 3649 smart contracts with etherscan.io and GitHub.
2. Imported contracts into Elasticsearch, an open source search engine.
3. Using the Kibana web interface with rich search and filtering capabilities, we discovered 72 unique PRNG implementations.
4. After manually analyzing each contract, we found that 43 contracts were vulnerable.

​

Vulnerable generators​

The analysis identified four categories of vulnerable PRNGs:

• generators using block variables as a source of entropy;
• generators using the hash of the previous block;
• generators using the hash of the previous block in combination with a supposedly secret seed;
• generators exposed to front-running vulnerabilities.

Let's look at each category with examples of vulnerable code.

Generator using block variables​

There are a number of block variables that can be mistakenly used as sources of entropy:

• block.coinbase represents the address of the miner who mines this block;
• block.difficulty - a relative indicator of how difficult it is to create a block;
• block.gaslimit - maximum "gas" consumption for all transactions in the block;
• block.number - the height of this block;
• Block.timestamp - block mining date.

All of these variables can be manipulated by miners, so they cannot be used as a source of entropy. Moreover, it is obvious that these variables are the same within the same block. And if the attacker's contract calls the victim's contract with an internal message, the same generator in both contracts will return the same value.

Example 1 ( 0x80ddae5251047d6ceb29765f38fed1c0013004b7 ):​

// Won if block number is even
// (note: this is a terrible source of randomness, please don’t use this with real money)
bool won = (block.number % 2) == 0;

Example 2 ( 0xa11e4ed59dc94e69612f3111942626ed513cb172 ):​

// Compute some *almost random* value for selecting winner from current transaction.
var random = uint(sha3(block.timestamp)) % 2;

Example 3 ( 0xcC88937F325d1C6B97da0AFDbb4cA542EFA70870 ):​

address seed1 = contestants[uint(block.coinbase) % totalTickets].addr;
address seed2 = contestants[uint(msg.sender) % totalTickets].addr;
uint seed3 = block.difficulty;
bytes32 randHash = keccak256(seed1, seed2, seed3);
uint winningNumber = uint(randHash) % totalTickets;
address winningAddress = contestants[winningNumber].addr;

Generator using block hash​

Each block in the Ethereum blockchain has a hash for verifying transactions. The so-called Ethereum virtual machine (EVM) allows you to get the hash of a block using a function block.blockhash(). The function expects a numeric argument that denotes a block number. During our research, we found that the result of a function is block.blockhash() often misused when generating random values.

There are three main vulnerable variations of block hash generators:

• block.blockhash(block.number) - hash of the current block;
• block.blockhash(block.number-1) - hash of the last block;
• block.blockhash() - hash of a block that is at least 256 blocks older.

Let's consider each of the listed variations.

block.blockhash (block.number)​

A state variable block.number lets you know the height of a given block. When a miner adds a transaction to a block that executes the contract code, the block.numberfuture block of this transaction is known and its value is available to the contract. However, at the time a transaction is executed in the EVM, the hash of the generated block is still unknown for obvious reasons, and the EVM always returns zero.

Some contracts misinterpret the meaning of an expression block.blockhash(block.number). In such contracts, the block hash is considered known at the time of transaction execution and is used as a source of entropy.

Example 1 ( 0xa65d59708838581520511d98fb8b5d1f76a96cad ):​

function deal(address player, uint8 cardNumber) internal returns (uint8) {
   uint b = block.number;
   uint timestamp = block.timestamp;
   return uint8(uint256(keccak256(block.blockhash(b), player, cardNumber, timestamp)) % 52);
}

Example 2 ( https://github.com/axiomzen/eth-random/issues/3 ):​

function random(uint64 upper) public returns (uint64 randomNumber) {
   _seed = uint64(sha3(sha3(block.blockhash(block.number), _seed), now));
   return _seed % upper;
}

block.blockhash (block.number-1)​

Some contracts use generators based on the hash of the last block. It is clear that this approach is also vulnerable: an attacker can create an exploit contract with the same generator value in order to invoke the attacked contract through an internal message. The "random" numbers of both contracts will match.

Example 1 (0xF767fCA8e65d03fE16D4e38810f5E5376c3372A8):​

//Generate random number between 0 & max
uint256 constant private FACTOR =  1157920892373161954235709850086879078532699846656405640394575840079131296399;
function rand(uint max) constant private returns (uint256 result){
   uint256 factor = FACTOR * 100 / max;
   uint256 lastBlockNumber = block.number - 1;
   uint256 hashVal = uint256(block.blockhash(lastBlockNumber));
   return uint256((uint256(hashVal) / factor)) % max;
}

block.blockhash () - hash of the future block​

A more reliable way is to use the hash of the future block, for example, as follows.

1. The player places a bet, the casino remembers the block.number of the transaction.

2. On the second call to the contract, the player asks the casino for the winning number.

3. The casino retrieves the stored block.number, gets the hash of the block by its number and then uses the hash to generate a pseudo-random number.

This approach only works if one important requirement is met. There is a warning in the Solidity documentation about the limited number of block hashes that an EVM can store.

For scalability reasons, hashes are not available for all blocks. It is possible to access the hashes of only the last 256 blocks, and all other values will be zero.

Therefore, if the second call was not made within 256 blocks and there was no check of the block number, the pseudo-random number will be known in advance - this is 0.

The most notorious case of exploitation of this vulnerability is the SmartBillions lottery hack. The contract incorrectly checked the age of block.number, which resulted in the player winning 400 ETH: after creating 256 blocks, he requested a predictable winning number, which he sent in the first transaction.

Generators using the hash of the previous block with a private seed​

To increase entropy, some of the contracts studied used an initial value that is considered secret. This was the case in the Slotthereum lottery. Sample code:

bytes32 _a = block.blockhash(block.number - pointer)
for (uint i = 31; i >= 1; i--) {
   if ((uint8(_a[i]) >= 48) && (uint8(_a[i]) <= 57)) {
       return uint8(_a[i]) - 48;
   }
}

The variable pointer is declared private, that is, other contracts do not have access to its value. After each game, the winning number from 1 to 9 was assigned to this variable and then used as a random offset block.number to obtain the block hash by number.

One of the properties of blockchain technology is its transparency, so secret data should not be stored in it in the clear. Despite the fact that private variables are not available to other contracts, it is possible to retrieve the contents of the contract store from the blockchain. For example, in the web3 client, popular in Ethereum, there is an API method web3.eth.getStorageAt()that can be used to retrieve the contents of a persistent storage of a contract based on the indexes of records in it.

In this case, it will not be difficult to get the value of the private variable pointer from the contract and use it as an argument in the exploit:

function attack(address a, uint8 n) payable {
   Slotthereum target = Slotthereum(a);
   pointer = n;
   uint8 win = getNumber(getBlockHash(pointer));
   target.placeBet.value(msg.value)(win, win);
}

Generators Affected by Front-Running Vulnerabilities​

To grab the largest reward, miners use transactions to create a new block based on the cumulative gas received from each transaction. The order in which a transaction is executed in a block is determined by the gas price. The transaction with the highest gas price will be executed first. Thus, by manipulating the price, it is possible to ensure that the desired transaction is executed before the others in the block. This can be a vulnerability when the execution of a contract depends on its position in the block.

Let's consider an example. The lottery has an external "oracle" for generating pseudo-random numbers, which is used to determine the winner among the players who place their bets in each round. The numbers are transmitted unencrypted. An attacker can look at the pool of unconfirmed transactions and wait for the number from the oracle. As soon as the predictor's transaction appears in the pool, the attacker sends a bet with a higher gas price. This transaction was sent last in the round, but it is executed before the oracle transaction due to the highest gas price, and thus the attacker becomes the winner. A similar technique was demonstrated at the ZeroNights ICO Hacking Contest.

There is another example of a contract prone to a forward-of-transaction vulnerability - Last is me! The player buys a ticket, takes the last place, and the countdown timer starts. If no one buys a ticket after creating a certain number of blocks, the contract gives the winning seat to the one who bought the ticket last. When the round ends, the attacker monitors the pool of unconfirmed transactions of other participants and wins by sending a transaction with a higher gas price.

How to create a safer PRNG​

There are several approaches to creating safer PRNGs on the Ethereum blockchain:

• external oracle;
• Signidice algorithm;
• Commit-Reveal approach.

External oracles​

Oraclize​

Oraclize is a service for decentralized applications that serves as a link between the blockchain and the external environment (the Internet). With Oraclize, smart contracts can request data from a web API (for example, currency rates, weather forecasts, stock prices). In addition, Oraclize can be used as a PRNG. Some of the contracts examined used Oraclize to get random numbers from random.org.

Oraclize in action

The main disadvantage of this approach is that the service is centralized. Can we be sure the Oraclize daemon won't change the result? Can random.org and all of its infrastructure be trusted? Despite the fact that Oraclize uses the TLSNotary service, verification is done off-chain (in the case of lotteries, after the winner is announced). Better to use Oraclize as a source of "random" data using Ledger proofs that can be verified within the blockchain.

BTC Relay​

BTC Relay is a bridge between Ethereum and Bitcoin blockchains. With the help of BTC Relay, smart contracts of the Ethereum blockchain can query the hash of the future Bitcoin block and use it as a source of entropy. An example of a project that uses BTC Relay as PRNG is The Ethereum Lottery.

BTC Relay is not suitable for solving the problem of miner motivation. Here the barrier is higher than when using future Ethereum blocks, but only because of the higher price of bitcoin. So this approach reduces, but does not eliminate, the likelihood of miner fraud.

Signidice Algorithm​

Signidice is an algorithm based on cryptographic signatures. It can be used as a PRNG in smart contracts - with two parties (player and casino). The algorithm works as follows.

1. The player places a bet by calling the contract method.
2. The casino sees the bet, signs it with a private key and sends the signature to the contract.
3. The contract verifies the signature using the public key.
4. The signature is then used to generate a random number.

Ethereum has a built-in function ecrecover() to verify ECDSA signatures on the blockchain. However, the ECDSA algorithm cannot be used in Signidice, since the casino can change the input parameters (in particular, the parameter k) and thus affect the value of the final signature. The implementation of this fraudulent scheme was demonstrated by Alexey Pertsev.

Fortunately, with the release of the Metropolis hard fork, a new exponentiation operator was introduced, which allowed RSA signature verification, which, unlike ECDSA, does not allow manipulating the input data to pick up the signature.

Commit - Reveal approach​

As the name suggests, this approach consists of two stages.

• Commit: the parties transfer their data to the smart contract in encrypted form;
• Reveal: the parties send the initial values in clear text, the contract confirms that the data is correct, the initial values are used to generate a random number.

You cannot rely on either side to properly apply this approach. Although the players do not know the initial values of the owner, the owner can be a player at the same time, so players cannot trust him.

Randao is a smarter application of the Commit-Reveal approach. This pseudo-random number generator collects hashed seed values from multiple parties and each party receives a reward for participating. The parties don't know each other's initial value, so a truly random result is generated. However, refusal by one of the parties to disclose the initial value will lead to DoS.

Commit - Reveal can be matched using the hash of the future block. In this case, there are three sources of entropy:

• sha3 (seed1) owner;
• sha3 (seed2) of the player;
• hash of the future block.

Of of The of of The Of of The Of of The Number The of The Of Of Is the of the of the of the of the of of The of the the Random of the of of The generated as with the with the with the with the with the with the with the with the FOLLOWS: sha3(seed1, seed2, blockhash). The Commit - Reveal approach solves the problem of the miner's motivation: the miner determines whether to publish the found hash on the blockchain, but does not know the initial values of the owner and the player. The approach also solves the problem of the owner's motivation: the owner knows only the initial value of the owner, the initial value of the player and the hash of the future block are unknown to him. In addition, the approach works great if the owner and the miner are the same person: he chooses the hash of the block and knows the initial value of the owner, but not the player.

Conclusion​

Building secure pseudo-random number generators on the Ethereum blockchain is still a challenge. The study showed that due to the lack of ready-made solutions, developers are more likely to use their implementation tools. However, it is easy to make a design mistake as the sources of entropy on the blockchain are limited. When creating a PRNG, the developer should make sure that he understands the motivations of each party, and then proceed with the choice of approach.