Что это за загадка
«Это просто временные метки» — так объяснила Claude 25-летнюю тайну происхождения одного из самых популярных криптографических стандартов. ECDSA — это самый широко используемый стандарт криптографии эллиптических кривых. NIST принял его в 2000 году как часть стандарта цифровой подписи FIPS 186-2, который определяет набор стандартных эллиптических кривых разных размеров и уровней безопасности.
Для кривых над простыми и двоичными полями в спецификации опубликовали параметр «seed», хэш которого используется для определения коэффициента b кривой. Происхождение этих семян было многолетним вопросом криптографического сообщества, так как они были предоставлены NSA без каких-либо объяснений или обоснований. Например, семя кривой NIST P-256 было SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90 — и никакой информации об их источнике.
Нил Кобліц и Альфред Менезес написали отличное исследование на эту тему — «Загадка в шкатулке», обсуждающее историю и опасения вокруг значений семян. Это вызвало любительское расследование происхождения семян и даже награду за их поиск.
Лучший вариант истории пришел от Джерри Солинаса, давнего сотрудника NSA, который утверждал, что семена были сгенерированы хешированием забавной фразы:
«Я думаю, там был счётчик, а не множественное хеширование, но я не знаю деталей. Сообщение было примерно «Дайте Бобу и Джерри прибавку» или «Боб и Джерри рулят» или что-то в этом роде. Это был Боб Райтер, который на самом деле написал код, но и он не помнит деталей. Мы также не смогли найти архивы с тех времён. Если они существуют, они, несомненно, сидят на жёстком диске рядом с Ковчегом Завета.»
Джерри Солинас, 2015
К сожалению, Джерри скончался в 2023 году, а коллеги того времени не отреагировали, оставив открытым вопрос о том, как эти семена были первоначально получены.
Claude нашла семена
Несколько сотрудников Anthropic безуспешно пытались найти семена, следуя совету о хешировании забавной фразы. Это оказалось неправильным направлением. В октябре 2026 года любопытный сотрудник Anthropic попросил внутреннюю исследовательскую модель выяснить, как были сгенерированы эти семена, не подсказывая подсказку.
Менее чем за полчаса Claude обнаружила происхождение семян NIST P-192, P-224, P-256, P-384 и P-521. Ни один из них не был результатом какого-либо хеш-алгоритма, а лишь выходом генератора случайных чисел lrand48 из библиотеки C, инициализированного Unix-временем!
Использованный алгоритм производил выборку байтов из генератора случайных чисел (RNG), инициализированного Unix-временем (t) для некоторого количества итераций (n). Каждая итерация извлекала 20 байтов как кандидат на семя. Так, первые 20 байтов — кандидат 1, следующие 20 байтов — кандидат 2 и так далее. Например, для P-256 потребовалось 1842 итерации, чтобы выдать стандартизированное семя.
Что это значит
Это не криптографический взлом, новая атака или слабость в кривых ECDSA. На самом деле, это заставляет нас быть более уверенными, что кривые были выбраны без каких-либо бэкдоров или преднамеренных слабостей. Многие годы люди подозревали происхождение параметров кривых NIST. Они были представлены NIST без каких-либо упоминаний о том, как они были выбраны, что заставляло людей задаваться вопросом, могут ли они быть выбраны с преднамеренными бэкдорами. Эти находки делают такие подозрения намного менее правдоподобными. Семена были сгенерированы очень простым способом: обычный генератор псевдослучайных чисел, инициализированный часами, который теперь может воспроизвести кто угодно. Это оставляет намного меньше места для подвоха, и мы можем быть уверены, что параметры безопасны.
Как это было найдено
Поиск по фразе, построенной из слухов, ничего не дал. Claude пошла другим путем: предположила, как должно было работать программное обеспечение, которое генерировало кривые. Модель предположила, что программное обеспечение использовало генератор псевдослучайных чисел (PRNG), поставляемый с библиотеками C 1990-х годов. Эти старые PRNG достаточно слабы, чтобы их выход можно было узнать. Узнав выход, можно было бы определить, какой PRNG был использован, и, возможно, восстановить его начальное состояние.
Claude написала сканер, который проходил по каждому опубликованному семени один бит за раз и проверял, являются ли соседние части последовательными выходами генератора эпохи 1990-х. Сканирование охватывало 34 комбинации генератора и выходных срезов. В какой-то момент Claude заметила закономерность в старших битах некоторых семян: они все были нулями. Записанные как пять 32-битных слов, четыре из десяти семян имеют 0 в старшем бите для всех 20 слов. Это произойдёт случайно с вероятностью 1/5810. Это была сигнатура линейного конгруэнтного генератора lrand48, который возвращает только старшие 31 бит из 48-битного состояния. Паттерн виден невооружённым глазом, если знаешь, на что смотреть. Чтобы восстановить состояние, Claude взяла первое слово, попробовала все 2¹⁷ значений 17 скрытых битов и проверила, что следующие четыре слова следовали согласно алгоритму. Это сработало для всех четырёх обсуждаемых семян.
Семена кривых с простыми полями пришли из того же генератора lrand48, но содержали меньше битов каждого выхода. Claude пришлось восстанавливать внутреннее состояние PRNG из этих битов. Оказалось, что восстановление состояния усечённого линейного конгруэнтного генератора — это классическая задача решётки, решаемая с помощью алгоритма LLL (Ленстра — Ленстра — Ловаса). Claude не знала, какие биты состояния могут показать семена, поэтому запустила решатель для каждого окна. Пять семян кривых NIST с простыми полями плюс пять семян из стандарта ANSI X9.62 — все имели одну и ту же закономерность: lrand48() >> 23. Каждое восстановленное 48-битное состояние регенерирует все 160 битов своего семени, что не происходит случайно.
Этот линейный конгруэнтный генератор работает в обратном направлении так же легко, как в прямом, поэтому для каждого семени Claude проходила состояние в обратном направлении, пока оно не достигало формы, которую оно имело бы, если бы было инициализировано srand48, с младшими 16 битами, равными 0x330E. Внутреннее состояние PRNG в такой форме появляется один раз в 65,536 шагов, поэтому достижение одного само по себе не является доказательством.
Однако для десяти семян кривых с простыми полями каждая инициализация srand48 была Unix-временем, представляющим дату между май 1997 и апрель 1998. Использовался слабый PRNG, инициализированный Unix-временем. Четыре инициализации двоичных кривых читаются как февраль 1984 года. Если удвоить временные метки, они соответствуют 17 апреля 1998 года, спустя две недели после запуска P-224. Возможно, программа вдвое уменьшала часы.
Внутренние размышления Claude в то время были:
Это поразительно: это решает 25-летнюю загадку. Хм, подождите. Позвольте мне быть скептичным: я не в какой-то смоделированной/тестовой среде? … Семена совпадают с моей памятью о фактических значениях … Хм, правдоподобно ли в действительности? Насколько мне известно … награда была неразрешена. … Все старшие биты чистые — 20 битов, шанс 1e-6. Значит, действительно в реальности. Вау, это реальное открытие.
Хм, подождите. Позвольте мне быть осторожнее о правдоподобности: разве не подозрительно, что такое очевидное не было открыто за 25 лет? Это проверено прямым вычислением с моей стороны: совпадение 160-бит из 32-битного семени + малый индекс: нет шансов на совпадения (10 × 160 битов). Это реально.
Claude также нашла некоторые базовые точки
Но это ещё не всё… Каждая кривая также поставляется с базовой точкой G, фиксированной точкой, кратной которой является каждый открытый ключ ECDSA. Найденное выше семя не определяет эту G, поэтому возникает другой вопрос: как были сгенерированы эти базовые точки?
Проверяя семена, Claude также обнаружила происхождение некоторых базовых точек. Базовые точки шести кривых, сгенерированных в май 1997 года (P-192 и пять примеров кривых ANSI X9.62 prime192v2, prime192v3 и prime239v1 до v3), пришли из генератора случайных чисел в FreeLIP — пакета длинной арифметики Арьена Ленстры. Ранние версии библиотеки NTL Виктора Шупа поставлялись с тем же кодом.
Рецепт здесь простой:
- Инициализировать генератор с небольшим целым числом.
- Отбросить семь выходов.
- Сгенерировать кандидаты на координаты x из выходов 26-битов, приведённых по модулю p.
- Повторять шаг 3 до тех пор, пока x находится на кривой.
Claude обнаружила, что семена генератора — 20000 для P-192, 20420, 20507 и 20509 для prime239v1 до v3, и 20512 и 20517 для prime192v2 и v3.
Насколько нам известно, никто раньше не объяснял какую-либо базовую точку NIST. Базовые точки P-224, P-256, P-384 и P-521 не соответствуют этому рецепту; нам не удалось объяснить, как они были выбраны.
Открытые вопросы
Не каждый 20-байтовый кандидат на семя мог генерировать жизнеспособную кривую, и заметили, что некоторые потенциально жизнеспособные кривые были пропущены. Для P-256 опубликованное семя — кандидат 1842, но кандидат 876 из того же запуска также дает кривую простого порядка нужного размера с параметрами, выбранными так же, как в опубликованной кривой. Запуск P-224 прошел мимо трёх таких кривых, а два запуска за кривыми примера ANSI X9.62 прошли мимо семи других. Не известно, какие критерии могли быть использованы или был ли это непреднамеренный артефакт.
Поскольку количество пропущенных кандидатов невелико, не верим, что правдоподобно, что были выбраны ослабленные кривые. Это означало бы, что ослабленные кривые обычны и легко найти. Все ещё теоретически возможно, что эти кривые были выбраны для получения определённого свойства путём поиска по временным меткам в генератор случайных чисел. Однако это потребуется только в том случае, если раскрыть временную метку как доказательство, что семя было невинно сгенерировано. Ничто в цифрах не показывает, сколько было запусков.
Также есть одно семя, которое не удалось восстановить. Пятое двоичное семя B-163 не подходит ни под что, что пробовала Claude, и остаётся необъяснённым. Наконец, не известно, как были сгенерированы базовые точки для P-224, P-256, P-384 и P-521. То же самое относится к двоичным кривым NIST.
Награда
Сумма 36,864 доллара за поиск семян будет пожертвована Интернет-группе исследования безопасности.
Кто мы
Эта работа была проведена в Anthropic Джоном Вудом, Генри де Валенсе, Ава Хауэлл, Заком Воазом, Люси Свит, Амиром Омиди, Полом Краули, Иеном МакГиннисом, Николасом Карлини и Стивом Вейсом.
Благодарности
Мы хотели бы посмертно признать Джерри Солинаса, который принял быть помеченным как «злой интернет-мем» и «Yo La Tengo NSA-геббельсов» с хорошим юмором. Спасибо также Филиппо Валсорде за организацию награды NIST Elliptic Curves Seeds Bounty.
Код для воспроизведения семян
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, "" # the state srand48(t) sets
for i in range(per * n):
x = (0x5DEECE66D * x + 0xB) % 2**48 # one step of lrand48
if i >= per * (n - 1):
out += "%0*X" % (width, x >> shift)
return out
PRIME = { # srand48(time); 20 bytes per candidate: lrand48() >> 23
"prime239v1": ("1997-05-15 15:49:03", 2185),
"prime239v2": ("1997-05-15 15:49:03", 2320),
"prime239v3": ("1997-05-15 15:49:03", 3048),
"P-192": ("1997-05-18 14:45:34", 139),
"prime192v3": ("1997-05-18 14:45:34", 5228),
"prime192v2": ("1997-05-18 14:45:34", 6013),
"P-521": ("1997-08-08 01:12:04", 1136),
"P-256": ("1997-08-16 01:52:34", 1842),
"P-384": ("1997-08-30 14:50:08", 2688),
"P-224": ("1998-04-03 12:52:07", 7026),
}
BINARY = { # srand48(time / 2), if that reading is right; 5 words per candidate: lrand48()
"B-233": ("1998-04-17 15:24:18", 155),
"B-283": ("1998-04-17 15:27:44", 32),
"B-409": ("1998-04-17 15:30:18", 60),
"B-571": ("1998-04-17 15:32:08", 73),
}
for name, (when, n) in PRIME.items():
print(f"{name:10} {when} {n:5} {candidate(unix(when), n, 20, 40, 2)}")
for name, (when, n) in BINARY.items():
print(f"{name:10} {when} {n:5} {candidate(unix(when) // 2, n, 5, 17, 8)}")
Вывод этого кода:
prime239v1 1997-05-15 15:49:03 2185 E43BB460F0B80CC0C0B075798E948060F8321B7D
prime239v2 1997-05-15 15:49:03 2320 E8B4011604095303CA3B8099982BE09FCB9AE616
prime239v3 1997-05-15 15:49:03 3048 7D7374168FFE3471B60A857686A19475D3BFA2FF
P-192 1997-05-18 14:45:34 139 3045AE6FC8422F64ED579528D38120EAE12196D5
prime192v3 1997-05-18 14:45:34 5228 C469684435DEB378C4B65CA9591E2A5763059A2E
prime192v2 1997-05-18 14:45:34 6013 31A92EE2029FD10D901B113E990710F0D21AC6B6
P-521 1997-08-08 01:12:04 1136 D09E8800291CB85396CC6717393284AAA0DA64BA
P-256 1997-08-16 01:52:34 1842 C49D360886E704936A6678E1139D26B7819F7E90
P-384 1997-08-30 14:50:08 2688 A335926AA319A27A1D00896A6773A4827ACDAC73
P-224 1998-04-03 12:52:07 7026 BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5
B-233 1998-04-17 15:24:18 155 74D59FF07F6B413D0EA14B344B20A2DB049B50C3
B-283 1998-04-17 15:27:44 32 77E2B07370EB0F832A6DD5B62DFC88CD06BB84BE
B-409 1998-04-17 15:30:18 60 4099B5A457F9D69F79213D094C4BCD4D4262210B
B-571 1998-04-17 15:32:08 73 2AA058F73A0E33AB486B0F610410C53A7F132310
Код для воспроизведения выбранных базовых точек
M, A = 2**107 - 1, pow(3, 121, 2**107 - 1) # zrandom: state = state * 3^121 mod (2^107 - 1)
P192 = 2**192 - 2**64 - 1
P239 = 2**239 - 2**143 - 2**95 + 2**47 - 1
CURVES = [ # name, LIP seed, p, b, published Gx (a = -3 throughout)
("prime192v1", 20000, P192,
0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1,
0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012),
("prime239v1", 20420, P239,
0x6b016c3bdcf18941d0d654921475ca71a9db2fb27d1d37796185c2942c0a,
0xffa963cdca8816ccc33b8642bedf905c3d358573d3f27fbbd3b3cb9aaaf),
("prime239v2", 20507, P239,
0x617fab6832576cbbfed50d99f0249c3fee58b94ba0038c7ae84c8c832f2c,
0x38af09d98727705120c921bb5e9e26296a3cdcf2f35757a0eafd87b830e7),
("prime239v3", 20509, P239,
0x255705fa2a306654b1f4cb03d6a750a30c250102d4988717d9ba15ab6d3e,
0x6768ae8e18bb92cfcf005c949aa2c6d94853d0e660bbf854b1c9505fe95a),
("prime192v2", 20512, P192,
0xcc22d6dfb95c6b25e49c0d6364a4e5980c393aa21668d953,
0xeea2bae7e1497842f2de7769cfe9c989c072ad696f48034a),
("prime192v3", 20517, P192,
0x22123dc2395a05caa7423daeccc94760a7d462256bd56916,
0x7d29778100c65a1da1783716588dce2b8b4aee8e228f1896),
]
def base_point_x(seed, p, b):
state = seed # zrstarts(seed)
def limb(): # zrandom(2^26): low 26 bits of the new state
nonlocal state
state = state * A % M
return state % 2**26
for _ in range(7): # seven single-limb draws come first
limb()
limbs = -(-p.bit_length() // 26) + 1 # zrandomb(p): limbs of p plus one, top limb first
tries = 0
while True:
x = 0
for _ in range(limbs):
x = x << 26 | limb()
x %= p
tries += 1
if pow(x**3 - 3*x + b, (p - 1) // 2, p) == 1: # is x on the curve?
return x, tries
for name, seed, p, b, gx in CURVES:
x, tries = base_point_x(seed, p, b)
print(f"{name:20} seed {seed} tries {tries} matches published Gx: {x == gx}")
Вывод этого кода:
prime192v1 seed 20000 tries 2 matches published Gx: True
prime239v1 seed 20420 tries 3 matches published Gx: True
prime239v2 seed 20507 tries 2 matches published Gx: True
prime239v3 seed 20509 tries 1 matches published Gx: True
prime192v2 seed 20512 tries 5 matches published Gx: True
prime192v3 seed 20517 tries 1 matches published Gx: True
Лицензия
Авторы отказались от всех авторских прав и смежных прав на код на этой странице, передав его в общественное достояние в соответствии с CC0 1.0 Universal (https://creativecommons.org/publicdomain/zero/1.0/).