R0 CREW

Predicting Random Numbers in Ethereum Smart Contracts

Оригинал: consensys.github.io

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

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

Наши исследования были выполнены в следующих шагах:

  1. 3,649 смарт-контрактов было собрано из etherscan.io и GitHub.
  2. Затем эти контракты были импортированы в поисковую систему Elasticsearch с открытым исходным кодом.
  3. Используя веб-интерфейс Kibana для расширенного поиска и фильтрации, было найдено 72 уникальных реализации PRNG.
  4. Основываясь на ручной оценке каждого контракта, 43 контракта были идентифицированы как уязвимые.

Уязвимые реализации

Анализ выявил четыре категории уязвимых PRNG:

  • PRNG, использующие блок-переменные в качестве источника энтропии
  • PRNG, основанные на блокхэше какого-то предыдущего блока
  • PRNG, основанные на блокхэше прошлого блока в сочетании с seed, который считается приватным
  • PRNG подвержены front-running

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

PRNG на основе блок-переменных

Существует несколько блок-переменных, которые могут быть ошибочно использованы в качестве источника энтропии:

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

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

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

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

PRNG, основанные на блокхэше

Каждый блок в блокчейне Ethereum имеет хеш проверки. Виртуальная машина Ethereum (EVM) позволяет получать такие блокхэши через функцию block.blockhash(). Эта функция ожидает числовой аргумент, указывающий номер блока. В ходе исследования мы обнаружили, что результат block.blockhash() часто используется неправильно в реализациях PRNG.

Существуют три основных недостатка таких PRNG:

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

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

block.blockhash (block.number)

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

Некоторые контракты неправильно интерпретируют значение блока expression.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)

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

Пример 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 из памяти и получает свой блок-код, который затем используется для генерации псевдослучайного числа.

Этот подход работает только в том случае, если выполнено важное требование. Документация Solidity предупреждает о пределе сохраненных блокировок, которые EVM может хранить:

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

Таким образом, если второй вызов не был выполнен в пределах 256 блоков и валидация блокхэша отсутствует, псевдослучайное число будет известно заранее - блокхэш будет равен нулю.

Наиболее известным случаем использования этой уязвимости является взлом лотереи SmartBillions. В контракте была недостаточная проверка возраста block.number, это привело к тому, что было потеряно 400 ЕТН – их получил неизвестный игрок, который дождался 256 блоков, прежде чем выявить прогнозируемый выигрышный номер.

Блокхэш с приватным seed

Чтобы увеличить энтропию, некоторые анализируемые контракты использовали дополнительный 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;
  }
}

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

Будучи прозрачным по своей природе, блокчейн не должен использоваться для хранения секретов в открытом виде. Хотя приватные переменные защищены от других контрактов, можно получить содержимое хранилища контрактов вне сети. Например, популярный клиент 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

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

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

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

На пути к безопасному PRNG

Существует несколько подходов к внедрению более безопасных PRNG в блок-цепочке Ethereum:

  • Внешние оракулы
  • Signidice
  • Подход к раскрытию (Commit-reveal approach)

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

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

Рисунок 1. Схема работы Oraclize

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

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

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

Подход BTCRelay небезопасен в отношении проблемы стимулирования майнеров. Хотя этот подход устанавливает более высокий барьер по сравнению с использованием блоков Ethereum, он просто использует тот факт, что цена Bitcoin выше, чем Ethereum, что уменьшает, но не устраняет риск обмана майнеров.

Signidice

Signidice - это алгоритм, основанный на криптографических подписях, которые могут использоваться в качестве PRNG в интеллектуальных контрактах, включающих только две стороны: игрока и дом. Алгоритм работает следующим образом:

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

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

К счастью, с выпуском хардфорка Метрополис был введен модульный оператор возведения в степень. Это позволяет реализовать проверку подписи RSA, которая, в отличие от ECDSA, не позволяет манипулировать входными параметрами, чтобы найти подходящую подпись.

Подход сделка-обнаружение (Commit-reveal approach)

Как следует из названия, подход сделка-обнаружение состоит из двух этапов:

  • Стадия «Сделки», когда стороны передают свои криптографически защищенные секреты в интеллектуальный контракт.
  • Стадия «раскрытия», когда стороны объявляют seed’ы чистого текста, смарт-контракт подтверждает, что они верны, и seed’ы используются для генерации случайного числа.

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

Лучшей реализацией подхода фиксации является Randao. Этот PRNG собирает хэшированные seed’ы от нескольких сторон, и каждая сторона получает вознаграждение за участие. Никто не знает seed’ы других, поэтому результат действительно случайный. Однако одна сторона, отказывающаяся раскрывать seed, приведет к отказу в обслуживании.

Commit-reveal можно комбинировать с будущими блокхэшами. В этом случае существует три источника энтропии:

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

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

Заключение

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

© Translated by AlexS special for r0 Crew