Predicting Random Numbers in Ethereum Smart Contracts

The Ethereum blockchain is deterministic and as such it imposes certain difficulties for those who have chosen to write their own pseudo-random number generator (PRNG), which is an inherent part of any gambling application. We decided to research smart contracts in order to assess the security of PRNGs written in Solidity and to highlight common design antipatterns that lead to vulnerabilities allowing prediction of the future state.

Transcript

1. PREDICTING RANDOM NUMBERS IN ETHEREUM SMART CONTRACTS Arseny Reutov @theRaz0r raz0r@positive.com AppSec California 2018
2. About me ▸ Application security researcher at Positive.com ▸ Member of PHDays security conference team (CFP is open!) ▸ Occasional web security blogger at Raz0r.name
3. Agenda ▸ Ethereum and smart contracts 101 ▸ Hands on vulnerable PRNGs in the wild ▸ Towards a safer PRNG ▸ Automating discovery of vulnerable contracts ▸ … and a bonus wargame with prizes!
4. ETHEREUM AND SMART CONTRACTS 101
5. Blockchain transaction 1 transaction 2 ... transaction n hash(block N+1) N+2 block header transaction 1 transaction 2 ... transaction n hash(block N) N+1 block header hash(block N-1) transaction 1 transaction 2 ... transaction n N block header
6. Blockchain properties ▸ Incorruptible ▸ Transparent ▸ Decentralized
7. Blockchain evolution ▸ Blockchain 1.0 ▹ Cryptocurrency: Bitcoin, Litecoin, etc ▸ Blockchain 2.0: ▹ Smart contracts: Ethereum, NEO, etc
8. Ethereum High-level language (Solidity, Serpent, Viper, etc) Contract bytecode Ethereum Virtual Machine
9. Externally Owned Accounts (EOAs) ▸ have an ether balance ▸ can send transactions (ether transfer or trigger contract code) ▸ are controlled by private keys ▸ have no associated code
10. Contract accounts ▸ have an ether balance ▸ have associated code ▸ code execution is triggered by transactions or messages (calls) received from other contracts or EOAs ▸ when executed - perform operations of arbitrary complexity (Turing completeness)
11. Solidity ▸ looks like JavaScript ▸ but is strongly-typed ▸ has no string operations, has no floats (integers only) ▸ is mainly used to implement ERC20 tokens ▸ as a Turing-complete language can be used to create lotteries, card games or roulettes ▸ contracts have bugs!
12. HANDS ON VULNERABLE PRNGs IN THE WILD
13. 3649 contracts from etherscan.io and GitHub 43 are vulnerable 72 unique implementations including self-destructed ones
14. 1. Vulnerable implementations ▸ Based on block variables ▸ Based on past blockhash ▸ Based on past blockhash and a “private” seed ▸ Prone to front-running
15. PRNGs based on block variables There are a number of block variables that may be wrongly used as a source of entropy: ▸ block.coinbase ▸ block.difficulty ▸ block.gaslimit ▸ block.number ▸ block.timestamp
16. PRNGs based on block variables ▸ You don’t even need to be a miner to predict the outcome ▸ An exploit contract with the same PRNG function can call the target contract ▸ Since these calls are in the same transaction, all the block variables will be shared
17. PRNGs based on block variables // 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; https://etherscan.io/address/0x80ddae5251047d6ceb29765f38fed1c0013004b7
18. PRNGs based on block variables // Compute some *almost random* value for selecting winner from current transaction. var random = uint(sha3(block.timestamp)) % 2; https://etherscan.io/address/0xa11e4ed59dc94e69612f3111942626ed513cb172
19. PRNGs based on block variables 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; https://etherscan.io/address/0xcC88937F325d1C6B97da0AFDbb4cA542EFA70870
20. PRNGs based on blockhash Three major flawed variations: ▸ block.blockhash(block.number) ▸ block.blockhash(block.number - 1) ▸ block.blockhash() of a block that is at least 256 blocks older than the current one
22. block.blockhash(block.number) 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); } https://etherscan.io/address/0xa65d59708838581520511d98fb8b5d1f76a96cad
23. block.blockhash(block.number) function random(uint64 upper) public returns (uint64 randomNumber) { _seed = uint64(sha3(sha3(block.blockhash(block.number), _seed), now)); return _seed % upper; } https://github.com/axiomzen/eth-random/issues/3
24. block.blockhash(block.number - 1) ▸ Last block’s hash cannot be used as a source of entropy as well ▸ Again, an attacker can use an exploit contract to call the target one ▸ In both contracts the blockhash will be the same
25. block.blockhash(block.number - 1) //Generate random number between 0 & max uint256 constant private FACTOR = 1157920892373161954235709850086879078532699846656405640394575840079 131296399; 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; } https://etherscan.io/address/0xF767fCA8e65d03fE16D4e38810f5E5376c3372A8
26. Blockhash of an old block ▸ A better approach is to get the blockhash of some future block, however: ▸ It means that if a PRNG does not check the age of block (should be within most recent 256 blocks), then it is vulnerable
27. SmartBillions ▸ SmartBillions lottery saved block.number in the storage when a bet was made ▸ The outcome was calculated in a second call which retrieved blockhash of the saved block.number ▸ However the contract failed to validate block.number age ▸ The attacker just waited for 256 blocks and won 400 ETH https://etherscan.io/address/0x5ace17f87c7391e5792a7683069a8025b83bbd85
28. Blockhash with a private seed ▸ Blockchain is transparent to anyone, you should not keep secrets here ▸ Although variables with private scope cannot be accessed directly by other contracts, they can be looked up off-chain, e.g. using web3.eth.getStorageAt()
29. Slotthereum 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; } } https://etherscan.io/address/0x6910443699506d7366489524d1aaca51346c9a49
30. Slotthereum https://github.com/slotthereum/source/issues/1
31. Slotthereum 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); } https://etherscan.io/address/0x2983eedfbd560b6d65ffa47de6a0f6d6fee6e136
33. Front-running ▸ Transactions in a block are ordered by the gas price ▸ Contract execution may depend on its position in the block ▸ An attacker may watch tx pool for an externally submitted random number and instantly issue his tx with higher gas price so that both transactions appear in the same block
34. ZeroNights ICO Hacking Contest https://blog.positive.com/zeronights-ico-hacking-contest-writeup-63afb996f1e3
35. Last is me! ▸ Every time a player buys a ticket, he or she claims the last seat and the timer starts the countdown ▸ If nobody buys the ticket within N blocks, the last player wins the jackpot ▸ When the round is about to finish, an attacker may observe tx pool for other contestants’ transactions and claim the jackpot with higher gas price https://etherscan.io/address/0x5d9b8fa00c16bcafae47deed872e919c8f6535bf
36. TOWARDS A SAFER PRNG
37. 2. Safe(r) implementations ▸ External oracles ▸ Commit-reveal approach ▸ Signidice
38. External oracles: Oraclize Client Oraclize Oraclize daemon Random.org __callback(rand)
39. External oracles: Oraclize ▸ Can Oraclize be trusted? ▸ Can Random.org be trusted? ▸ TLSNotary can be used to verify the results, but only off-chain (i.e. after the winner had been chosen)
40. External oracles: Oraclize Some examples: ▸ Block King ▸ Smart Contract Casino ▸ EtherFlip ▸ Etheroll
41. External oracles: BTCRelay ▸ BTCRelay is a bridge between Ethereum and Bitcoin blockchains ▸ Smart contracts in Ethereum blockchain can request Bitcoin’s future blockhashes and use them as a source of entropy https://etherscan.io/address/0x302fE87B56330BE266599FAB2A54747299B5aC5B
42. Signidice PRNG ▸ Player makes a bet by calling smart contract ▸ House sees the bet, signs it with its private key and sends the signature to the smart contract ▸ Smart contract verifies the signature using the known public key ▸ This signature is then used to generate a random number https://github.com/gluk256/misc/blob/master/rng4ethereum/signidice.md
43. ECDSA-based Signidice ▸ Ethereum uses ECDSA as a means to verify signatures ▸ However, ECDSA cannot be used in Signidice since the house is able to manipulate input parameters (k) and thus affect the resulting signature ▸ See PoC of such cheating implementation by Alexey Pertsev
44. RSA-based Signidice ▸ Unlike ECDSA, RSA does not allow to manipulate input parameters to find a suitable signature ▸ With Metropolis hardfork, modular exponentiation operation became available thus allowing to implement RSA signature verification ▸ Implemented in DAO.casino
45. Commit-reveal with a single party Commit-reveal approach is two-phase: ▸ Commit: an owner posts a hashed seed as sha3(seed) ▸ Reveal: the owner announces clear text seed and the random number is generated
46. Commit-reveal with a single party ▸ Players do not know the original seed, so their chances are equal ▸ But an owner can also be a player, thus we cannot trust him Some examples: ▸ HonestDice ▸ TheEthereumLottery ▸ EthereumRoulette
47. A better commit-reveal: Randao ▸ Randao is a PRNG that collects hashed seeds from multiple parties ▸ Each party is paid a reward for participation ▸ Nobody knows each other’s seeds so the result is truly random ▸ However, a single party refusing to reveal the seed will result in DoS
48. An even better commit-reveal: future blockhash Sources of entropy: 1. Owner’s sha3(seed1) 2. Player’s sha3(seed2) 3. Smart contract uses a future blockhash Random number is then generated as: sha3(seed1, seed2, blockhash) https://blog.winsome.io/random-number-generation-on-winsome-io-future-blockhashes-fe44b1c61d35
49. An even better commit-reveal: future blockhash ▸ Solves miner incentive problem: he can decide on blockhash but does not know owner’s and player’s seeds ▸ Solves owner incentive problem: he knows only his seed, but player’s seed and future blockhash is unknown ▸ Solves owner & miner incentive problem: he decides on blockhash and knows the owner’s seed but does not know player’s seed
50. AUTOMATING DISCOVERY OF VULNERABLE CONTRACTS
51. Mythril ▸ Mythril is a tool by Bernhard Mueller to search Ethereum blockchain for vulnerable contracts ▸ It has a symbolic execution engine based on Z3 ▸ By resolving constraints it is possible to construct a nearly complete CFG of a contract
52. Looking for weak PRNGs with Mythril ▸ “weak_random” plugin allows to detect ether value transfers that are constrained by ▹ predictable block variables ▹ past blockhashes ▸ Thanks to Bernhard for his collaboration on pull request :)
53. THANK YOU Arseny Reutov @theRaz0r raz0r@positive.com