Slabý generátor náhodných čísel umožňuje faktorizovať RSA moduly
Akoby nestačilo napadnutie certifikačných autorít v roku 2011 a nedávne priznanie Trustwave, že vydávala certifikáty na korporátne man-in-the-middle útoky, našla sa ďalšia trhlina spôsobená nesprávnou implementáciou generátora náhodných čísel (kauza s debianími slabými kľúčami bola podobne spôsobená chybou v náhodnom generátore).
Tým výskumníkov vedený A. Lenstrom z EPFL našiel v databáze certifikátov z SSL Observatory a iných zdrojoch ďalšie páry kľúčov, ktoré zdieľajú v RSA module prvočíslo. To znamená, že použitím obyčajného vyše 2000 rokov starého Euklidovho algoritmu je možné niektoré RSA moduly faktorizovať. Z ich výsledkov vyplýva, že zhruba 2 z 1000 kľúčov idú týmto spôsobom faktorizovať. Testovali celkovo 11.7 milióna RSA, ElGamal, DSA a ECDSA kľúčov, z toho šlo uvedenou metódou prelomiť cca 27000 RSA kľúčov.
DSA a ElGamal kľúče nevykazovali žiadne podobné štatistické anomálie, ECDSA kľúč bol len jeden. Z uvedeného sa dá usudzovať, že PGP a GnuPG slabým generátorom netrpia (pretože väčšina testovaných ne-RSA kľúčov bola vygenerovaná jedným z týchto softwarov). Zatiaľ sa nevie, ktoré implementácie vygenerovali zmienené slabé RSA kľúče.
V diskrétnom grafe použitom na modelovanie zdieľaných prvočísiel a modulov je prvočíslo reprezentované vrcholom, hrana spája dve prvočísla patriace k modulu (moduly s viacerými prvočíslami neboli nájdené). V ideálnom prípade by vrcholov malo byť dvakrát toľko čo hrán, tj. žiadny pár RSA modulov nezdieľa prvočíslo. V Lenstrových výsledkoch sa ale nachádza 1995 nesúvislých komponent s tromi a viac vrcholmi.
Preložené do „nematematičtiny“: existuje 1995 skupín po niekoľkých RSA kľúčoch, kde keď poznáte prvočísla aspoň jedného z vrcholov, môžete faktorizovať ostatné. Rovnako znalosť dvoch modulov z rovnakej skupiny umožňuje použiť Euklidov algoritmus na zistenie jedného z prvočísiel a teda faktorizovanie oboch modulov.
Lenstra tiež zmieňuje dlhšie známy fakt o zdieľaní RSA modulov v X.509 SSL/TLS certifikátoch. Podľa jeho údajov 4 % kľúčov sú zdieľané, často medzi nesúvisejúcimi organizáciami alebo jedincami. Časť „s nesúvisejúcimi organizáciami“ ale treba brať trocha s rezervou.
O zdieľaní kľúčov v certifikátoch som mal pár debát s rôznymi výskumníkmi, napríklad s Ralphom Holzom, ktorého práca SSL Landscape je spomínaná v Lenstrovom príspevku. Obaja sme našli rôzne kľúče zdieľané medzi zdanlivo nesúvisejúcimi stranami, ale keď sa človek do toho začal vŕtať viac, tak zistil, že nejak prepojené sú (ale to treba robiť ručne prehliadaním obchodných registrov, atp.). Napriek tomu existujú kľúče ktoré sú zdieľané medzi organizáciami bez toho, aby to bolo úmyselné (napríklad niekto nezmení na VPS hostingu SSH/SSL kľúče, ktoré sa nakopírujú z inštalačného obrazu).
Podľa iného článku sa problém týka hlavne embedded zariadení, ktoré majú pri generovaní kľúčov malý zdroj entropie, takže netreba až tak moc panikáriť. Linkovaný článok obsahuje veľa technických podrobností, hlavná pointa je, že najskôr sa to netýka internetového bankovníctva a iných vysoko citlivých aplikácií.
Záujemcov o podrobnosti odkážem na pôvodný príspevok od Lenstra, et al publikovaný na eCrypt archíve (pdf).
Ondrej Mikle
0
