Суть разгадки: от хеша к lrand48
Долгие годы криптографическое сообщество подозревало, что параметры NIST P-192, P-224, P-256, P-384 и P-521 содержат заложенные NSA бэкдоры, так как происхождение их «семян» (seed) оставалось загадкой. Claude опроверг эту теорию: семена не являются результатом криптографического хеширования или сложного алгоритма. Они — прямой вывод библиотеки C-функции lrand48 (линейный конгруэнтный генератор), инициализированной Unix-временем.
Для получения одного 160-битного семени генератор делал тысячи итераций. Например, для P-256 потребовалось 1 842 итерации. Вероятность случайного совпадения 160 бит при 32-битном семени и индексе практически равна нулю, что подтверждает достоверность находки.
Методология: как AI нашел паттерн
Anthropic отказалась от поиска по слухам (например, о фразе «Give Bob and Jerry a raise») и применила системный анализ. Claude написал сканер, проверяющий 34 комбинации генераторов 1990-х годов. Ключевым индикатором стало то, что старшие биты некоторых семян были нулевыми — характерный признак lrand48, возвращающего только старшие 31 бит из 48-битного состояния.
Для восстановления скрытых битов Claude использовал алгоритм базисной редукции LLL (Lenstra–Lenstra–Lovász), решив задачу решеток. Это позволило восстановить внутреннее состояние PRNG для всех 10 семян (5 NIST + 5 ANSI X9.62).
Ключевые метрики и даты
| Параметр | Значение / Детали |
|---|---|
| Время решения | Менее 30 минут |
| Итераций для P-256 | 1 842 |
| Вероятность совпадения | ~1/5 810 (для паттерна старших битов); 0 для 160-битного совпадения |
| Диапазон дат (Unix-таймстампы) | Май 1997 – Апрель 1998 (для кривых над простыми полями) |
| Алгоритм восстановления | LLL (Lenstra–Lenstra–Lovász) basis reduction |
| Статус безопасности | Нет бэкдоров; параметры воспроизводимы |
Почему это важно для индустрии
Результат снимает главные подозрения в адрес стандарта FIPS 186-2. Если бы семена были сгенерированы криптографически стойким алгоритмом с секретным ключом, это могло бы указывать на намеренное ослабление. Использование простого srand48 с таймстампом означает, что параметры были выбраны случайно и прозрачно. Любой исследователь может воспроизвести процесс, запустив тот же PRNG с известной датой.
Кроме того, Claude нашел происхождение базовых точек (base points) для шести кривых, сгенерированных в мае 1997 года, связав их с генератором случайных чисел из библиотеки FreeLIP Арена Ленстры. Это закрывает еще один вопрос о происхождении параметров, оставшийся открытым с момента публикации стандарта в 2000 году.
Источник: Anthropic ↗