Claude нашёл в сидах кривых NIST обычные метки времени

Сиды стандартных эллиптических кривых NIST много лет подозревали в закладке АНБ. Оказалось, что это не хеши шуточной фразы, как помнил их автор, а выход генератора lrand48 из библиотеки C, запущенного от системных часов в 1997–1998 годах. Так пишет Anthropic: внутренняя исследовательская модель Claude меньше чем за полчаса восстановила происхождение сидов P-192, P-224, P-256, P-384 и P-521.

Сид нужен вот зачем. В стандарте подписи FIPS 186-2, который NIST принял в 2000 году, для кривых над простыми и двоичными полями опубликован параметр seed, и из его хеша получается коэффициент b кривой. Сиды предоставило АНБ без каких-либо пояснений. У P-256, например, это просто строка C49D3608 86E70493 6A6678E1 139D26B7 819F7E90. Хеш защищает только тогда, когда понятно, откуда взялся сам сид. Если источник неизвестен, можно перебирать сиды, пока не выпадет кривая с нужным свойством. Anthropic подчёркивает, что взлома и новой атаки здесь нет и делать ничего не нужно. По её оценке, после находки версия о закладке стала куда менее правдоподобной.

Шутка, которой не было

Поиски до октября 2026 года шли по одной и той же наводке:

• осень 1997 года: по словам Альфреда Менезеса, главного автора ANSI X9.62, сиды ему передал Джерри Солинас из АНБ. Выбирал ли их Солинас сам, Менезес не знал (Saweis);
• 1999 год: X9.62 опубликован, и, по данным Saweis, на Usenet почти сразу спросили, откуда взялись сиды;
• 2000 год: NIST включает ECDSA в FIPS 186-2;
• 6 сентября 2014 года: Д. Дж. Бернстайн спрашивает Солинаса, откуда сид P-256. Тот, по данным Saweis, отвечает, что сиды получены хешированием (как ему помнилось, через SHA-1) шуточного сообщения, текста которого он не помнит;
• 2015 год: Солинас пишет, что сообщение было в духе «Give Bob and Jerry a raise» или «Bob and Jerry rule», код писал Боб Райтер, который тоже ничего не помнит, а архивы, если и сохранились, лежат «на жёстком диске рядом с Ковчегом Завета»;
• 2023 год: Солинас умирает. 12 октября 2023 года Schneier on Security пишет о премии в 12 тысяч долларов за восстановление сидов и называет возможную находку сокрушительным ударом по теории о злонамеренном выборе P-кривых;
• август 2024 года: по данным Saweis, Бернстайн и Ланге публикуют письма Солинаса в приложении C к работе «Safe curves for elliptic-curve cryptography»;
• октябрь 2026 года: сотрудник Anthropic просит внутреннюю модель выяснить, как получены сиды, и ничего не говорит ей про фразу.

Несколько сотрудников Anthropic и до этого искали фразу и ничего не нашли. Наводка оказалась ложной: ни один из найденных сидов вообще не выход хеш-функции.

Как узнали lrand48

Claude зашёл с другой стороны и стал прикидывать, как могла работать программа, которая генерировала кривые. Он предположил, что она брала числа из штатного генератора псевдослучайных чисел в библиотеках C 1990-х. Такие генераторы настолько слабы, что их выход можно узнать, а иногда и восстановить по нему внутреннее состояние. Claude написал сканер, который сдвигал окно по каждому сиду на один бит и проверял, не идут ли соседние куски подряд из генератора той эпохи. Всего он перебрал 34 комбинации генератора и нарезки выхода.

Зацепку дали старшие биты. Если записать сид как пять 32-битных слов, то у четырёх из десяти сидов старший бит нулевой во всех 20 словах. По расчёту Anthropic, случайно так бывает с вероятностью 1 к 5810. Так выглядит подпись lrand48: у этого линейного конгруэнтного генератора 48-битное состояние, а наружу он отдаёт только верхние 31 бит. Claude взял первое слово, перебрал все 2¹⁷ значений 17 скрытых битов и проверил, получаются ли из найденного состояния следующие четыре слова. Получились у всех четырёх сидов, и это двоичные кривые B-233, B-283, B-409 и B-571.

С простыми кривыми было сложнее: в каждый байт сида шло lrand48() >> 23, то есть от каждого выхода генератора оставалось только 8 бит. Восстановить состояние усечённого линейного конгруэнтного генератора можно на решётках, это учебная задача для алгоритма LLL (Ленстры, Ленстры и Ловаса). Какие биты состояния видны в сиде, Claude не знал, поэтому прогнал решатель по всем окнам. Одинаковый рисунок дали пять сидов NIST и ещё пять примеров кривых из ANSI X9.62. Каждое восстановленное 48-битное состояние воспроизводит все 160 бит своего сида, а случайно такое не совпадает. Модель и сама сначала засомневалась, не подсунули ли ей тест:

Hmm wait. Let me be skeptical: am I in some sort of simulated/test environment? … It’s verified by direct computation on my side: 160-bit match from a 32-bit seed + small index: no chance coincidences (10 × 160 bits). It’s real.

Даты в сидах

Такой генератор крутится назад так же легко, как вперёд. Claude откатывал состояние каждого сида, пока его младшие 16 бит не становились равны 0x330E. Именно такое состояние выставляет srand48 при инициализации. Само по себе совпадение ничего не доказывает: подходящее состояние встречается раз в 65 536 шагов. Но у всех десяти сидов простых кривых в этой точке оказалась Unix-метка времени в интервале с мая 1997 по апрель 1998 года:

• 15 мая 1997 года, 15:49:03: один запуск дал prime239v1, v2 и v3;
• 18 мая 1997 года: P-192 (кандидат 139), prime192v3 и prime192v2;
• 8 августа 1997 года: P-521;
• 16 августа 1997 года, 01:52:34: P-256 (кандидат 1842);
• 30 августа 1997 года: P-384;
• 3 апреля 1998 года: P-224 (кандидат 7026).

Каждый кандидат занимал 20 байт подряд из генератора, так что для P-256 программа выдала 1842 кандидата, прежде чем дошла до опубликованного. Метки двоичных кривых указывают на февраль 1984 года. Если их удвоить, получается 17 апреля 1998 года, четыре запуска с 15:24 до 15:32, через две недели после P-224. Anthropic предполагает, что программа могла делить показания часов пополам. По данным Saweis, Менезес вспоминал, что получил сиды осенью 1997 года. С датами P-224 и двоичных кривых это воспоминание не сходится.

Проверить всё это может любой: Anthropic выложила под лицензией CC0 короткий скрипт на Python, который по метке времени и номеру кандидата печатает все 14 сидов.

Базовые точки

У каждой кривой есть ещё базовая точка G, кратным которой является любой публичный ключ ECDSA. Сид её не определяет. Попутно Claude объяснил базовые точки шести кривых, сгенерированных в мае 1997 года: P-192 и пяти примеров из X9.62. Их дал генератор случайных чисел из FreeLIP, пакета длинной арифметики Арьена Ленстры (тот же код был в ранних версиях NTL Виктора Шоупа). Генератор инициализируют небольшим числом, выбрасывают семь выходов, из 26-битных выходов собирают кандидата в x-координату по модулю p и повторяют, пока x не окажется на кривой. Числа для инициализации: 20000 для P-192, 20420, 20507 и 20509 для prime239v1, v2 и v3, 20512 и 20517 для prime192v2 и v3. Каждой кривой хватило от одной до пяти попыток. Насколько известно Anthropic, ни одну базовую точку NIST раньше объяснить не удавалось. Точки P-224, P-256, P-384, P-521 и двоичных кривых в этот рецепт не укладываются, и откуда они взялись, пока неизвестно.

Пропущенные кандидаты

Не каждый 20-байтный кандидат даёт пригодную кривую, но некоторые пригодные почему-то пропустили. У P-256 опубликован кандидат 1842, хотя кандидат 876 из того же запуска тоже даёт кривую простого порядка нужного размера, построенную тем же способом. При генерации P-224 пропустили три таких кривых, в двух запусках для X9.62 ещё семь. По каким критериям отбирали кандидатов и было ли это намеренно, Anthropic не знает. По её логике, выбрать ослабленную кривую среди такого малого числа пропусков можно было бы, только если ослабленные кривые встречаются часто и находятся легко. Теоретически свойство можно было подобрать и перебором меток времени, но такое имело бы смысл только при намерении потом раскрыть метку как доказательство невинности. Сколько всего было запусков, по числам не видно. Сид B-163 не подошёл ни под одну проверенную схему.

Премию за сиды, 36 864 доллара, Anthropic передаст Internet Security Research Group. В благодарностях авторы упоминают Филиппо Вальсорду, который организовал сбор премии, и посмертно Солинаса, который с юмором относился к прозвищам «evil Internet meme» и «Yo La Tengo of NSA bogeymen».