2008/10/15

RSA-közép

Többen panaszkodtatok, hogy a blogom nem technikai jellegű, nem arról írok, hogy mi is történik a cégben. Ezen most egy picikét változtatok.

Vannak a gyárban mindenféle „tech talk”-ok. Néha kollégák, néha külső meghívott vagy épp csak betoppanó emberek beszélnek erről-arról, beül akit érdekel. Néha unalmas (laptop nem árt ha van kéznél), néha viszont nagyon hasznos és érdekes. A mai talán az eddigiek csúcsa volt.

Adi Shamir járt itt. Róla első körben annyit kell tudni, hogy a számítástechnika legelterjedtebb (nyilvános kulcsú) titkosítási algoritmusának, az RSA-nak a középső betűjét ő adta. Nagyjából az a szakmája, hogy feltörhetetlen titkosításokat talál ki, majd azokat feltöri. :-)

Az RSA-t mi is tanultuk az egyetemen, sőt, aztán uszkve tizenegy alkalommal gyakorlatot is tartottam belőle, aminek kapcsán újra és újra megpróbáltam igazán megtanulni és átérezni, többé-kevésbé sikerült is. Az algoritmus 30 éves, és mai tudásunk szerint matematikai értelemben feltörhetetlen.

Na de mi van akkor, ha egy matematikailag tökéletes algoritmust a valós világban korántsem tökéletes számítógépek hajtanak végre? A mai tech talk ezt a témát járta körül.

Mutatott két trükköt, amikről már korábban hallottam. Az egyik arról szólt, hogy ha ellopnak egy becsukott (sleep módban lévő) laptopot, amin titkosított a fájlrendszer, akkor hogyan lehet egyszerűen hozzájutni az adatokhoz. A kulcs nyilván a memóriában van valahol, hiszen az operációs rendszer egyfolytában használja a diszkműveletekhez, és a diszken nyilván nem lehet. (A felhasználó mondjuk egyszer begépeli a gép indulásakor.) Nos, íme a teendők. A gépet fel kell nyitni, a memóriát gyorsan lefagyasztani, így az áramtalanítás után kábé 1 percig nagyjából megőrzi tartalmát. Ezalatt egy spéci rendszert kell elindítani, ami lementi a memória tartamát, utána már bőven van idő azt kielemezni. Persze nem könnyű megtalálni a kulcsot gigabyte-nyi adatban, de segít benne, hogy a diszk titkosításra használt tipikus algoritmus (jajj, ez itt konkrétan az AES volt?) olyan természetű, hogy több hasonló kulcsot is használ, melyek valószínűleg a memóriában egymás mellett helyezkednek el, tehát csak egy nagyjából ismétlődő mintát kell keresni, ráadásul ha a több hasonló cuccot megtaláljuk egymás mellett, az erősen segít az áramtalanítás során megváltozott néhány bit helyreállításában is.

A másik trükk azt használja ki, hogy a kétmagos processzorokban egy közös cache (gyorsítótár) van. Persze ennél sokkal több konkrétumot is tudni kell a cache pontos működéséről, leginkább arról, hogy mely különböző memóriacímek osztoznak közös gyorsítótár cellán, ahol tehát az egyik berakása kiüti a másikat. A feltörés alap ötlete az, hogy ha az egyik mag a titkosító kódot futtatja, a másik pedig ezt próbálja meg feltörni, akkor aztáltal, hogy bizonyos memóriacímekről gyorsan (tehát cache-ből), bizonyosakról pedig csak lassan (tehát az igazi memóriához fordulva) tudja kiolvasni az ott lévő értéket, le tud vonni következtetést, hogy a másik (titkosító) folyamat használt-e bizonyos memóriacímeket, és ez vezethet a kulcs megfejtéséhez. Konkrétan a Linux fájlrendszerek AES kódolását lehet állítólag a másodperc törtrésze alatt feltörni ezzel a módszerrel.

Szó volt a kvantum kriptográfia, mint új irányzat alapjaival, aminek valahol a határozatlansági reláció az alapja, nevezetesen hogy ha például egy szem foton polarizációja hordoz információt, akkor ezt nem lehet egyszerre megfigyelni és változatlanul hagyni. Erre alapozva olyan kommunikációs csatorna építhető, ahol a felek meg tudják állapítani, ha valaki lehallgatja a kommunikációt. És amikor eljutottunk arra a pontra, hogy na ez így nyilván tökéletes és feltörhetetlen, akkor megmutatta, hogy egy egyszerű trükkel hogyan lehet mégis feltörni. Az egésznek csak az a titka, hogy teljesen másképp kell gondolkodni. Tök érdekes volt hallani erről, ez a téma teljesen ismeretlen volt számomra.

Az RSA kódolást is feltörtük, kétféleképpen is.

Az egyik egy képzeletbeli eszmefuttatás volt. Láttunk már processzort, amelyik nem tud osztani; táblázatprogramot, amelyik nem tud szorozni (vagy összeadni? – mindegy). Mi van, ha egy processzor nem tud szorozni? Mondjuk akár egy véletlen hiba, akár a titkosszolgálat szándékos közreműködése következtében elképzelhető, hogy van két konkrét 64 bites szám, melyek szorzatát picit hibásan számolja ki. (A világegyetem összes processzora sem lenne elég ahhoz, hogy az összes ilyen szorzást leellenőrizzük épeszű idő (értsd: párezer év) alatt.) Ha valaki ismeri ezt a két számot, nyert ügye van. Levezettük, hogy ennek a számpárnak az ismeretében hogyan lehet egy RSA-kódolást végző számítógép titkos kulcsát megszerezni. A levezetés végén a hallgatóságban tőlem balra valaki halkan csak ennyit mondott: „Fuck!” Azt hiszem, ennél jobban nem is lehetett volna kifejezni, amit én is éreztem.

A másik szerintem még érdekesebb volt. A szitu: kolléga gépe valami RSA-kódolást végző progit (OpenSSL kódot) futtat a háttérben. Kolléga lemegy ebédelni, otthagyja a gépet. Feladatunk a titkos kulcs megszerzése úgy, hogy ő ezt ne tudja meg. A billentyűzettel nem tudunk mit kezdeni, a képernyő le van lakatolva. A gépet szétszedni nem tudjuk, valami kevésbé feltűnő megoldás kell. Mit csinálunk? Használjuk az USB csatlakozót. Persze adat nem jön rajta, lehet hogy le is van tiltva. Használjuk hát helyette az USB csati 5V-os tápfeszét! Naplózzuk a feszültség időbeli változását, amit a processzorban nyílódó-záródó tranzisztorok okoznak. Fedezzük fel a periodikusságot, ami alapján meg tudjuk mondani, hogy mettől meddig tart egy-egy nagy (párezer bites) számpár összeszorzása. Aztán jól megkonstruált kétfajta inputra keressük meg a teljesen azonos görbéket, ezek azokat a helyeket takarják, amikor a két esetben ugyanazt a két nagy számot szorozta össze a gép. Ebből vissza tudunk következtetni arra, hogy a sok-sok szorzásból összerakott hatványozás pontosan hogyan is zajlott, vagyis hányadik hatványra emeltünk, amiből már adódik a kulcs. A részleteket is pontosan végigvettük, de ehhez persze az eredeti RSA-t is ismerni kell, asszem ennyire mégsem akarnék technikai lenni ebben a blogban. De a lényeg, az alapötlet engem eléggé kiakasztott. Diszkrét (egész számokkal történő) algebrai titkosítást feltörni az USB csatin lévő tápfesz analóg ingadozásának vizsgálatával... ööööö... Fuck!

3 megjegyzés:

Daniel A. Nagy írta...

Ezexerint Adi Shamir ugyanazzal az előadással szórakoztatja a közönséget mindenfelé (félreértés ne essék: én is nagyon élveztem egy kriptográfiai konferencián).

A hibás szorzásból adódó feltörhetőséget protokoll szintű megoldásokkal ki lehet, ki kell és ki is szokták védeni; tényleges RSA-alapú biztonsági rendszereket általában nem lehet megszivatni ilyen módon, bár persze azért nagyon vicces az eredmény.

Egyébként vannak további érdekes törések és kiskapuk a modern kriptográfiában. A DSS/DSA aláírás titkos kulcsa egyetlen aláírásból kiolvasható, amennyiben a felhasznált véletlen nem is olyan véletlen, vagy kettőből, ha közük van egymáshoz. Azaz a random seed felülírásával ki lehet szedni a titkos kulcsot úgy, hogy megnézünk egy aláírt dokumentumot. Backupról helyreállított rendszerek ellen lehet jól alkalmazni, amikor kimentik és visszaállítják a random seed-et. Volt már rá példa élesben.

Aztán egészen brutális dolog a Moti Yung nevű úriember által "kleptography" néven népszerüsített kiskapu-család, amikor úgy generál neked titkos kulcsot a géped, hogy black-box módszerrel az életbe' nem jössz rá, hogy lyukas, de ha visszafejted a kódot, ami csinálta, sőt működés közben megfigyeled, akkor is csak észrevenni tudod, hogy nem stimmel a dolog; más, ugyanezáltal a kód által elrontott kulcsokat továbbra sem tudsz felismerni, feltörni meg pláne nem. Viszont az, aki ismeri a megpiszkált kulcsgenerátor titkos kulcsát (nyilván itt is nyilvánus kulcsú kriptográfiát használnak, csak épp a szokásossal ellentétes céllal), az az összes ilyen kulcsot fel is tudja ismerni és meg is tudja olcsón keresni a titkos párjukat. Ilyennel még tudtommal senki sem bukott le. Egyébként lehet ez ellen is védekezni: lehet direkt olyan kulcspárokat generálni, amiknek a nyilvános kulcsából biztosan lehet tudni, hogy nincs így megpiszkálva. Még nem láttam ilyet élőben, pedig szerintem jelentősen növelné a bizalmat.

Aztán vicces dolog még a Klima-Rosa támadáscsalád, amikor a szimmetrikus titkosítással (tipikusan jelszóval) jól védett titkos kulcsot űgy szerzi meg a támadó, hogy a nyilvános részét cseréli ki (azaz ehhez is bele kell piszkálni az áldozat gépébe). Ez ellen úgy kell védekezni, hogy integritásvédelemmel nem csak a titkos információt (pl. titkos kitevő) kell ellátni, hanem mindent együtt. Ezt már alkalmazták a gyakorlatban is (a támadást is, meg a védekezést is ellene).

További vicces dolog, hogy a billentyüzetek a mai napig kb. úgy működnek, ahogy a ZX Speccy: egy mátrixot olvas végig egy ciklus, és ha megtalálta a lenyomott billentyű(ke)t, ujrakezdi. Maga a mátrix természetesen tök jó antenna, a billentyűzet felette meg "átlátszó" dielektrikum. Igazándiból még egy zsebrádiót is meg lehet úgy berhelni (sőt, némelyiket berhelni sem kell), hogy adott frekire behangolva jellegzetesen más hangot adjon attól függően, hogy milyen billentyű van lenyomva. Vannak ez ellen védett billentyűzetek, de azok nem olcsóak és nem igazán szokták őket boltban árusítani.

Ja, és az irodaépületek vasszerkezete prímán vezeti a billentyűleütések hangját, amikből szintén elég sok következtetést le lehet vonni arra vonatkozóan, hogy mit is gépelnek abban az épületben (a reflexiók révén még diszkriminálni is könnyű a különböző helyen gépelő emberek által keltett zajok között). Csak egy hagyományos (LP) lemezjátszó hangszedőjét kell nekinyomni a mélygarázsban egy oszlopnak és megfelelő csatolással rákötni egy jó minőségű hangkártya bemenetére. A többi már csak szoftver.

A CRT monitorok (szerencsére már mennek ki a divatból) képernyőjén lényegében csak egy pötty ég teljes fényerővel, és az szkenneli végig a képet, ezért az ablakon át még akkor is el lehet olvasni, hogy mi van a képernyőn, ha a monitor a másik irányba néz és az ablak le van függönyözve.

Szóval tág tere van a paranoiának. :-)

Tgr írta...

A kvantumszámítógépek pedig polinomiális időben tudnák törni az RSA-t, és minden mást, ami valamilyen diszkrét logaritmus nehezen kiszámíthatóságán alapszik. Jelenleg a legnagyobb ilyen gépeknek pár tíz bites memóriája van, úgyhogy kétjegyűnél hosszabb kulcsokra nem veszélyesek, de ki tudja, a titkosszolgálatok mennyivel tartanak előbbre a nyilvános kutatásoknál...

Bónis írta...

"És amikor eljutottunk arra a pontra, hogy na ez így nyilván tökéletes és feltörhetetlen, akkor megmutatta, hogy egy egyszerű trükkel hogyan lehet mégis feltörni. Az egésznek csak az a titka, hogy teljesen másképp kell gondolkodni. "


Ezt kifejtenéd egy kicsit bővebben, kérlek?