IDEA: mednarodni algoritem za šifriranje podatkov — definicija in delovanje

IDEA: poglobljen vodič o mednarodni blokovni šifri — princip delovanja, 128‑bitni ključ, 64‑bitni bloki, 8,5 krogov, uporaba v PGP in varnostne analize.

Mednarodni algoritem za šifriranje podatkov (International Data Encryption Algorithm, IDEA) je blokovna šifra, ki sta jo leta 1991 zasnovala Xuejia Lai in James Massey z ETH Zürich. IDEA je bila razvita kot zamenjava za standarda šifriranja podatkov (Data Encryption Standard) in je izhajala iz predhodne sheme šifri imenovane Proposed Encryption Standard (PES), ki so ji avtorji dodali več izboljšav — prvotno ime je bilo zato IPES (Improved PES). IDEA je zasnovana tako, da zagotavlja močno zamenjavo (confusion) in razpršitev (diffusion) z omejenim številom osnovnih operacij, kar omogoča relativno enostavno implementacijo v programski in strojni opremi.

Osnovne značilnosti

Algoritem deluje na 64-bitnih blokih z uporabo 128-bitnega ključa. Struktura šifre vsebuje serijo osmih enakih transformacij (krogov) in eno izhodno transformacijo (polovični krog), skupaj torej 8,5 kroga. Postopka šifriranja in dešifriranja sta si po strukturi podobna, pri čemer se dešifriranje izvaja z ustrezno inverzno podključeno shemo.

Notranja dela kroga (round function)

Vsak vhodni 64-bitni blok se deli na štiri 16-bitne besede (X1, X2, X3, X4). V vsakem od osmih krogov se uporabi šest podključev, v polovičnem krogu pa štiri; skupaj torej 52 podključev, od katerih je vsak dolg 16 bitov. Tipične osnovne operacije v enem krogu so:

• množenje modulo 65537 (tj. modulo 2¹⁶+1), pri čemer se vrednost 0 v praksi obravnava kot 65536,
• seštevanje modulo 2¹⁶ (tj. modulo 65536),
• bitno izključujoče OR (XOR).

Tipičen vrstni red operacij v krogu (poenostavljeno) je naslednji: vsaka izmed dveh besed se pomnoži z ustreznim podključem, dve sosednji besedi se seštejeta z ustreznima podključema; nato sledita dve zaporedni mešanji z uporabo multiplikacije in seštevanja ter več XOR operacij, ki rezultat ponovno permutirajo. Končna (polovična) transformacija uporablja štiri podključevanja, dodeljena za zadnje linearne in nelinearne korake.

Podključna shema

Prvih osem 16-bitnih podključev se pridobi neposredno iz 128-bitnega ključa, pri čemer je K1 najnižjih šestnajst bitov in K8 najvišjih šestnajst bitov. Nadaljnim skupinam osmih ključev se pridobiva z vrtenjem glavnega 128-bitnega ključa v levo za 25 bitov po ustvarjanju prejšnje skupine; s šestimi takimi vrtenji se ustvarijo vse potrebne podključe (6 × 8 + 8 = 56, od katerih se uporablja prvih 52). Ta preprost postopek omogoča hitro generacijo vseh 52 podključev.

Za dešifriranje je treba izračunati inverze določenih podključev: multiplicativne inverze po modulu 65537 za množenja ter aditivne inverze modulo 2¹⁶ za seštevanja. To pomeni, da je dešifriranje mogoče z uporabo iste strukture, vendar z drugačnim zaporedjem in vrednostmi podključev (inverznimi vrednostmi).

Matematične opombe (množenje mod 65537)

Specifična lastnost IDEA je uporaba množenja modulo 65537 (2¹⁶+1), ker je to praštevilo. Pri tem se vrednost 0 prišteje v posebno mapiranje: v operacijah multipliciranja se 16-bitna vrednost 0 obravnava kot 65536, produkt se izračuna modulo 65537, nato pa se rezultat, če je enak 65536, preslika nazaj na 0. Ta shema povečuje nelinearnost in preprečuje algebraične poenostavitve med različnimi skupinami operacij.

Varnost in znane kriptoanalitične ugotovitve

IDEA večino svoje varnosti dosega z vzajemnim prepletanjem operacij iz različnih algebraičnih skupin (modularno seštevanje, množenje modulo 65537 in bitni XOR), ki so izbrane tako, da so med seboj "algebraično nezdružljive". To otežuje klasično linearno in diferencialno kriptoanalizo.

Oblikovalci so izvedli analize proti diferencialni kriptoanalizi in poročali, da algoritem kroge prenese dobro, razen v določenih hipotetičnih primerih. Do danes ni bilo poročil o praktičnem polnem preboju IDEA (tj. zlom celotnih 8,5 kroga) z uporabnim časom za vse ključe. Odkriti so bili nekateri razredi šibkih ključev (npr. Daemen in sodelavci, 1994), vendar so ti izredno redki in jih je mogoče praktično ignorirati ob naključnem izbiranju ključa.

Od leta 2007 pa so znani napadi, ki omogočajo zlom zmanjšane različice IDEA: najboljši javno znani napadi lahko razbijejo šifro, če je omejena na 6 krogov (polnih 6 krogov), medtem ko polna različica (8,5 kroga) še ni razbit v razumnem času za vse ključe. Napredki v kriptoanalizi so del razloga, da so v praksi za nove sisteme pogosto izbrani drugi algoritmi (na primer AES), čeprav IDEA še vedno velja za konceptualno močno shemo.

Uporaba, patenti in zgodovina

Šifra IDEA je bila uporabljenav programu PGP (Pretty Good Privacy) v verziji 2.0 kot zamenjava za BassOmatic, ki je bil v verziji 1.0 ranljiv. IDEA se lahko uporablja z OpenPGP, kjer je sicer eno od več možnih simetričnih šifrirnih izbir.

IDEA je bila patentirana v številnih državah; ime "IDEA" je tudi blagovna znamka. Patenti je imel v lasti konzorcij/licenčnik, danes pa ima licenco za šifro IDEA po vsem svetu podjetje MediaCrypt. Patenti so potekli v letih 2010–2011, kar je odstranilo nekatere pravne ovire za prosto uporabo v programski opremi; vendar je vedno smiselno preveriti lokalno zakonodajo in licenčne pogoje ob integraciji starejših algoritmov v komercialne rešitve.

Ocene in primerjava z drugimi algoritmi

Leta 1996 je Bruce Schneier o algoritmu IDEA zapisal: "Po mojem mnenju je to najboljši in najvarnejši algoritem za blokiranje, ki je trenutno na voljo javnosti." (Applied Cryptography, 2nd ed.). V poznejših letih pa je Schneier zaradi več razlogov — napredkov v kriptoanalizi, razpoložljivosti hitrejših algoritmov in vprašanj glede patentov — IDEA priporočal manj za nove sisteme (1999 in naprej). Danes je med najpogostejšimi izbirami za nove sisteme standard AES (Rijndael), ki ima širšo industrijsko podporo in ni bil patentiran.

V primerjavi z AES ima IDEA preprosto strukturo z manjšimi pomnilniškimi zahtevami, zaradi česar je bila privlačna za programske implementacije s skromnimi viri; po drugi strani pa je AES pogosto hitrejši in bolj primeren za strojno pospeševanje (npr. AES-NI).

Implementacijske opombe in varnostne prakse

Pri implementaciji IDEA je treba upoštevati nekaj pomembnih vidikov:

• pri dešifriranju se morajo podključi pretvoriti v njihove multiplikativne oziroma aditivne inverze (zahteva računanje inverzov modulo 65537 in modulo 65536);
• uračunati je treba preslikavo 0 ↔ 65536 pri množenju modulo 65537, kar zahteva pazljivost pri programski implementaciji, da se ne vpeljejo napake;
• kot pri vseh kriptografskih implementacijah je treba upoštevati zaščito pred stranskimi kanali (timing, power analysis) in uporabljati preverjene knjižnice, kjer je mogoče;
• zaradi rasti zmogljivosti napadalcev in izboljšav kriptoanalize je priporočljivo uporabiti sodobne, preverjene simetrične načine šifriranja in ustrezne načine delovanja (npr. AEAD načine), razen če obstaja tehtni razlog za uporabo IDEA zaradi združljivosti z obstoječimi sistemi.

Na kratko: IDEA je zgodovinsko pomembna in tehnično zanimiva blokovna šifra z 64-bitnim blokom in 128-bitnim ključem, ki je v svojem času nudila dobro kombinacijo varnosti in učinkovitosti. Čeprav so patenti potečeni in algoritem ni več pravno omejen za uporabo, so zaradi razvoja kriptoanalize in razpoložljivosti hitrejših in bolj standardiziranih algoritmov (kot je AES) za nove rešitve pogosto primernejše sodobnejše alternative. Kljub temu IDEA ostaja primer dobre zasnove kriptografskega algoritma in se še vedno pojavlja v nekaterih obstoječih implementacijah, zlasti tam, kjer je potrebna združljivost z zgodnejšo programsko opremo (npr. starejše implementacije PGP/OpenPGP).

Vprašanja in odgovori

V: Kaj je mednarodni algoritem za šifriranje podatkov (IDEA)?

V: Kako deluje IDEA?

V: Ali je program IDEA patentiran?

V: Ali je bil program IDEA uporabljen v programu Pretty Good Privacy (PGP)?

V: Ali je bil prijavljen kakšen uspešen napad na program IDEA?

V: Kaj je o algoritmu IDEA povedal Bruce Schneier?

Išči po črki