Blog

Az egyszeri kitöltés algoritmusa és az étkező kriptográfusok protokollja

2008.05.26. 23:11:11, Földes Ádám Máté

Ez a bejegyzés egy hosszabbra tervezett, kriptográfiai témájú sorozat harmadik darabja. A bejegyzésekben nem bocsátkozom komoly elméleti fejtegetésekbe – csak a privátszféra védelme iránt érdeklődő laikus vagy szakmabeli számára potenciálisan érdekes dolgokat szeretném kifejteni. A sorozat előző darabja itt olvasható:http://pet-portal.eu/blog/2008_04_23_Szimmetrikus_kriptografia/

Előző bejegyzésemben megígértem, hogy írok majd az OTP-ről, vagyis az egyszeri kitöltés algoritmusról, méghozzá azért, hogy illusztráljam, nem minden algoritmust lehet feltörni a nyers erő módszerével. Úgy éreztem, hogy ennek a szimmetrikus kriptográfiáról szóló blogbejegyzés után van itt az ideje. Ebben a bejegyzésben azonban terítékre kerül az étkező kriptográfusok protokollja is, mivel a két algoritmus által használt matematikai konstrukció ugyanaz. E két módszer ismertetésénél azonban sajnos nem lehet „megúszni” a matematikát, úgyhogy ebben a bejegyzésben kicsit több lesz az elmélet. Mindazonáltal bízom benne, hogy ez nem riasztja el a laikusokat – igazán bonyolult dolgokról nem lesz ugyanis szó.

Először is definiálni kell egy fontos matematikai műveletet: úgy hívják, kizáró VAGY (exclusive OR, XOR (ejtsd „exor” )). Ennek a műveletnek a jele, ahogy az ábrán is látszik, egy karikába tett + jel. Ez nem véletlen: az XOR jelentése a kettes számrendszerben (vagyis a biteken) az átvitel nélküli összeadás. A tízes számrendszerben ez például azt jelentené, hogy 9 + 5 = 4, és hogy 5 + 6 = 1. Mindez a kettes számrendszerben az ábrán látható módon összegezhető.

 

Kizáró VAGY

 

Az egyszeri kitöltés a következőképpen működik. Először bitekkel (0-kkal és 1-ekkel) reprezentáljuk a nyílt szöveget, és megnézzük, hogy az milyen hosszú. Aztán veszünk egy tökéletesen véletlenszerű, ugyanilyen hosszú bitsorozatot, ő fogja az algoritmus kulcsát alkotni. Végül a titkos szöveg úgy áll elő, hogy a nyílt szövegnek és a kulcsnak bitenként vesszük az XOR kapcsolatát (bitwise XOR). A titkos szöveget úgy fejthetjük vissza, hogy ugyanezen kulccsal XOR-oljuk. (Ennek igazolása az ábrán látható.)

Az algoritmus legfigyelemreméltóbb tulajdonsága, hogy nem lehet a nyers erő módszerével feltörni, vagyis feltétlenül biztonságos (unconditionally secure). Ha ugyanis egynél több titkos szövegnyi hosszú értelmes nyílt szöveg van, a kulcsbitek tökéletes véletlenszerűsége miatt semmilyen „perdöntő” információnk sincs a titkosított nyílt szövegről – mindegyik értelmes nyílt szöveg pontosan ugyanolyan valószínű. (Megjegyzés: tökéletesen véletlenszerű bitsorozatot előállítani nagyon nehéz. Ha viszont a kulcsbitek generálásakor számottevő az „elfogultság” (bias), vagyis például az 1 valószínűbb a 0-nál, már lehetséges különbséget tenni valószínű és valószínűtlen nyílt szövegek közt.)

Mindazonáltal az OTP csak akkor biztonságos, ha egy kulcsot csak egyszer használunk fel. Ha ugyanis tudjuk, hogy két nyílt szöveget ugyanazon kulccsal titkosítottak, a két titkos szöveg XOR kapcsolatával hozzájutunk a két nyílt szöveg XOR kapcsolatához, vagyis a kulcs kiesik. (Lásd az ábrát.) Ez sok esetben elég lehet a kriptanalízishez (vagyis a nyílt szövegek meghatározásához). Felfoghatjuk ugyanis ezt az eredményt úgy, hogy az egyik nyílt szövegre alkalmazták az OTP módszert, méghozzá oly módon, hogy a kulcs a másik nyílt szöveg volt. Ez azért rossz, mert a kulcs nem véletlenszerű többé (hiszen csak az értelmes nyílt szövegek halmazából kerülhet ki).

A kulcsok egyszer használatos jellege mellett még a kulcshossz problémája is fellép. Ha például egy CD-nyi tartalmat szeretnénk titkosítani, akkor egy másik CD-nyi tartalom lesz a kulcs. A kulcshossz a kulcsgenerálást, a tárolást és a szállítást egyaránt megnehezítheti, ezért az OTP algoritmust ritkán használjuk önmagában. Ez azonban korántsem jelenti azt, hogy a koncepciónak nincsenek a gyakorlatban hasznos hozadékai.

Az egyik ilyen a folyamtitkosítók koncepciója. Az ilyen rejtjelezők egy viszonylag rövid kulcsból egy algoritmus segítségével előállítanak egy álvéletlen bitsorozatot (ezt nevezzük kulcsfolyamnak), majd ennek a bitsorozatnak és a nyílt szövegnek a bitenkénti XOR kapcsolata lesz a titkos szöveg. Az előző bejegyzésben említett RC4 például folyamtitkosító.

Az OTP koncepciójának egy másik – PET-szempontból érdekesebb – felhasználása az étkező kriptográfusok protokollja. Ez a protokoll visszakövethetetlenséget (untraceability) biztosít egy csoport szórással (broadcast) kommunikáló tagjainak (így a küldő és a fogadó is visszakövethetetlenné válik). Ez azt jelenti, hogy a csoport tagjai úgy tudnak anonim módon jelezni egymásnak, hogy minden kommunikációt mindenki hall. A módszer alapmodellje a következő szituációval illusztrálható.

Egy étteremben egy asztal körül három kriptográfus ül (a protokoll több résztvevőre általánosítható ). Mindegyik kriptográfus feldob egy „cinkeletlen” (unbiased) érmét, és megmutatja az eredményt a tőle jobbra ülőnek, de úgy, hogy az étlappal eltakarja a többiek elől. Ezután mindegyik kriptográfus aszerint jelent IGAZ-at (1-et) vagy HAMIS-at (0-t), hogy a saját és bal oldali szomszédja érméje azonos oldalára esett-e avagy sem. Ha azonban az egyik kriptográfus szeretne jelezni a többieknek, akkor pontosan ezzel ellentétesen cselekszik, vagyis hazudik. Ha mindenki jelentett, akkor minden egyes kriptográfus tudhatja, hogy volt-e olyan, aki jelzett avagy sem, ha képzi a jelentések XOR kapcsolatát. Ha az eredmény 0, akkor nem volt jelzés, ha 1, akkor valaki jelzett (feltéve persze, hogy maximum egy kriptográfus jelez). A procedúra tetszőleges számú alkalommal megismételhető, így tetszőleges számú jel küldhető.

Felmerülhet azonban néhány kérdés a protokollal kapcsolatban. Egyrészt nem magától értetődő, hogy hogyan is lehet így „értelmes” kommunikációt folytatni. Egy lehetséges módszer, hogy bármilyen üzenet kezdetét egyetlen jel jelenti, majd akkor ítéljük úgy, hogy az üzenetnek vége, ha már adott ideje nem volt egyetlen jel sem. Az adás időtartama alatt a „van jel” 1-es, a „nincs jel” 0-s bitet jelent.

Másrészt muszáj pár szót szólni arról, hogy mi történik, ha egyszerre többen is akarnak jelezni, vagyis ütközés (collision) lép fel. Az XOR művelet tulajdonságai miatt lehet tudni, hogy ha az ütközésben páros számú kriptográfus vesz részt, akkor mindannyian észlelik az ütközés tényét. Ilyenkor mindannyian várakoznak véletlen számú időegységet, majd újra megpróbálnak adni. Ha páratlan számú ütköző van, akkor az ütközés egy következő bitnél derülhet csak ki.

Harmadrészt az sem triviális, hogy mi biztosítja a visszakövethetetlenséget. A protokoll ezen tulajdonságát indirekt módon úgy igazolhatjuk, ha egy épp nem jelző kriptográfus „bőrébe bújunk”. Ebből a szemszögből két eshetőséget figyelhetünk meg. Az első az, amikor a saját és a bal oldali szomszéd által feldobott érme azonos oldalra esett. Ekkor a másik két kriptográfus közül egy IGAZ, egy pedig HAMIS jelentést tett. Ha a számára láthatatlan érme az általa ismert értékű érmékkel megegyezik, akkor a HAMIS-at mondó kriptográfus jelzett. Ha az ismeretlen érme különbözik a másik kettőtől, akkor az IGAZ-at mondó kriptográfus hazudott. Mivel azonban az érme „cinkeletlen”, mindkét eshetőség pontosan ugyanolyan valószínű. A másik eset az, amikor a saját és a bal oldali szomszéd által feldobott érme nem azonosak. Ha ilyenkor mindkét másik kriptográfus HAMIS-at mondott, akkor a „hazudós” kriptográfus ül a nem ismert érmével azonos oldalára esett érme mellett. Ha a többi kriptográfus IGAZ-at mondott, akkor az hazudott, aki a nem látott érmétől különböző érme mellett ül. Itt sem tudunk azonban dönteni a két eset között, tekintve, hogy ugyanolyan valószínűek. (A protokoll két fő esetére is értelmezhető; ez esetben egy külső megfigyelő képzelen eldönteni, hogy melyik fél küld éppen.)

Látható, hogy az étkező kriptográfusok protokolljánál is sok múlik a statisztikai szempontból kiegyensúlyozott, tökéletesen véletlenszerű kulcsgeneráláson (vagyis az érmék feldobásán): az anonimitást az biztosítja, hogy képtelenek vagyunk dönteni két azonos valószínűségű eset közt. Hasonlóan lehet azt is végiggondolni, hogy a kulcs (vagyis érmefeldobás-sorozat) „újrahasznosítása” itt is veszélyes, mert az OTP-nél látható módon kiejthető a „spórolós” kriptográfus kulcsa a számításból.

A problémák sora azonban ezzel nem merül ki: az étkező kriptográfusok protokollja például meglehetősen pazarlóan bánik a kommunikációs közeggel – arról már nem is beszélve, hogy a kriptográfusok egy csoportja összejátszhat a jelzés forrásának kiderítése érdekében, valamint hogy egy „notórius hazudozó” képes használhatatlanná tenni a csatornát. Ezek a problémák bizonyos mértékig orvosolhatóak, azonban a tény ettől még tény marad: az étkező kriptográfusok protokollját önmagában nehéz széles körben hasznosítani a gyakorlatban. Viszont speciális helyzetekben, amikor a visszakövethetetlenség kulcsfontosságú (és nem mellesleg a résztvevők száma nem túl nagy), az ötletnek lehet létjogosultsága.

Csatolmányok:

Hozzászólások

Összesen 1 hozzászólás látható.

2008.05.27.

Gulyás Gábor 2008.05.27. 10:03:37
... és ez a két protokoll azért érdekes, mert feltétel nélküli biztonságos, valamint anonimitást képesek nyújtani. Így mindkettő a maga nemében (security ´n´ privacy) a csúcs ezen szempontból, persze mindkettővel menedzsment és erőforrás gazdálkodás körüli gondok vannak, ahogy említetted.

(Szép bejegyzés!)

A hozzászóláshoz be kell jelentkezni!

© PET Portál és Blog, 2008-2010 | Impresszum | Adatvédelmi nyilatkozat