Дослідники з Каліфорнійського університету в Сан-Дієго розробили вдосконалену техніку атаки на алгоритм RSA, що дозволяє підробляти цифрові підписи без факторизації простих чисел, що лежать в основі RSA, і без необхідності відновлення закритого ключа. Ресурси, необхідні для здійснення атаки на 1024-розрядний ключ RSA, оцінені в 1380 років обчислень на одному процесором ядрі, що на наявному університетському кластері дозволило за 5 місяців визначити параметри, необхідні для формування фіктивних RSA-підпис (в експерименті не використовувалися AI-прискорювачів і G прискорювачів G). Для порівняння класичний метод факторизації вимагає відтворення закритого ключа RSA-1024 від 500 тисяч до мільйона років обчислень на одному процесором ядрі.
Для проведення атаки потрібна наявність можливості багаторазово відправляти запити на підписання даних, що формуються атакуючим, наприклад, звертаючись до сервісу авторизації або HSM-модулю. Для визначення параметрів RSA-1024 достатньо відправити 232 подібних запитів, а для атаки на ключі RSA-2048, що використовуються в протоколі Privacy Pass, - 243. Отримавши масив підписаних даних, запускається тривалий процес обчислення параметрів (для RSA-1024 може бути створено 265 операцій), після отримання витрачаючи на кожен підпис приблизно 180 годин обчислень на одному ядрі.
Метод застосовується тільки для RSA-підписів, в яких не використовується форматування та додаткове заповнення перед шифруванням (padding). Атаку схильні до реалізації сліпого підпису, у тому числі використовувані в протоколі Privacy Pass. Більшість реалізацій RSA, що знаходяться в побуті, включаючи PKCS#1v1.5 і RSA-PSS (використовуються в TLS і SSH), застосовують додаткове заповнення і атаці не схильні.
В основі шифрування RSA лежить операція зведення в ступінь модуля великого числа. У відкритому ключі міститься модуль та ступінь. Модуль формується на підставі двох випадкових простих чисел, які відомі лише власнику закритого ключа. Запропонований метод заснований на опублікованому в 2007 році дослідженні, що довело, що вилучення кореня у зазначеному у відкритому ключі ступені з зашифрованого повідомлення без інформації про секретних множників є менш ресурсомісткою операцією, ніж факторизація самих множників.
Використовуючи спеціальний метод решета числового поля (SNFS), дослідникам вдалося звести складність компрометації ключів RSA-1024 до 265 операцій, що дозволяє здійснювати практичні атаки на сучасних кластерах. Для 2048-розрядних ключів RSA складність атаки оцінюється в 290, що теоретично можна здійснити великими корпораціями або спецслужбами. Для 4096-розрядних ключів складність атаки становить 2119 операцій, що на практиці поки що недосяжно, але нижче за мінімум 2128, рекомендований АНБ, Національним інститутом стандартів і технологій та Європейським агентством з мережевої та інформаційної безпеки.
Джерело: opennet.ru
