Сиды кривых NIST разгаданы: 5 мифов о ECDSA

В течение двадцати пяти лет сиды кривых ECDSA от NIST были самым близким к нерешённому «глухарю» в прикладной криптографии. Пять на вид случайных 160-битных значений, переданных NIST от АНБ без единого объяснения, лежали в основе подписей всего: от ваших TLS-соединений до транзакций Bitcoin. На этой неделе дело закрыто, и ответ почти обидный: сиды были выводом генератора lrand48() из стандартной библиотеки C, засеянного Unix-временем 1997 и 1998 годов. И всё. Никакого хеша секретной фразы, никакой экзотической механики — srand48(time(NULL)), именно тот шаблон, который каждый курс по безопасности велит никогда не использовать.

Открытие сделала исследовательская модель Anthropic, которую любопытный сотрудник направил на эту задачу. Она распознала статистическую сигнатуру линейного конгруэнтного генератора 90-х в опубликованных константах и прогнала состояние назад, пока не вышла на календарные даты. Я достаточно лет аудитировал криптографические системы, чтобы понимать важность этого — не потому, что кривые взломаны (они не взломаны), а потому, что это разрушает несколько вещей, в которые наша индустрия уверенно верила. Разберём мифы по одному.

Миф 1: непонятные константы означают скрытый бэкдор

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

Неудобная правда для любителей конспирологии, и я сам иногда грешу этим: непонятное обычно означает недокументированное, а не злонамеренное. Реальный процесс генерации выглядел так: разработчик запускал небольшую программу на C, позволял стандартному PRNG засеяться от настенных часов и брал первого кандидата, который давал пригодную кривую. Опубликованное зерно P-256 — это кандидат номер 1 842 из запуска, стартовавшего в 1:52 ночи 16 августа 1997 года. Так не работает агентство, подкладывающее теоретико-числовую ловушку. Так работает инженер в час ночи, который гоняет цикл, пока не выдаст что-нибудь годное.

Я видел этот паттерн в разборах инцидентов чаще, чем могу сосчитать. Загадочное значение в конфиге, недокументированная магическая константа, шаг деплоя, который никто не может объяснить, — а постмортем показывает, что это было разумное на тот момент решение уставшего инженера, которое так и не записали. Главный грех АНБ здесь был не в том, что они подкинули бэкдор в кривые. Он в том, что они отправили криптографические константы всему миру без README.

Миф 2: метод генерации доказывает честность отбора

Теперь перегиб в другую сторону. Многие комментарии на этой неделе восприняли «это же просто временные метки» как полное оправдание. Это не так, и сами исследователи аккуратно это оговаривают. Знание того, как генерировались кандидаты, ничего не говорит о том, как отбирались итоговые кривые, а отбор шёл месяцами, с мая 1997 по апрель 1998 года.

Доказательства работают в обе стороны. В запуске для P-256 кандидат 876 тоже дал простую кривую нужного порядка, построенную с теми же параметрами, — и его пропустили. Опубликованной стала кривая 1 842. В запуске для P-224 отбросили три жизнеспособные кривые, в запусках ANSI X9.62 — ещё семь. Мы видим полную историю отброшенных кандидатов не целиком, а только те, что восстанавливаются по записанным запускам. Если кто-то хотел кривую с конкретным редким свойством, он мог в принципе перебирать временные метки, пока не выпадет нужная, а потом молчать о самой метке. «Сделать и промолчать» всегда было вариантом.

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

Зерна получили так, как сделал бы аспирант: стандартный PRNG и системные часы. Скандал был никогда не в математике. Он был в отсутствии документации.

Миф 3: старые слабые PRNG безвредны, если использовать их один раз

Этот миф должен заставить вздрогнуть каждого инженера, который хоть раз писал srand(time(NULL)). Двадцатипятилетняя завеса тайны существовала из-за одного конструктивного свойства lrand48(): он выдаёт собственную структуру. Генератор возвращает только старшие 31 бит 48-битного состояния, поэтому в его выходных словах старший бит всегда нулевой. Если записать последовательность 32-битными словами, у четырёх из десяти зерен для бинарных кривых старшие биты нулевые на протяжении двадцати подряд слов — событие с вероятностью около одного к 58 000 при равномерном распределении. Сигнатура была видна невооружённым глазом любому, кто догадался посмотреть.

Дальше атака на удивление дешёвая. Чтобы восстановить состояние для бинарных кривых, берём первое выходное слово, перебираем 2^17 скрытых младших бит и проверяем, совпадают ли следующие четыре слова. Это несколько миллисекунд вычислений. Для простых кривых зерна раскрывали меньше бит на выход, поэтому восстановление состояния потребовало классической атаки на усечённый LCG: моделируем задачу как решётку и применяем сокращение базиса LLL. Буквально учебная задача. Раз состояние известно, LCG идёт назад так же легко, как вперёд, поэтому его откручивают, пока не появится форма инициализации srand48 — младшие биты равны 0x330E — и считывают временную метку, которой он был засеян.

# The whole mystery, reproduced
from datetime import datetime, timezone
def unix(when):
return int(datetime.fromisoformat(when).replace(tzinfo=timezone.utc).timestamp())
def candidate(t, n, per, shift, width):
x, out = (t << 16) | 0x330E, ""   # state set by srand48(t)
for i in range(per * n):
x = (0x5DEECE66D * x + 0xB) % 2**48   # one lrand48 step
if i >= per * (n - 1):
out += "%0*X" % (width, x >> shift)
return out
# P-256: run started 1997-08-16 01:52:34 UTC, candidate 1842
print(candidate(unix("1997-08-16 01:52:34"), 1842, 20, 40, 2))
# -> C49D360886E704936A6678E1139D26B7819F7E90  (the published NIST seed)

Урок выходит далеко за пределы стандартизирующих органов. Любое «случайно выглядящее» значение, которое вы выдаёте, — токены сессий, ID запросов, соль, имена файлов, — несёт отпечаток генератора, который его создал. Если это линейный конгруэнтный генератор или Mersenne Twister, нескольких выходов хватает, чтобы восстановить внутреннее состояние, и всё, что генерировалось до и после, становится предсказуемым. Одно использование двадцать пять лет назад, в файле, который должен был выглядеть как шум, было полностью инвертировано. Когда я ревьюю код, который использует некриптографические RNG для чего-либо, что злоумышленник может наблюдать, я теперь буду приводить именно эту историю.

Миф 4: константы «ничего не скрываю» никогда не были реальной защитой

Идея «ничего не скрываю» — выводить константы из чего-то очевидно невинного, например из цифр числа «пи», — нужна, чтобы ограничить степени свободы разработчика. Если я могу показать, что моя константа следует из публичной жёсткой процедуры, у меня не было места для контрабанды бэкдора. Зерна NIST провалили этот тест процедурно: процедура была секретной, так что границы степеней свободы были неизвестны. Но эта история вскрывает кое-что важное — даже когда тест «ничего не скрываю» работает, он слабее, чем мы делали вид.

Посмотрите, что на самом деле даёт «проверяемо случайное из временной метки». Временная метка для правдоподобного окна содержит около 31 бита энтропии. Любой — включая самого автора — может перебрать миллионы временных меток, сгенерировать миллионы кандидатов-кривых и опубликовать только ту, которая нужна, вместе с безобидно выглядящим зерном. Если кривые с секретной слабостью встречаются с частотой один на миллион, перебор меток найдёт одну за день. Зерно доказывает, откуда взялось число, и почти ничего не говорит о том, почему выбрана именно эта. То же относится и к схемам с хешем парольной фразы, поэтому слух о шутке Соллинаса тоже никогда не успокаивал до конца.

Более строгая современная практика — жёсткое построение кривых: берём наименьший коэффициент, удовлетворяющий публичному списку критериев безопасности, с правилами отбора, зафиксированными до начала поиска. Это философия, стоящая за Curve25519, и именно аргументы Дэна Бернштейна о жёсткости изменили то, как сообщество оценивает кривые. Реальная защита от злонамеренных констант никогда не состояла в красивой истории вывода. Она в минимизации пространства поиска, публикации критериев заранее и наличии достаточного числа независимых глаз на математике, чтобы скрытое свойство не могло оставаться скрытым. Аудит констант — это аудит процесса, который их отфильтровал. Поэтому нерешённые вопросы здесь (пропущенные кандидаты, необъяснённые базовые точки для P-256 и родственных кривых, всё ещё не идентифицированное зерно для B-163) стоит оставить открытыми в протоколе, а не прятать под ковёр в честь торжества.

Миф 5: LLM лишь пересказывают — оригинальный криптоанализ им не под силу

Этот миф бьёт сильнее всего, потому что я сам верил в его версию. Открытая задача оставалась нерешённой четверть века, несмотря на публичную премию в $36 864 и серьёзное внимание квалифицированных любителей. Несколько исследователей Anthropic сами гонялись за ней, шли по следу «хеша смешной фразы» и ничего не нашли. Потом внутренняя исследовательская модель, которой не передали слух, попробовала другой угол меньше чем за полчаса. Вместо того чтобы угадывать вход хеша, она спросила, какое ПО могло сгенерировать зерна, выдвинула гипотезу о PRNG из стандартной библиотеки C 90-х, написала сканер, проходивший по каждому зерну и проверявший 34 комбинации генератора и среза выходных битов, заметила паттерн нулевого старшего бита, применила атаку на решётке к усечённым выходам и прошла состояния назад до календарных дат.

Обратите внимание, что это за рабочий процесс. Это не припоминание — ни один обучающий документ не содержал ответа, потому что ответа нигде не было. Это генерация гипотез плюс использование инструментов плюс проверка, и именно такова реальная форма криптоаналитической работы. Модель даже проверяла собственную адекватность по ходу: не тестовая ли это среда, неужели такая очевидная вещь могла 25 лет остаться незамеченной, исключает ли совпадение 160-битное совпадение с 32-битного зерна? Такой самоскепсис я бы хотел видеть у человека-аналитика, и, честно говоря, некоторые люди-аналитики его пропускают. Мы уже какое-то время проверяем мифы о том, что эти модели делают на самом деле, и это чистый пример: LLM теперь могут выполнять многошаговое криминалистическое рассуждение над реальными артефактами, а не только над бенчмарками.

Честное возражение практиков касается происхождения. Модель не изобрела восстановление состояния LCG или LLL — она опирается на десятилетия опубликованного криптоанализа, авторов которого названы и не названы, и не может сказать, чьи статьи повлияли на её подход. Меня это беспокоит меньше, чем некоторых. Сканер, код проверки и скрипт воспроизведения публичны; люди в команде задали вопрос и подтвердили результат. Разделение труда стоит признать честно: машина дала неутомимый поиск гипотез, а люди — суждение и ответственность. Премия в $36 864 досталась Internet Security Research Group — достойный способ всё завершить.

Что это меняет для аудитов безопасности

Итак, что это значит для работающего инженера? Несколько конкретных сдвигов в том, как я буду подходить к аудитам. Во-первых, относиться к каждой магической константе в протоколе или кодовой базе как к криминалистическому артефакту, а не как к факту природы. Спрашивать, какой генератор мог её выдать, проверять структурные отпечатки — смещённые старшие биты, коррелированные последовательные слова LCG, восстановления состояния, правдоподобные по временным меткам, — прежде чем принимать ответ «это случайно». Инструменты для этого теперь доступны буквально каждому.

Во-вторых, если вы публикуете константы, публикуйте и генератор: исходный код, точные входные данные, точное окружение. «Проверяемо случайно» без воспроизводимого рецепта принесёт вам двадцать пять лет подозрений и премию на ваше наследие. В-третьих, продолжайте использовать P-256: находка повышает доверие к кривым, а не снижает его, а реальная модель угроз для эллиптических кривых — это квантовое железо, а не часы рабочей станции 1997 года. Но честно прочитайте открытые вопросы: необъяснённые базовые точки и пропущенные кандидаты — это хвосты, и зрелая работа с безопасностью означает держать их в учётных книгах.

Самый глубокий вывод касается институциональной памяти. Джерри Соллинас помнил шутку про прибавку зарплаты, которая оказалась неверной. Архивы, по его словам, скорее всего лежали на жёстком диске где-то рядом с Ковчегом Завета. Мы знаем правду сегодня только потому, что сам результат сохранил достаточно структуры, чтобы «признаться». Ваши системы прямо сейчас пишут собственные признания — в каждом ID, токене и константе, которые вы выпускаете. Позаботьтесь о том, чтобы они признавались в том, чем вы будете гордиться.