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	Lai-Massey-Schema
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 boolesche 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. Dies 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 in seinem Buch Angewandte Kryptographie: „Meiner Ansicht nach ist IDEA der beste und sicherste Blockalgorithmus, der zur Zeit öffentlich verfügbar ist.“ Im Jahr 1999 empfahl er den Algorithmus jedoch aufgrund von Kryptoanalyse-Fortschritten und der Probleme mit Softwarepatenten nicht mehr.

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 in der Praxis wenig Bedeutung, da sie selten vorkommen und deshalb nicht explizit bei der Zufallsschlüssel-Bildung umgangen werden müssen. Um das Problem zu lösen, wurde vorgeschlagen: Jeder Teilschlüssel soll während der XOR-Operation mit einer 16-Bit-Konstante mit dem Wert 0x0DAE verknüpft werden. Größere Klassen schwacher Schlüssel wurden im Jahr 2002 entdeckt.

Literatur

• Xuejia Lai, James L. Massey: A Proposal for a New Block Encryption Standard. In: EUROCRYPT. 1990, ISBN 3-540-46877-3, S. 389–404. 

Weblinks

• IDEA-Applet

Einzelnachweise

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