Исследователи из Калифорнийского университета в Сан-Диего и французского Inria подделали цифровую подпись RSA с 1024-битным ключом, не вычисляя закрытый ключ. Эксперимент занял пять месяцев на вычислительном кластере, суммарно 1380 процессорных ядро-лет.
RSA, распространённый алгоритм цифровых подписей и шифрования, обычно оценивают по сложности факторизации: разложения большого числа из открытого ключа на простые множители. По оценке авторов, факторизация использованного ими числа потребовала бы от 500 тысяч до миллиона ядро-лет.
Команда пошла другим путём. В роли «оракула», то есть сервиса, выполняющего операции с закрытым ключом по внешним запросам, выступил HSM, аппаратный модуль для защищённого хранения ключей. Исследователи получили около 4,29 млрд результатов необработанных RSA-операций, а затем смогли создавать подписи офлайн. Закрытый ключ при этом не покидал HSM. После основной подготовки каждая новая подделка требовала ещё около 180 ядро-лет, пишет HWBusters.
Метод предложили ещё в 2007 году, но до полноценного эксперимента на 1024-битном ключе дошли только сейчас. Работа опубликована в архиве IACR ePrint как препринт: она ещё не прошла рецензирование, а независимого повторения результата пока нет, отмечает The Hack Academy.
Повода срочно выкорчёвывать RSA из всех систем пока нет. Атака требует доступа к необработанным RSA-операциям без дополнения данных перед подписью. Распространённые схемы PKCS#1 v1.5 и RSA-PSS обычно такого доступа не дают. В зоне внимания находятся слепые RSA-подписи и отдельные интерфейсы HSM. Кроме того, практический эксперимент проведён только для устаревшего 1024-битного ключа; оценки для 2048 и 4096 бит пока остаются расчётными.
Что это значит
- Для вас. Обычным пользователям ничего делать не нужно: исследование не показывает массовый взлом сертификатов или защищённых соединений.
- Что сделать. Администраторам и разработчикам стоит найти оставшиеся 1024-битные ключи подписи и запланировать замену. В системах со слепыми подписями и HSM нужно проверить, могут ли внешние пользователи запрашивать необработанные RSA-операции с выбранными ими данными.
- За чем следить. Главные маркеры: прохождение экспертной проверки, независимое повторение эксперимента и результаты оптимизации на графических процессорах. Именно они покажут, насколько метод опасен за пределами академического кластера.