Anthropic нашла объяснение происхождению пяти кривых NIST

Специалисты компании Anthropic сумели разгадать криптографическую загадку, которая больше двадцати лет ставила в тупик исследователей по всему миру. Речь идёт о происхождении так называемых зёрен — исходных чисел, из которых генерируются параметры пяти стандартных эллиптических кривых, утверждённых Национальным институтом стандартов и технологий США (NIST). Эти кривые используются в алгоритме цифровой подписи ECDSA, включённом в американский стандарт FIPS 186-2 ещё в 2000 году, и от того, как именно выбирались их параметры, напрямую зависит доверие к безопасности всей схемы. Вопрос «почему выбрано именно это зерно» десятилетиями оставался без ответа, порождая конспирологические версии и вполне серьёзные подозрения в намеренно ослабленной криптографии.

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

Модель написала сканирующую программу, которая перебирала биты в опубликованных зёрнах и проверяла 34 комбинации различных генераторов и способов усечения выдачи. Выяснилось, что когда четыре зерна разбили на двадцать 32-битных целых чисел, старший бит у всех двадцати оказался нулевым. Это и стало уликой: след вёл к генератору lrand48. Он хранит внутри 48-битное целое, при каждом вызове умножает его на константу, прибавляет другую константу и оставляет младшие 48 бит как новое состояние, а на выход отдаёт только старшие 31 бит — из-за чего в 32-битном слове верхний бит всегда нулевой. Обнаружив этот характерный отпечаток, Claude применил алгоритм редукции решёток LLL, чтобы восстановить усечённые состояния, а затем занялся вопросом инициализации. Функция srand48 помещает входное значение в старшие 32 бита состояния, младшие 16 бит фиксирует константой 0x330E и запускает рекурсию. Обратный расчёт показал: источником инициализации служила метка времени Unix.

Все найденные моменты инициализации укладываются в промежуток с мая 1997 по апрель 1998 года. Иными словами, достаточно взять конкретное мгновение, превратить его в целое число, скормить генератору и особым образом извлечь результат — и на выходе получится ровно то самое зерно из стандарта. Для кривой P-256 это, например, 16 августа 1997 года, 01:52:34 по UTC: если запустить генератор от этой точки и взять 1842-й кандидат, получится последовательность, начинающаяся с C49D. Остальные четыре зерна также удалось соотнести с конкретными временными метками.

Любопытно, что многолетние догадки энтузиастов оказались ложными. Ещё в те годы один из причастных к созданию стандарта, Джерри Солинас, вспоминал, что зерно могли получить хешированием шутливой фразы про прибавку к зарплате для Боба и Джерри, и эта версия кочевала по статьям и форумам. Инженер Филиппо Вальсорда даже объявлял публичное вознаграждение за разгадку, но поиски ни к чему не привели. Теперь же результат Anthropic прошёл независимую проверку со стороны инициатора этого вознаграждения.

Сами исследователи признают, что картина восстановлена не полностью. Неясно, почему при создании стандарта пропускались некоторые кандидатные кривые, которые формально тоже подходили; остаётся открытым и вопрос о зерне для кривой B-163, а также о способе генерации базовых точек для части кривых. Тем не менее главный вывод обнадёживает: найденное объяснение не указывает на каких-либо скрытых уязвимостей, а значит, стандартными кривыми можно пользоваться без опасений. История эта примечательна ещё и тем, что задачу, над которой десятилетиями бились специалисты, решила машина — и решила, не имея на руках почти никаких подсказок.