Изследователи в областта на сигурността демонстрираха по-бърз начин за компрометиране на определени внедрявания на RSA, без да факторизират публичния модул, което оспорва предположението, че практическата устойчивост на RSA винаги следва цената на факторизирането на цели числа.

Атаката превръща временния достъп до услуга за подписване или декриптиране с необработен RSA в постоянна възможност за фалшифициране на подписи или офлайн декриптиране на избрани шифротекстове.

Laura Shea, Miro Haller, Adam Suhl, Nadia Heninger и Emmanuel Thomé приложиха техниката срещу 1024-битов RSA ключ. Тяхната изчислителна работа е консумирала 1380 CPU ядрени години за пет месеца и е изисквала 232 заявки към оракула. За сравнение, факторизирането на 1024-битов RSA модул се оценява на приблизително от 500 000 до един милион ядрени години.

Методът, наречен eNFS от изследователите, принадлежи към семейството на решетото на числовото поле. Вместо общото решето на числовото поле, използвано за факторизиране на RSA модули, той се доближава до сложността на по-бързото „специално“ решето на числовото поле, като заменя част от обичайната математическа работа с отговори от оракула за подписване. От изключителна важност е, че той никога не възстановява простия множител или частния RSA ключ.

Нов начин за разбиване на RSA

Атаката се развива на етапи. Предварително изчисление от приблизително 1200 ядрени години зависи единствено от публичния модул и експонентата. След това атакуващият изпраща избрани стойности към необработения RSA оракул. След като тези отговори бъдат събрани, достъпът може да бъде прекъснат: фалшифицирането на всеки избран подпис или декриптирането на цел отнема още около 180 ядрени години и може да се повтаря офлайн.

Основният алгоритъм не е нов. Antoine Joux, David Naccache и Emmanuel Thomé го представят през 2007 г., но новата разработка осигурява първата му реализация и широкомащабна демонстрация върху 1024-битов ключ. Кодът разчита до голяма степен на CADO-NFS, като същевременно добавя необходимите инженерни решения за избор на полиноми, пресяване, линейна алгебра, извличане на корени и спускане в този мащаб.

Това не е универсално разбиване на RSA. Атакуващият се нуждае от временен достъп до оракул за необработено степенуване — възможност, която конвенционалните RSA подписи, използващи PKCS#1 v1.5 или RSA-PSS допълване, обикновено не разкриват. По-вероятните мишени включват HSM интерфейси, позволяващи необработени PKCS#11 RSA операции, и протоколи за слепи подписи като Privacy Pass, където заслепените заявки могат да осигурят необходимото поведение на оракула.

Изследователите оценяват работата на 2^{90} и 2^{43} заявки към оракула срещу 2048-битов RSA в този модел, в сравнение с обикновено приписваната 112-битова сила на факторизиране. Те прогнозират приблизително 2^{119} работа за 4096-битов RSA, което го оставя под съвременната цел за 128-битова сигурност. Тези разходи остават извън възможностите на повечето атакуващи, но могат да имат значение за добре финансирани злонамерени субекти и протоколи с дълготрайни публични ключове.

Организациите не трябва незабавно да се отказват от правилно коригирания RSA. Операторите трябва да деактивират излишните необработени RSA механизми, да одитират HSM политиките, да ограничат излагането на оракули и по-често да ротират ключовете за уязвими слепи подписи.

Проектантите на протоколи могат да проучат доказателства с нулево знание за правилно форматирани заявки, докато дългосрочната миграция трябва да даде предимство на съвременните схеми за цифрови подписи и постквантовата криптография, вместо по-големите RSA ключове да се разглеждат като трайно решение.