Claude за полчаса раскрыл тайну кривых NIST

Anthropic 16 октября рассказала, что её внутренняя исследовательская модель Claude выяснила происхождение «сидов» эллиптических кривых NIST. Это числа, из которых построены кривые P-256 и другие, на них держатся цифровые подписи ECDSA в браузерах, банках и мессенджерах. Вопрос оставался открытым около 25 лет, а модели на решение понадобилось меньше получаса.

NIST утвердил ECDSA в 2000 году в стандарте FIPS 186-2. Коэффициенты кривых получали хешированием опубликованных сидов, а сами сиды предоставило АНБ без объяснений. Из-за этого в криптосообществе годами обсуждали, не спрятан ли в кривых бэкдор.

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

Оказалось, что сиды кривых P-192, P-224, P-256, P-384 и P-521 вообще не результат хеш-функции. Их выдал обычный генератор псевдослучайных чисел lrand48 из стандартной библиотеки языка C, запущенный от метки времени Unix. Для P-256 генератор прокрутили 1842 раза.

Claude сначала проверил выходы генераторов 1990-х годов в 34 комбинациях. Затем модель заметила, что старшие биты некоторых сидов всегда равны нулю, а это типичный след lrand48. Скрытое состояние генератора она восстановила алгоритмом LLL, который ищет короткие векторы в решётках.

Метки времени для кривых над простыми полями приходятся на период с мая 1997 по апрель 1998 года. У бинарных кривых даты указывают на февраль 1984-го, но после удвоения дают 17 апреля 1998 года. Авторы предполагают, что программа «уполовинила часы». Заодно модель нашла источник базовых точек для P-192 и пяти кривых стандарта ANSI X9.62: генератор из пакета FreeLIP математика Арьена Ленстры.

Что это значит для безопасности

«Это не взлом криптографии, не новая атака и не слабость кривых ECDSA», — подчёркивают в Anthropic. Наоборот, простой и воспроизводимый способ получения сидов делает версию о бэкдоре гораздо менее правдоподобной. Обновлять что-либо пользователям не нужно.

Прежние догадки не подтвердились. Многолетний сотрудник АНБ Джерри Солинас, умерший в 2023 году, считал, что сиды получены из хеша шуточной фразы. В 2015 году он писал, что если исходные данные и существуют, то «лежат на жёстком диске рядом с Ковчегом Завета».

Часть загадки осталась. Не объяснены сид кривой B-163 и базовые точки P-224, P-256, P-384, P-521 и бинарных кривых. Награду за разгадку, $36 864, организовал криптограф Филиппо Валсорда. Anthropic передаст её Internet Security Research Group, которая управляет центром сертификации Let’s Encrypt.

Источники: Anthropic — исследование происхождения кривых ECDSA