ECDSA — самый распространённый стандарт криптографии на эллиптических кривых. NIST принял его в 2000 году в составе стандарта цифровой подписи FIPS 186-2, где перечислен набор стандартных кривых разного размера и уровня стойкости. Для кривых над простыми и бинарными полями в спецификации опубликован «seed»: значение его хеша задаёт коэффициент b кривой. Откуда взялись эти seed’ы, никто не знал: их передало АНБ без объяснений и обоснований. Например, для кривой NIST P-256 seed был таким: SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90, и ни слова о том, откуда он.
Нил Коблиц и Альфред Менезес написали отличный обзор этой истории, «A Riddle Wrapped in an Enigma», где разбирают ход событий и опасения вокруг seed’ов. Загадка породила любительское расследование и награду тому, кто найдёт происхождение seed’ов.
Лучшая из версий гласила, что Джерри Солинас, давний сотрудник АНБ, получил seed’ы как хеш шуточной фразы:
«Мне кажется, там был счётчик, а не многократное хеширование, но подробностей я не знаю. Сообщение было что-то вроде “Give Bob and Jerry a raise” или “Bob and Jerry rule”. Код писал Боб Райтер, и он тоже не помнит деталей. Архивов с тех пор мы не нашли. Если они и существуют, то, наверное, лежат на жёстком диске где-нибудь рядом с Ковчегом Завета.»
Джерри Солинас, 2015
К сожалению, Джерри умер в 2023 году, остальные коллеги того времени на связь не выходили, и вопрос о том, как seed’ы получили изначально, остался открытым.
Claude нашёл seed’ы
Несколько сотрудников Anthropic безуспешно искали seed’ы по подсказке про хеш шуточной фразы. Эта подсказка оказалась неверной. В октябре 2026 года один любопытный сотрудник Anthropic спросил внутреннюю исследовательскую модель, сможет ли она выяснить, как получили эти seed’ы, не указывая ей на подсказку.
Меньше чем за полчаса Claude установил происхождение seed’ов NIST P-192, P-224, P-256, P-384 и P-521. Ни один из них не был результатом какого-либо хеш-алгоритма. Это выход генератора случайных чисел lrand48 из библиотеки C, инициализированного Unix-временем!
Алгоритм работал так. Генератор случайных чисел (ГСЧ) инициализируется Unix-временем (t), и за некоторое число итераций (n) из него набирают байты. На каждой итерации берётся 20 байт как кандидат в seed: первые 20 байт — кандидат 1, следующие 20 — кандидат 2 и так далее. Например, чтобы получить стандартный seed для P-256, понадобилась 1842 итерация.
Что это значит
Это не криптографический взлом, не новая атака и не слабость кривых ECDSA. Наоборот, теперь мы ещё больше уверены, что кривые выбирали без бэкдоров и намеренных слабостей. Много лет люди подозревали, что у параметров кривых NIST есть тёмное происхождение. Их передали в NIST без объяснений, как они выбирались, и оставалось гадать, не заложили ли в них бэкдоры намеренно. Найденное делает это куда менее правдоподобным. Seed’ы получили очень простым способом: обычный генератор псевдослучайных чисел, инициализированный часами. Это теперь может повторить кто угодно. Свободы для подрыва остаётся гораздо меньше, и можно быть уверенными, что параметры безопасны.
Как это нашли
Поиск по фразе, собранной из слухов, ничего не давал. Claude зашёл с другой стороны: попытался предугадать, как должна была работать программа, генерировавшая кривые. Он предположил, что программа использовала ГСЧ из C-библиотек 1990-х. Такие старые генераторы достаточно слабы, чтобы их вывод можно было опознать, а опознав, понять, какой ГСЧ использовался, и, возможно, восстановить его начальное состояние.
Claude написал сканер, который скользил по каждому опубликованному seed’у на один бит и проверял, являются ли соседние куски последовательными выходами генератора 1990-х годов. Сканирование охватило 34 комбинации генератора и срезов вывода. В какой-то момент Claude заметил закономерность в старших битах некоторых seed’ов: все они нулевые. Если записать seed как пять 32-битных слов, то у четырёх из десяти seed’ов старший бит равен 0 во всех 20 словах. Случайно так бывает с вероятностью 1/5810. Это была сигнатура линейного конгруэнтного генератора lrand48, который возвращает только старшие 31 бит из 48-битного состояния. Закономерность видна глазом, если знать, куда смотреть. Чтобы восстановить состояние, Claude взял первое слово, перебрал все 2¹⁷ значений 17 скрытых битов и проверил, что следующие четыре слова сходятся. Для всех четырёх обсуждаемых seed’ов это сработало.
Seed’ы кривых над простыми полями получены тем же генератором lrand48, но от каждого вывода сохранено меньше битов. Claude пришлось восстанавливать внутреннее состояние ГСЧ по этим битам. Оказывается, восстановление состояния усечённого линейного конгруэнтного генератора — учебная задача на решётки, и решается она алгоритмом приведения базиса Ленстры — Ленстры — Ловаса (LLL). Claude не знал, какие биты состояния могут оказаться в seed’ах, поэтому прогнал решатель по всем окнам. Пять простых кривых NIST и ещё пять из ANSI X9.62 показали один и тот же рисунок: lrand48() >> 23. Каждое восстановленное 48-битное состояние воспроизводит все 160 бит своего seed’а, а случайно так не бывает.
Этот линейный конгруэнтный генератор так же легко идёт назад, как и вперёд. Поэтому для каждого seed’а Claude отматывал состояние назад, пока не дошёл до вида, который получается после инициализации через srand48: младшие 16 бит равны 0x330E. Состояние такого вида встречается раз в 65 536 шагов, так что само по себе его появление ничего не доказывает.
Однако у всех десяти seed’ов простых кривых каждая инициализация srand48 оказалась Unix-временем, причём датой между маем 1997 и апрелем 1998 года. То есть использовался слабый ГСЧ, инициализированный Unix-временем. Четыре инициализации бинарных кривых читаются как февраль 1984 года. Если время удвоить, получится 17 апреля 1998 года, через две недели после запуска для P-224. Возможно, программа делила показания часов пополам.
Внутренние рассуждения Claude в тот момент были такими:
Это поразительно: так решается 25-летняя загадка. Хм, подожди. Надо быть скептичным: не нахожусь ли я в какой-то симулированной или тестовой среде? … Seed’ы совпадают с моей памятью о реальных значениях … Хм, а правдоподобно ли это в реальности? Насколько я знаю … награда не была востребована. Все старшие биты сброшены, 20 битов, вероятность 1e-6. Значит, это действительно реальный мир. Ого, это настоящее открытие.
Хм, подожди. Давай осторожнее с правдоподобием: не подозрительно ли, что такая очевидная вещь не нашлась за 25 лет? Я проверил прямым вычислением: совпадение 160 бит при 32-битном seed’е и небольшом индексе — случайных совпадений быть не может (10 × 160 бит). Это реально.
Нашлись и некоторые базовые точки
Но и это не всё. У каждой кривой есть базовая точка G, фиксированная точка, кратным которой является каждый открытый ключ ECDSA. Найденный выше seed G не определяет, поэтому возникает другой вопрос: как получили базовые точки?
Проверяя seed’ы, Claude нашёл происхождение и некоторых базовых точек. Базовые точки шести кривых, созданных в мае 1997 года (P-192 и пять примеров кривых из ANSI X9.62: prime192v2, prime192v3 и prime239v1–v3), получены от генератора случайных чисел из FreeLIP, пакета длинной арифметики Арьена Ленстры. Тот же код был в ранних версиях библиотеки NTL Виктора Шоупа.
Рецепт простой:
-
инициализировать генератор небольшим целым числом;
-
отбросить семь выходов;
-
порождать кандидатов в координату x из 26-битных выходов по модулю p;
-
повторять предыдущий шаг, пока x не окажется на кривой.
Claude нашёл начальные значения генератора: 20000 для P-192; 20420, 20507 и 20509 для prime239v1–v3; 20512 и 20517 для prime192v2 и prime192v3.
Насколько нам известно, до этой работы никто не объяснял происхождение ни одной базовой точки NIST. Базовые точки P-224, P-256, P-384 и P-521 в этот рецепт не укладываются, и объяснить их выбор не удалось.
Открытые вопросы
Не из каждого 20-байтного кандидата в seed получалась годная кривая, и мы заметили, что некоторые потенциально годные кривые пропускались. Для P-256 опубликованный seed — это кандидат 1842, но кандидат 876 из того же запуска тоже даёт кривую простого порядка нужного размера, с параметрами, выбранными так же, как у опубликованной. В запуске P-224 пропущены три такие кривые, а в двух запусках, стоящих за примерами кривых ANSI X9.62, ещё семь (см. рисунок). Какие критерии применялись и не было ли это случайным артефактом, мы не знаем.
Пропущенных кандидатов мало, поэтому мы не считаем правдоподобным, что выбирались ослабленные кривые: это означало бы, что ослабленные кривые встречаются часто и найти их легко. Всё же нельзя исключить, что кривые отбирали по какому-то свойству, перебирая начальные значения времени для генератора. Но так стоило бы делать, только если собирались раскрыть метку времени как свидетельство невинного происхождения seed’а. Числа не показывают, сколько было запусков.
Остался и один seed, который восстановить не удалось. Пятый бинарный seed, B-163, не подходит ни под что из того, что пробовал Claude, и остаётся необъяснённым. И наконец, неизвестно, как получили базовые точки P-224, P-256, P-384 и P-521. То же касается бинарных кривых NIST.
Награда
Награду в $36 864 за поиск seed’ов передадут организации Internet Security Research Group.
Кто это делал
Работу провели в Anthropic Джон Вуд, Анри де Валанс, Ава Хауэлл, Зак Воэйз, Люси Свит, Амир Омиди, Пол Кроули, Иэн Макгиннис, Николас Карлини и Стив Уэйс.
Благодарности
Мы посмертно отдаём должное Джерри Солинасу, который с юмором принял ярлыки «злого интернет-мема» и «Yo La Tengo из бугименов АНБ». Спасибо и Филиппо Вальсорде за организацию награды за seed’ы эллиптических кривых NIST.
Код для воспроизведения seed’ов
Код авторы отдали в общественное достояние (CC0 1.0).
from datetime import datetime, timezonedef 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 outPRIME = { # 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 E43BB460F0B80CC0C0B075798E948060F8321B7Dprime239v2 1997-05-15 15:49:03 2320 E8B4011604095303CA3B8099982BE09FCB9AE616prime239v3 1997-05-15 15:49:03 3048 7D7374168FFE3471B60A857686A19475D3BFA2FFP-192 1997-05-18 14:45:34 139 3045AE6FC8422F64ED579528D38120EAE12196D5prime192v3 1997-05-18 14:45:34 5228 C469684435DEB378C4B65CA9591E2A5763059A2Eprime192v2 1997-05-18 14:45:34 6013 31A92EE2029FD10D901B113E990710F0D21AC6B6P-521 1997-08-08 01:12:04 1136 D09E8800291CB85396CC6717393284AAA0DA64BAP-256 1997-08-16 01:52:34 1842 C49D360886E704936A6678E1139D26B7819F7E90P-384 1997-08-30 14:50:08 2688 A335926AA319A27A1D00896A6773A4827ACDAC73P-224 1998-04-03 12:52:07 7026 BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5B-233 1998-04-17 15:24:18 155 74D59FF07F6B413D0EA14B344B20A2DB049B50C3B-283 1998-04-17 15:27:44 32 77E2B07370EB0F832A6DD5B62DFC88CD06BB84BEB-409 1998-04-17 15:30:18 60 4099B5A457F9D69F79213D094C4BCD4D4262210BB-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 - 1P239 = 2**239 - 2**143 - 2**95 + 2**47 - 1CURVES = [ # 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, triesfor 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: Trueprime239v1 seed 20420 tries 3 matches published Gx: Trueprime239v2 seed 20507 tries 2 matches published Gx: Trueprime239v3 seed 20509 tries 1 matches published Gx: Trueprime192v2 seed 20512 tries 5 matches published Gx: Trueprime192v3 seed 20517 tries 1 matches published Gx: True
ссылка на оригинал статьи https://habr.com/ru/articles/1095684/