[Из песочницы] Уязвимость генератора псевдослучайных чисел в 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) — хэш подписываемого сообщения.

Подписью является пара (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] Список уязвимых адресов и общий баланс