IDEA (International Data Encryption Algorithm) – definition og funktion
Lær om IDEA: definition, funktion og sikkerhed i dette klassiske 64-bit blokchiffer med 128-bit nøgle, rundestruktur og anvendelse i PGP og OpenPGP.
Inden for kryptografi er den internationale datakrypteringsalgoritme (IDEA) en blokchiffer, der blev udviklet af Xuejia Lai og James Massey fra ETH Zürich i 1991. Det var meningen, at det skulle være en erstatning for Data Encryption Standard. IDEA minder meget om en tidligere kryptering kaldet Proposed Encryption Standard (PES), men med nogle forbedringer. På grund af dette blev IDEA først kaldt IPES (Improved PES).
Chiffret er patenteret i en række lande, men kan bruges af alle til ikke-kommerciel brug. Navnet "IDEA" er også et varemærke. Patenterne udløber i 2010-2011. I dag er IDEA licenseret på verdensplan af et firma ved navn MediaCrypt.
IDEA blev brugt i Pretty Good Privacy (PGP) v2.0, efter at det blev konstateret, at det krypteringssystem, der blev brugt i v1.0, BassOmatic, kunne brydes. IDEA kan anvendes sammen med OpenPGP-standarden.
IDEA opererer med 64-bit blokke ved hjælp af en 128-bit nøgle. Den indeholder en serie af otte identiske transformationer (runder) og en udgangstransformation (den halve runde). Den gør dette i alt i 8,5 runder. Processerne for kryptering og dekryptering er ens.
IDEA opnår en stor del af sin sikkerhed ved at sammenflette operationer fra forskellige grupper - modulær addition og multiplikation og bitvis eXclusive OR (XOR) - som er valgt til at være "algebraisk inkompatible".
Hver af de otte runder bruger seks undernøgler, mens den halve runde bruger fire, hvilket giver i alt 52 undernøgler. Hver undernøgle har en længde på 16 bit. De første otte undernøgler udtrækkes direkte fra 128-bit-nøglen, idet K1 er de laveste 16 bit og K8 de højeste 16 bit; yderligere grupper af otte nøgler oprettes ved at rotere hovednøglen til venstre 25 bit efter oprettelsen af den foregående gruppe; seks rotationer genererer alle undernøgler.
Designerne analyserede IDEA for at måle dets styrke over for differentiel kryptoanalyse og konkluderede, at det kun er usårligt under visse forudsætninger. Der er ikke blevet rapporteret om vellykkede lineære eller differentielle angreb. Der er fundet nogle klasser af svage nøgler - f.eks. (Daemen et al. , 1994) - men de er af ringe betydning, da de er så sjældne, at de udtrykkeligt kan undgås. Fra 2007 kan det bedste angreb, der gælder for alle nøgler, bryde IDEA, hvis det reduceres til 6 runder (den fulde IDEA-chiffer bruger 8,5 runder).
I 1996 skrev Bruce Schneier om IDEA: "Efter min mening er det den bedste og mest sikre blokalgoritme, der er tilgængelig for offentligheden på nuværende tidspunkt." (Applied Cryptography, 2nd ed.) I 1999 anbefalede han imidlertid ikke længere IDEA på grund af tilgængeligheden af hurtigere kryptografiske algoritmer, visse fremskridt i kryptoanalysen og spørgsmålet om patenter. [1]
Design og funktion — kort forklaring
IDEA arbejder på 64-bit blokke, der opdeles i fire 16-bit ord (ofte kaldet X1–X4). Hver runde kombinerer disse ord ved hjælp af tre typer operationer:
- Multiplikation modulo 65.537 (det vil sige modulo 216+1). Værdien 0 behandles særligt (ofte kortlagt til 65.536) for at få en multiplikativ gruppe uden nulproblemer.
- Addition modulo 65.536 (altså modulo 216).
- Bitvis XOR (eksklusivt eller).
En typisk runde bruger seks 16-bit undernøgler (K1–K6). Først anvendes multiplikation og addition på de fire ord med K1–K4. Derefter følger en blanding (XOR og yderligere multiplikation/addition med K5 og K6) der kombinerer de midterste værdier, hvorefter nogle ord byttes for at forberede næste runde. Efter otte fulde runder udføres en afsluttende (halv)rundetransformation med fire undernøgler for at danne den endelige ciphertext. Denne struktur—skiftevis brug af additive, multiplicative og XOR-operationer—er valgt for at skabe algebraisk kompleksitet og modvirke analyser, som udnytter kun én type algebraisk struktur.
Nøgleplan og dekryptering
IDEA udleder 52 undernøgler à 16 bit fra hovednøglen på 128 bit. De første otte undernøgler tages direkte som laveste til højeste 16-bit segmenter af hovednøglen. Efter hver gruppe på otte undernøgler roteres hovednøglen 25 bit til venstre for at danne næste gruppe; efter seks sådanne rotationer er alle 52 undernøgler genereret.
Til dekryptering anvendes de samme operationer i omvendt rækkefølge, men multiplicative undernøgler udskiftes med deres multiplicative inverser modulo 65.537, og additive undernøgler erstattes med deres additive inverse modulo 65.536. Denne symmetri betyder, at krypterings- og dekrypteringsalgoritmerne er meget ens, bortset fra nøgleinverteringen og rækkefølgen.
Sikkerhed og kryptoanalyse
IDEA var designet med henblik på modstand mod differential- og lineær kryptoanalyse ved at kombinere operationer fra "uforenelige" algebraiske grupper. Gennem årene er der udført omfattende kryptoanalytisk arbejde:
- Der er identificeret visse klasser af svage nøgler, men de er så sjældne, at de normalt kan undgås i praksis.
- Der er ikke rapporteret om praktisk gennemførlige fuldnøgleangreb på den fulde 8,5-rundes IDEA i almindelige anvendelsesscenarier.
- Forskning har imidlertid reduceret sikkerheden for reducerede varianter (fx 6 runder), og fra 2007 var det bedste generelle angreb i stand til at håndtere 6 runder. Det betyder, at IDEA ikke længere har samme margin til anerkendt sikkerhed som nyere designs, men det er stadig betragtet som robust mod direkte fuldnøgleangreb i praksis.
Anvendelse, licensering og ydeevne
IDEA fik tidlig udbredelse, især via PGP v2.0, og kan bruges sammen med OpenPGP. Licens- og patentforhold spillede en stor rolle i adoptionen: selvom ikke-kommerciel brug oprindeligt var tilladt, blev kommerciel brug kontrolleret af indehaveren af patent- og licensrettighederne (blandt andre MediaCrypt). Ifølge tidligere oplysninger udløb patenterne omkring 2010–2011, hvilket lettede juridiske begrænsninger.
Ydeevnemæssigt var IDEA konkurrencedygtig i 1990'erne, men den indeholder 16-bit multiplikationer modulo 65.537, hvilket gør den ikke så hurtig som nogle nyere blokchifre (fx AES/Rijndael) på typisk moderne hardware, hvor 32- eller 64-bit aritmetik er mere effektiv. I hardware eller på ældre arkitekturer kunne IDEA dog være relativt effektiv.
Sammenligning og moderne status
Efter fremkomsten af AES (Rijndael) og andre hurtigere og patentrettighedsmæssigt ukomplicerede algoritmer faldt IDEA i brug. AES blev standardiseret og er i dag langt mere udbredt end IDEA i de fleste nye systemer. Ikke desto mindre forbliver IDEA et vigtigt historisk eksempel på designprincipper, især brugen af flere algebraiske operationer for at øge kompleksiteten over for kryptoanalyse.
Konklusion
IDEA var et banebrydende blokchiffer i starten af 1990'erne, kendt for sin innovative sammenfletning af forskellige algebraiske operationer og for sin anvendelse i PGP. Selvom det i dag er erstattet i mange anvendelser af hurtigere eller standardiserede algoritmer som AES, forbliver IDEA et interessant og indflydelsesrigt design, især som case-studie i blokchifferdesign og nøgleplaner.
En krypteringsrunde af IDEA med seks undernøgler
Spørgsmål og svar
Spørgsmål: Hvad er den internationale datakrypteringsalgoritme (IDEA)?
A: IDEA er en blokchiffer, der blev udviklet af Xuejia Lai og James Massey fra ETH Zürich i 1991. Den skulle være en erstatning for Data Encryption Standard og indeholder en række otte identiske transformationer (runder) og en udgangstransformation (den halve runde).
Spørgsmål: Hvordan virker IDEA?
A: IDEA opererer på 64-bit blokke ved hjælp af en 128-bit nøgle. Den gør dette i i alt 8,5 runder. Processerne for kryptering og dekryptering er ens. IDEA opnår en stor del af sin sikkerhed ved at sammenflette operationer fra forskellige grupper - modulær addition og multiplikation og bitvis eXclusive OR (XOR) - som er valgt til at være "algebraisk inkompatible". Hver af de otte runder anvender seks undernøgler, mens den halve runde anvender fire, hvilket giver i alt 52 undernøgler. Hver undernøgle har en længde på 16 bit.
Spørgsmål: Er IDEA patenteret?
Svar: Ja, det er patenteret i flere lande, men kan anvendes af alle til ikke-kommerciel brug. Navnet "IDEA" er også et varemærke, og patenterne udløber i 2010-2011. I dag er det licenseret på verdensplan af MediaCrypt.
Spørgsmål: Blev IDEA brugt i Pretty Good Privacy (PGP)?
A: Ja, det blev brugt i PGP v2, efter at BassOmatic - det krypteringssystem, der blev brugt i v1 - viste sig at kunne brydes. Det kan også bruges med OpenPGP-standarden i dag.
Spørgsmål: Er der rapporteret om et vellykket angreb på IDEA?
A: Der er endnu ikke rapporteret om vellykkede lineære eller differentielle angreb mod IDEA; der er dog fundet nogle klasser af svage nøgler, men de er så sjældne, at de let kan undgås, når algoritmen anvendes sikkert. Fra 2007 kan det bedste angreb, som gælder for alle nøgler, bryde IDEA, hvis det reduceres til 6 runder (den fulde version bruger 8 runder).
Spørgsmål: Hvad sagde Bruce Schneier om IDEA?
Svar: I 1996 skrev han, at det var "den bedste og mest sikre blokalgoritme, der var tilgængelig" på det tidspunkt; i 1999 anbefalede han den dog ikke længere, da der var hurtigere algoritmer til rådighed, og da der var gjort visse fremskridt med hensyn til kryptoanalysen af den samt patentproblemer i forbindelse med dens anvendelse.
Søge