Claude раскрыл происхождение seed эллиптических кривых NIST

Подробно

Что именно нашёл Claude в параметрах кривых NIST?

В октябре 2026 года сотрудник Anthropic поставил задачу внутренней исследовательской модели Claude. Название и версия модели не раскрываются. Прежнюю подсказку о якобы использованной шуточной фразе модели при этом не сообщили. По утверждению Anthropic, происхождение пяти seed удалось найти менее чем за полчаса.

Выяснилось, что seed пяти NIST-кривых над простыми полями не были хешами фраз. Их байты оказались выходом 48-битного линейного конгруэнтного генератора семейства drand48/lrand48, который инициализировали функцией srand48 значением Unix timestamp. Каждой кривой соответствует свой запуск генератора:

• P-192 - запуск 18.05.1997 в 14:45:34 UTC, опубликованный seed оказался кандидатом №139;
• P-521 - 08.08.1997 в 01:12:04 UTC, кандидат №1136;
• P-256 - 16.08.1997 в 01:52:34 UTC, кандидат №1842;
• P-384 - 30.08.1997 в 14:50:08 UTC, кандидат №2688;
• P-224 - 03.04.1998 в 12:52:07 UTC, кандидат №7026.

Та же закономерность обнаружилась у пяти примерных prime-кривых стандарта ANSI X9.62: prime239v1, prime239v2, prime239v3, prime192v2 и prime192v3. Всего восстановлено десять seed из нескольких запусков генератора. Над исследованием работали сотрудники Anthropic John Wood, Henry de Valence, Ava Howell, Zack Voase, Lucy Sweet, Amir Omidi, Paul Crowley, Iain McGinniss, Nicholas Carlini и Steve Weis.

Откуда взялась загадка seed кривых NIST?

По свидетельству криптографа Альфреда Менезеса, осенью 1997 года seed для ANSI X9.62 передал ему Джерри Солинас, представлявший NSA на заседаниях по стандартизации. Был ли Солинас их непосредственным автором, Менезес не знал. 27 января 2000 года NIST опубликовал стандарт FIPS 186-2 с ECDSA и набором рекомендуемых кривых. Seed в нём были приведены, но выбор их исходных значений не объяснялся.

В 2015 году в переписке с Дэниелом Бернштейном Солинас по памяти утверждал, что seed получали хешированием SHA-1 текста шуточного сообщения, возможно со счётчиком, а точный текст и архивы утрачены. Сообщение он вспоминал примерно так:

«Дайте Бобу и Джерри прибавку» или «Боб и Джерри рулят»

Теперь ясно, что эта подсказка была ошибочной. В том же 2015 году Нил Коблиц и Альфред Менезес опубликовали анализ споров вокруг NSA, ECC и происхождения параметров. 5 октября 2023 года Филиппо Вальсорда объявил вознаграждение за восстановление происхождения пяти NIST P-seed.

Как работала схема генерации seed через lrand48?

Программа вызывала srand48(timestamp) и брала старший байт каждого следующего 48-битного состояния генератора, то есть lrand48() >> 23 или эквивалентное (int)(drand48() * 256). Двадцать таких байтов составляли одного кандидата в seed. Затем по стандартной процедуре ANSI X9.62/NIST из хеша seed вычислялся коэффициент b кривой, и кандидаты перебирались, пока не находилась подходящая кривая.

Anthropic в своём тексте пишет о lrand48, Вальсорда - о drand48. Противоречия здесь нет: обе функции работают на одном POSIX-генераторе и дают одинаковый старший байт состояния.

Как модель восстановила происхождение seed?

Модель проверила 34 сочетания генераторов и способов извлечения битов. Зацепкой стало то, что в 20 словах четырёх seed отсутствовал старший бит. Anthropic оценивает вероятность такого совпадения в 1/5810.

Для четырёх seed состояние генератора восстановили перебором 2^17 скрытых битов первого слова с проверкой следующих слов. Для усечённых выходов prime-кривых применили восстановление состояния линейного конгруэнтного генератора с помощью алгоритма редукции решёток LLL. Затем генератор прокрутили назад до состояния сразу после srand48, у которого младшие 16 бит равны 0x330E. Само такое совпадение встречается раз в 65 536 состояний. Но у всех десяти prime-seed полученные 32-битные значения к тому же оказались Unix-метками времени с мая 1997 по апрель 1998 года.

Anthropic также воспроизвела seed четырёх двоичных кривых NIST: B-233, B-283, B-409 и B-571. Их состояния напрямую читаются как даты февраля 1984 года, а после удвоения timestamp дают последовательные моменты 17.04.1998 года: 15:24:18, 15:27:44, 15:30:18 и 15:32:08 UTC. Версию о том, что исходная программа делила время пополам, авторы называют предположением.

Кроме того, удалось найти происхождение базовой точки G у P-192 и пяти примерных ANSI-кривых, созданных в мае 1997 года. Для них использовался генератор из пакета длинной арифметики FreeLIP Арьена Ленстры, код которого был и в ранних версиях библиотеки NTL Виктора Шупа. Генератор инициализировали небольшим целым числом: 20000 для P-192, 20420, 20507 и 20509 для prime239v1-v3, 20512 и 20517 для prime192v2 и prime192v3. Затем отбрасывали семь выходов, собирали x-координату из 26-битных выходов по модулю p и продолжали, пока x не соответствовал точке на кривой.

Anthropic опубликовала короткий код на Python, который воспроизводит пять NIST P-seed, пять ANSI prime-seed и четыре binary-seed. Код передан в общественное достояние по лицензии CC0 1.0.

Кто проверил результат и кто получит вознаграждение?

Организатор вознаграждения Филиппо Вальсорда независимо переписал алгоритм на Go и опубликовал код на GitHub.

«Я повторно реализовал алгоритм на Go, чтобы проверить утверждение», - написал Вальсорда.

Техническое издание CellCog также сообщило, что запустило код Anthropic и получило значения, совпадающие с FIPS 186-2 для пяти P-кривых и четырёх binary-кривых. Пять ANSI-кривых издание не проверяло, так как у него не было текста стандарта.

Команда Anthropic подала заявку на полное вознаграждение 15 октября 2026 года в 01:07:51 UTC (04:07:51 по Москве). Базовая сумма составляла 12 288 долларов и утраивалась при передаче американской благотворительной организации категории 501(c)(3). Команда выбрала Internet Security Research Group, некоммерческую организацию - оператора Let's Encrypt, поэтому пожертвование составит 36 864 доллара.

Есть ли бэкдор в кривой NIST P-256?

Сама находка ничего не ломает. Seed - не закрытый ключ пользователя: из его хеша лишь вычисляется коэффициент b кривой. Раскрытие происхождения seed не позволяет подделывать подписи и не ослабляет уже созданные ключи. Речь идёт о доменных параметрах стандартизованных кривых, которые применяются не только в ECDSA.

«Это не криптографический взлом, новая атака или слабость кривых ECDSA», - говорится в заявлении Anthropic.

Компания считает воспроизводимое происхождение seed аргументом против гипотезы о намеренно подобранной слабой кривой. Вальсорда приводит расчёт: даже если NSA могла выбрать любой timestamp 1997-1998 годов и одного из первых 16 кандидатов с простым порядком, это давало лишь около 30 бит свободы. Для гипотетической техники выбора слабой кривой, которую описывали Бернштейн и Ланге, нужно примерно 70 бит.

«Недостаточно, чтобы намеренно нацелиться на гипотетический малый класс слабых кривых; недостаточно, чтобы встроить NOBUS-бэкдор», - оценивает Вальсорда.

По его мнению, находка усиливает доверие к кривым NIST. С учётом детерминированных и hedged-вариантов ECDSA, формально проверенных реализаций арифметики и полных формул сложения он теперь лично рекомендовал бы NIST-кривые вместо Curve25519, Ed25519 и X25519. При этом он отмечает, что классические кривые будут постепенно уступать место постквантовым подписям.

Вывод об отсутствии закладки - вероятностная оценка, а не математическое доказательство. Официальной реакции NIST или NSA на публикацию найти не удалось. Действующий стандарт FIPS 186-5 по-прежнему включает ECDSA, рекомендуемые кривые определены в SP 800-186. Двоичные кривые там объявлены устаревающими, и NIST настоятельно рекомендует prime-кривые.

Что в происхождении кривых NIST осталось необъяснённым?

Загадка решена не полностью. Seed двоичной кривой B-163 восстановить не удалось: он не соответствует ни одному из проверенных вариантов. Происхождение базовых точек P-224, P-256, P-384, P-521 и двоичных кривых по-прежнему неизвестно.

Открытым остаётся и вопрос, почему пропускались часть подходящих кандидатов. Для P-256 кандидат №876 тоже давал кривую нужного размера с простым порядком, но был пропущен до выбора №1842. Для P-224 пропущены пригодные кандидаты №777, №1485 и №5736. Вальсорда выявил один дополнительный критерий: кандидат отвергался, если битовая длина порядка кривой n превышала битовую длину поля p. Но даже с ним подходящих кандидатов остаётся примерно вдвое больше, чем опубликовано. Обсуждаются версии о ещё одном критерии, о повторном использовании того же генератора при проверке или об ошибке в старом коде, однако ни одна не подтверждена.

Публикация Anthropic - корпоративный исследовательский отчёт, а не рецензируемая статья. Время работы, число запросов к модели и объём участия людей независимо проверить нельзя. Название и версия модели не раскрыты, о её доступности и условиях доступа не объявлено.