International Data Encryption Algorithm

IDEA
Eine Verschlüsselungsrunde des IDEA-Algorithmus
Entwickler	James L. Massey, Xueija Lai
Veröffentlicht	1991
Abgeleitet von	PES
Schlüssellänge	128 Bit
Blockgröße	64 Bit
Struktur	Substitutions-Permutations-Netzwerk
Runden	8,5
Beste bekannte Kryptoanalyse
Ein Klartextangriff mit 264 bekannten Klartextblöcken kann bis zu 6 Runden bei einer Schlüssellänge von 128 Bit mit 2126,8 Operationen entschlüsseln.

Der International Data Encryption Algorithm (IDEA) wurde 1990 als ein Gemeinschaftsprojekt zwischen der ETH Zürich und der Ascom Systec AG von James L. Massey und Xueija Lai entwickelt. IDEA ist ein symmetrischer Algorithmus und gehört zu den Blockchiffren. Der Algorithmus wurde durch eine Überarbeitung eines früheren Kryptosystems namens PES (Proposed Encryption Standard) entwickelt, anfangs wurde er als IPES (Improved PES) bezeichnet und wurde als Ersatz für DES in Erwägung gezogen.

Die Ascom Systec AG hielt die Patente an IDEA. Das entsprechende Europäische Patent EP 0 482 154 B1^[1] wurde mit Wirkung für die EPÜ-Vertragsstaaten Deutschland, Frankreich, Italien, Liechtenstein, Niederlande, Österreich, Schweden, Schweiz, Spanien und Vereinigtes Königreich eingetragen und ist am 16. Mai 2011 erloschen. Das entsprechende US-Patent US 5,214,703^[2] ist ebenfalls am 16. Mai 2011 erloschen.

Arbeitsweise

IDEA benutzt eine Serie von acht identischen Transformationen, welche je einer Runde entsprechen, und einer Ausgabetransformation, welche einer halben Runde entspricht. Der Entschlüsselungsprozess entspricht dem Verschlüsselungsprozess in umgekehrter Form. Bei der Verschlüsselung wird der Klartext in 64 Bit große Blöcke unterteilt und der Schlüssel in Teilstücke zu je 16 Bit zerlegt. Die Verschlüsselung geschieht durch Kombination der folgenden drei Operationen:

• Die boolsche Operation XOR, auch „exclusives oder“ genannt (mit einem blau umkreisten Plus dargestellt ⊕)
• Die Addition modulo 2¹⁶ (mit einem grünen, gerahmten Plus dargestellt ⊞).
• Die Multiplikation modulo 2¹⁶+1, wo alle NULL-word-Werte (0x0000) als Wert 2¹⁶ interpretiert werden (mit einem rot umkreisten Punkt dargestellt ⊙).

Die Kombination dieser drei Operationen aus unterschiedlichen algebraischen Gruppen soll ein hohes Maß an Sicherheit gewährleisten. Das Verfahren ist dazu optimiert, Angriffen durch differentielle Kryptoanalyse zu widerstehen. Nach acht Runden kommt eine finale halbe Runde, die Ausgabetransformation, zum Einsatz, die in der Illustration unten dargestellt ist.

Key Schedule

Jede der acht Runden benutzt sechs 16-Bit-Teilschlüssel, während die finale halbe Runde deren vier benutzt, was zusammen 52 Teilschlüssel für 8,5 Runden ergibt. Die ersten acht Teilschlüssel werden direkt vom Schlüssel extrahiert, wobei der Schlüssel K1 der ersten Runde aus den 16 niederwertigsten Bits gebildet wird. Danach wird der Schlüssel 25 Bits nach links rotiert und aus dem rotierten Schlüssel wiederum acht Teilschlüssel extrahiert. Die wird wiederholt, bis nach insgesamt sechs Rotationen alle 52 Teilschlüssel gebildet wurden.

Sicherheit

Die Entwickler analysierten IDEA, um seine Stärke gegen die differentielle Kryptoanalyse zu messen, und kamen zu dem Schluss, dass der Algorithmus unter bestimmten Umständen gegen diese Art von Angriffen immun ist. Es wurden weiter keine linearen oder algebraischen Schwächen entdeckt. Der beste Angriff auf IDEA ist ein Klartextangriff und stammt aus dem Jahr 2011. Dieser bricht den Algorithmus, wenn er auf 6 Runden reduziert wird, und benötigt 16 Klartextblöcke und weniger als 2¹¹² Operationen.^[3]

Bruce Schneier hatte im Jahr 1996 eine hohe Meinung von IDEA und schrieb im Buch (Applied Cryptography, 2nd ed.) „In my opinion, it is the best and most secure block algorithm available to the public at this time.“ deutsch: „Meiner Ansicht nach ist es die beste und sicherste Blockverschlüsselung welcher der Öffentlichkeit im Moment zugänglich ist.“ Im Jahr 1999 empfahl er den Algorithmus allerdings zugunsten von schnelleren Algorithmen, Fortschritten in der Kryptoanalyse und der Probleme mit Softwarepatenten nicht mehr weiter.

Der einfache Key Schedule macht IDEA mit einer Klasse von schwachen Schlüsseln angreifbar. Schlüssel, welche eine große Anzahl an Bits mit dem Wert 0 beinhalten, führen zu einer schwachen Verschlüsselung. Diese haben allerdings in der Praxis wenig Bedeutung, da sie selten vorkommen und deshalb auch nicht explizit bei der Erstellung von Zufallsschlüsseln umgangen werden müssen. Es wurde eine kleine Änderung vorgeschlagen, um das Problem zu lösen: Jeder Teilschlüssel soll während der XOR-Operation mit einer 16-Bit-Konstante mit dem Wert 0x0DAE verknüpft werden. Größere Klassen von schwachen Schlüsseln wurden im Jahr 2002 entdeckt.

Literatur

• Xuejia Lai and James L. Massey: A Proposal for a New Block Encryption Standard. In: EUROCRYPT. 1990, S. 389–404, doi:10.1.1.14.3451.

Weblinks

• Erläuterung und Schaubild zum Verfahren
• IDEA-Applet

Einzelnachweise

1. ↑ Patent EP0482154.
2. ↑ Patent US5214703.
3. ↑ Eli Biham, Orr Dunkelman, Nathan Keller und Adi Shamir: New Data-Efficient Attacks on 6-Round IDEA. (http://eprint.iacr.org/2011/417).