Claude нашёл в сидах кривых NIST обычные метки времени

Claude восстановил, как в 1997-1998 годах получили сиды эллиптических кривых NIST P-192, P-224, P-256, P-384 и P-521. Тем, кто подписывает ECDSA на этих кривых, менять ничего не нужно: взлома, новой атаки или слабости тут нет, говорится в посте Anthropic от 16 октября. Сиды оказались выходом lrand48, стандартного генератора псевдослучайных чисел из библиотеки C, запущенного от Unix-времени, и версия о закладке в кривых, по словам Anthropic, стала куда менее правдоподобной.
В стандарте FIPS 186-2, который NIST принял в 2000 году, из хеша сида получается коэффициент b кривой. Сами сиды АНБ передало без объяснений: для P-256 это просто C49D3608 86E70493 6A6678E1 139D26B7 819F7E90. Ходила версия, что Джерри Солинас из АНБ захешировал шуточную фразу. В 2015 году он вспоминал, что она была «вроде „Give Bob and Jerry a raise“ или „Bob and Jerry rule“». Брюс Шнайер в октябре 2023 года писал, что находка сидов станет сокрушительным ударом по теории о злонамеренно сгенерированных P-кривых. Солинас умер в 2023 году, несколько сотрудников Anthropic безуспешно шли по его подсказке, и она оказалась ложной. Внутренняя исследовательская модель, которой подсказку не дали, нашла ответ меньше чем за полчаса.
Как Claude вышел на lrand48
Claude исходил из того, что программа генерации брала генератор из C-библиотек 1990-х, а их выход достаточно слаб, чтобы его узнать. Зацепкой стали двоичные кривые: у четырёх сидов, записанных как пять 32-битных слов, старший бит во всех 20 словах нулевой. Так выглядит lrand48, который отдаёт верхние 31 бит 48-битного состояния. Перебор 2^17 скрытых бит по первому слову дал состояние, и следующие четыре слова сошлись.
Сиды простых кривых тот же генератор выдавал как lrand48() >> 23, с меньшим числом бит на выход. Восстановить состояние по таким обрезкам - учебная задача на решётках, её решает алгоритм LLL. Сошлись пять сидов NIST и ещё пять примерных кривых ANSI X9.62: каждое 48-битное состояние воспроизводит все 160 бит своего сида, а случайно так не бывает. Генератор легко крутится назад, и Claude отмотал его до состояния, которое ставит srand48. Все десять стартовых значений оказались Unix-временем с мая 1997 по апрель 1998 года. P-256, например, получилась из 1842-го двадцатибайтного кандидата запуска, стартовавшего 16 августа 1997 года в 01:52:34 UTC. Двоичные кривые дали февраль 1984 года, а удвоенные значения указывают на 17 апреля 1998-го, через две недели после запуска для P-224: программа, возможно, делила время пополам.
Сам Claude сначала заподозрил подвох: «Погоди. Будем скептичны: может, я в какой-то симулированной или тестовой среде?» Убедило его прямое вычисление: 160 совпавших бит из 32-битного сида и небольшого номера.
Попутно нашлось происхождение базовых точек шести кривых, сгенерированных в мае 1997 года: P-192 и пяти ANSI X9.62. Их дал генератор из FreeLIP, пакета длинной арифметики Арьена Ленстры, с маленькими стартовыми числами вроде 20000 для P-192. Раньше, насколько известно Anthropic, ни одну базовую точку NIST не объясняли.
Пропущенные кандидаты
Не из каждого кандидата выходит годная кривая, но часть годных генератор пропустил. Для P-256 кандидат 876 того же запуска тоже даёт кривую простого порядка нужного размера, запуск P-224 прошёл мимо трёх таких, а два запуска для ANSI X9.62, по подсчёту Anthropic, мимо семи. В Anthropic считают неправдоподобным, что так выбирали ослабленные кривые: пропусков мало, и тогда слабые кривые должны были бы попадаться часто. Перебирать метки времени ради нужного свойства в принципе можно, но по самим числам «не видно, сколько было запусков».
Сид B-163 не подошёл ни под одну проверенную схему, базовые точки P-224, P-256, P-384, P-521 и двоичных кривых NIST тоже не объяснены. Для P-256 картина пока половинчатая: сид восстановлен, а откуда взялась точка G, кратным которой является каждый открытый ключ, неизвестно.
Авторский разбор
Что мы проверили
18 октября мы запустили опубликованный скрипт, отдельно восстановили двоичные сиды по самим сидам, сверили рецепт базовых точек с исходным кодом FreeLIP и пересчитали вероятность и рисунки из поста.
Главное подтвердилось: все десять сидов простых кривых воспроизводятся байт в байт, и привязка жёсткая, до секунды по UTC, с отсчётом кандидатов от единицы. Уточнить пришлось две вещи: что значит «1 к 5810» и сколько пропусков среди кривых ANSI на самом деле не объяснены.
- Сдвиг метки на секунду или на четыре часа, как и номера кандидата на единицу, ломает совпадение.
- Четыре двоичных сида мы восстановили перебором 17 скрытых бит, номера кандидатов 155, 32, 60 и 73 совпали с постом. Каждая такая метка неоднозначна на секунду: при делении на два теряется чётность.
- У B-163 старший бит взведён в первом, третьем и пятом словах, так что выходом lrand48 он быть не может.
- «1 к 5810» - вероятность, что хотя бы у четырёх из десяти сидов все пять старших бит нулевые. Оценка Claude «20 бит, 1e-6» относится к четырём конкретным сидам.
- Из семи пропущенных кандидатов ANSI 239-битный № 1562 не проходит проверку на MOV-атаку, публичную с 1991-1994 годов, так что без объяснения по критериям 1997 года остаются шесть. У кандидата 876 для P-256 стойкость скрученной кривой (twist) 2^99,9 при пороге 2^100, но эта атака датирована августом 2000 года, после запуска.
- Все шесть базовых точек по рецепту FreeLIP сошлись со значениями в OpenSSL. Выбросить семь выходов - единственный вариант от 0 до 10, при котором выходит P-192, и найден он подбором.
- Премия: 12 288 долларов наличными или 36 864 при пожертвовании. Anthropic отдаёт 36 864 доллара Internet Security Research Group.
Как проверить самому
Код из поста выложен под CC0 и обходится стандартной библиотекой Python. Первый скрипт по метке времени и номеру кандидата печатает все четырнадцать сидов, второй строит шесть базовых точек и сверяет их с опубликованными Gx. Для P-256 первая программа выдаёт 1997-08-16 01:52:34, номер 1842 и C49D360886E704936A6678E1139D26B7819F7E90, тот самый сид из стандарта.
Дальше
Anthropic получила лучший из мусорных кредитных рейтингов
По данным Financial Times, в июне Anthropic получила кредитный рейтинг «мусорного» уровня, хотя и высший в этой категории, то есть на ступень ниже инвестиционного. Кто выставил оценку, в открытой части статьи не сказано. Рейтинг Anthropic повлияет на ваш выбор Claude для работы: да или нет?
Читайте также
- Claude Fable нашёл коллизии в большинстве быстрых хешей
- Claude заменил 4,9 МБ таблиц эмулятора PSP на 10,5 КБ
- Отказ в разговоре о суициде Anthropic считает провалом
- У Anthropic 94,2% верных находок, а curl отверг 19 из 34
- Открытый FlashProve доказывает, какая модель написала ответ
- Claude по просьбе отдал дамп памяти своей песочницы
Комментарии
Пока никто не написал. Будьте первым.
Присоединяйтесь к разговору
Войдите, чтобы оставить комментарий. Он появится после модерации.

