ШІ Claude розгадав 25-річну криптографічну загадку АНБ

Протягом десятиліть деякі з найталановитіших криптографів світу ганялися за привидом. П’ять математичних кривих, що використовувалися для захисту інтернет-комунікацій, містили загадкові числа, надані Агентством національної безпеки (NSA), і ніхто не міг задовільно пояснити, звідки ці числа взялися. Теорії варіювалися від забутих жартів до навмисно вбудованих слабких місць. Тоді штучний інтелект Claude від компанії Anthropic взявся за розгадку цієї загадки і простежив походження цих чисел до старої комп’ютерної програми та часових міток, датованих майже трьома десятиліттями тому.

25-річна загадка, в центрі якої — АНБ

Історія починається наприкінці 1990-х років, коли математики розробляли стандарти для криптографії на основі еліптичних кривих — методу захисту цифрової інформації за допомогою складної математики. П’ять кривих, відомі як P-192, P-224, P-256, P-384 та P-521, зрештою стали частиною стандартів, опублікованих Національним інститутом стандартів і технологій (NIST). Їхні математичні властивості допомогли забезпечити безпеку веб-сайтів, фінансових транзакцій та урядових комунікацій.

Але ось у чому суть. Кожна крива була побудована з використанням таємничого 160-бітного початкового числа, яке називається «початковим значенням». Будь-хто міг перевірити математичну процедуру, використану для побудови кривих, але ніхто не знав, як АНБ обирало ці вихідні числа. Це питання, що залишилося без відповіді, породило припущення, що агентство могло навмисно підібрати «насіння», щоб приховати вразливість, яку могли б використати лише його власні фахівці.

Криптографи Ніл Кобліц та Альфред Менезес розглянули цю суперечку у своїй статті 2015 року «Загадка, оповита таємницею». Жодного практичного «заднього ходу» так і не було виявлено, але таємниця не хотіла зникати.

Таємна фраза, якої, мабуть, ніколи не існувало

Протягом багатьох років найпоширенішим поясненням була версія, пов’язана з математиком АНБ Джеррі Солінасом, який, як повідомлялося, надав початкові початкові значення. Солінас та інші згадували, що числа були згенеровані шляхом хешування гумористичних англійських фраз, можливо, чогось на кшталт «Джеррі заслуговує на підвищення». Хешування перетворює інформацію на математичний відбиток фіксованої довжини. На жаль, ніхто не пам’ятав точних фраз, а оригінальний комп’ютер, як повідомлялося, було замінено.

Сам Солінас намагався відтворити цей процес, але без успіху. Зрештою за розгадку цієї таємниці було призначено винагороду. У жовтні 2023 року криптограф Філіппо Вальсорда запропонував винагороду в розмірі 12 288 доларів тому, хто зможе пояснити походження початкових значень. Завдяки благодійній програмі подвоєння суми потенційна винагорода зросла до 36 864 доларів. Протягом трьох років ніхто не претендував на ці гроші. Тоді на сцену вийшов Клод.

Клод знаходить відповідь, що ховалася на очах у всіх

Згідно з дослідженням компанії Anthropic, опублікованим 16 жовтня, один із співробітників попросив внутрішню дослідницьку модель «Клод» дослідити початкові значення, не згадуючи про давню теорію секретної фрази. Модель почала вивчати закономірності, пов’язані зі старими комп’ютерними програмами. Одразу ж виділилася одна підказка. Кілька початкових значень містили групи чисел, найстарші біти яких послідовно дорівнювали нулю — це закономірність, ймовірність випадкового виникнення якої становить приблизно 1 до 5 810.

Це вказувало на lrand48 — псевдовипадковий генератор чисел, широко поширений у середовищах програмування епохи Unix. На відміну від справді випадкових процесів, псевдовипадкові генератори створюють передбачувані послідовності, щойно стають відомі їхні початкові значення. «Клод» проаналізував математику у зворотному напрямку, відновив внутрішні стани генератора та точно відтворив опубліковані початкові значення. А потім сталося щось справді вражаюче.

Початкові значення відповідали часовим мітками Unix — звичайним числовим представленням дат і часу — з 1997 та 1998 років. Записані міркування моделі відображали її власне очевидне здивування: «Це дивовижно: це розгадує 25-річну загадку». Усе це зайняло менше ніж 30 хвилин.

П’ять кривих, п’ять часових міток і одне надзвичайне збіг

Відновлені початкові значення дозволили відстежити п’ять кривих NIST у полі простих чисел до конкретних дат у період з травня 1997 року по квітень 1998 року. Крива P-192 походила з часової мітки, що відповідала 18 травня 1997 року, тоді як крива P-521 — до 8 серпня того ж року. P-256 з’явилася 16 серпня, P-384 — 30 серпня, а P-224 — 3 квітня 1998 року. Очевидний алгоритм був майже комічно простим. Ініціалізувати звичайний генератор випадкових чисел за допомогою часової мітки, генерувати потенційні початкові значення, перевіряти їх на відповідність математичним вимогам і продовжувати пошук, доки не з’явиться прийнятна крива.

Для P-256 прийнятне початкове число з’явилося на 1 842-му кандидаті. Для P-224 знадобилося 7 026 кандидатів. Збіги були точними: відтворювалися всі 160 бітів опублікованих початкових чисел, а не просто генерувалися схожі на них числа. Вальсорда самостійно відтворив ці результати за допомогою мови програмування Go, підтвердивши отримані висновки. Компанія Anthropic також опублікувала код, що дозволяє іншим перевірити цю роботу. Отримані результати надають переконливі математичні докази на користь цього методу генерації, хоча вони й не встановлюють точно, хто саме керував оригінальним програмним забезпеченням або чому певні кандидати були відхилені.

Що це відкриття означає для інтернет-безпеки

Наслідки цього відкриття вселяють впевненість, хоча вони й не є універсальною гарантією безпеки. Одне з давніх занепокоєнь стосувалося можливості того, що АНБ мало достатню свободу при виборі початкових значень, щоб навмисно обирати математично вразливі криві. Відновлений процес, як видається, надавав набагато менше варіантів вибору, ніж того вимагали б деякі гіпотетичні атаки. Дослідники компанії Anthropic оцінили свободу вибору приблизно в 30 бітів за найоптимістичніших припущень, що значно менше, ніж приблизно 70 бітів, передбачених в одному із запропонованих сценаріїв вибору вразливих кривих.

Це робить цю конкретну теорію про «задні двері» значно менш імовірною. Важливо зазначити, що це відкриття не руйнує криптографію на основі еліптичних кривих і не доводить, що всі можливі слабкі місця було виключено. Воно також безпосередньо не впливає на Bitcoin чи Ethereum, які використовують іншу еліптичну криву під назвою secp256k1.

Грегорі Максвелл остудив ентузіазм щодо «великого моменту» Клода

Цікаво, що розробник біткойна Грегорі Максвелл висловив менш ентузіастичну думку, заявивши на Hackernews, що 20 вересня він запропонував дослідити ту саму криптографічну загадку своєму другові, у якого закінчувалися кредити Anthropic AI. Штучний інтелект цього друга провів над проблемою кілька годин без успіху, через що Максвелл залишився незадоволеним його здатністю до міркування.

Максвелл, відвертий критик підходу Anthropic до штучного інтелекту, засумнівався, чи не обмежила компанія можливості моделі його друга, і покепкував з розголосу навколо відкриття Клода. Він не став приписувати собі заслуги чи заперечувати висновки, припустивши, що різниця в результатах може просто відображати те, як саме було налаштовано штучний інтелект.

«Я кажу це не для того, щоб натякнути, що misanthropic знову привласнив чужу роботу — це очевидне запитання, яке, безсумнівно, ставили багато людей, і успіх, ймовірно, залежав від експертного використання (якого в прикладі мого друга абсолютно не було)», — написав Максвелл. «Але мене все ж цікавить, чи не погіршила компанія непомітно продуктивність моделі».

Винагорода виплачена, але питання залишаються

Це відкриття нарешті вирішило трирічну суперечку, яку розпочав Вальсорда. Команда Anthropic перерахувала винагороду в розмірі 36 864 доларів організації Internet Security Research Group, яка керує проектом Let’s Encrypt. Вальсорда охарактеризував це відкриття як те, що «допомагає заповнити сторінку історії криптографії та зміцнює нашу впевненість у цих критично важливих криптографічних примітивах». Деякі питання все ще залишаються відкритими. Дослідники до кінця не пояснили, чому деякі математично прийнятні варіанти були відкинуті, а походження початкового значення іншої кривої, B-163, залишається невирішеним.

Проте головна загадка, здається, розгадана. Після десятиліть підозр, спекуляцій та невдалих спроб відтворити нібито забуту секретну фразу, відповідь виявилася у звичайній комп’ютерній процедурі 1990-х років. Таємничі числа АНБ не обов’язково приховували якийсь складний секрет. Можливо, вони просто відлічували час.