ИИ разгадал 25-летнюю загадку кривых АНБ: что это значит для биткоина

Модель искусственного интеллекта Anthropic выяснила, откуда взялись необъяснённые «сиды» (начальные значения) для эллиптических кривых NIST, которые предоставило Агентство национальной безопасности США, — над этой загадкой криптографы бились около 25 лет. Согласно публикации Anthropic от 16 октября, числа, из которых выведены кривые P-192, P-224, P-256, P-384 и P-521, оказались вовсе не хешами секретной фразы, а результатом работы обычного генератора случайных чисел 1990-х, запущенного от системных часов.

В чём была загадка

• В 2000 году Национальный институт стандартов и технологий США (NIST) утвердил набор эллиптических кривых в стандарте цифровой подписи FIPS 186-2 (ECDSA). В частности, P-256 лежит в основе значительной доли современного зашифрованного веб-трафика и цифровых подписей.
• Каждую кривую выводили из опубликованного 20-байтного сида, хеш которого задавал один из параметров кривой. АНБ передало эти сиды в 1997 году, не объяснив, как их выбрали.
• После разоблачений Сноудена и истории с генератором Dual EC часть криптографов подозревала, что агентство могло перебирать сиды, пока не нашло кривую со слабостью, известной только ему.
• Самая известная версия принадлежала математику АНБ Джерри Солинасу: якобы сиды — это хеши шуточной фразы. Солинас умер в 2023 году, и в том же году криптоинженер Филиппо Вальсорда и другие объявили награду за разгадку.

Что нашёл Claude

• Сотрудник Anthropic попросил внутреннюю исследовательскую модель разобраться, не упоминая слухи о фразе. По словам компании, модель нашла ответ меньше чем за полчаса.
• Claude заметил, что в четырёх из десяти сидов старший бит каждого 32-битного слова равен нулю — Anthropic оценивает вероятность этого как 1 к 5810. Это «отпечаток» функции lrand48 из старых библиотек C.
• Восстановив внутреннее состояние генератора и прокрутив его назад, модель свела каждый сид кривых над простым полем к Unix-времени между маем 1997 и апрелем 1998 года. Сид P-256 — 1842-й 20-байтный кандидат из запуска, начатого 16 августа 1997 года в 01:52:34 UTC.
• Вальсорда говорит, что независимо воспроизвёл метод и подтвердил результат. Команда передала награду Internet Security Research Group — некоммерческой организации, стоящей за Let's Encrypt, — и сумма утроилась до $36 864.

Что-то сломано?

Нет. Anthropic подчёркивает, что это «не криптографический взлом, не новая атака и не слабость», и пользователям не нужно ничего делать иначе. Сид, полученный от генератора, запущенного от часов, который теперь может воспроизвести любой, оставляет гораздо меньше места для намеренных манипуляций. Открытые вопросы остаются: несколько пригодных кандидатов были пропущены (в том же запуске для P-256 пригодную кривую даёт и кандидат 876), сид бинарной кривой B-163 до сих пор не объяснён, как и выбор базовых точек для P-224, P-256, P-384 и P-521.

Почему биткоина это не касается

Биткоин, а позже и Ethereum, используют другую кривую — secp256k1. Её задают две небольшие фиксированные константы, так что настраивать почти нечего и спрятать слабость негде, как отмечает CoinDesk. Однако тот же предсказуемый генератор был бы катастрофой внутри кошелька: приватный ключ, созданный через lrand48, мог бы восстановить любой, кто примерно угадал время его создания. Именно поэтому кошельки используют криптографически стойкую случайность — см. наш материал о том, что такое аппаратный кошелёк.

Настоящая долгосрочная угроза для биткоина — квантовые вычисления: они могли бы вывести приватный ключ из раскрытого публичного независимо от кривой. На этой неделе Google сообщил о крупном шаге в снижении ошибок на чипе Willow (наш материал), а новый Quantum Alliance отслеживает монеты с раскрытыми ключами. Тем не менее ни одна существующая машина даже близко не способна взломать ключ биткоина.