Уязвимость генератора псевдослучайных чисел в Bitcoin +27



Приватные Биткоин-ключи — это целочисленное значение от 1 до 115792089237316195423570985008687907852837564279074904382605163141518161494337 или в HEX 1 до 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141. В главной сети Биткоина существуют адреса начинающиеся на 1: compressed, uncompressed; адреса на 3: SigScript и обратно совместимые с SegWit, а так же нативные SegWit адреса начинающиеся на bc1. К тому же есть уже порядка семидесяти форков, имеющие другие префиксы, но те же корни что и основного Биткоина.

Биткоин-адреса рассчитываются криптографической функцией подписи ECDSA ( ) основанной на эллиптической кривой.

Итак, рассмотрим генерацию Биткоин-адреса из приватного ключа.

Закрытый ключ d — число
Открытый ключ Q — точка эллиптической кривой, равная dG,
где G — базовая точка кривой.

  • Для подписи выбирается случайное число k, в диапазоне [1, n-1].
  • Вычисляется точка кривой (x1,y1) = k*G
  • Вычисляется r = x1 mod N, где N — порядок кривой.
  • Вычисляется s = k-1(H(m)+rd) mod N, где k-1 — число, обратное по модулю N к k.
  • H(m) — хэш подписываемого сообщения.

image

Подписью является пара (r,s).

Переменная «k» рандомная и получается в алгоритме ECDSA из стандартных библиотек операционной системы.

Таким образом, во всей функции можно повлиять только на эту переменную. Что даёт два вектора атаки:

  1. заложенная уязвимость в псевдослучайное число
  2. и вселенское везение при котором случайное число выпадает дважды


Атака генератора псевдослучайных чисел


Первым эту проблему исследовал и опубликовал Nils Schneider в 28 января 2013 на своей личной странице. Но проблема сохранилась и более того, приобрела новый масштаб.

Программная атака на ГПСЧ подразделяется на три типа:
Прямая криптографическая атака основанная на анализе выходных данных алгоритма.

Атаки, основанные на входных данных, могут быть разделены на атаки с известными входными данными, атаки с воспроизводимыми входными данными и атаки на избранные входные данные.

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

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

К программным уязвимостям также относится слабая генерация псевдослучайных чисел в отдельных библиотеках. Таких как SSL, OpenSSL, некоторые библиотеки Java, JavaScript и т.д. Подробные материалы неоднократно описывались в периодических изданиях по взлому и со временем становились примерами в учебниках криптографии.

Каков масштаб угрозы для Биткоина?


Имея полную Биткоин ноду, можно провести сравнение и группировку всех транзакций сети. Достаточно сравнить переменную «к» во всех транзакциях по каждому адресу и найти дублирующие.

Первый раз мы делали сверку в конце 2016 года, тогда база данных составляла более 210 миллионов адресов, транзакций с общим количеством более 170 миллионов адресов, а подписей 447 миллионов. Сканирование уязвимых адресов в десять потоков заняло неделю.

В итоге было найдено 1327 уязвимых адреса с одинаковыми подписями! Список адресов можно найти в конце статьи.

Это означает, что к этим адресам можно вычислить приватный ключ, а значит получить контроль над деньгами.

Самая крупная утечка произошла летом 2015 года. JavaScript кошелька Blockchain.info несколько часов выдавал одно и тот же значение переменной «к». Что привело к краже порядка 200 Биткоинов!

Если убрать человеческий фактор программных уязвимостей, вероятность совпадения примерно 0,000296868 %. Совсем не много, но очень бы не хотелось стать таким “счастливчиком” и потерять свои деньги.

Как с этим бороться ?


Как мы описывали выше, данная уязвимость работает только при отправке платежей и генерации одинаковой переменной “К”, как минимум на двух транзакциях. Следовательно, если не создавать исходящих транзакций или свести их количество к минимуму, то и угрозы нет ни какой. Такая идея давно реализована в Биткоин протоколе BIP 32 (Hierarchical Deterministic Wallets, HD wallet) Иерархический Детерминированный Кошелек.

Его идея заключается в том, что используется приватный ключ из которого можно получить бесконечную цепочку Биткоин-адресов. Для приема каждой отдельной транзакции можно использовать одноразовый адрес. При этом сумма баланса HD wallet — это сумма всех балансов цепочки адресов. А при исходящей транзакции, с этих адресов собираются монеты, составляя для каждого Биткоин-адреса одну исходящую транзакцию. Сдача будет направлена на новый Биткоин-адрес из цепочки адресов.

Такая схема работы значительно увеличивает безопасность и анонимность кошелька.

Ссылки:

[1] ECDSA?—?Application and Implementation Failures, Markus Schmid, UC SANTA BARBARA, CS 290G, FALL 2015.

[2] Nils Schneider: Recovering Bitcoin private keys using weak signatures from the blockchain, Blog entry, 28 January 2013.

[3] Private Key Recovery Combination Attacks

[4] Список уязвимых адресов и общий баланс

Вы можете помочь и перевести немного средств на развитие сайта



Комментарии (12):

  1. vics001
    /#19384422

    Вроде как все известные кошельки теперь возвращают «остаток» на новый приватный ключ, то есть input не используется в качестве output. Правильно я понимаю, что это и есть защита от атаки?

    • MBoyarov
      /#19384534

      Да, всё верно. Практически все современные кошельки клиентов используют HD wallet. Т.е. каждый раз создают новые адреса из одного xpub ключа. Это как раз и сделано для предотвращения этой уязвимости и для большей безопасности владельца. Но до сих пор ещё очень много обычных ключей в приложениях и в старых кошельках.

      PS: Мы поставили блокчейн на новое сканирование. Результаты исследования позже обновим.

  2. unxed
    /#19384466

    Вот читаешь такой заголовок в духе «в биткойне дыра», и паника сразу, пульс подскакивает, уже думаешь, куда выводить и по какому курсу, а, нет, как обычно, чисто академическая уязвимость в устаревших кошельках, выдыхаем, прячем валерьянку обратно в аптечку, планета вновь понеслась по орбите, хабр торт!

    • shalm
      /#19384492

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

    • TimsTims
      /#19384596 / +1

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

    • Chugumoto
      /#19389010

      ага. а я подумал что из-за этого цена упала чуть.
      самое интересное, что для фулноды и системные требования для такого анализа уже нехилые нужны. ну помимо дискового пространства. помню как-то пытался парсером одним пройтись — 32гб озу было мало…

      • MBoyarov
        /#19389262

        В последней версии Биткоин ноды 0.17, базу очень здорово оптимизировали и она стала 180GB+ вместо 220GB. Но что бы сделать такой анализ, вам нужно распарсить необходимые поля. Для этого потребуется ещё примерно 500GB жесткого диска.
        В документации к ноде написано о минимум 2GB ОЗУ для запуска, но ещё надо на парсер и базу данных.

        • Chugumoto
          /#19389606

          О__О ну я парсер юзал, который в оперативке все держал… а именно хдд юзался или ссд? ну что на неделю растянулся анализ

          • MBoyarov
            /#19390022

            Тогда был Raid-0 массив из HDD. Сейчас SSD массив. Новые испытания запустим на следующей недели, потому что сменили базу данных на более быструю.
            Мы параллельно разрабатываем биткоин-эксплорер с поддержкой SegWit и прием платежей для интернет магазинов.

      • unxed
        /#19389814

        Цена упала из-за легалайза в нескольких странах подряд, надо полагать. Всё-таки чёрные рынки — одно из существенных практических применений битков (вы же не считаете хранение в них денег действием достаточно разумным, чтобы считаться практическим применением?:).

  3. orignal
    /#19385412

    >Достаточно сравнить переменную «к» во всех транзакциях по каждому адресу и найти дублирующие.

    Может быть все таки «r», а не «k»?

  4. MBoyarov
    /#19390034

    Готовлю новый материал по BrainWallet. Тема не новая, но собрана интересная статистика из 18к+ приватных ключей.