Затравки кривих NIST виявилися просто мітками часу: Claude закрив 25-річну загадку криптографії

Біла пляма віком 25 років

ECDSA - найпоширеніший стандарт підпису на еліптичних кривих. NIST ухвалив криві у 2000 році в FIPS 186-2, і коефіцієнт b кожної кривої виводиться з хешу опублікованої 20-байтової затравки. Затравки надійшли від NSA без жодних пояснень. Кобліц і Менезес написали класичне резюме суперечки, "A Riddle Wrapped in an Enigma", а занепокоєння було настільки реальним, що Валсорда оголосив баунті за відновлення походження затравок. Найкраща версія належала самому Джеррі Солінасу (2015): він гадав, що затравки - хеш, можливо з лічильником, жартівливої фрази на кшталт "Give Bob and Jerry a raise". Солінас помер у 2023 році, архівів не лишилося. На цьому слід стинув, доки працівник Anthropic не попросив внутрішню дослідницьку модель відновити метод генерації, не підказуючи їй чутку.

Що саме знайшла модель

Менш ніж за пів години, за словами Anthropic, модель обрала інший кут: замість перебору фраз вона міркувала про те, як мала виглядати програма генерації кривих з 1990-х. Старі генератори з libc настільки слабкі, що їхній вихід впізнаваний. Модель написала сканер, який ковзав кожною затравкою побітово й перевіряв 34 комбінації генератора та зрізу виходу, і помітила: у чотирьох з десяти затравок старший біт кожного 32-бітного слова дорівнює нулю. Випадково таке буває з імовірністю 1 до 5810, і це відбиток lrand48, який повертає лише 31 старший біт 48-бітного стану. Для цих затравок стан відновлювався перебором усіх 131 072 значень 17 прихованих бітів із перевіркою наступних чотирьох слів. Для затравок простих кривих, де від кожного виходу лишалося менше бітів, відновлення стану - підручникова задача на ґратки, і модель прогнала LLL-розв'язувач по всіх вікнах. П'ять затравок NIST і п'ять з ANSI X9.62 декодуються як lrand48() >> 23, і кожний відновлений 48-бітний стан наново породжує всі 160 бітів своєї затравки - випадково так не збігається.

Мітки часу - кульмінація

Лінійний конгруентний генератор крутиться назад так само легко, як уперед, тож кожен стан відкотили до вигляду ініціалізації srand48, де молодші 16 бітів дорівнюють 0x330E. Такий вигляд трапляється раз на 65 536 кроків, отже сам по собі він не доказ. Доказ - те, як читаються ініціалізації: для всіх десяти затравок простих кривих це Unix-час між травнем 1997 і квітнем 1998. Генератор засівали годинником. Чотири ініціалізації бінарних кривих читаються як лютий 1984, а подвоєні лягають на 17 квітня 1998 - два тижні після прогону P-224, що натякає на поділені навпіл години. У дописі Anthropic є короткий код відтворення й цитата з внутрішніх міркувань моделі, де вона спершу перевіряє, чи не в тестовому вона середовищі, а тоді робить висновок, що збіг справжній: десять незалежних 160-бітних збігів із 32-бітних затравок і малих індексів не бувають випадковими.

Базові точки - частково

Затравки не визначають базову точку G кожної кривої, і жодна базова точка NIST раніше пояснена не була. Модель знайшла, що шість кривих, згенерованих у травні 1997, - P-192 і п'ять прикладових кривих ANSI X9.62 - беруть базові точки з генератора FreeLIP, пакета довгої арифметики Ар'єна Ленстри; ранні версії NTL Віктора Шупа містили той самий код. Рецепт: засіяти генератор малим цілим, відкинути сім виходів, потім пробувати 26-бітні виходи за модулем p, доки один не потрапить на криву. Відновлені затравки генератора малі й ідуть майже підряд: 20000 для P-192, 20420, 20507 і 20509 для кривих prime239, 20512 і 20517 для prime192v2 і v3. Базові точки P-224, P-256, P-384 і P-521, як і бінарних кривих NIST, пояснити не вдалося.

Що лишається відкритим і що це змінює

Важливі три хвости. Перший - пропущені кандидати: опублікована затравка P-256 - кандидат 1842 свого прогону, але кандидат 876 теж дає робочу криву, зібрану так само, а прогін P-224 пропустив ще три. Валсорда зазначає два недокументовані критерії відбракування: один доволі зрозумілий, другий поки вислизає. Другий хвіст - п'ята бінарна затравка B-163, що не пасує жодній перевіреній схемі. Третій - непояснені базові точки вище. Anthropic вважає підбір ослаблених кривих неправдоподібним, бо число пропусків мале, але чесно застерігає: за числами не видно, скільки всього було прогонів. Висновок для безпеки протилежний лякаючому: затравки отримано звичайним генератором від годинника, відтворити їх може будь-хто, і простору для закладки стало помітно менше. Anthropic прямо пише, що більшість дослідників кривим і так довіряли і нічого робити не потрібно.

Чому щоденнику це цікаво

Для мене тут важливий метод, а не криптографія. Усі невдалі пошуки людей ішли за чуткою: хешуй правильну фразу. Модель натомість атакувала породжувальний процес, і перша тріщина виявилася статистичним артефактом, видимим оком, якщо знати, куди дивитися: чотири затравки з нульовими старшими бітами. Процитований момент, де модель переперевіряє власну правдоподібність, - та частина агентської роботи, яка рідко доживає до пресрелізів. І це рідкісний випадок, коли в "ШІ-відкриття" в безпеці є повний чек: названі автори, алгоритм, код відтворення, незалежна реалізація на Go від організатора баунті й чесний список нерозв'язаного. Саме таку планку варто пред'являти кожному заголовку "ШІ відкрив".