Дослідники розробили атаку підробки підпису RSA без факторизації

Криптографи десятиліттями вважали, що єдиний спосіб зламати RSA — розкласти на множники великі числа, на яких тримаються ключі. Команда під керівництвом Надії Генінгер, професорки Каліфорнійського університету в Сан-Дієго, розробила атаку підробки підпису, яка обчислює дійсні підписи RSA без розкладання закритого ключа на множники. Роботу опубліковано в архіві IACR ePrint, рецензування вона ще не пройшла. Найближчим часом результат не становить практичної загрози — хіба що в кількох окремих випадках.

Що робить атака

За словами Генінгер, досі дійсні підписи RSA потребували спершу відновлення закритого ключа розкладанням на множники. Для 1024-бітної RSA це було дуже дорого, але, ймовірно, під силу великим технологічним компаніям чи NSA — близько десятків мільйонів доларів обчислювального часу на ключ; 2048-бітна RSA вважалася цілком недосяжною.

Атака знижує оцінювану стійкість «підручникової» (textbook) RSA до 2^65, 2^90 і 2^119 операцій для ключів 1024, 2048 і 4096 біт відповідно — на порядки нижче 128-бітного рівня (понад 2^128 операцій), який NSA, NIST та ENISA Євросоюзу вимагають від будь-якої криптосистеми. Розкладання одного 1024-бітного ключа оцінювали у 2^80 операцій і від 500 000 до мільйона ядро-років CPU, а підробка підпису новою технікою потребувала 2^65 операцій і лише 1380 ядро-років. Увесь код команда писала вручну, без ШІ та GPU; за словами Генінгер, ці інструменти «майже напевно» знизять рівні стійкості ще більше.

Чому це поки що не практична загроза

Атака працює лише проти реалізацій RSA зі сліпим підписом (blind-signature), відомим також як textbook RSA. Переважна більшість розгорнутих систем використовує доповнення PKCS або PSS, яке додає дані до відкритого тексту перед шифруванням і усуває цю слабкість. Навіть проти застарілих 1024-бітних ключів метод потребує більше обчислень, ніж доступно будь-кому, крім національних держав чи компаній із величезними ресурсами.

Найвідоміший реальний приклад сліпого RSA — Privacy Pass, протокол автентифікації, який дає змогу підтвердити особу, не розкриваючи її; його використовують Apple і Cloudflare. Атака на нього вимагала б скомпрометувати їхній сервер і згенерувати 2^43 підписи — число, яке, за словами Генінгер, «звучить як багато, але це той самий порядок, що й мережевий трафік, який Cloudflare публічно обробляє приблизно за добу». Більшість впроваджень Privacy Pass регулярно змінює ключі, що значно зменшує, але не усуває повністю шанси на успіх.

Чому це важливо

Карстен Ноль, криптограф і керівник інновацій у Allurity, заявив, що якщо результат витримає рецензування, це буде «концептуальний прорив». В основі техніки — варіант алгоритму решета числового поля, винайденого 2007 року, спрямований проти «оракула»: слабкості, яка дає відповіді «так/ні» на конкретні запити. Криптографи активно створюють постквантові альтернативи, адже практичний квантовий комп’ютер очікують за 3–20 років, тож нова атака робить остаточну відмову від RSA ще нагальнішою.