Svájci kutatók egy érdekes tanulmányt publikáltak a napokban a weben elérhető nyilvános kulcsok jóságáról. Az eredmények alapján elmondható, hogy átlagosan ezerből két RSA kulcs gyenge valamilyen szempontból. Mivel ehhez képest a DSA (hagyományos és elliptikus görbéken alkalmazott) és ElGamal eljárásokhoz tartozó titkokkal kapcsolatban az eredmények jobbak, a szerzők alátámasztottnak látják azt a véleményt, hogy egy komponensű titkokkal operálni biztonságosabb, mint két komponensűekkel.
Egy kis frissítés: Az RSA kulcsgeneráláshoz két, általában p-vel és q-val jelölt, nagy prímszámra van szükség. Ezeket a számokat (ál)véletlengenerátorokkal sorsolják, és prímtesztelő eljárásokkal győződnek meg a jóságukról. A nyilvános kulcs az n=pq és a (p-1)(q-1)-hez relatív prím e számokból alkotott páros. A d titkos kulcs e multiplikatív inverze, azaz d=e^(-1) mod (p-1)(q-1). (Jelenlegi ismereteink szerint) a titkos kulcs, csak p és q ismeretében számítható hatékonyan, p és q a nyilvános komponensekből nem számítható vissza.
A következő néhány bekezdés nagy vonalakban bemutatja az alkalmazott módszereket és a főbb eredményeket, némi matekos beállítottság nem árt. Ha csak a konklúzió érdekel, hajts a poszt végére!
+++
Az elvégzett tesztek mindenek előtt azt mutatják, hogy a széles és jól kitesztelt eszköztár ellenére a kriptográfiával kapcsolatos feladatok kezelése néhány esetben még mindig nehéz feladatnak bizonyul. Néhány esetben a publikus exponens (e) értéke 1 vagy páros, előfordulnak feketelistás Debian kulcsok, prím n értékek, alacsony (2^24-nél kisebb) faktor értékek, és olyan is megesik, hogy a kulcsokat hibásan másolják be a rendeltetési helyükre. Szintén figyelemre méltó, hogy néhány éve tanúsított kulcsok között is előfordul rövid, 512-bites modulus.
A cikk megállapításának alapját azonban nem ezek az eredmények, hanem a megosztott tényezők problematikája adja. Közös p érték esetén a különböző n1, n2-höz tartozó q1, q1 tényezők triviálisan kiszámíthatók, melynek következtépben mindkét titkos kulcs kompromittálódik. A problémát egy gráffal modellezhetjük, melynek csúcsai a prímszámok, az élek pedig az n modulusok, melyek saját tényezőiket kötik össze. Optimális esetben a weben megtalálható tanúsítványok paramétereit tartalmazó gráf a tanúsítványok számával (c) megegyező élet tartalmazna, melyek ugyanennyi összefüggő komponenst határoznak meg.
Az n értékek birtokában ez a gráf elkészíthető Daniel J. Bernstein módszerével, ami egy "közel lineáris" komplexitású algoritmust ad arra, hogy egész számok véges halmazából kiválasszunk egy olyan, egymáshoz relatív prímekből álló részhalmazt, melynek tagjainak szorzataként az eredeti halmaz bármely eleme előállítató. Ez az eredeti prímtényezőkre bontás problémájának leegyszerűsítése, ami viszont remekül illeszkedik ehhez a feladathoz. A feladat ilyen módon "órákon belül" elvégezhető egyetlen hagyományos CPU-n.
A valóságban létrejövő gráf messze van az optimálistól. Az eredmények szerint nagyjából kétezer olyan összefüggő komponens áll elő, ami legalább két n-élet tartalmaz. Ezen részgráfok túlnyomó része egy mélységű fa, ezek döntő többsége pedig két levéllel rendelkezik, de a kutatók találtak magasabb pontszámú példányokat, például egy 4627 levelű fát is (az ebben szereplő modulusok kiadói megismerhetik egymás kulcsait). Különböző összekötettéseket használva végül majdnem 13000 modulust sikerült tényezőkre bontani, ami a vizsgált halmaz 0,2%-a. Az eredményt tovább rontják a közösen használt modulusok, ahol idegen publikus kulcsokhoz azonos n érték, vagyis azonos titkos kulcsok tartoznak.
Mint kiderült, mások is dolgoztak ezen a problémán. A Freedom to Tinker kutatói hasonló módszerekkel az weben elérhető SSL kulcsok 0,4%-át kompromittálták, az összegyűjtött tanúsítványok 1%-ának modulusa pedig legalább két esetben előfordul. Az eljárást nagy vonalakban ismertető blog poszt rávilágít arra, hogy a probléma jórészt a különböző beágyazott eszközök által használt kulcsok esetében jelentkezik. A vizsgált eszközök 4,6%-a egyszerűen az előre telepített - minden példányban azonos - kriptográfiai paramétereket használja. Másrészt vannak olyan eszközök is, melyek első induláskor generálják ezeket a paramétereket. Ebben az esetben azonban az álvéletlen generátort sokszor csak alacsony entrópiájú adatokkal lehet inicializálni, így a generált prím számok közül legalább az egyik egy kis elemszámú halmazból fog kikerülni (a második generálása előtt sokszor újra seedelik a PRNG-t).
+++
Mindkét eredmény hiánypótlónak számít, és valószínűleg még sok kutatás fog rájuk hivatkozni a jövőben. Bár a megállapított arányok - százezernyi több helyen is használt, tízezerni komprommitálható kulcs - félelmetesnek tűnhetnek, ahogy általában, most sincs ok a pánikra. Először is, gyakorlatilag az összes gyenge kulcs hitelesítetlen vagy lejárt tanúsítványokhoz tartozott, melyekben amúgy sem lenne okunk megbízni, arra pedig a kutatás nem tér ki, hogy ezek közül egyáltalán mennyi volt ténylegesen használatban (valószínűleg nem sok). Az önaláírt tanúsítványok egyébként is nagyságrendekkel gyakoribbak, mint a gyenge kriptográfiai paraméterekkel rendelkezők. Fontos felismerni azt is, hogy a feltárt problémák nem adnak lehetőséget célzott támadásra: ha ismerem is egy gyenge kulcs privát tagját, nem tudom, hogy hol használják azt. Annak az esélye pedig, hogy egy gyenge kulcsot fontos helyen használnak, gyakorlatilag elhanyagolható.
Fontos megjegyezni ugyanakkor, hogy a vizsgálatok csak a legegyszerűbb támadási módszerekre támaszkodtak. Kifinomultabb módszerekkel, illetve nagyobb számítási teljesítménnnyel feltehetően még több kulcs elvérzett volna. Nem lehet szó nélkül elmenni a gyenge paraméterek és a generáló eszközök jellege közötti korreláció mellett. Az eredmények szerint gyakorlatilag minden nagy beágyazott eszközökkel foglalkozó gyártó termékei hajlamosak alacsony entrópiával dolgozni, fontos lenne tehát, hogy hangsúlyt kapjon az ilyen kis entrópiát nyújtó környezetek kutatása.
Persze magukkal a véletlengenerátorokkal is van probléma, ilyen algoritmusokatt konstruálni ugyanis nehéz, tesztelni őket pedig még nehezebb. Ebből kiindulva nem tűnik elrugaszkodottnak az az ötlet, hogy egy kriptorendszerbe a véletlengenerátor buherálásával helyezzenek hátsó kaput - persze az összesen hét különböző értéket előállítani képes algoritmus esetében valószínűleg inkább egyszerű hozzánemértésről lehetett szó.
A több komponensű titkokkal szembeni érvelésbe bele lehet kötni egyrészt azért, mert a kulcsmenedzsmentből adódó problémák (lejárt tanúsítványok, tanúsítatlan kulcsok, stb.) bőven elnyomják az esetleges elméleti gyengeségeket. Másrészt a kutatás fókuszában eleve az RSA-val szembeni támadások álltak, miközben más szemszögből az egy komponensű titokkal dolgozó algoritmusok tekinthetők "gyengébbnek". Az RSA-t tehát még bőven nem kell temetni, mint ahogy a többi nyilvános-kulcsú módszert sem.
