A kriptográfiai előadások vázlata Informatikai biztonság alapjai c. tárgy (Műszaki Info. BSc szak, tárgyfelelős: Dr. Bertók Botond) Dr.Vassányi István Információs Rendszerek Tsz.
[email protected] 2008 szept. 22.-okt. 6. (3 darab 4x45 perces előadás)
1. Történeti áttekintés1 A legelső alkalmazás az adatrejtés2 (szteanográfia): • i.e. 480, „üres” írótábla, szalamiszi csata (Xerxes perzsa hajóhadának veresége) • fejre írt szöveg • keménytojás belsejére írt üzenet • a betűk összekeverése sokszögletű pálca alkalmazásával. Átmenet a kriptográfia felé, mert a pálca tekinthető kulcsnak, P-doboz A kriptográfiai módszerek feltételezik, hogy a támadó ismeri a módszert, a nyelvet és a témát, de nem ismeri a kulcsot: • ókori monoalfabetikus módszerek, pl Caesar-kód (26 lehetséges kulcs), vagy egy teljesen összekevert kód-ABC (26! lehetséges kulcs, de a kulcs „nehezebben” megjegyezhető), S-doboz • törése: IX sz. arab tudósok, betűgyakoriság-elemzések (a Korán kapcsán) (K1.1. kép) • ennek ellenére a középkorig Európa-szerte a diplomáciában alkalmazzák és törik a virágnyelvvel kombinálva • javításai: o 1626 után XIII és XIV Lajos udvarában a Rossignolok által tervezett „Nagy Kód”: betűkód és szótagkód keveréke, nullitások és törlő jelek (200 évvel később fejtették csak meg a Vasálarcos miatt) o homofonikus kódok: a gyakoriságra alapozott törést a betűkapcsolatokra kell kiterjeszteni • 1586: a legnagyobb bukás (túlbecsült kriptorendszer): Mária skót királynő kivégzése (K1.2, K1.3. kép) • XVIII. sz., a bécsi „Fekete szoba”: fenti monoalfabetikus kriptorendszerek üzemszerű törése, kereskedés az információval
1
[1] és [2] alapján. Az egész anyag vázlatos áttekintését lásd [3]-ban. Az adatrejtést a mai napig alkalmazzák, gyakran a kriptográfiával kombinálva (pl. kép- és hangfájlokba rejtett kódolt fájlok). Ismétlődő, nagy adatmennységet érintő kommunikációra nem alkalmas, mert a módszer kitutódik, de nehezítheti a kriptorendszer feltörését. 2
1/6
• • •
• •
1586: a Viginere-kód publikálása (polialfabetikus kód), kulcsszavas eltolás, (K1.4., K1.5. kép) törése: Babbage, 1854: betűkapcsolatok ismétlődése alapján a kulcsszó hossza, ezután a kód-ABC-k egymástól független visszafejtése betűgyakoriságok alapján rotoros titkosítógépek az I-II világháborúban (igen sok ABC-s polialfabetikus) o 1917: nagy bukás, a Zimmermann-távirat feltörése 2 hét alatt (Amerika hadbalépése) (K1.51. kép) o az Enigma elve (K1.52. kép), története (K1.6., K1.7. kép)… o …és törése (Turing-bomba, a „kapaszkodó” szerepe) 1918: az egyszer használatos kulcs, Vernam-cipher, one-time-pad (tömeges adatküldésre nem alkalmazható) egyéb módszerek: o navaho kódbeszélők: az egyetlen soha fel nem tört kriptorendszer o szótár-módszer, a Beale-féle kincs Buford falu környékén, 1820: az egyszer használatos kulcs előnye (K1.8-9. kép), ill. Svejk az I. világháborúban
2. Modern kriptográfia: alapok3 Az adatbiztonság tényezői: szervezeti, fizikai, informatikai biztonság, cél az egyenszilárdság. A kriptorendszer tervezésének alapelve: költség vagy az idő miatt ne legyen érdemes támadni. A kriptorendszer alapsémája: a nyílt szöveg, a rejtett szöveg és a kulcs szerepe. A támadó célja a kulcs megszerzése. A támadások típusai: • rejtett szöveg • nyílt szöveg • választott nyílt szöveg • választott rejtett szöveg Egyéb támadások, esetenként a hálózati elemek manipulációjával: • újraküldés ill. korábbi üzenetek alapján hamis rejtett szöveg konstruálása (cutand-paste, forging) • beékelődés (man-in-the-middle) és az azonosság ellopása (identity theft)
3. A tökéletes titkosítás4 Shannon definíciója alapján I(X,Y)=0, ez lebontható két gyakorlati feltételre. Az OTP módszer nyílt szöveg típusú támadása, a kulcskezelési probléma. (1. előadás vége) A „brute force” módszer alkalmatlanságának demonstrációja: a támadó nem veszi észre, hogy eltalálta a kulcsot. rejtett: PEFOGJ = PEFOGJ kulcs1: PLMOEZ kulcs2: MAAKTG nyílt: ATTACK DEFEND (mindkettő értelmes!) 1950-es évek, hidegháború: a szovjet titkosszolgálat nagy bukása az OTP-vel, a Rosenberg-házaspár kivégzése 1953-ban 3 4
[4] alapján [4] alapján
2/6
4. A természetes nyelvi entrópia5 A kriptoanalízis elvi alapja: Ha X, Y, és K betűi vagy részei között közvetlen kapcsolat áll, fenn, akkor a nyelv redundanciája alapján lényegesen kevesebb kulcsot kell kipróbálni. HL és RL definíciója. RL , A és K számosságával megadható, milyen hosszú rejtett szövegből található ki a kulcs.
5. A modern, iteratív blokkos kriptorendszerek módszerei6 A cél a kapcsolat megszüntetése. Titkos kulcsú eljárás (OTP) alkalmazása S és P dobozokkal kombinálva (produkciós kriptorendszer), több iterációban, mindig más kulccsal. Az S és P dobozok miatt a támadó nem veszi észre, ha egy belső iterációs kulcsot eltalált. A cél nem a tökéletes kriptorendszer használata, hanem az hogy a támadónak az összes kulcsot végig kelljen próbálnia, ami praktikusan nem megoldható: számítási teljesítményre alapozott biztonság (computational secrecy) Szimmetrikus titkos kulcsú rendszer: a rejtő és a fejtő kulcs ugyanaz, gyakran az eljárás is lényegében ugyanaz. A DES (1977, K2,3,4 kép), Feistel-struktúra. A lavina-hatás (K4.1 kép): ha a bemenet egy bitet változik, a kimenetnek várhatóan a fele változzon: a kiterjesztési művelet célja. Az S-dobozok bemenetén egy bit változás több kimeneti bit változását eredményezi. Törések: • Algoritmikusan nem tudták törni (1990: 238 db. nyílt szöveg felhasználásával a kulcs meghatározható). • 1998: AWT Deep Crack, egy chipen 24 mag, 64x28 chip 40 MHz-en, egy kulcsot 16 óraciklus alatt vizsgát meg, ezért maximum 7.7 nap alatt találta meg a kulcsot (210 ezer USD) Az AES: 2000. A módszer (K4.5 kép) Nagy kulcstér, hatékonyabb szoftver megvalósítás (x86-ra 457 byte-on is leprogramozták). A megoldó-algoritmus a rejtő-algoritmus lépéseinek inverzeit használja, fordított sorrendben. • Algoritmikusan nem tudták törni. A biztonság értékelése: a termodinamikai korlát. (K4.6 kép)
6. Blokkos és folyamelvű kriptorendszerek alkalmazásai7 Problémák: cut-and-paste támadás és kivédése láncolással (K5 kép). A folyamtitkosítás (stream cipher) a blokkos titkosítással szemben: • Egybites vagy –byte-os blokk (előnyös, ha nincs lehetőség pufferelésre) • Azonos bemenet a pozíciótól függően különböző kimenetet adhat • A kulcsgenerátort indulás előtt inicializálni kell a titkos kulccsal, ezután akármilyen hosszú adatfolyamot folyamatosan az éppen aktuális kulccsal kombinál. Blokkos rendszer átalakítása folyamra: a DES OFB módja. (K6 kép) Más elvű folyamtitkosítók: • Enigma
5
[4] alapján [2,5] alapján 7 [2,4,5] alapján 6
3/6
•
RC4 (1987), byte-os blokkok, tízszer gyorsabb a DES-nél (az SSL egyik alapalgoritmusa). A kulcs a 0..255 sorozat egy permutációja, a periódus nagyon hosszú. Minden adatbyte-nál változik a kulcs-tömb, majd kiválasztják belőle az aktuális kulcsot. A kulccsal való kombinálás XOR. Nem találtak érdemi törést hozzá. Nem publikus. • A GSM rendszerek A5/1, A5/3 LFSR-alapú folyam-algoritmusai, challengeresponse alapú viszonykulcs (session key) generátorral kiegészítve. A 128 bites titkos kulcs a SIM kártyán van tárolva, a session key-t az LFSR-ek inicializálására használják. (K6.5 kép) Az 5/1 könnyen törhető (real-time), bár nem publikus. A valóban véletlen kulcsok generálásának a problémái és megoldásai: • valódi véletlen alap-kulcsok, magok előállítása fizikai folyamatból: radioaktív sugárzás, termikus zaj, kozmikus háttérsugárzás, gerjedő oszcillátor, turbulens áramlás… • ezzel a maggal pszeudo-véletlen kulcssorozatok generálása (pl. DES-sel K7 kép), a KEK fogalma (K8 kép) Kulcskezelési probléma: a titkos kulcsok biztonságos megosztása (2. előadás vége)
7. Nyilvános kulcsú kriptorendszerek8 A és B között soha sem létesül védett csatorna, ahol titkos kulcsot cserélhetnek. Minden módszer nehezen invertálható egyirányú műveleten (one-way function, trap function) alapul. A támadások nem „nyers erő”, hanem algoritmikus jellegűek, a jövőbeli fejlődésük a termodinamikai korláttal ellentétben nehezen jósolható, ezért a nyilvános kulcsú kriptorendszerek alapvetően kevésbé megbízhatóak, mint a titkos kulcsúak, ezenkívül lassabbak is (K10 kép). A gyakorlatban ezért a különféle nyílt és titkos kulcsú módszerek kombinációját alkalmazzák (hibrid kriptorendszer), részletes ajánlások és protokollok alapján. A Diffie-Hellman módszer (1976): az első titokmegosztás nyilvános csatornán. (K9 kép): a közös titok lesz a titkos viszonykulcs. A módszerben az egyirányú művelet a moduláris hatványozás (inverze a moduláris logaritmus). n és g tipikusan 200-512 bit hosszú prímek, g n generátora. Továbbfejlesztett változata az ElGamal módszer, a DSS digitális aláírás-szabvány alapja. Aszimmetrikus kriptorendszer: A és B más kulcsot használnak. Erre példa az RSA (K9 kép). Az RSA módszer (Rivest, Shamir, Adleman, 1977) az internetes adatbiztonság alapja, az SSL is használja. A módszer alapgondolata: nyilvános és titkos kulcsból álló egyedi kulcspár. A támadó nem tudja az üzenetet elolvasni, a küldő nem tudja az üzenetet letagadni. Az egyirányú művelet a nagy prímszám-szorzatok faktorizálása. Az üzenetet változó hosszú bináris blokkok sorozatára kell átalakítani (padding). Fontos az ajánlások betartása a módszer használata során (pl. padding, a prímszámok választása és ellenőrzése…).
8
[2,5] alapján
4/6
Demo: javascript alapú RSA megvalósítás: http://www.irt.vein.hu/~vassanyi/info/rsa/index.html Támadások: • n faktorizálása (n legyen legalább 1024 bites) vagy gyökvonás • egyéb rosszul választott paraméterekből adódó algoritmikus gyengeségek kihasználása • választott rejtett szöveg (1998): megfigyelt Y alapján konstruált Y’ és az ehhez tartozó X’ alapján X. Y’ dekódoltatása: oracle service (pl. csata a Midway szigeteknél) • időzítéses támadás (timing attack, 1995, 2003) • beékelődés (man-in-the-middle, K11 kép) => digitális tanúsítványok (bizonyítványok) Elliptikus görbékre alapuló nyílt kulcsú rendszer (ECC): RSA-nál kisebb kulcsméret azonos biztonsághoz (ha RSA 1024 bit, akkor ECC 161 bit), egyszerű megvalósítás. Az elliptikus görbén ( y 2 = x 3 + ax + b , K12 kép) moduláris aritmetikával végeznek különféle műveleteket. A módszer alapja: gyakorlatban nehezen megvalósítható művelet a diszkrét logaritmus az elliptikus görbék felett. Az ElGamal, Diffie-Hellman, DSA módszereknek kialakíthatók a nagyobb biztonságot nyújtó ECC-alapú változataik. A leggyakoribb hibrid kriptorendszer: a titkos véletlen szimmetrikus viszonykulcs (pl. AES) átvitele nyilvános kulcsú rendszerrel (pl. RSA). (K11 kép) TDES-RSA alapú hibrid rendszer a mobilbank-szolgáltatások alapja. Az SSL-ben a szerver és a kliens megegyeznek a későbbiek során használandó nyilvános és titkos kulcsú módszerekben (K16 kép).
8. A digitális aláírás és tanúsítvány9 Az alapgondolat: titkosított üzenetpecsét, cél az üzenet letagadhatatlansága és a sérthetetlensége. Az RSA alkalmazása aláírásra (K13 kép). A digitális tanúsítvány részei és felhasználása (K14, 14.1 képek), lejárat, revocation list A DSA (1993, USA szabvány) az RSA-hoz hasonló szerkezettel (titkos és nyilvános kulcs), csak aláírásra. Üzenetpecsétek (message digest, hash). Elvárások: • gyorsan számítható, rögzített méretű • a pecsétből egy ilyen pecsétet adó üzenetet nehéz meghatározni (preimage támadás) • nehéz két, ugyanolyan pecsétet adó üzenetet találni (ütközés, collision) vagy egy adott üzenethez egy másikat • lavinahatás (lásd a DES-nél) Iteratív, blokkos algoritmusok: • MD5 (1992, K14.2 kép): 128 bit • SHA-1 (1993), SHA-2 család (SHA-256, -384, -512, K14.3, 14.5 képek) 9
[2,5] alapján
5/6
• MD5 és SHA-1 nem biztonságos Támadások az üzenetpecsétek ellen: sok üzenetnek ugyanaz a pecsétje. • A születésnap-támadás • Szivárvány-táblák (K14.4 kép), különösen max. 8 karakteres rendszerjelszók törésére a hash érték alapján. A tábla specifikus egy adott hash függvényre, jelszóhosszra és karakterkészletre. Védekezés: az eredeti jelszó sózása („salting”, linuxon 48 bit) vagy a hash többszöri, akár 1000-szeri alkalmazása (key stretching). Tanúsítási rendszerek (K15 kép): • Hierarchikus lánc bizalmi horgonyokkal (üzleti világ) • Bizalmi háló, Web-of-trust (PGP): Nyilvános kulcsszerverek (public keyserver), pl. http://pgp.mit.edu (civil világ) Magyarországon 2001 óta a digitális aláírás egyenértékű a papír-alapú aláírással (2001 évi XXXV törvény).
9. Public Key Infrastructure, PKI10 Algoritmus, alkalmazás, protokoll, különféle szabványok, ajánlások és opciók összessége. A cél az algoritmikus támadások nehezítése. Kulcstárolás: Az igazi megoldás a kulcstároló/titkosító célhardver (16. kép): • Funkcionalitás: kulcsgenerálás (fizikai véletlenszám-generálás) és kulcstárolás, X509 tanúsítványok tárolása, titkosítás: DES CBC/ECB, TDES, RC4), aláírás (DSA, SHA-1 és MD5 alapon) • Támogatott PKI rendszerek: RSA. Diffie-Hellman, ElGamal, ECC, DSS… • Windows rendszerekben a Crypto API alá épül be egy dll segítségével, ezen keresztül hívhatják az alkalmazások. demo: Cryptophane 0.7: • 2db kulcspár generálása aláírásra és titkosításra felhasználói interakcióval (kulcs ID, fingerprint, algoritmus, lejárat), kulcskarika (keyring) • fájl titkosítása a címzett nyilvános kulcsával, a fájl kibontása a címzettnél • fájl aláírása a feladó titkos kulcsával, ellenőrzés a címzettnél (3. előadás vége)
10. Kitekintés: kvantum-kriptográfia11 A kvantum-számítógép egyszerre végtelen sok kulcsot tud kipróbálni…
Irodalom [1] [2] [3] [4]
Simon Singh: Kódkönyv. Park, 2001. Virrasztó Tamás: Titkosítás és adatrejtés. Netacademia, 2004. Vassányi István: Információelmélet (kivonatos jegyzet). Pannon Egyetem. Richard B. Wells: Applied Coding and Information Theory for Engineers, Prentice Hall, 1999 [5] R.E. Smith: Internet security. Addison-Wesley, 1997.
10 11
[2] alapján [1] alapján
6/6
