Новий метод підробки підписів знижує захист RSA без доповнення
Дослідники описали метод підробки підписів для RSA зі сліпими підписами, який потребує менше обчислень, ніж факторизація ключа.
Дослідники запропонували метод підробки цифрових підписів для реалізацій RSA зі сліпими підписами, який потребує значно менше обчислень, ніж факторизація ключа. Як повідомляє Ars Technica, атака застосовна лише до RSA без схем доповнення PKCS або PSS і не становить практичної загрози для переважної більшості сучасних застосувань цього криптосистемного алгоритму.
Автори роботи використали варіант алгоритму решета числового поля, створений у 2007 році. Метод спрямований на так званий оракул — слабкість у RSA та деяких інших криптосистемах, яка дає відповіді «так» або «ні» на спеціально сформовані запити. Велика кількість таких операцій дає змогу зібрати дані, достатні для розшифрування або підробки підпису.
Менші обчислювальні витрати
За оцінкою дослідників, нова атака знижує рівень захисту для ключів RSA довжиною 1024, 2048 і 4096 біт до 2⁶⁵, 2⁹⁰ та 2¹¹⁹ операцій відповідно. Для порівняння, факторизація 1024-бітного ключа потребує орієнтовно 2⁸⁰ операцій і від 500 тисяч до 1 мільйона процесорних ядер-років. Підробка підпису за допомогою решета, за наведеними даними, зайняла 1380 ядер-років.
Ці показники можуть зменшитися: команда Heninger виконувала програмування вручну та не застосовувала для підробок ані штучний інтелект, ані графічні процесори. Дослідниця заявила, що ці інструменти «майже напевно» ще знизять рівні захисту.
Ризики для Privacy Pass
Більшість реалізацій RSA використовує PKCS або PSS — формати, які додають дані перед шифруванням і усувають оракул, необхідний для цієї атаки. Водночас RSA зі сліпими підписами досі застосовують у деяких системах. Серед відомих прикладів — протокол Privacy Pass, що дає користувачам змогу автентифікуватися без розкриття особи. Його використовують Apple, Cloudflare та інші організації.
Для атаки на Privacy Pass зловмисникові потрібно скомпрометувати сервер однієї з організацій і згенерувати 2⁴³ підписів. За словами Heninger, цей обсяг зіставний із мережевим трафіком, який Cloudflare, за її словами, публічно оцінювала приблизно в один день. Регулярна ротація ключів у більшості реалізацій Privacy Pass істотно знижує, але не усуває автоматично ймовірність успіху атаки.
