[Перевод] Предсказание случайных чисел в умных контрактах Ethereum

ce9d9b6ca2d53c87dc13d76d36fc4ecb.jpg

Ethereum приобрёл огромную популярность как платформа для первичного размещения монет (ICO). Однако она используется не только для токенов ERC20. Рулетки, лотереи и карточные игры — всё это можно реализовать на блокчейне Ethereum. Как любая реализация, блокчейн Ethereum не поддаётся подделке, он децентрализован и прозрачен. Ethereum допускает выполнение тьюринг-полных программ, которые обычно пишут на языке программирования Solidity. По словам основателей платформы, это превращает систему во «всемирный суперкомпьютер». Перечисленные характеристики полезны в приложениях для азартных игр, где особенно важно доверие пользователей.

Блокчейн Ethereum является детерминированным и поэтому представляет определённые сложности при написании генератора псевдослучайных чисел (ГПСЧ) — неотъемлемой части любого приложения для азартных игр. Мы решили исследовать смарт-контракты, чтобы оценить безопасность ГПСЧ на Solidity и подчеркнуть характерные ошибки проектирования, которые ведут к появлению уязвимостей и возможности предсказания будущего состояния ГПСЧ.

Наше исследование проводилось в несколько этапов:

  1. На etherscan.io и GitHub собрана информация о 3649 смарт-контрактах.
  2. Контракты импортировались в свободную поисковую систему Elasticsearch.
  3. С помощью веб-интерфейса Kibana для функционального поиска и фильтрации найдены 72 уникальные реализации ГПСЧ.
  4. После ручной оценки 43 смарт-контракта признаны уязвимыми.


Уязвимые приложения
Анализ выявил четыре категории уязвимых ГПСЧ:

  • ГПСЧ с использованием переменных блока как источника энтропии.
  • ГПСЧ на основе хэша какого-то предыдущего блока.
  • ГПСЧ на основе хэша предыдущего блока в сочетании с якобы секретным начальным числом (seed).
  • ГПСЧ, подверженные уязвимости с опережением транзакции (front-running).


Посмотрим на примеры уязвимого кода в каждой категории.

ГПСЧ с использованием групп переменных


Вот некоторые переменные блока, которые ошибочно принимают за источник энтропии:

  • block.coinbase — адрес майнера, который нашёл текущий блок.
  • block.difficulty — относительный показатель сложности при майнинге текущего блока.
  • block.gaslimit — максимальное потребление газа для транзакций в блоке.
  • block.number — высота текущего блока.
  • block.timestamp — отметка времени, когда найден блок.


Прежде всего, майнеры могут манипулировать всеми переменными блока, так что по одной этой причине их нельзя использовать как источник энтропии. Что ещё более важно, переменные блока очевидно одинаковы в пределах блока. Так что если контракт злоумышленника обращается к контракту жертвы через внутреннее сообщение, то одинаковый ГПСЧ в обоих контрактах выдаст одинаковый результат.

Пример 1 (0×80ddae5251047d6ceb29765f38fed1c0013004b7):

// 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;


Пример 2 (0xa11e4ed59dc94e69612f3111942626ed513cb172):

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


Пример 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;


ГПСЧ на хэша блока


У каждого блока в цепочке Ethereum есть проверочный хэш. Виртуальная машина Ethereum Virtual Machine (EVM) позволяет получать эти хэши с помощью функции block.blockhash(). Функция получает на вход числовой аргумент с указанием номера блока. В ходе этого исследования мы обнаружили, что результаты выполнения функции block.blockhash() зачастую некорректно используются в реализациях ГПСЧ.

Есть три основных разновидности таких уязвимых ГПСЧ:

  • block.blockhash(block.number), хэш текущего блока.
  • block.blockhash(block.number - 1), хэш последнего блока.
  • block.blockhash(), хэш блока, который отстоит как минимум на 256 блоков от текущего.


Посмотрим на каждый из этих случаев.

block.blockhash (block.number)

Переменная состояния block.number позволяет узнать высоту текущего блока. Когда майнер забирает транзакцию, которая выполняет код контракта, то известна переменная block.number будущего блока с этой транзакцией, так что контракт может надёжно получить её значение. Однако в момент выполнения транзакции в EVM хэш создаваемого блока по очевидным причинам ещё не известен, а EVM всегда будет выдавать нуль.

Некоторые контракты неверно интерпретируют выражение block.blockhash(block.number). В этих контрактах хэш текущего блока считается известным во время выполнения и используется в качестве источника энтропии.

Пример 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);
}


Пример 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)

В некоторых контрактах используется другой вариант ГПСЧ на основе хэша блока: там берётся хэш не текущего, а предыдущего блока. Нечего говорить, что такой подход тоже неприемлем: злоумышленник может создать эксплоит-контракт с тем же кодом ГПСЧ, чтобы вызвать целевой контракт через внутреннее сообщение. В обоих контрактах будут одинаковые «случайные» числа.

Пример 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.number транзакции.
  • При повторном вызове контракта игрок просит, чтобы контора объявила выигрышный номер.
  • Контора извлекает из хранилища сохранённый block.number и получает его хэш, который затем используется для генерации псевдослучайного числа.


Такой подход работает только при соблюдении одного важного требования. Документация Solidity предупреждает о лимите хэшей блоков, которые способна хранить EVM:

По причинам масштабируемости доступны хэши не для всех блоков. Можно получить доступ к хэшам только последних 256 блоков, а все остальные значения будут равны нулю.


Поэтому если в течение 256 блоков не поступило второго вызова с проверкой хэша, то псевдослучайное число можно предсказать заранее — хэш будет равен нулю.

Самый известный случай эксплуатации этой уязвимости — взлом лотереи SmartBillions. В контракте не проверялся возраст block.number, из-за чего 400 ETH ушли неизвестному игроку, который подождал 256 блоков перед раскрытием предсказуемого выигрышного числа.

Хэш блока с секретным начальным числом

Для увеличения энтропии некоторые контракты применяют дополнительное начальное число (seed), которое считается секретным. Один из примеров — лотерея 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;
  }
}


Переменная pointer объявлена секретной, то есть другие контракты не могут получить к ней доступ. После каждой игры этой переменной присваивается выигрышное число от 1 до 9, а потом используется оно для смещения block.number при получении хэша блока.

Прозрачный по своей природе блокчейн не должен использоваться для хранения секретов в чистом тексте. Хотя секретные переменные защищены от других контрактов, но можно получить содержимое хранилища контрактов вне цепочки. Например, в популярном Ethereum-клиенте web3 есть метод API web3.eth.getStorageAt(), позволяющий получить записи хранилища по заданным индексам.

Учитывая этот факт, становится тривиальной задачей извлечь значение секретной переменной из хранилища контрактов и использовать его как аргумент в коде эксплоита:

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);
}


Опережение транзакции


Чтобы получить максимальную награду, майнеры выбирают транзакции для создания нового блока на основе совокупного газа (топлива), который тратится каждой транзакцией. Порядок выполнения транзакций в блоке определяется ценой газа. Первой будет выполнена транзакция с максимальной ценой газа. Так что изменяя цену газа можно добиться, чтобы нужная транзакция выполнилась раньше всех остальных в текущем блоке. Это может представлять собой проблему безопасности — которую обычно называют опережением (front-running), когда исполнение контракта зависит от его положения в блоке.

Рассмотрим следующий пример. Лотерея задействует внешнего оракула для получения псевдослучайных чисел, которые используются для выбора победителя среди игроков, сделавших ставки в текущем раунде. Эти числа отправляются в открытом виде. Злоумышленник может наблюдать пул ожидающих транзакций и ждёт числа от оракула. Как только транзакция от оракула появляется в пуле транзакций, злоумышленник делает ставку с большей ценой газа. Транзакция злоумышленника пришла последней в текущем раунде, но благодаря наивысшей цене газа она в реальности будет исполнена раньше, чем транзакция оракула, что принесёт игроку победу. Такую задачу выполняли участники хакерского конкурса ZeroNights ICO.

Другой пример контракта, подверженного уязвимости с опережением транзакции — игра под названием Last is me! Каждый раз, когда игрок покупает билет, он занимает последнее место и начинается отсчёт таймера. Если за определённое количество блоков никто не покупает билет, то последний «занявший место» игрок выигрывает джекпот. Когда раунд близится к завершению, злоумышленник может наблюдать пул транзакций других участников и присвоить джекпот, установив более высокую цену газа.

Более безопасные ГПСЧ
Есть несколько подходов для реализации более безопасных ГПСЧ в блокчейне Ethereum:

  • Внешние оракулы
  • Signidice
  • Схема «коммит-раскрытие»


Внешние оракулы: Oraclize


Oraclize — это сервис для распределённых приложений, которые устанавливают мост между блокчейном и внешним окружением (Интернет). При использовании Oraclize смарт-контракты могут запрашивать данные из API в вебе, такие как курсы валют, прогнозы погоды, котировки акций. Один из самых известных вариантов использования — способность Oraclize работать как ГПСЧ. Некоторые из контрактов, которые анализировались в ходе нашей работы, использовали Oraclize для получения случайных чисел с random.org через коннектор URL. Эта схема изображена на рис. 1.

53415cbb048e427f7db4fb932d8bbee0.png
Рис. 1. Схема работы Oraclize

Главный недостаток такого подхода — централизация. Можем ли мы верить, что демон Oraclize не вмешивается в результаты? Можем ли мы доверять random.org и всей инфраструктуре, лежащей в основе этого сервиса? Хотя Oraclize проверяет результаты через аудиторский сервис TLSNotary, его можно использовать только вне цепочки блоков — в случае с лотерей только после оглашения победителя. Лучше использовать Oraclize как источник «случайных» данных с применением доказательств Ledger, которые можно проверить в цепочке.

Внешние оракулы: BTCRelay


BTCRelay — это мост между цепочками блоков Ethereum и Bitcoin. При использовании BTCRelay смарт-контракты в блокчейне Ethereum могут запрашивать хэши будущих блоков Bitcoin и использовать их как источник энтропии. Один из проектов, применяющих BTCRelay в качестве ГПСЧ — лотерея Ethereum Lottery.

Метод BTCRelay не защищён от проблемы стимулирования майнеров. Хотя здесь барьер выше, чем в случае блоков Ethereum, но только из-за более высокой цены биткоина. Так что этот подход снижает, но не устраняет вероятность мошенничества со стороны майнеров.

Signidice


Signidice — это алгоритм на основе криптографических подписей. Его можно использовать как ГПСЧ в смарт-контрактах с участием двух сторон: игрока и конторы. Алгоритм работает следующим образом:

  • Игрок делает ставку, вызывая смарт-контракт.
  • Контора видит ставку, подписывает её своим секретным ключом и отправляет подпись в смарт-контракт.
  • Смарт-контракт проверяет подпись с помощью известного открытого ключа.
  • Эта подпись затем используется для генерации случайного числа.


В Ethereum есть встроенная функция ecrecover() для проверки подписей ECDSA в цепочке. Однако ECDSA нельзя использовать в Signidice, поскольку контора может манипулировать входными параметрами (в частности, параметром k) и так влиять на получающуюся в результате подпись. Алексей Перцев показал демонстрационный пример такого мошенничества.

К счастью, с выходом жёсткого форка Metropolis появился оператор модульного возведения в степень. Это позволяет реализовать проверку подписи RSA. В отличие от ECDSA, она не допускает манипуляцию входными параметрами для поиска подходящей подписи.

Схема «коммит-раскрытие»


Как понятно из названия, схема «коммит-раскрытие» (commit–reveal) состоит из двух этапов:

  • Этап коммита, когда стороны отправляют в смарт-контракт свои криптографически защищённые секреты.
  • Этап раскрытия, когда стороны объявляют начальные числа открытым текстом, смарт-контракт проверяет их правильность, и они используются для генерации случайного числа.


Правильно реализованная схема коммита-раскрытия не должна полагаться на единственную сторону. Хотя игроки не знают оригинального начального числа, поданного владельцем, и их шансы равны, но владелец тоже может быть игроком, поэтому игроки не могут ему доверять.

Схема «коммит-раскрытие» более грамотно реализована в сервисе Randao. ГПСЧ собирает хэши начальных чисел от нескольких сторон, и каждая из них получает вознаграждение за участие. Никто не знает чужих начальных чисел, так что результат абсолютно случаен. Однако если хоть одна сторона откажется сообщить своё начальное число, то сервис даёт сбой.

Схему «коммит-раскрытие» можно совместить с использованием хэшей будущих блоков. В этом случае задействуются три источника энтропии:

  • sha3 владельца (seed1)
  • sha3 игрока (seed2)
  • хэш будущего блока


Тогда случайное число генерируется следующим образом: sha3(seed1, seed2, blockhash). Поэтому схема «коммит-раскрытие» решает проблему стимулирования майнеров: майнер может повлиять на хэш блока, но он не знает начальных чисел владельца и игрока. Она также решает проблему стимулирования владельца: он знает только собственное начальное число, но не знает начальное число игрока и хэш будущего блока. Вдобавок, такая схема подходит для ситуаций, когда человек выступает одновременно в роли владельца и майнера: он определяет хэш блока, знает начальное число владельца, но не знает начальное число игрока.

Заключение
Безопасная реализация ГПСЧ в блокчейне Ethereum по-прежнему остаётся нерешённой задачей. Как показало наше исследование, из-за отсутствия готовых решений разработчики склонны внедрять собственные реализации ГПСЧ. Но при этом легко сделать ошибку, поскольку в цепочке блоков немного источников энтропии. При разработке ГПСЧ разработчику следует убедиться, что он понимает мотивацию каждой стороны, — и тогда выбирать соответствующий подход.

© Habrahabr.ru