Kalifornijas Universitātes Sandjego pētnieki ir izstrādājuši uzlabotu uzbrukuma tehniku pret RSA algoritmu, kas ļauj viltot digitālos parakstus, nefaktorizējot pamatā esošos RSA pirmskaitļus un bez nepieciešamības atgūt privāto atslēgu. Resursi, kas nepieciešami, lai uzbruktu 1024 bitu RSA atslēgai, tiek lēsti 1380 aprēķinu gadu apmērā vienā procesora kodolā. Izmantojot universitātes esošo klasteri, tas ļāva viņiem piecu mēnešu laikā noteikt parametrus, kas nepieciešami viltotu RSA parakstu ģenerēšanai (eksperimentā netika izmantoti mākslīgā intelekta paātrinātāji vai grafiskie procesori, taču to izmantošana varētu ievērojami samazināt aprēķinu laiku). Salīdzinājumam, klasiskā faktorizācijas metode prasa no 500 5 līdz miljonam aprēķinu gadu vienā procesora kodolā, lai rekonstruētu RSA-1024 privāto atslēgu.
Lai veiktu uzbrukumu, ir nepieciešama iespēja atkārtoti sūtīt pieprasījumus uzbrucēja ģenerēto datu parakstīšanai, piemēram, piekļūstot autorizācijas pakalpojumam vai HSM modulim. Lai noteiktu RSA-1024 parametrus, pietiek nosūtīt 232 šādus pieprasījumus, bet, lai uzbruktu RSA-2048 atslēgām, kas tiek izmantotas Privacy Pass protokolā, pietiek ar 243. Saņemot parakstīto datu masīvu, sākas ilgs parametru aprēķināšanas process (aptuveni 265 darbības RSA-1024 gadījumā). Kad šie parametri ir aprēķināti, uzbrucējs var izveidot viltotus parakstus jebkuriem datiem, katram parakstam veltot aptuveni 180 aprēķinu stundas.
Šī metode ir piemērojama tikai RSA parakstiem, kas pirms šifrēšanas neizmanto formatējumu vai papildināšanu. Aklo parakstu ieviešanas, tostarp tās, kas tiek izmantotas Privacy Pass protokolā, ir neaizsargātas pret uzbrukumu. Visbiežāk izmantotās RSA ieviešanas, tostarp PKCS#1v1.5 un RSA-PSS (izmantotas TLS un SSH), izmanto papildināšanu un nav neaizsargātas pret uzbrukumu.
RSA šifrēšana balstās uz liela skaitļa kāpināšanu pakāpē, kas tiek aprēķināta no liela skaitļa. Publiskā atslēga satur moduli un pakāpi. Modulis tiek ģenerēts, izmantojot divus nejaušus pirmskaitļus, kas zināmi tikai privātās atslēgas īpašniekam. Piedāvātā metode ir balstīta uz 2007. gadā publicētu pētījumu, kurā tika pierādīts, ka šifrēta ziņojuma saknes iegūšana publiskajā atslēgā norādītajā pakāpē, nezinot slepenos faktorus, ir mazāk resursu ietilpīga darbība nekā pašu faktoru faktorizācija.
Izmantojot specializētu sieta skaitļu lauka metodi (SNFS), pētnieki spēja samazināt RSA-1024 atslēgu kompromitēšanas sarežģītību līdz 265 operācijām, nodrošinot praktiskus uzbrukumus mūsdienu klasteriem. 2048 bitu RSA atslēgām sarežģītība tiek lēsta 290 operāciju apmērā, kas teorētiski ir iespējams lieliem uzņēmumiem vai izlūkdienestiem. 4096 bitu atslēgām sarežģītība ir 2119 operācijas, kas pašlaik praksē nav sasniedzama, bet ir zemāka par NSA, Nacionālā standartu un tehnoloģiju institūta un Eiropas Tīklu un informācijas drošības aģentūras ieteikto minimālo 2128 operāciju skaitu.
Avots: opennet.ru
