Даследнікі з Каліфарнійскага ўніверсітэта ў Сан-Дыега распрацавалі ўдасканаленую тэхніку нападу на алгарытм 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
