8.2. Szimmetrikus kulcsú algoritmusok

A modern kriptográfia ugyanazokat az alapötleteket használja, mint a hagyományos titkosítás: helyettesítést és keverést, de ma már máson van a hangsúly. A tradicionális kódkészítők egyszerű algoritmusokat használtak. Ma ennek az ellenkezője igaz: a cél olyan bonyolult és szövevényes algoritmusok megalkotása, hogy a kódfejtő még hatalmas mennyiségű, általa választott üzenet kódolt megfelelőjének birtokában se legyen képes abból bármit is kibogozni a kulcs nélkül.

A fejezetben elsőként tárgyalt algoritmuscsoport az úgynevezett szimmetrikus kulcsú algoritmusok (symmetric-key algorithms) csoportja lesz. Ezek onnan kapták a nevüket, hogy ugyanazt a kulcsot használták a titkosításhoz és a visszafejtéshez is. A 8.2. ábra a szimmetrikus kulcsú algoritmus használatát szemlélteti. Ezúttal konkrétan a blokk-kódolókkal (block cipher) fogunk foglalkozni, melyek egy n bites blokkban kapják a nyílt szöveget, és azt a kulcs segítségével egy n bites blokkba alakítják át titkosított szöveggé.

A kriptográfiai algoritmusokat (a sebesség érdekében) hardveresen és (a rugalmasság miatt) szoftveresen is meg lehet valósítani. Bár tárgyalásunk legnagyobb része a tényleges megvalósítástól független algoritmusokkal és protokollokkal foglalkozik, mégis érdekes lehet pár szót ejteni a kriptografikus hardverek felépítéséről. A helyettesítés és a keverés egyszerű elektronikus áramkörökkel is megvalósítható. A 8.6.(a) ábra egy P-doboznak (a P a permutációt jelöli) nevezett eszközt mutat, mellyel 8 bites bemeneti adatokon lehet végrehajtani a keverést. Ha a 8 bitet fentről lefelé sorszámmal látjuk el (01234567), akkor ennek a P-doboznak a kimenete a 36071245 lesz. Megfelelő belső huzalozással a P-doboz tetszőleges keverést elvégezhet, mindezt gyakorlatilag fénysebességgel, hiszen számítások nincsenek, csak jelterjedés van. Ez a tervezés Kerckhoff elvét követi: a támadó tudja, hogy az általános módszer a bitek permutálása. Amit nem tud, az az, hogy melyik bit hova kerül, hiszen ez maga a kulcs.

A helyettesítést ún. S-dobozok (az S a substitution szóból származik) végzik, ahogy azt a 8.6.(b) ábra mutatja. A fenti eszköz 3 bites nyílt üzenetekből ugyancsak 3 bites, titkosított szöveget gyárt. A 3 bitnyi bemenet egy vonalat választ ki az első fokozat nyolc kimenetéből, amin 1-es értéket állít be, a többin 0-t. A második lépcsőben egy P-doboz található. A harmadik fokozat a kiválasztott aktív bemeneti vonala alapján újra bináris alakú kódot generál. A bemutatott huzalozással, ha a bemenetre a 01234567 sorozatot adjuk, a kimeneten a 24506713 szekvencia fog megjelenni. Más szavakkal a 0-t 2-vel helyettesíti, az 1-et a 4-gyel stb. Megint igaz, hogy az S-dobozban található P-doboz megfelelő kialakításával bármilyen helyettesítést elvégezhetünk. Egy ilyen eszközt ráadásul a hardverbe is be lehet építeni, és így nagy sebességet lehet elérni, mivel a kódolók és dekódolók csak egy- vagy kétkapunyi (nanomásodpercnél kisebb) késleltetést jelentenek, és a jelterjedés ideje a P-dobozon keresztül jóval 1 pikomásodperc alatt maradhat.

Ezeknek az építőköveknek akkor mutatkozik meg az igazi erejük, amikor sorba kapcsoljuk őket, így létrehozva a 8.6.(c) ábrán látható szorzat típusú titkosítót (product cipher). Ennél a példánál első lépésben 12 bemeneti vonalat cserélünk fel. Elméletileg a második fokozatban elhelyezhetnénk egy olyan S-dobozt, amely egy 12 bites bemenethez egy 12 bites kimenetet rendelne. Ehhez azonban 212 = 4096 egymást keresztező vezetékre lenne szükség az eszköz belsejében. Ehelyett a bemenetet 4 db 3 bites csoportra bontjuk, mindegyiket egymástól függetlenül helyettesítünk. Bár ez a megoldás már nem annyira általános, de még mindig hatékony. Kellően nagyszámú fokozatot használva a kódolóban, a kapott kimenet rendkívül bonyolult függvénye lesz a bemenetnek.

8.6. ábra - A szorzattitkosítók alapvető elemei. (a) P-doboz. (b) S-doboz. (c) Szorzattitkosító

kepek/08-06.png


A k bites bemenetből k bites kimenetet előállító szorzattitkosítók nagyon elterjedtek. A k értéke jellemzően 64 és 256 között mozog. A hardveres megvalósítások a 8.6.(c) ábra 7 fokozatával szemben rendszerint legalább 18 fizikai fokozatot tartalmaznak. A szoftveres megvalósítást egy legalább 8 iterációt tartalmazó ciklussal programozzák be, ahol minden iteráció egy S-doboz típusú helyettesítést hajt végre a 64–256 bites adatblokk egy alblokkján, melyet egy olyan permutáció követ, amely az S-dobozok kimenetét keveri össze. A művelet elején és végén gyakran van még egy speciális permutáció is. A szakirodalomban ezeket az iterációkat köröknek (rounds) nevezik.

8.2.1. DES – az adattitkosító szabvány

1977 januárjában az amerikai kormányzat egy az IBM által kifejlesztett szorzat típusú kódolót fogadott el szabványként a nem bizalmas információ számára. A kódoló, amit DES (Data Encryption Standardadattitkosító szabvány) névre kereszteltek, az iparban is széles körben elterjedt a biztonsági termékek piacán. Eredeti formájában ma már nem tekinthető biztonságosnak, de némi kiegészítéssel ma is használható. A DES működését tekintjük át a következőkben.

A DES vázlatos működése a 8.7.(a) ábrán követhető nyomon. A nyílt szöveget 64 bites blokkonként kódoljuk, ami során szintén 64 bites titkos üzeneteket kapunk. Az algoritmus, melynek paraméteréül egy 56 bites kulcs szolgál, 19 különálló fokozatból épül fel. Az első lépés egy kulcsfüggetlen keverés a 64 bites bemeneten. Az utolsó lépés ennek pontosan az inverz művelete. Az utolsót megelőző lépésben az első 32 bites részt felcseréljük a hátsó 32 bites résszel. A maradék 16 lépés működése ehhez hasonló, de mindegyik paraméteréül a kulcs különböző függvényekkel képzett értéke szolgál. Az algoritmus lehetővé teszi, hogy a dekódolást ugyanazzal a kulccsal végezhessük, mint a kódolást. Egyedül a lépések sorrendjét kell megfordítanunk.

A közbenső lépések egyikét mutatja részletesebben a 8.7.(b) ábra. Mindegyik ilyen fokozat két 32 bites bemenetből ugyancsak kettő 32 bites kimenetet produkál. A bal oldali kimenet egyszerűen a jobb oldali bemenet másolata. A jobb oldali kimenetet kizáró vagy (xor) művelettel kapjuk, amit egyrészt a bal oldali bemenet, másrészt a jobb oldali bemenet, valamint a fokozathoz tartozó kulcsérték alapján egy adott függvénnyel képzett érték között végzünk el. Az algoritmus szövevényessége ebben az adott függvényben rejlik.

8.7. ábra - Az adattitkosító szabvány. (a) Általános vázlat. (b) Egy iteráció részletesebben. A bekarikázott + a kizáró vagy műveletet jelenti

kepek/08-07.png


A függvény négy lépésből áll, melyeket egymás után végzünk el. Első lépésben egy 48 bites számot képzünk a 32 bites jobb oldal kiterjesztésével, amit egy rögzített keverés és másolás segítségével kapunk. A második lépésben az E, illetve a értékek között kizáró vagy műveletet hajtunk végre. Az így kapott eredményt 8 db 6 bites csoportra osztjuk, amiket aztán különböző S-dobozokba pumpálunk. Egy ilyen 64 lehetőséget magában hordozó inputból az egyes S-dobozok 4 bites kimenetet generálnak. Végül az így nyert  bitet egy P-dobozon engedjük keresztül.

Mind a 16 iterációs lépésben különböző kulcsokat használunk. Az algoritmus kezdetekor egy 56 bites keverést végzünk a kulcson. Mindegyik lépés megkezdése előtt a kulcsot két 28 bites részre particionáljuk, mindegyiket az iteráció sorszámának megfelelő számú bittel balra forgatva. A -t ezekből a szegmensekből egy újabb 56 bites keverés során kapjuk meg. Az 56 bites kulcs egy 48 bites részét minden fokozatban még külön permutáljuk.

A DES megerősítésére olykor egy úgynevezett fehérítés (whitening) eljárást is használnak. Ez abból áll, hogy a DES alkalmazása előtt minden egyes nyílt szöveg blokkot kizáró vagy (xor) kapcsolatba hoznak egy véletlenszerű 64 bites kulccsal, majd a titkosított szöveget az átvitel előtt egy másik 64 bites kulccsal is kizáró vagy kapcsolatba hozzák. A fehérítés egyszerűen eltávolítható ezen műveletek fordítottjainak elvégzésével (feltéve, hogy a vevő is rendelkezik a két fehérítő kulccsal). Az eljárás tulajdonképpen a kulcs hosszát növeli meg, sokkal időigényesebbé téve ezzel a teljes kulcstérben való keresést. Figyeljük meg, hogy minden egyes blokkra ugyanazt a fehérítő kulcsot alkalmazzuk (vagyis csak egy fehérítő kulcs van).

A DES-t megszületése óta viták övezik. Története egy, az IBM által készített és szabadalmaztatott kódolóval kezdődik, mely a Lucifer névre hallgatott. Az IBM által kifejlesztett titkosító azonban nem 56 bites, hanem 128 bites kulcsokkal dolgozott. Amikor az amerikai kormányzat kódolószabványt szeretett volna elfogadtatni a nem bizalmas információk titkosítására, „meghívta” az IBM-et, hogy „megvitassa” a problémát az NSA-val, a kormányzat kódfejtő szervezetével, mely a világ legnagyobb, matematikusokat és kriptográfiai szakembereket foglalkoztató cége. Az NSA körül annyi titok leng, hogy az iparban közszájon forog a következő tréfa:

Kérdés: Mit jelent az NSA rövidítés?

Válasz: Nincs Semmiféle Alakulat.

A viccet félretéve, az NSA a National Security Agency (Nemzeti Biztonsági Ügynökség) rövidítése.

A tárgyalások után az IBM a 128 bitről 56 bitre csökkentette a kulcsok hosszát, és úgy döntött, hogy titokban tartja a DES tervezésével kapcsolatos információt. Sokan feltételezik, hogy a kulcshossz ilyetén való csökkentése azért történt, hogy az NSA még feltörhesse a DES-t, de bármely kisebb költségvetésű szervezet erre képtelen legyen. A tervezéssel kapcsolatos titkok pedig némelyekben azt a gyanút keltik, hogy kiskapu van elrejtve az algoritmusban, amelynek segítségével az NSA jóval könnyebben törheti fel a DES-kódot. A DES-t övező nyugtalanság csak fokozódott, amikor egy NSA-alkalmazott tapintatosan felkérte az IEEE-t, hogy ne tartson meg egy tervezett kriptográfiai konferenciát. Az NSA persze mindent tagadott.

1977-ben két stanfordi, kriptográfiával foglalkozó szakember, Diffie és Hellman [1977] egy, a DES feltörésére alkalmas gép terveit dolgozta ki, mely körülbelül 20 millió dollárból megépíthető lett volna. Egy viszonylag kicsi üzenetdarabka és annak kódolt párja alapján a gép megtalálhatja a titkosításhoz használt kulcsot a kulcstér mind a 256 darab kulcsának végigpróbálásával egy napon belül. Ma már ilyen gép létezik, és kevesebb mint 10 000 dollárból megépíthető [Kumar és mások, 2006].

8.2.1.1. Háromszoros DES

Az IBM már 1979-ben felismerte, hogy a DES-kulcs túlságosan rövid, és a biztonság növelésének érdekében kidolgoztak egy háromszoros kódolást használó eljárást [Tuchman, 1979]. Az általuk választott módszert, melyet azóta a 8732-es számú Nemzetközi Szabvány is tartalmaz, a 8.8. ábrán mutatjuk be. Itt két kulcsot és három fokozatot használnak. Az első lépcsőben a nyílt üzenetet a szokott módon a kulccsal kódoljuk. Második lépésben dekódolást végzünk, melyhez a -t használjuk kulcsként. Végül az így kapott eredményt ismét az első kulccsal kódoljuk.

8.8. ábra - (a) DES-t használó háromszoros titkosítás. (b) Dekódolás

kepek/08-08.png


Ez a konstrukció rögtön két kérdést vet fel. Először is, miért használtunk csupán két kulcsot három helyett? Másodszor, miért alkalmaztuk az EDE (Encrypt Decrypt Encrypt kódol-dekódol-kódol) algoritmust, és nem az EEE (Encrypt Encrypt Encrypt kódol-kódol-kódol) sorrendet? A két kulcs oka az, hogy még a legparanoiásabb kriptográfusok is egyetértenek abban, hogy az elkövetkező időkben az üzleti alkalmazások számára a 112 bites kulcshossz bőven elegendő. (Márpedig a kriptográfusoknál a paranoia nem hibának, hanem kívánatos tulajdonságnak számít.) 168 bit alkalmazása csak felesleges többletköltséget jelentene a tárolás és a kulcscsere során, és ehhez képest nem járna túl sok haszonnal.

Az alkalmazott sorrendre, mely szerint először kódolunk, dekódolunk, majd ismét kódolunk, a régi, egykulcsos DES-rendszerekkel való kompatibilitás miatt volt szükség. Mind a kódolás, mind a dekódolás egy függvénynek tekinthető a 64 bites számok halmazán. Kriptográfiai szempontból mindkét leképezés egyforma erejű. Az EEE helyett az EDE sorrend alkalmazása viszont lehetővé teszi, hogy egy háromlépcsős kódoló egy hagyományos társával is együtt tudjon működni a azonos kulcsok használatával. A háromszoros DES ezen tulajdonsága miatt alkalmas a fokozatos bevezetésre. Az elméleti kriptográfusoknak ez nem sokat jelent, de annál fontosabb az IBM és ügyfelei számára.

8.2.2. AES – a fejlett titkosító szabvány

Amikor a DES és a háromszoros DES is aktív életük vége felé közeledtek, a NIST (National Institute of Standards and Technology Nemzeti Szabványügyi és Technológiai Intézet), vagyis az amerikai Kereskedelmi Minisztérium kormányzati szabványok jóváhagyásával megbízott ügynöksége úgy döntött, hogy a kormánynak új kriptográfiai szabványra van szüksége a nem bizalmas információ titkosításához. Az NIST élénken emlékezett még a DES-t övező vitákra, és jól tudta, hogy ha csak úgy bejelentene egy új szabványt, akkor mindenki, aki egy kicsit is járatos a kriptográfiában, rögtön azt feltételezné, hogy az NSA egy kiskaput épített a szabványba, vagyis hogy az NSA minden azzal titkosított dolgot el tud olvasni. Ilyen feltételek mellett pedig valószínűleg senki nem használná a szabványt, és az szépen, csendben kimúlna.

A NIST ezért a kormányzati bürokráciában meglepően új megközelítést választott: egy kriptográfiai versenyt írt ki. 1997 januárjában a világ minden tájáról kutatókat hívtak meg, hogy javaslatokat tegyenek az új szabványra, mely az AES (Advanced Encryption Standard fejlett titkosító szabvány) nevet fogja kapni. A verseny szabályai a következők voltak:

  1. Az algoritmusnak szimmetrikus blokk-kódoláson kell alapulnia.

  2. A teljes konstrukciónak nyilvánosnak kell lennie.

  3. Támogatni kell a 128, 192 és 256 bit hosszú kulcsokat.

  4. Az eljárás legyen hardveresen és szoftveresen is megvalósítható.

  5. Az algoritmus legyen nyilvános vagy megkülönböztetések nélküli alapon engedélyezett.

Tizenöt komoly javaslat érkezett. Később nyilvános konferenciákat szerveztek, ahol előadták a javaslatokat, és arra buzdították a hallgatóságot, hogy próbáljanak azokban sebezhető pontokat találni. 1998 augusztusában a NIST öt döntőst választott ki, elsősorban a biztonság, a hatékonyság, az egyszerűség, a rugalmasság és a memóriaigények (ez a beágyazott rendszereknél fontos) alapján. Ezután tovább folytak a konferenciák és a feltörési kísérletek.

2000 októberében a NIST bejelentette, hogy a Rijndaelt választotta, amelyet Joan Daemen és Vincent Rijmen dolgozott ki. A Rijndael név (melyet nagyjából rájn-doll-nak kell ejteni), a szerzők vezetéknevéből származik (Rijmen + Daemen). 2001 novemberében a Rijndael az amerikai kormányzati AES szabványává vált, amelyet a FIPS 197-ben (Federal Information Processing Standard – Szövetségi Információfeldolgozási Szabvány) tettek közzé. A verseny rendkívüli nyíltságának, a Rijndael műszaki tulajdonságainak, valamint annak a ténynek köszönhetően, hogy a győztes csapat két fiatal belga kriptográfusból állt (akik valószínűleg nem építettek be kiskaput csak az NSA kedvéért), a Rijndael a világ meghatározó kriptográfiai szabványa lett. Az AES-titkosítás és -megfejtés mostanra számos mikroprocesszor (például Intel) utasításkészletének része lett.

A Rijndael 128-tól 256 bitig terjedő kulcsokat és blokkokat támogat, 32 bites lépésekben. A kulcsok és a blokkok hosszúságát egymástól függetlenül lehet megválasztani. Az AES viszont rögzíti, hogy a blokknak 128, a kulcsnak pedig 128, 192 vagy 256 bitesnek kell lennie. Kétséges, hogy fog-e bárki is valaha 192 bites kulcsokat használni, így az AES-nek gyakorlatilag két változata van: az egyik 128 bites blokkokat és 128 bites kulcsot, a másik pedig 128 bites blokkokat és 256 bites kulcsot alkalmaz.

Az algoritmus további részletezésénél csak a 128/128-as esetet vizsgáljuk, mert a kereskedelemben valószínűleg ez lesz az irányadó. A 128 bites kulcs révén kulcsot tartalmazó kulcstérhez jutunk. Ha az NSA-nak sikerülne egy egymilliárd párhuzamosan működő processzort tartalmazó gépet építenie, melyben minden processzor pikomásodpercenként egy kulcsot értékel ki, nos, egy ilyen géppel még akkor is 1010 évig tartana a kulcstér végignézése. Addigra pedig már a Nap is kiég, úgyhogy az akkori emberek már csak gyertyafénynél olvashatják el az eredményeket.

8.2.2.1. Rijndael

Matematikai szempontból a Rijndael a Galois-mezők elvén alapszik, ennek köszönhetően van néhány bizonyítható biztonsági tulajdonsága. Mi azonban tekinthetjük most egyszerű C kódnak is anélkül, hogy belemennénk a matematikai részletekbe.

A DES-hez hasonlóan a Rijndael is helyettesítést és keverést alkalmaz, szintén több körben. A körök száma a kulcs és a blokk méretétől függ: 128 bites kulcs és 128 bites blokkok esetén 10 kör van, majd nagyobb kulcsok és blokkok esetén egyre több, egészen 14-ig. A DES-sel ellentétben azonban itt minden művelet egész bájtokra vonatkozik, hogy hardveresen és szoftveresen is hatékony megvalósításokat lehessen készíteni. A kód vázlatát a 8.9. ábra mutatja. Megjegyezzük, hogy ez a kód csak illusztráció. A védelmi kód jó megvalósítása még további gyakorlatokat igényel, olyat, mint amilyen például a könnyen sérülő memória nullázása annak használata után. Lásd például Ferguson és mások munkáját [2010].

8.9. ábra - A Rijndael kódjának C nyelvű vázlata

kepek/08-09.png


A rijndael függvénynek három paramétere van: a plaintext (nyílt szöveg), mely egy 16 bájtból álló tömb a bemeneti adatokkal, a ciphertext (titkosított szöveg), egy 16 bájtos tömb a végeredmény számára, és a key (kulcs), maga a 16 bájtos kulcs. A számítások során az adatok aktuális állapotát a state (állapot) bájttömb tárolja, melynek mérete NROWS × NCOLS. 128 bites blokkok esetén ez a tömb 4 × 4 bájtot tartalmaz, így 16 bájton a teljes 128 bites adatblokk tárolható.

A state tömbbe kezdetben a nyílt szöveg kerül, amit később a számítás minden lépésében módosítanak. Egyes lépésekben bájtról bájtra történő helyettesítéseket végeznek, másokban a tömbön belül keverik a bájtokat, de más átalakításokat is végrehajtanak. Végül a state tömb tartalmát adják vissza titkosított szövegként.

A kód először kiterjeszti a kulcsot 11 darab, az állapotmátrixszal megegyező méretű tömbbe. Ezeket az rk-ban tárolják, ami egy tömbökből álló struktúra, melyben minden tömb egy állapotmátrixot tartalmaz. Az egyik tömböt a számítás elején, a többi tizet pedig a 10 kör során, egyenként alkalmazzák. A körökben használt kulcsokat meglehetősen bonyolult módon állítják elő a titkosító kulcsból, ezért ebben most nem mélyedünk el. Legyen elég annyit mondanunk, hogy a körök kulcsait ismételt forgatásokkal és a kulcsbitek különböző csoportjainak kizáró vagy (xor) kapcsolatával állítják elő. A részleteket Daemen és Rijmen [2002] munkája tartalmazza.

A következő lépésben a nyílt szöveget átmásolják a state tömbbe, hogy az egyes körökben dolgozni lehessen vele. A másolás oszloponként történik: az első négy bájt kerül a 0. oszlopba, a következő négy az elsőbe, és így tovább. A sorok és az oszlopok is 0-tól vannak számozva, a körök viszont 1-től. A 12 darab 4 × 4 bájtos tömb kezdeti állapotát a 8.10. ábra szemlélteti.

8.10. ábra - A state és az rk tömbök létrehozása

kepek/08-10.png


Még egy lépés van a számítás törzse előtt: az -t bájtról bájtra kizáró vagy (xor) kapcsolatba hozzák a state tömbbel. Más szóval a state-ben található 16 bájtot egyenként kicserélik egy olyan bájtra, amely a saját maga és az megfelelő bájtja kizáró vagy kapcsolatából adódik.

Most pedig eljött a fő mutatvány ideje! A ciklus 10 iterációt hajt végre, vagyis körönként egyet, és minden iteráció során átalakítja a state tömböt. Minden kör négy lépésből áll. Az elsőben egy bájtról bájtra történő helyettesítést végeznek a state tömbön. Az egyes bájtokat az S-doboz indexelésére használják, hogy azok tartalmát az S-doboz megfelelő bejegyzésének tartalmával cseréljék fel. Ez tulajdonképpen egy közvetlen, egybetű-helyettesítéses kódolás. A DES-sel ellentétben a Rijndaelnak csak egyetlen S-doboza van.

A második lépés mind a négy sort balra forgatja. A 0. sor 0 bájttal fordul el (azaz nem változik), az 1. sor 1 bájttal, a 2. kettővel, a 3. pedig hárommal. Ez a lépés szétszórja az aktuális adatokat a blokkban, hasonlóan a 8.6. ábra permutációihoz.

A harmadik lépés az egyes oszlopokat a többitől függetlenül keveri össze. A keverést mátrixszorzással hajtják végre, melyben az új oszlop a régi oszlop és egy konstans mátrix szorzata lesz, ahol a szorzást a véges Galois-mező segítségével végzik el. Bonyolultnak hangzik ugyan, de létezik egy algoritmus, mely lehetővé teszi, hogy az új oszlop minden egyes elemét két darab táblázatból való kikeresés és három kizáró vagy művelet segítségével kiszámíthassuk [lásd Daemen és Rijmen, 2002, E függelék].

Végül a negyedik lépés az adott kör kulcsát kizáró vagy (xor) kapcsolatba hozza a state tömbbel.

Mivel minden lépés megfordítható, a dekódolás egyszerűen az algoritmus visszafelé történő futtatásával végezhető el. Van ugyanakkor egy olyan trükk is, melynek segítségével a dekódolást is a kódoló algoritmussal végezhetjük el, más táblázatok felhasználásával.

Az algoritmust nemcsak nagyfokú biztonságra, hanem nagy sebességre is tervezték. Egy 2 GHz-es gépen futó jó szoftveres megvalósítás elérheti a 700 Mb/s-os titkosítási sebességet, ami elég gyors ahhoz, hogy több mint 100 MPEG-2 videót lehessen valós időben titkosítani vele. A hardveres megvalósítások pedig még ennél is gyorsabbak.

8.2.3. Titkosítási módok

Bonyolultsága ellenére az AES (akárcsak a DES vagy bármelyik hasonló blokk-kódoló) alapjában véve csak egy egybetű-helyettesítéses kódoló, ami elég nagy karaktereket használ (128 bites karaktereket az AES-nél, illetve 64 biteseket a DES-nél). Ugyanaz a nyílt szövegblokk mindig ugyanazt a titkosított blokkot eredményezi. Ha például az abcdefgh nyílt szöveget ugyanazzal a DES-kulccsal kódoljuk 100-szor, akkor mind a 100-szor ugyanazt a titkosított szöveget kapjuk. A kódfejtő kihasználhatja ezt a tulajdonságot a kód feltörésére.

8.2.3.1. Elektronikus kódkönyv mód

64 bites blokkokat egyszerűbb ábrázolni, mint 128 biteseket, ezért a (háromszoros) DES példáján keresztül muttajuk be, hogyan lehet az egybetű-helyettesítéses titkosítók ezen tulajdonságát a kód részleges legyőzésére felhasználni. Ettől függetlenül az AES-nél szintén jelentkezik ez a probléma. A DES-t hosszú szövegek kódolására a legegyszerűbben úgy alkalmazhatjuk, hogy a szöveget felbontjuk egymást követő 8 bájtos (64 bites) blokkokra és azokat sorban ugyanazzal a kulccsal titkosítjuk. Az utolsó blokkot szükség esetén kiegészítjük, hogy elérje a 64 bites hosszt. Ezt az eljárást ECB-módnak (Electronic Code Book mode elektronikus kódkönyv mód) nevezzük, a régi kódkönyvek után, melyekben a nyílt szöveg minden szava fel volt sorolva, a hozzá tartozó kódszóval együtt (ez általában egy ötjegyű decimális szám volt).

A 8.11. ábrán egy adatállomány elejét találjuk, melyben egy cég az egyes dolgozóinak juttatandó éves prémiumokat tárolta. Az állomány 32 bájtos rekordok sorozatából áll, ahol minden rekord egy-egy alkalmazotthoz tartozik és a következő formátumú: 16 bájt név, 8 bájt a beosztás és 8 bájt a prémium mértéke. Mind a 16 db 8 bájt hosszú blokkot (0-tól 15-ig) DES segítségével kódoltunk.

8.11. ábra - Egy titkosítandó állomány nyílt szövege mint a 16 blokkos DES

kepek/08-11.png


Leslie éppen összekülönbözött a felettesével, így nem sok jutalékra számíthat. Ezzel ellentétben Kim a főnök kedvence, amit mindenki tud. Az állomány Leslie kezébe kerül titkosítás után, de még mielőtt a bankba küldenék. Vajon kiegyenlítheti-e Leslie a prémiumok közötti különbséget csupán a titkosított állomány birtokában?

Minden különösebb gond nélkül! Csak annyit kell tennie, hogy a titkosított állomány 12. blokkját (ami Kim jutalékát tartalmazza) a 4. blokkba másolja (Leslie prémiumának helyére). Leslie nem ismeri a 12. blokk tartalmát, mégis egy vidámabb karácsonynak nézhet elébe. (Igazából a 8. blokkot is lemásolhatná, de azt sokkal könnyebben észrevennék, emellett Leslie sem annyira mohó.)

8.2.3.2. Titkosított blokkok láncolásának módja

Az ilyen típusú támadásokat az összes blokk-kódolóban kivédhetjük a kódolók különböző módon történő láncolásával, így a Leslie által is alkalmazott blokkcsere a visszafejtés után szemetet fog eredményezni a megváltoztatott blokk pozíciójától kezdődően. A láncolás egyik módja a titkosított blokkok láncolása (cipher block chaining). Ahogy azt a 8.12. ábrán is nyomon követhetjük, ennél a módszernél mindegyik nyílt szövegblokk és az azt megelőző titkosított blokk között kizáró vagy (xor) műveletet hajtunk végre, mielőtt az adott blokkot kódolnánk. Ennek eredményeképpen ugyanaz a nyílt szövegrész már nem ugyanarra a titkosított blokkra fog leképeződni, így az algoritmusunk a továbbiakban már nem tekinthető csupán egy robusztus egybetű-helyettesítéses titkosítónak. Az első blokkhoz egy véletlenszerűen választott inicializáló vektort (initialization vector, IV) használunk párként, amit aztán a titkosított üzenettel együtt (de nyílt szövegként) továbbítunk.

8.12. ábra - Titkosított blokkok láncolása. (a) Kódolás. (b) Dekódolás

kepek/08-12.png


Nézzük meg lépésről lépésre, hogy hogyan működik a 8.12. ábrán bemutatott blokk-kódoló. Legelőször kiszámoljuk a értéket. Ezután a meghatározásával folytatjuk. Dekódoláskor a lépéssel kezdünk. Vegyük észre, hogy az i. szegmens kódolt megfelelője függ mindegyik 0-tól -ig terjedő nyílt szövegblokktól, így ugyanazt a szövegrészt más-más alakra kódolja a titkosító attól függően, hogy hányadik blokkban szerepel. A Leslie által véghezvitt transzformáció a hozzá tartozó blokkoktól kezdődően badarságot fog eredményezni két blokkban a kimeneten. Egy agyafúrt biztonsági tisztviselő számára a rendellenesség helye nyilvánvalóvá teszi, hogy hol kezdje a vizsgálatot.

A titkosított blokkok láncolásának azon kedvező tulajdonsága, hogy ugyanaz a szegmens más-más szegmensekre képződik le, a kriptoanalízist is megnehezíti. Ez a legfőbb ok, ami miatt alkalmazzák.

8.2.3.3. Visszacsatolásos kódolási mód

A blokk-kódolók láncba fűzésének hátránya azonban az, hogy meg kell várnunk egy teljes 64 bites blokk megérkezését a dekódolás megkezdése előtt. Interaktív termináloknál, ahol a felhasználók 8 karakternél rövidebb sorozat bevitele után is válaszra várhatnak, ez a módszer használhatatlanná válik. A bájtonként történő titkosítást az ún. visszacsatolásos kódolóval (cipher feedback mode) oldjuk meg, amit a 8.13. ábrán mutatunk be. Az ábrán azt az állapotot látjuk, amikor a kódoló a 0-tól 9-ig terjedő bájtokat már kódolta és elküldte. Amikor az ábrán látható módon megérkezik a 10. bájt, a DES-algoritmus a 64 bites shift regiszter tartalmából készíti el a 64 bites kódolt üzenetet. A kódolt szövegrész legbaloldalibb karaktere és a között ezután egy kizáró vagy (xor) műveletet hajtunk végre, amit aztán továbbítunk. A shift regiszter tartalmát 8 bittel balra mozgatjuk, melynek eredményeképpen a kipottyan a bal oldalon, a pedig beül arra a helyre, amit ekkor hagy el a . Vegyük észre, hogy a shift regiszter tartalma az eddig kódolásra került teljes nyílt szövegtől függ, így egy a kódolandó szövegben többször előforduló minta más-más kódolt párt kap, attól függően, hogy hol szerepel. Akárcsak a láncolt kódolóknál, itt is szükség van egy inicializáló vektorra, hogy elinduljon a játék.

8.13. ábra - Visszacsatolásos titkosító. (a) Kódolás. (b) Dekódolás

kepek/08-13.png


A visszacsatolásos módban a dekódolás ugyanúgy működik, mint a kódolás. Tulajdonképpen a shift regiszter tartalmát inkább kódoljuk, mint dekódoljuk, mivel az a bájt, melyből a -et állítjuk elő a -zel való kizáró vagy művelet során, ugyanaz, mint amit a előállításához használunk a küldő oldalán, amikor a -zel hajtjuk végre a kizáró vagy műveletet. A visszakódolás így tökéletesen működik, feltéve, ha a két shift regiszter azonos. A folyamatot a 8.13.(b) ábra szemlélteti.

Egy sajátságos mellékhatása a módszernek, hogy a titkosított szöveg egyetlen bitjének véletlenszerű megsérülése nyolc visszakódolt bájt deformálódását okozza, amelyekkel együtt szerepelt a shift regiszterben. Amint a hibás bit kikerül a dekódoló shift regiszterből, ismét hibátlan szöveget kódolhatunk vissza. Így egyetlen bit véletlen átbillenése lokálisan jelentkezik, és nem teszi tönkre a teljes hátralevő üzenetrészt, csupán csak annyi bitet, amennyi bit a shift regiszterben van.

8.2.3.4. Folyamtitkosítási mód

Vannak olyan alkalmazások, melyekben elfogadhatatlan, ha az átvitelben történt 1 bites hiba a nyílt szövegben egy 64 bites részt tesz tönkre. Az ilyen alkalmazások számára egy negyedik módszer, a folyamtitkosítási mód (stream cipher mode) jelentheti a megoldást. Ebben először egy inicializáló vektort (IV) kódolnak a kulcs segítségével, így kapnak egy kimeneti blokkot. Ezután ezt a kimeneti blokkot kódolják ugyanazon kulccsal, így jön létre a második kimeneti blokk. Ezt újfent kódolják, így áll elő a harmadik blokk és így tovább. A kimeneti blokkok (tetszőleges hosszúságú) sorozatát kulcsfolyamnak (keystream) nevezik, és egyszer használatos bitmintaként használják, vagyis kizáró vagy (xor) kapcsolatba hozzák a nyílt szöveggel, és így áll elő végül a titkosított szöveg. A folyamatot a 8.14.(a) ábra mutatja be. Figyeljük meg, hogy az IV-t csak az első lépésben használjuk, azután mindig a kimenetet kódoljuk. Megfigyelhető még az is, hogy a kulcsfolyam független az adatoktól, vagyis ha kell, előre ki lehet számolni. A folyam ezenkívül az átviteli hibákra is teljesen érzéketlen. A dekódolás menetét a 8.14.(b) ábra mutatja.

8.14. ábra - Folyamtitkosító. (a) Kódolás. (b) Dekódolás

kepek/08-14.png


A dekódolás úgy zajlik, hogy a vételi oldalon ugyanazt a kulcsfolyamot állítják elő. A kulcsfolyam csak az IV-től és a kulcstól függ, ezért nincsenek rá hatással a titkosított szöveg átvitelénél történt hibák. Ily módon az átvitt titkosított szövegben egy 1 bites hiba a visszafejtett nyílt szövegben is csak egy 1 bites hibát okoz.

Nagyon fontos, hogy sose használjuk kétszer ugyanazt a (kulcs, IV) párost egy folyamtitkosítóban, hiszen ha így tennénk, akkor mindkét alkalommal ugyanazt a kulcsfolyamot kapnánk, ezáltal pedig egy kulcsfolyam-újrafelhasználásos támadás (keystream reuse attack) veszélyének tennénk ki magunkat. Képzeljük el ugyanis, hogy a nyílt szövegblokkot egy kulcsfolyammal titkosítva megkapjuk a kizáró vagy -t. Később egy másik nyílt szövegblokkot, -t is ugyanazzal a kulcsfolyammal titkosítunk, így kapjuk kizáró vagy -t. Ha a támadó megszerzi mindkét titkosított blokkot, akkor egy egyszerű kizáró vagy műveletet elvégezve megkapja kizáró vagy -t, vagyis megszabadul a kulcstól. A támadó tehát rendelkezik a két nyílt szövegblokk kizáró vagy értékével. Ha az egyik nyílt szöveget ismeri, vagy ki tudja találni, akkor meg tudja a másikat is. Bárhogy is legyen, a két nyílt szöveg kizáró vagy értékét meg lehet támadni az üzenetek statisztikai tulajdonságainak felhasználásával. Egy angol szöveg esetén például a folyam leggyakoribb karaktere valószínűleg két szóköz kizáró vagy értéke lesz, majd ezt követi a szóköz és az „e” betű kizáró vagy értéke stb. Egy szóval: a két nyílt szöveg kizáró vagy értékének birtokában a kódfejtőnek kiváló esélye van mindkét üzenet visszafejtésére.

8.2.3.5. Számláló mód

Az elektronikus kódkönyv módon kívül az összes módnál jelentkezik az a probléma, hogy nem lehetséges velük a titkosított adathoz való közvetlen hozzáférés. Tegyük fel például, hogy egy állományt átvisznek a hálózaton, majd titkosított formában tárolják a háttértáron. Ez ésszerű megoldás lehet, mondjuk akkor, ha a fogadó gép egy hordozható számítógép, amit esetleg ellophatnak. Ha tehát minden fontos állományt titkosított formában tárolunk, akkor nagyban csökkenthetjük a rossz kezekbe került számítógépekből kiszivárgó titkos információ által okozott károkat.

Csakhogy a háttértáron lévő állományokat sokszor nem szekvenciális úton érjük el; különösen igaz ez az adatbázisok állományaira. Ha egy állományt a titkosított blokkok láncolásával kódoltunk, akkor egy tetszőleges blokk eléréséhez először az összes azt megelőző blokkot dekódolnunk kell, márpedig ez költséges megoldás. Emiatt egy újabb módot is kifejlesztettek: ez a számláló mód (counter mode), melyet a 8.15. ábra szemléltet. Itt nem közvetlenül a nyílt szöveget titkosítjuk, hanem először egy konstanssal megnöveljük az inicializáló vektort, az eredményt kódoljuk, és az így kapott titkosított szöveget hozzuk kizáró vagy kapcsolatba a nyílt szöveggel. Ha minden újabb blokknál eggyel növeljük az inicializáló vektort, akkor az állomány tetszőleges blokkját könnyen dekódolhatjuk anélkül, hogy előtte az összes azt megelőző blokkot is dekódolnunk kellene.

8.15. ábra - Titkosítás a számláló mód segítségével

kepek/08-15.png


A számláló mód hasznos módszer ugyan, mégis van egy gyengéje, amire érdemes rámutatni. Tegyük fel, hogy valamikor a későbbiekben ugyanazt a K kulcsot használjuk (más nyílt szöveggel, de ugyanazzal az IV-vel), és a támadó megszerzi mindkét titkosított szöveget. A kulcsfolyam mindkét esetben azonos, ezáltal a kódot ugyanolyan kulcsfolyam újrafelhasználásos támadás fenyegeti, mint amilyet a folyamtitkosítóknál láttunk. A kódfejtőnek mindössze annyi a dolga, hogy kizáró vagy kapcsolatba hozza a két titkosított szöveget, ezáltal megszabadul a kriptográfiai védelemtől és megkapja a két nyílt szöveg kizáró vagy értékét. A számláló mód ezen gyengéje persze nem jelenti azt, hogy maga az ötlet rossz. Ez mindössze annyit jelent, hogy mind a kulcsokat, mind az inicializáló vektort egymástól függetlenül és véletlenszerűen kell megválasztani. Ha véletlenül kétszer ugyanazt a kulcsot használnánk, de az IV különbözik a két esetben, akkor a nyílt szöveg még így is biztonságban marad.

8.2.4. Egyéb kódolók

Az AES (Rijndael) és a DES számítanak a legismertebb szimmetrikus kulcsú kriptográfiai algoritmusoknak és ipari szabványnak, ha csak a felelősségvállalást tekintjük. (Senki nem fog nekünk szemrehányást tenni azért, ha a termékeinkben az AES-t használjuk, és azt feltörik, de minden bizonnyal rossz néven veszik, ha egy nem szabványos titkosítót használunk, amelyet később feltörnek.) Érdemes ugyanakkor megemlíteni, hogy számos más szimmetrikus kulcsú titkosító módszert is kidolgoztak, melyek közül néhányat különböző termékekbe ágyazva is megtalálunk. A 8.16. ábra néhány gyakoribb módszert sorol fel. Ezeknek a kombinációját is használni lehet (például az AES-t a Twofish felett), hogy mindkét titkosítást fel kelljen törni az adatok kinyerése érdekében.

8.16. ábra - Néhány gyakori szimmetrikus kulcsú kriptográfiai algoritmus

kepek/08-16.png


8.2.5. Kriptoanalízis

Mielőtt elhagynánk a szimmetrikus kulcsú kriptográfia témáját, érdemes legalább említés szintjén tárgyalnunk négy kriptoanalitikai fejlesztést. Az első ilyen a differenciális kriptoanalízis (differential cryptoanalysis), melyet Biham és Shamir [1993] dolgozott ki. A módszer tetszőleges blokk-kódoló elleni támadásra használható. Működésének alapja, hogy a kódolás során minimálisan eltérő szövegblokkok útját követik nyomon párhuzamosan. Sok esetben egyes bitminták sokkal nagyobb gyakorisággal fognak előfordulni, mint mások, ez a megfigyelés pedig valószínűségi alapon történő támadásokat tesz lehetővé.

A második figyelemre méltó módszer a lineáris kriptoanalízis (linear cryptoanalysis) [Matsui, 1994]. Ezzel mindössze ismert nyílt szöveg alapján feltörhető a DES. Úgy működik, hogy a nyílt és titkosított szövegek adott bitjei között kizáró vagy műveletet végez, és az eredményt vizsgálja. Ha elég gyakran ismételjük a műveletet, akkor az eredményben az 1-es és 0-s biteknek nagyjából egyenlő arányban kell megjelenniük. A kódolók azonban gyakran hajlamosak az egyik vagy másik irányba eltérést mutatni, és akármilyen kicsi is ez az eltérés, mégis felhasználható a feltörés munkaigényének csökkentésére. A részleteket Matsui dolgozata tartalmazza.

A harmadik módszer az elektromos teljesítményfelvétel elemzésével próbálja megtalálni a titkos kulcsokat. A számítógépeken rendszerint 3 V felel meg az 1-es bitnek, és 0 V a 0 bitnek. Ebből kifolyólag egy 1-es feldolgozásához több elektromos energia kell, mint egy 0 feldolgozásához. Ha a kriptográfiai algoritmus egy hurkot tartalmaz, melyben a kulcsbiteket sorban egymás után dolgozzák fel, és a támadó lecseréli a gép n GHz-es órajelét egy lassabb (például 100 Hz-es) órajelre, majd krokodilcsipeszeket rak a processzor táp- és földcsatlakozójára, akkor az egyes gépi utasítások által felvett teljesítmény pontosan megfigyelhető lesz. Ezekből az adatokból pedig meglepően egyszerű kikövetkeztetni a kulcsot. Az effajta kriptoanalízis ellen csak úgy lehet védekezni, ha az algoritmust gondosan, assembly nyelven kódolják, és biztosítják, hogy a teljesítményfelvétel független legyen a kulcstól és az egyes körök kulcsaitól is.

A negyedik módszer az időzítéselemzés. A kriptográfiai algoritmusok tele vannak if utasításokkal, melyek az egyes körök kulcsaiban tesztelik a biteket. Ha a then és else utasítások végrehajtása különböző időt vesz igénybe, akkor az órajel lelassításával és az egyes lépések időigényének figyelésével itt is ki lehet következtetni az egyes körök kulcsait. Ha pedig ismertek a körkulcsok, akkor általában az eredeti kulcs is kiszámítható. A teljesítmény- és időzítéselemzés egyszerre is alkalmazható, hogy még könnyebben eredményre jussunk. Ezek a módszerek kissé egzotikusnak tűnhetnek ugyan, a valóságban azonban igen hatékony eljárásoknak bizonyulnak, melyekkel bármilyen kódot fel lehet törni, melyet nem készítettek fel külön arra, hogy ellenálljon az ilyen próbálkozásoknak.