ТехволнаИскусственный интеллект за полчаса разгадал криптографическую тайну, мучившую экспертов четверть века
Специалисты компании Anthropic применили внутреннюю версию своего ИИ-ассистента Claude, чтобы раскрыть происхождение чисел, более 25 лет остававшихся головной болью для криптографов. Речь идёт о 160-битных начальных значениях, на основе которых в конце девяностых выбирали параметры для пяти эллиптических кривых NIST — P-192, P-224, P-256, P-384 и P-521. Модель справилась с задачей менее чем за тридцать минут.
Эти числа когда-то передало Агентство национальной безопасности США, но метод их получения никогда не объясняло. Отсутствие прозрачности десятилетиями питало подозрения: многие допускали, что значения могли быть специально подобраны, чтобы создать скрытую уязвимость или дать АНБ неизвестное другим преимущество. Одно время даже всерьёз обсуждалась шуточная версия о пропущенной через хеш-функцию фразе.
Claude пошёл иным путём. Вместо гадания о намерениях он попытался реконструировать, какой программный код конца 1990-х годов мог оставить узнаваемый математический след в опубликованных данных. Этот след привёл к lrand48 — старому генератору псевдослучайных чисел из стандартных библиотек языка C.
Восстановленная схема оказалась на удивление простой и бытовой. Программа запускала lrand48, используя в качестве затравки метку времени Unix, после чего последовательно генерировала 20-байтовые варианты и проверяла их пригодность для будущей кривой. Для кривой P-256, например, генератор стартовал с отметки 16 августа 1997 года, а стандартизированное значение было найдено после перебора 1842 кандидатов.
Искусственный интеллект сначала заметил характерный рисунок в битах опубликованных чисел, затем восстановил внутреннее состояние генератора и прокрутил его назад. Для всех пяти простых кривых NIST получились даты в промежутке между маем 1997-го и апрелем 1998 года. Тот же самый механизм объяснил происхождение ещё пяти значений из стандарта ANSI X9.62.
Восстановленные состояния генератора заново выдают все 160 бит исходных чисел, что практически исключает случайное совпадение. Это открытие не служит математическим доказательством того, что при выборе кривых никто не пытался добиться скрытого свойства. Однако версия о заранее подготовленной закладке стала гораздо менее правдоподобной.
Исследователи получили простой и воспроизводимый способ появления чисел, которые раньше казались произвольными и подозрительными. Несколько вопросов всё же остались без ответа. Генератор иногда пропускал кандидатов, которые тоже подходили по известным критериям, и причину этого исследователи пока не нашли.
Также не удалось восстановить начальное значение для кривой B-163. Claude объяснил происхождение базовой точки P-192 и нескольких кривых ANSI, но выбор базовых точек для P-224, P-256, P-384 и P-521 пока остаётся загадкой. На практическую безопасность алгоритма ECDSA находка никак не влияет.
Менять ключи или сами алгоритмы не требуется. За разгадку происхождения чисел ранее было назначено вознаграждение в размере 36 864 долларов. После решения задачи всю сумму решили передать некоммерческой организации Internet Security Research Group.
