Kalifornian yliopiston San Diegossa tutkijat ovat kehittäneet parannetun hyökkäystekniikan RSA-algoritmia vastaan, joka mahdollistaa digitaalisten allekirjoitusten väärentämisen ilman, että taustalla olevia RSA-alkulukuja tarvitsee tekijöihin jakaa ja yksityistä avainta palauttaa. 1024-bittisen RSA-avaimen hyökkäämiseen tarvittavien resurssien arvioidaan olevan 1 380 vuotta laskentaa yhdellä suorittimen ytimellä. Yliopiston olemassa olevan klusterin avulla he pystyivät määrittämään väärennettyjen RSA-allekirjoitusten luomiseen tarvittavat parametrit viidessä kuukaudessa (kokeessa ei käytetty tekoälykiihdyttimiä tai näytönohjaimia, mutta niiden käyttö saattoi lyhentää laskenta-aikaa merkittävästi). Vertailun vuoksi klassinen tekijöihinjakomenetelmä vaatii 500 000 - miljoona vuotta laskentaa yhdellä suorittimen ytimellä RSA-1024-yksityisen avaimen rekonstruoimiseksi.
Hyökkäyksen suorittaminen edellyttää kykyä lähettää toistuvasti pyyntöjä hyökkääjän luoman datan allekirjoittamiseksi esimerkiksi käyttämällä valtuutuspalvelua tai HSM-moduulia. RSA-1024-parametrien määrittämiseen riittää 232 tällaisen pyynnön lähettäminen, ja Privacy Pass -protokollassa käytettyjen RSA-2048-avainten hyökkäämiseen riittää 243. Kun allekirjoitettu data on vastaanotettu, alkaa pitkä parametrien laskentaprosessi (noin 265 operaatiota RSA-1024:lle). Kun nämä parametrit on laskettu, hyökkääjä voi luoda väärennettyjä allekirjoituksia mille tahansa datalle käyttäen noin 180 tuntia laskentaa yhteen ytimeen allekirjoitusta kohden.
Menetelmää voidaan soveltaa vain RSA-allekirjoituksiin, jotka eivät käytä muotoilua tai täyttöä ennen salausta. Sokeat allekirjoitustoteutukset, mukaan lukien Privacy Pass -protokollassa käytetyt, ovat alttiita hyökkäykselle. Yleisimmin käytetyt RSA-toteutukset, mukaan lukien PKCS#1v1.5 ja RSA-PSS (käytetään TLS:ssä ja SSH:ssa), käyttävät täyttöä eivätkä ole alttiita hyökkäykselle.
RSA-salaus perustuu operaatioon, jossa suuri luku korotetaan potenssiin modulo suuri luku. Julkinen avain sisältää modulon ja potenssin. Moduuli generoidaan käyttämällä kahta satunnaista alkulukua, jotka vain yksityisen avaimen omistaja tietää. Ehdotettu menetelmä perustuu vuonna 2007 julkaistuun tutkimukseen, joka osoitti, että salatun viestin juuren purkaminen julkisessa avaimessa määritettyyn potenssiin ilman salaisten tekijöiden tuntemusta on vähemmän resursseja vaativa operaatio kuin itse tekijöiden jakaminen tekijöihin.
Käyttämällä erikoistunutta seulapohjaista numerokenttämenetelmää (SNFS) tutkijat pystyivät vähentämään RSA-1024-avainten murtamisen monimutkaisuutta 265 operaatioon, mikä mahdollisti käytännön hyökkäykset nykyaikaisia klustereita vastaan. 2048-bittisten RSA-avainten monimutkaisuudeksi arvioidaan 290 operaatiota, mikä on teoriassa mahdollista suurille yrityksille tai tiedustelupalveluille. 4096-bittisten avainten monimutkaisuus on 2119 operaatiota, mikä on tällä hetkellä käytännössä mahdotonta saavuttaa, mutta alhaisempi kuin NSA:n, National Institute of Standards and Technologyn ja Euroopan verkko- ja tietoturvaviraston suosittelema 2128 operaation vähimmäismäärä.
Lähde: opennet.ru
