Метод на атака, който значително намалява ресурсите за фалшифициране на цифрови подписи RSA

Изследователи от Калифорнийския университет в Сан Диего разработиха усъвършенствана техника за атака срещу RSA алгоритъма, която позволява подправяне на цифрови подписи без факторизация на основните прости числа, и без необходимост от възстановяване на секретния ключ. Ресурсите, необходими за извършване на атака срещу 1024-битов RSA ключ, са оценени на 1380 години изчисления на едно процесорно ядро, което в наличния университетски клъстър позволи за 5 месеца да се определят параметрите, необходими за генериране на фалшиви RSA подписи (в експеримента не бяха използвани AI ускорители и GPU, и при тяхното прилагане времето за изчисления може да бъде значително съкратено). За сравнение, класическият метод на факторизация изисква за възстановяване на секретния ключ 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