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

https://blog.positive.com/predicting-random-numbers-in-ethereum-smart-contracts-e5358c6b8620
  • Перевод


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

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


У каждого блока в цепочке 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.


Рис. 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 по-прежнему остаётся нерешённой задачей. Как показало наше исследование, из-за отсутствия готовых решений разработчики склонны внедрять собственные реализации ГПСЧ. Но при этом легко сделать ошибку, поскольку в цепочке блоков немного источников энтропии. При разработке ГПСЧ разработчику следует убедиться, что он понимает мотивацию каждой стороны, — и тогда выбирать соответствующий подход.
Поделиться публикацией
Похожие публикации
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 17
  • 0

    Интересно, а для Solidity IDE со статическим анализатором ещё не придумали? Штуки вроде block.blockhash(block.number) бегут ловятся статически.

    • 0

      Нагуглил Solhint, который что-то умеет. В частности, ругается на любое использование block.blockhash. Это, конечно, слишком глупо, но лучше чем ничего. И даже плагин к IDEA имеется.

    • +1
      У oraclize можно получить случайное число не только через random.org: docs.oraclize.it/#data-sources-random (вопрос честности, впрочем, все равно открыт)

      • 0
        Здравствуйте. Не могли бы вы пояснить, как влияние майнера на блок эфира или биткоина, позволит ему извлечь выгоду, например, из лотереи на смарт-контракте?
        • 0
          В теории, если крупный Майнер имеет стойкий мотив в результатах лотереи, то когда такой результат зависит по известной (код контракта ведь публичные) формуле от хеша блока и/или времени его генерации, то Майнер помимо основной задачи, может искать такое решение которое даст такой хеш блока, который бы дал нужный результат в лотерее.
          Вопрос лишь в экономике
          • 0
            Разве это не означает, что майнер должен отклонять добытые им блоки, стоимостью в тысячи долларов, на каждую неудачную попытку добыть нужный хеш?
            • 0
              Означает, но уязвимость есть уязвимость. В лотерее на кону может быть и больше чем 5 ETH
              • 0
                Речь же идет об одной смене блока за 5 ETH. Это разве не то же самое, что купить еще один лотерейный билет, только за несколько тысяч долларов? Почему дорогостоящая смена одного случайного хеша на случайный другой является уязвимостью? Какой возможный сценарий атаки при такой модели?
              • 0
                Всё верно.Но как я уже писал — вопрос экономики. Если на кону джекпот под 100$млн — возможность манипуляции результатом «вызывает вопросы». Если же речь о «школьных завтраках» — то, конечно, заморачиваться никто и не будет.

                • 0
                  Не могли бы вы пояснить, какие вопросы вызывает дорогостоящая смена одного случайного хеша на случайный другой? Каким образом можно при этом осуществить атаку или как-то получить выгоду?
              • 0
                может искать такое решение которое даст такой хеш блока

                Только если он может влиять на результат (что есть нонсенс, и исключено при правильно построенной схеме того же «коммит-раскрытия»).


                Например, если все "ходы + сиды" каждого "игрока" (включая майнера если он тоже играет) во первых подписаны заранее (до опубликования/раскрытия сидов), во вторых ему неизвестны (он знает только их подписи), то он при всём желании не сможет повлиять на результат, от слова никак. Даже взлом SHA1 над сообщением 50% мое / 50% чужое (майнер против конторы) НО с последующим подбором его нового сида под уже готовую (им же заранее сделанную подпись) связан просто с чудовищными затратами (и временными, и ресурсными).
                И если вообще реализуемо (в случае какого-нибудь доступного вектора атаки при ошибке проектирования), то как минимум затягивается (очень и очень надолго), т.е. вызывает подозрение у всех участников контракта. Т.е. кроме сомнительного результата, он еще и рискует доверием к нему как к честному майнеру.

            • 0
              Del
              • 0
                Однако если хоть одна сторона откажется сообщить своё начальное число, то сервис даёт сбой.

                А нельзя просто выкидывать из участия тех, кто не раскрыл число? Или тогда появляется возможность манипулирования через кучу аккаунтов и раскрытием определённого их числа?

                • 0
                  у тех кто не раскрыл число забирается депозит, размер депозита должен подбираться так что бы нарушение правил было экономически нецелесообразным. Честно говоря эта тема ОЧЕНЬ подробна разжевана в соответствующих кругах, но да, с переводами на русский по теме эфира слабовато пока положение, по крайней мере то что мне попадалось.
                  • 0

                    Те кто не раскрыл свое число должны точно определяться. Транзакция может зависнуть в мемпуле и на это тоже можно повлиять, повышая стоимость газа и заливая в сеть новые транзакции.

                  • +2
                    >По словам основателей платформы, это превращает систему во «всемирный суперкомпьютер»
                    Им бы хотелось но нет. Каждый майнер выполняет все транзакции сам, все параллельно делают одно и тоже. 10 майнеров или 1000 — вычислительная мощность сети не меняется. Вы не можете загрузить код который не сможет выполнить одна нода (точнее можете но либо ноды его отбросят либо вы потратите кучу бабла и вся сеть слегка встанет) То есть распределенных вычислений в эфире нет в принципе. И вряд ли будут при текущей схеме оплаты газом. Она собственно и введена для того что бы не заморачиваться на проблему тьюринга и сделать ресурсоемкие вычисления дорогими.
                    • 0
                      Однако ECDSA нельзя использовать в Signidice, поскольку контора может манипулировать входными параметрами (в частности, параметром k) и так влиять на получающуюся в результате подпись.

                      Можно её использовать… Всё дело в том, как именно...


                      … эта подпись затем используется для генерации случайного числа.

                      Если у вас есть еще один (второй) seed и энтропия его достаточно высока (пусть даже от urandom), даже простейшего миксина с этим вторым рандом НО уже после получения смарт-контракта от первой даже и "неблагонадежной" конторы будет достаточно, чтобы манипуляции этой конторы (не знающей заранее второй seed) не смогли оказать никакого предсказуемого влияния на конечный результат.


                      Т. е. грубо алгоритм выглядит так:


                      1. Игроком генерируется случайный Pseed, но не публикуется, а подписывается его приватным ключом, после чего эта подпись Ps(Pseed) вместе со ставкой вызывает смарт-контракт.
                      2. ...
                      3. … все как в схеме выше ...
                      4. ...
                      5. Игрок публикует свой Pseed, который:
                        5.а. во первых, проверяется с помощью известного открытого ключа игрока и его ранее опубликованной подписью Ps(Pseed).
                        5.б. во вторых "замешивается", например AES-упаковкой, с подписью полученной от смарт-контракта, в результате создавая реальное случайное число.
                        5.в. подшивается к следующей транзакции (в качестве прува всей игры).

                      Т.е. это вовсе НЕ от алгоритма подписи (ECDSA, RSA, etc) собственно зависит, а от способа передачи информации от всех участвующих сторон, в идеальном случае — неизвестной ни одной из сторон до конца (до конечного опубликования).


                      Все остальные варианты от лукавого страдают тем же, что и в той ошибке от DAO.Casino, если не сейчас, то несколько позже, когда сложность алгоритма упадёт и/или появится какой-нибудь интересный/реализуемый вектор атаки.

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.