Jöhet a feltörhetetlen titkosítás

Hamarosan komoly áttörés jöhet a kriptográfiában egy fiatal kutatónak köszönhetően. Amit Sahai a Massachusetts Institute of Technologyn (MIT) diplomázott 1996-ban, mára a University of California professzora. Mindig is érdekelte az úgynevezett nulla ismeret problémája: ez egy olyan matematikai protokoll, ami anélkül tud bárkit meggyőzni arról, hogy igaz, hogy felfedné a részleteket, miért az. Sahai továbbgondolta a koncepciót: mi van, ha a belső működést úgy el lehet rejteni, hogy nemcsak a bizonyítás van benne, hanem egy egész program, amit az emberek úgy használhatnának, hogy nem visszafejthető a működése? – ezzel foglakozik a Wired friss cikke.

Az úgynevezett összezavaró-program ötlete nem új, de egyelőre senki nem tudott belőle működő verziót készíteni: a lényege, hogy a saját kódját, működését úgy összekuszálja, hogy a fontos információk nem visszafejthetőek. A cégek már több ilyennel is próbálkoztak, ezeket tényleg nehéz megérteni, de végül egyelőre az összes ilyen próbálkozást sikerült feltörni: a támadónak talán nem pár perc kell, de pár nap alatt megvannak. (Matematikailag bizonyítottan feltörhetetlen, úgynevezett OTP-típusú titkosítás azonban már 1882 óta létezik.)

Az elrejtett, biztonságos programok sok helyen hasznosak lehetnek: például védhetnék a szoftvereket, elfedhetnék a csipek működését, így tényleg komolyan titkosítani lehetne például a DVD-k másolásvédelmét, vagy akár a katonai drónok működését.

Sahai szerint, ha a koncepció egyszer megvalósul, ezeket a programokat ki lehet adni bárhová: elfoghatja az ellenség, lehallgathatja és darabjaira szedheti, de meg nem fejtheti. Ez megoldaná a kriptográfia elmúlt negyven évének nagyjából összes fontos problémáját, amelyek mind abból a tényből származnak, hogy hogyan tudunk kapcsolatba lépni a másik féllel biztonságosan, például az interneten, ahol sosem bízhatunk a másik oldalban. A kriptográfusok sokáig úgy gondolták, hogy erre a kérdésre nincs megoldás.

Mégis élünk

2013. július huszadikán azonban mégis megtörtént az áttörés: Sahai öt másik kutatóval közösen megjelentetett egy tanulmányt [PDF] a Cryptology ePrint Archive című kiptorgráfiai szaklapban: ebben bemutatnak egy lehetséges protokollt a fenti problémák megoldására. A bemutatott folyamatot megkülönböztethetetlen összezavarásnak (indistinguishability obfuscation) nevezték el. Két nappal később kiegészítették tanulmányukat, így már elméletben megvalósították a kriptográfusok álmát, a feltörhetetlen összezavarást.

A tanulmányok után után hat hónappal több témával kapcsolatos cikk jelent meg a lapban, mint az elmúlt 17 évben összesen. Ennek ellenére az új technológia még messze van a kereskedelmi használattól: a kicsi, egyszerű programokból az álcázáshoz egyelőre hatalmas monstrumokat készít. Feltörni azonban az első próbálkozók nem tudták. Ez pedig az utóbbi idők legnagyobb előrelépése.

Fekete doboz

Amikor Sahai elkezdett dolgozni a problémán, először úgynevezett fekete dobozban (black box) gondolkozott: ez annyira összekuszálja a programot, hogy a legnagyobb számítási kapacitással sem lehet semmit megállapítani róla, kivéve az elérhető bemenetet és kimenetet - a működése azonban rejtett marad.

Például nem lehet kitalálni egy jelszót, amit a program rejt, kivéve, ha ez az egyik kimenete. Ha létezne a fekete doboz, forradalmasítaná a kriptográfiát: nagyon könnyen lehetne például olyan titkosítókulcsokat készíteni, amihez nem kell a másik fél közreműködése, csak lefuttatja a szintén álcázott szoftvert – illetéktelen kezek viszont nem férnének hozzá. 2001-ben azonban Sahai és több más szerző bebizonyította, hogy ilyen program megalkotása lehetetlen.

Megkülönböztethetetlen

Sahai azonban nem adta fel: egy gyengébb összezavarás definiálásán dolgoztak tovább, az úgynevezett megkülönböztethetetlen zavarás koncepcióján. Az ezen az elven működő program úgy módosítja a benne lévő dolgokat, hogy a kimenete olyan, amit nem lehet megkülönböztetni attól, mintha egy másik program készítette volna (összezavarás nélkül). 

Az azonban nem volt egyértelmű, hogy mire is jó ez a koncepció: bár senki nem tud megkülönböztetni két álcázott programot, lehetséges lett volna a zavarószoftver vizsgálatával információkat kinyerni.

Viszont 2007-ben Shafi Goldwasser, az MIT és Guy Rothblum a Microsoft Research kutatói kimutatták, hogy ha a megkülönböztethetetlen zavaró megépíthető lenne, ez lenne a legjobb összezavaró: az ötlet annyi, hogyha van más zavaró, ami a legjobb összezavart kódot készíti, lehetne arra használni, hogy összekeverje a programot, ezután az eredeti programot és az összekevert verziót bele lehetne rakni egy megkülönböztethetetlen zavaróba, hogy még egy réteggel zavarosabb legyen a kód. Mint ez a mondat. De a koncepció tényleg erről szól.

Kívülről nem lehetne megállapítani, hogy az eredeti kód vagy az még egy zavaráson átesett párja, amit éppen látunk, ez azt jelenti, hogy ez a megoldás is ugyanolyan jól elrejtené a titkokat, mint a másik, „legjobb” zavaró.

A gond az, hogy senki nem tudott megépíteni ilyen gépet. Egészen 2013 nyaráig. Ekkor Sahai kollégáival együtt letett valamit az asztalra, ami nagyon sok, kusza alkódból állt, viszont működött. Amikor megpróbálták tisztítani a kódot, kiderült, hogy meg tudja csinálni a megkülönböztethetetlen zavarást. Gyakorlatilag megalkották a fekete dobozt: használható nyilvános kulcsok előállítására, digitális aláírásokra és más alapvető kriptografikus protokollokhoz (például két korábban nem megoldotthoz a funkcionális titkosításhoz és megtagadható tokosításhoz).

Mint a kirakó

A kutatócsoport zavarója úgy működik mint egy multilineáris kirakós: az eredeti program minden darabját jól kiválasztott darabokkal véletlenszerűen kuszálják össze. Ha viszont megfelelő módon futtatják a programot, akkor a véletlenszerűség megszűnik, a darabok összefüggnek, és a megfelelő kimenetet adják. 

A kutatócsoport megmutatta, hogy zavarási sémájuk törhetetlen, feltéve, hogy bizonyos új keletű, rácsokkal kapcsolatos matematikai problémákat valóban olyan nehéz megoldani, mint ahogy a csapat gondolja. Ezt a kérdést az idő majd eldönti, de több egyetem és a Microsoft kutatói már bizonyították, hogy a szokásos eljárásokkal nem lehet feltörni a megoldást.