Home
IPSec
SSL
AES-Kandidaten

e-Mail an mich

Der Algorithmus Twofish

zurück     Home

Twofish

Bruce Schneier entwickelte Twofish, um mit dieser Chiffre an der Auswahl zum AES teilzunehmen. Twofish belegte in der Runde der letzten Fünf den dritten Platz.

Twofish erlaubt die Schlüssellängen 128, 192 und 256 Bit. Es werden zwar auch andere Werte akzeptiert, diese Schlüssel werden dann allerdings mittels Padding auf eine der drei Standardlängen gebracht. Der Klartext wird in 128 Bit große Blöcke unterteilt und durchläuft 16 Runden des Algorithmus.

Der Textblock wird in vier 32-Bit-Worte aufgeteilt, die in der Inputverschleierung mit den 32-Bit-Teilschlüsseln K0 bis K3 XOR-verknüpft werden. Die Ergebnisse dieser Verknüpfungen sind die Worte R0,0, R0,1, R0,2 und R0,3, die den Input der folgenden Runde darstellen. In Bezug auf die jeweilige Runde r (mit r = 0,...,15) werden diese Worte als Rr,0, Rr,1, Rr,2 und Rr,3 bezeichnet.

Die Worte Rr,0 und Rr,1 dienen als Input der Funktion F. Hier rotiert Rr,1 zunächst um acht Positionen nach links, anschließend werden beide Worte in ihre vier Byte aufgeteilt und in den S-Boxen 0 bis 3 substituiert. Die Outputs der S-Boxen werden zu einem Vektor zusammengefasst und mit der Matrix MDS multipliziert. Die Matrix MDS ist über GF(28) definiert als:

                

Die Ergebnisse hieraus sind als T0 und T1 bezeichnet. T0 und T1 werden nun einer Pseudo-Hadamard-Transformation unterzogen, indem T1 zu T0 modulo 232 addiert wird und das Ergebnis zu T1 modulo 232 addiert wird. Danach wird zu beiden Ergebnissen je ein Teilschlüssel K2r+8 bzw. K2r+9 modulo 232 addiert. Die Ergebnisse hieraus sind Fr,0 und Fr,1. Rr,2 wird nun mit Fr,0 XOR-verknüpft und rotiert um eine Position nach rechts. Rr,3 rotiert um eine Position nach links und wird anschließend mit Fr,1 XOR-verknüpft. Die Ergebnisse hieraus werden zu Rr+1,0 bzw. Rr+1,1 gesetzt und Rr,0 bzw. Rr,1 werden zu Rr+1,2 bzw. Rr+1,3 gesetzt. Dieser Vorgang wird insgesamt 16-mal durchgeführt.

Zum Abschluss wird die letzte Vertauschung der Worte rückgängig gemacht und die vier Worte R16,0 bis R16,3 werden in der Outputverschleierung mit den Teilschlüsseln K4 bis K7 XOR-verknüpft und anschließend aneinander gefügt.

Zur Entschlüsselung wird der Algorithmus in der gleichen Richtung durchlaufen, wie bei der Verschlüsselung. Die Teilschlüssel werden in umgekehrter Reihenfolge benutzt und die Rundenfunktion wird leicht modifiziert. Das Wort Rr,2 rotiert zunächst um eine Position nach links und wird dann mit Fr,0 XOR-verknüpft und Rr,3 wird erst mit Fr,1 XOR-verknüpft und rotiert dann um eine Position nach rechts. Das folgende Bild zeigt die Unterschiede zwischen Ver- und Entschlüsselung.

Der Algorithmus benutzt 40 Teilschlüssel K0 bis K39, sowie den Schlüsselvektor S, der zur Definition der S-Boxen benötigt wird. Der geheime Schlüssel hat die Länge k mit k = Länge in Bit dividiert durch 64. Die möglichen Werte von k sind k = 2, 3 und 4 für die Schlüssellängen 128, 192 und 256 Bit. Der geheime Schlüssel besteht aus 8×k Bytes m0,...,m8k-1. Diese Bytes dienen zunächst der Erzeugung des Vektors S, indem sie mit der Matrix RS in folgender Form multipliziert werden:

                

mit            i = 0,...,k – 1

und          

Anschließend werden die Bytes des geheimen Schlüssels zu 32-Bit Worten zusammengefasst und in zwei Feldern Me und Mo der Länge k×32 Bit gespeichert. Dabei gilt:

                 Me= (M0,M2,...,M2k-2)

                 Mo= (M1,M3,…,M2k-1)

Zur Erzeugung der Teilschlüssel K0 bis K39 wird die Funktion h benötigt. Diese nutzt zur Generierung der K2j die Inputs 2j und Me, die Teilschlüssel K2j+1 nutzt mit die Inputs (2j + 1) und Mo. Die Inputs 2j bzw. (2j + 1) werden durch die festen Substitutionen q0 und q1 substituiert und anschließend mit einem Eintrag aus Me bzw. Mo XOR-verknüpft. Die Ergebnisse durchlaufen nochmals eine Substitution und es erfolgt wiederum eine XOR-Verknüpfung mit einem Eintrag aus Me bzw. Mo. Abschließend wird eine Substitution durchgeführt und die Ergebnisse werden zu einem Vektor zusammengefasst und mit der Matrix MDS multipliziert. Diese Zwischenergebnisse sind als Aj und Bj bezeichnet. Nachdem Bj um acht Positionen nach links rotiert ist, wird es zu Aj modulo 232 addiert. Das Ergebnis hiervon wird wiederum zu Bj modulo 232 addiert und rotiert anschließend um neun Positionen nach links. Die Erzeugung der Teilschlüssel K2j und K2j+1 ist im folgenden Bild für einen geheimen Schlüssel der Länge 128 Bit (k = 2) dargestellt.

Die S-Boxen sind bei Twofish vom Schlüssel abhängig, aber nicht zufällig. Sie bestehen aus den festen Substitutionstabellen q0 und q1, deren Ergebnisse mit den Einträgen des Vektors S XOR-verknüpft werden. Einen Überblick über die Funktionsweise der S-Boxen bietet das folgende Bild.

Twofish bietet hohe Sicherheit bei guter Leistung. Durch sein Design ist laut Bruce Schneier auch ein Einsatz als Stromchiffre und als Hashfunktion möglich.

zurück     Home

[Home] [IPSec] [SSL] [AES-Kandidaten] [Über mich] [Links] [Gästebuch]