ШІ розгадав 25-річну загадку кривих АНБ: що це означає для біткоїна

Модель штучного інтелекту від Anthropic з'ясувала, звідки взялися незрозумілі «сіди» (початкові значення) для еліптичних кривих NIST, які надало Агентство національної безпеки США, — над цією загадкою криптографи билися близько 25 років. Згідно з публікацією Anthropic від 16 жовтня, числа, з яких виведено криві P-192, P-224, P-256, P-384 і P-521, були зовсім не хешами таємної фрази, а результатом роботи звичайного генератора випадкових чисел 1990-х, запущеного від системного годинника.

У чому була загадка

• У 2000 році Національний інститут стандартів і технологій США (NIST) затвердив набір еліптичних кривих у стандарті цифрового підпису FIPS 186-2 (ECDSA). Зокрема, P-256 лежить в основі значної частки сучасного шифрованого вебтрафіку та цифрових підписів.
• Кожну криву виводили з опублікованого 20-байтного сіда, хеш якого задавав один із параметрів кривої. АНБ передало ці сіди у 1997 році, не пояснивши, як їх обрали.
• Після викриттів Сноудена та історії з генератором Dual EC частина криптографів підозрювала, що агентство могло перебирати сіди, доки не знайшло криву зі слабкістю, відомою лише йому.
• Найвідоміша версія належала математику АНБ Джеррі Солінасу: нібито сіди — це хеші жартівливої фрази. Солінас помер у 2023 році, і того ж року криптоінженер Філіппо Вальсорда та інші оголосили винагороду за розгадку.

Що знайшов Claude

• Співробітник Anthropic попросив внутрішню дослідницьку модель розібратися, не згадуючи чутки про фразу. За словами компанії, модель знайшла відповідь менш ніж за пів години.
• Claude помітив, що в чотирьох із десяти сідів старший біт кожного 32-бітного слова дорівнює нулю — Anthropic оцінює ймовірність цього як 1 до 5810. Це «відбиток» функції lrand48 зі старих бібліотек C.
• Відновивши внутрішній стан генератора й прокрутивши його назад, модель звела кожен сід кривих над простим полем до Unix-часу між травнем 1997 і квітнем 1998 року. Сід P-256 — 1842-й 20-байтний кандидат із запуску, розпочатого 16 серпня 1997 року о 01:52:34 UTC.
• Вальсорда каже, що незалежно відтворив метод і підтвердив результат. Команда передала винагороду Internet Security Research Group — неприбутковій організації, що стоїть за Let's Encrypt, — і сума потроїлася до $36 864.

Чи щось зламано?

Ні. Anthropic наголошує, що це «не криптографічний злам, не нова атака і не слабкість», і користувачам не потрібно нічого робити інакше. Сід, отриманий з генератора, запущеного від годинника, і який тепер може відтворити будь-хто, залишає набагато менше простору для навмисних маніпуляцій. Відкриті питання лишаються: кілька придатних кандидатів було пропущено (у тому ж запуску для P-256 придатну криву дає й кандидат 876), сід бінарної кривої B-163 досі не пояснено, як і вибір базових точок для P-224, P-256, P-384 і P-521.

Чому біткоїна це не стосується

Біткоїн, а згодом і Ethereum, використовують іншу криву — secp256k1. Її задають дві невеликі фіксовані константи, тож налаштовувати майже нічого і сховати слабкість ніде, як зазначає CoinDesk. Утім, той самий передбачуваний генератор був би катастрофою всередині гаманця: приватний ключ, створений через lrand48, міг би відновити будь-хто, хто приблизно вгадав час його створення. Саме тому гаманці використовують криптографічно стійку випадковість — див. наш матеріал про те, що таке апаратний гаманець.

Справжня довгострокова загроза для біткоїна — квантові обчислення: вони могли б вивести приватний ключ із відкритого публічного незалежно від кривої. Цього тижня Google повідомив про великий крок у зменшенні помилок на чипі Willow (наш матеріал), а новий Quantum Alliance відстежує монети з розкритими ключами. Проте жодна наявна машина навіть близько не здатна зламати ключ біткоїна.