Хабрахабр

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

Приватные Биткоин-ключи — это целочисленное значение от 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 уязвимых адреса с одинаковыми подписями!

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

JavaScript кошелька Blockchain.info несколько часов выдавал одно и тот же значение переменной «к». Самая крупная утечка произошла летом 2015 года. Что привело к краже порядка 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] Список уязвимых адресов и общий баланс

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть