Затравки кривых NIST оказались просто метками времени: Claude закрыл 25-летнюю загадку криптографии

Белое пятно возрастом 25 лет

ECDSA - самый распространённый стандарт подписи на эллиптических кривых. NIST принял кривые в 2000 году в FIPS 186-2, и коэффициент b каждой кривой выводится из хеша опубликованной 20-байтовой затравки. Затравки поступили от NSA без всяких пояснений. Коблиц и Менезес написали классическое резюме спора, "A Riddle Wrapped in an Enigma", а беспокойство было настолько реальным, что Валсорда объявил баунти за восстановление происхождения затравок. Лучшая версия принадлежала самому Джерри Солинасу (2015): он полагал, что затравки - хеш, возможно со счётчиком, шутливой фразы вроде "Give Bob and Jerry a raise". Солинас умер в 2023 году, архивов не сохранилось. На этом след остывал, пока сотрудник Anthropic не попросил внутреннюю исследовательскую модель восстановить метод генерации, не подсказывая ей слух.

Что именно нашла модель

Менее чем за полчаса, по словам Anthropic, модель выбрала другой угол: вместо перебора фраз она рассуждала о том, как должна была выглядеть программа генерации кривых из 1990-х. Старые генераторы из libc настолько слабы, что их выход узнаваем. Модель написала сканер, который скользил по каждой затравке побитно и проверял 34 комбинации генератора и среза выхода, и заметила: в четырёх из десяти затравок старший бит каждого 32-битного слова равен нулю. Случайно такое бывает с вероятностью 1 к 5810, и это отпечаток lrand48, который возвращает только 31 старший бит 48-битного состояния. Для этих затравок состояние восстанавливалось перебором всех 131 072 значений 17 скрытых бит с проверкой следующих четырёх слов. Для затравок простых кривых, где от каждого выхода оставалось меньше бит, восстановление состояния - учебниковая задача на решётки, и модель прогнала LLL-решатель по всем окнам. Пять затравок NIST и пять из ANSI X9.62 декодируются как lrand48() >> 23, и каждое восстановленное 48-битное состояние заново порождает все 160 бит своей затравки - случайно так не совпадает.

Метки времени - кульминация

Линейный конгруэнтный генератор крутится назад так же легко, как вперёд, поэтому каждое состояние откатили к виду инициализации srand48, где младшие 16 бит равны 0x330E. Такой вид встречается раз в 65 536 шагов, так что сам по себе он не доказательство. Доказательство - то, как читаются инициализации: для всех десяти затравок простых кривых это Unix-время между маем 1997 и апрелём 1998. Генератор засевали часами. Четыре инициализации бинарных кривых читаются как февраль 1984, а будучи удвоенными ложатся на 17 апреля 1998 - две недели спустя после прогона P-224, что намекает на поделённые пополам часы. В посте Anthropic есть короткий код воспроизведения и цитата из внутренних рассуждений модели, где она сначала проверяет, не в тестовой ли она среде, а потом заключает, что совпадение настоящее: десять независимых 160-битных совпадений из 32-битных затравок и маленьких индексов не бывают случайными.

Базовые точки - частично

Затравки не определяют базовую точку G каждой кривой, и ни одна базовая точка NIST раньше объяснена не была. Модель нашла, что шесть кривых, сгенерированных в мае 1997, - P-192 и пять примерных кривых ANSI X9.62 - берут базовые точки из генератора FreeLIP, пакета длинной арифметики Арьяна Ленстры; ранние версии NTL Виктора Шупа содержали тот же код. Рецепт: засеять генератор маленьким целым, отбросить семь выходов, затем пробовать 26-битные выходы по модулю p, пока один не попадёт на кривую. Восстановленные затравки генератора малы и идут почти подряд: 20000 для P-192, 20420, 20507 и 20509 для кривых prime239, 20512 и 20517 для prime192v2 и v3. Базовые точки P-224, P-256, P-384 и P-521, как и бинарных кривых NIST, объяснить не удалось.

Что остаётся открытым и что это меняет

Важны три хвоста. Первый - пропущенные кандидаты: опубликованная затравка P-256 - кандидат 1842 своего прогона, но кандидат 876 тоже даёт рабочую кривую, собранную так же, а прогон P-224 пропустил ещё три. Валсорда отмечает два недокументированных критерия отбраковки: один довольно понятен, второй пока ускользает. Второй хвост - пятая бинарная затравка B-163, которая не подходит ни под одну проверенную схему. Третий - необъяснённые базовые точки выше. Anthropic считает подбор ослабленных кривых неправдоподобным, потому что число пропусков мало, но честно оговаривает: по числам не видно, сколько всего было прогонов. Вывод для безопасности обратный пугающему: затравки получены обычным генератором от часов, воспроизвести их может любой, и пространства для закладки стало заметно меньше. Anthropic прямо пишет, что большинство исследователей кривым и так доверяли и ничего предпринимать не нужно.

Почему дневнику это интересно

Для меня тут важен метод, а не криптография. Все неудачные поиски людей шли за слухом: хешируй правильную фразу. Модель вместо этого атаковала порождающий процесс, и первая трещина оказалась статистическим артефактом, видимым глазом, если знать, куда смотреть: четыре затравки с нулевыми старшими битами. Процитированный момент, где модель перепроверяет собственную правдоподобность, - та часть агентской работы, которая редко доживает до пресс-релизов. И это редкий случай, когда у "ИИ-открытия" в безопасности есть полный чек: названные авторы, алгоритм, код воспроизведения, независимая реализация на Go от организатора баунти и честный список нерешённого. Именно такую планку стоит предъявлять каждому заголовку "ИИ открыл".