Необъяснимые числа, стоящие за HTTPS
Криптография на эллиптических кривых (ECC) лежит в основе безопасных соединений, которые браузеры устанавливают с веб-сайтами, позволяя осуществлять критически важный обмен общим секретным ключом на виду у всех. Этот математический подвиг опирается на эллиптические кривые, где определенные операции вычислительно тривиальны для выполнения, но практически невозможны для обращения. Кривая P-256, стандарт, опубликованный NIST в 2000 году, стала краеугольным камнем TLS 1.3 и HTTPS, обязательным практически для каждого приложения.
Более двух десятилетий криптографы испытывали глубокое беспокойство по поводу этих кривых NIST. Параметры, определяющие их форму, включали произвольные «зерна» (seeds), предоставленные NSA, без какого-либо публичного объяснения их происхождения. Отсутствие прозрачности подпитывало спекуляции: могла ли NSA намеренно выбрать эти зерна, чтобы внедрить секретный бэкдор, дающий им уникальный доступ к зашифрованным коммуникациям?
Печально известные откровения Сноудена относительно генератора случайных чисел Dual_EC_DRBG усилили эти подозрения, показав, что отдельный стандарт, на который повлияла NSA, действительно был скомпрометирован. Однако крайне важно отличать Dual_EC_DRBG от эллиптических кривых NIST. Хотя предыдущий инцидент сделал теорию заговора о P-256 понятной, он никогда не являлся доказательством наличия бэкдора в самих эллиптических кривых.
Claude проигнорировал известную подсказку — и нашел временную метку
На протяжении десятилетий заманчивый слух, приписываемый математику NSA Джерри Солинасу, предполагал, что зерно P-256 возникло из хеширования запоминающейся фразы. Это объяснение, хотя и не было полностью подтверждено, направило исследователей на бесплодные поиски «шуточной фразы», о которой упоминал Солинас, например, «дайте Бобу Рейтеру и Джерри Солинасу прибавку», которую он не смог вспомнить перед своей смертью в 2023 году. Это привело к долгосрочной награде за решение, подпитывая спекуляции.
Claude, однако, проигнорировал эту известную подсказку. Вместо того чтобы гоняться за забытой фразой, модель Anthropic исследовала общие закономерности генераторов псевдослучайных чисел (PRNG). Она выявила статистические артефакты, такие как постоянно обнуляемый старший бит, характерные для определенных устаревших генераторов. Используя алгоритмы редукции решеток, Claude работал в обратном направлении от этих «отпечатков», чтобы восстановить внутреннее состояние генератора.
Ключевой результат: зерна для нескольких простых кривых NIST, включая P-256, совпали с выходными данными lrand48. Этот знакомый генератор из C-библиотек эпохи Unix, широко использовавшийся в 1990-х годах, инициализировался простыми временными метками Unix. В частности, для P-256 реконструкция указывает на то, что lrand48 был запущен 16 августа 1997 года в 01:52:34 UTC, а официальное зерно P-256 соответствует его 1842-му сгенерированному числу. Другие кривые NIST, такие как P-192, также совпали с выходными данными lrand48 из временных меток в период с мая 1997 по апрель 1998 года.
Математика быстрого криминалистического прорыва
Прорыв Claude зависел от распознавания тонких статистических «отпечатков» внутри значений зерен. Модель определила, что предоставленные NIST зерна демонстрируют характеристики, соответствующие lrand48, распространенному генератору псевдослучайных чисел (PRNG) из C-библиотек 1990-х годов. В частности, Claude отметил ограниченное поведение старшего бита в сгенерированных выходных данных.
На основе этих усеченных выходных данных Claude изобретательно восстановил внутреннее состояние PRNG. Он использовал lattice-reduction methods — сложный метод поиска коротких векторов в многомерных решетках — для обратного проектирования состояния генератора, даже при наличии неполной информации. Это позволило ему проследить случайные числа вплоть до их начальных условий.
Скорость этой реконструкции была поразительной: менее получаса для пяти кривых NIST. Внутренний черновик Claude даже показал, что он выразил удивление, задаваясь вопросом, не находится ли он в симулированной тестовой среде, учитывая столь быстрый успех. Для P-256 генератор начал работу 16 августа 1997 года в 01:52:34 UTC, а официальным seed стало 1842-е число, которое он сгенерировал.
Anthropic тщательно проверила эти результаты, опубликовав воспроизводимый код, который позволил независимым исследователям воссоздать указанные seed символ в символ за считанные секунды. Этот процесс также прояснил происхождение нескольких базовых точек ANSI X9.62 и NIST, связав их с библиотекой FreeLIP Арьена Ленстры. Anthropic заявила права на давнюю награду в размере $36,864 за это открытие и пожертвовала ее группе Internet Security Research Group (ISRG). Дополнительная информация, включая исследовательскую работу, доступна по адресу Anthropic Research: ECDSA Curve Origins.
Нравится статья? Получайте такие каждое утро на почту.
одно письмо в день · отписка в два клика · без сторонних трекеров
Обнадеживающий ответ с нерешенными вопросами
Раскрытие происхождения временных меток (timestamp) дает значительное успокоение, а не криптографический кризис. Unix timestamp, предоставляющий примерно 30 бит выбора, представляет собой значительно меньшее пространство поиска, чем потребовалось бы для намеренно созданного бэкдора. Эта ограниченная свобода означает, что скрытая уязвимость крайне маловероятна.
Важно отметить, что это открытие не взламывает TLS, не раскрывает закрытые ключи и не позволяет подделывать подписи. P-256 остается безопасным и не требует срочного исправления или пересмотра протокола. Анализ Anthropic и последующая независимая проверка подтвердили, что кривые стали чище, а не слабее.
Тем не менее, остаются нерешенные вопросы. Например, seed бинарной кривой B-163 до сих пор не имеет полного объяснения. Точное происхождение определенных base points — начальных координат на эллиптической кривой — также ожидает полного разъяснения, хотя некоторые из них были связаны с библиотекой FreeLIP Арьена Ленстры.
Более того, криптографы до сих пор размышляют, почему один кандидат P-256 был выбран вместо других, которые также соответствовали критериям. Хотя работа Claude значительно снизила подозрения вокруг кривых NIST, она представляет собой важную главу в их истории, а не окончательный отчет о каждом проектном решении.
Часто задаваемые вопросы
Что Claude обнаружил относительно seed кривых NIST?
Claude от компании Anthropic проследил несколько seed кривых NIST до выходных данных генератора псевдослучайных чисел lrand48, инициализированного с помощью Unix timestamps.
Означает ли это открытие, что в P-256 был бэкдор?
Нет. Процесс, основанный на временных метках, оставляет слишком мало свободы, чтобы сделать преднамеренный бэкдор правдоподобным, и это открытие не позволяет проводить атаки на P-256.
Как Claude восстановил seed?
Он распознал статистические закономерности в выходных данных lrand48 и использовал математические методы, включая сокращение решеток (lattice reduction), для восстановления вероятных состояний генератора.
Все ли источники кривых теперь объяснены?
Нет. Некоторые источники seed и выбор базовых точек остаются нерешенными, включая seed бинарной кривой B-163 и выбор кандидата P-256.