Blowfish-16

Blowfish
Feistelnetzwerk von Blowfish
Entwickler	Bruce Schneier
Veröffentlicht	1993
Schlüssellänge	32-448 Bit (Standard 128 Bit)
Blockgröße	64 Bit
Struktur	Feistelchiffre
Runden	16
Beste bekannte Kryptoanalyse
• vier Runden von Blowfish sind anfällig für eine Differentielle Kryptoanalyse • 14 Runden sind, für eine Klasse von schwachen Schlüsseln, anfällig für eine Pseudozufalls-Permutation

Der Blowfishalgorithmus ist ein symmetrischer Blockverschlüsselungsalgorithmus, der 1993 von Bruce Schneier entworfen und erstmals im April 1994 in Doctor Dobb's Journal publiziert wurde. Er wurde als „public domain“ veröffentlicht und kann frei verwendet werden.

Eigenschaften

Blowfish hat als Blockchiffre eine fixe Blocklänge von 64 Bit, basiert auf einem Feistelnetzwerk, das die Umkehrbarkeit zwischen Verschlüsselung und Entschlüsselung garantiert und besitzt schlüsselabhängige S-Boxen. Die Schlüssellänge kann zwischen 32 Bit und 448 Bit betragen. Aus diesen Schlüsselbits werden vor Beginn der Ver- oder Entschlüsselung Teilschlüssel, so genannte Rundenschlüssel P₁ bis P₁₈, und die Einträge in den S-Boxen von aufsummiert 4168 Bit erzeugt.

Die Abbildung zeigt den internen Aufbau von Blowfish. Die einzelnen Datenpfade sind dabei 32 Bit breit, durch die linke und rechte Hälfte ergibt sich die Blocklänge von 64 Bit. Jede sogenannte Runde – es gibt in Summe 16 Runden – besitzt XOR-Verknüpfungen mit den vorab berechneten Rundenschlüsseln P₁ bis P₁₈ und eine Funktion f, in welcher schlüsselabhängige S-Boxen zum Einsatz kommen. Dabei wird ein 32 Bit breiter Eingabewert von der linken Seite eindeutig einem bestimmten 32 Bit breiten Ausgabewert auf der rechten Seite der Funktion zugeordnet. Das Ergebnis von f wird mit dem rechten Datenpfad XOR-verknüpft. Dieses Verfahren wird für alle 16 Runden wiederholt. Am Ende werden noch die beiden Rundenschlüssel P₁₇ und P₁₈ der linken oder rechten Pfade verknüpft.

Die Entschlüsselung läuft dabei exakt gleich ab, nur werden dabei alle Rundenschlüssel P₁ bis P₁₈ in umgekehrter Reihenfolge benutzt.

Kryptoanalyse

Bis heute (Stand 2008) ist kein effizienter Angriff auf die Blowfish-Verschlüsselung mit voller Rundenzahl öffentlich bekannt. Ein so genannter Sign-Extension-Bug wurde in einer Veröffentlichung des C-Codes gefunden.^[1]

Serge Vaudenay fand 1996 einen Known-Plaintext-Angriff der zum Brechen der Verschlüsselung 2^{8r + 1} bekannte Paare von Klartext und Cyphertext benötigt. Der Parameter r bezeichnet die Anzahl der Runden. Zudem entdeckte er eine Klasse von schwachen Schlüsseln, die erkannt und mit nur 2^{4r + 1} Klartext-Paaren gebrochen werden können. Dieser Angriff kann jedoch nicht gegen regulären Blowfish eingesetzt werden, da er die Kenntnis der schlüsselabhängigen S-Boxen voraussetzt.

Vincent Rijmen stellt in seiner Doktorarbeit einen differenziellen Angriff zweiter Ordnung vor, der Blowfish mit höchstens 4 Runden brechen kann. Außer der Brute-Force-Methode ist kein Weg bekannt, den Algorithmus mit 16 Runden zu brechen. ^[2]

Bruce Schneier merkt an, dass er den neueren Twofish-Algorithmus empfiehlt, obwohl Blowfish noch in breiter Verwendung ist. ^[3]

Algorithmus

Blowfish besitzt pro Runde einen P-Rundenschlüssel mit 18 mal 32 Bit und vier S-Boxen mit 256 mal 32 Bit in der Funktion f. Die Initialisierung des P-Wertes und der vier S-Boxen erfolgt mit einer fixen Zeichenkette, der hexadezimalen Ziffernfolge der Zahl π (Pi). Ausgehend von diesem Startwert werden sowohl alle P-Boxen, P₁ bis P₁₈, als auch alle S-Boxen, S₁ bis S₄, in ihren Werten schlüsselabhängig verändert. Danach bleiben die P-Werte und die Werte in den S-Boxen so lange konstant, bis ein neuer Schlüssel gewählt wird.

Verschlüsselung

Der Algorithmus wird mit Hilfe des Schlüssels initialisiert.

Zuerst wird der Schlüssel in 32-Bit-Blöcke aufgeteilt. Danach wird jeder Eintrag der P-Box mit den 32-Bit-Blöcken des Schlüssels XOR-verknüpft. Dabei wechseln sich die Blöcke des Schlüssels nacheinander ab. Danach wird ein Block mit 64 Nullbits verschlüsselt. Die linke und rechte Hälfte ersetzt dabei den ersten und zweiten Eintrag der P-Box. Dann wird mit dem aktuellen Stand der Geheimtext aus dem letzten Schritt verschlüsselt, und der dritte und vierte Eintrag der P-Box wird ersetzt. Dieses passiert solange, bis alle Einträge der P-Box und der vier S-Boxen ersetzt wurden.

Zur Verschlüsselung werden die eingehenden 64 Bit in zwei Blöcke zu je 32 Bit, L und R, aufgeteilt. Danach läuft folgende Prozedur durch:

Für alle i von 1 bis 16
    L = L xor Pi
    R = R xor f(L)
    vertausche L und R

Anschließend:

vertausche L und R
R = R xor P17
L = L xor P18

Entschlüsselung

Die Entschlüsselung ist unten dargestellt:

Für alle i von 18 bis 3
    L = L xor Pi
    R = R xor f(L)
    vertausche L und R

Anschließend:

vertausche L und R
R = R xor P2
L = L xor P1

Nun steht nur noch die Funktion f offen: Der eingehende 32-Bit-Wert wird in vier Teile zu je 8 Bit aufgeteilt. Danach wird aus den S-Boxen mit Hilfe dieser Werte je ein Wert entnommen, mit den anderen addiert und XOR-verknüpft.

Die Funktion gibt zurück:

f(x) = ( ( S₁(x_24…31) + S₂(x_16…23) mod 2³² ) xor S₃(x_8…15) ) + S₄(x_0…7) mod 2³²

Beispiele

Im GNU Privacy Guard sind Blowfish und Twofish implementiert und können auf Wunsch aktiviert werden. Das Crypto File System (CFS) ist ein auf NFS aufsetzendes Verschlüsseltes Dateisystem für UNIX und unterstützt ebenfalls Blowfish. Ein Windows-Programm (Open Source) zum Verschlüsseln von Dateien mittels Blowfish und Twofish ist Blowfish Advanced CS (Anleitung hierzu; PDF). Auch im OpenDocument Datenformat ist Blowfish als Verschlüsselungsmethode aufgeführt.

Referenzen

1. ↑ Mike Morgan: Blowfish can be cracked! (Fix included...). Veröffentlichung in der Newsgroup sci.crypt
2. ↑ Vaudenay, Serge (23. August 2006). On the Weak Keys of Blowfish (PostScript). Abgerufen am 31. Dezember 2007.
3. ↑ McConnachie, Dahna (27. Dezember 2007). Bruce Almighty: Schneier preaches security to Linux faithful. Computerworld S. 3. Abgerufen am 31. Dezember 2007. „At this point, though, I'm amazed it's still being used. If people ask, I recommend Twofish instead.“

• Vincent Rijmen: Cryptanalysis and design of iterated block ciphers, doctoral dissertation, October 1997.
• Bruce Schneier: Description of a New Variable-Length Key, 64-bit Block Cipher (Blowfish). Fast Software Encryption 1993: 191-204 [1].
• Bruce Schneier: The Blowfish Encryption Algorithm -- One Year Later, Dr. Dobb's Journal, 20(9), p. 137, September 1995 [2].
• Serge Vaudenay: On the weak keys of Blowfish Fast Software Encryption (FSE'96), LNCS 1039, D. Gollmann, Ed., Springer-Verlag, 1996, pp. 27--32.

Siehe auch

• Advanced Encryption Standard (AES) aktuelles Standardverschlüsselungsverfahren
• Twofish, Nachfolger von Blowfish
• Verschlüsselung
• Bruce Schneier
• Puffy, the blowfish, Maskottchen der OpenSSH

Weblinks

• Bruce Schneiers Beschreibung des Algorithmus incl etlicher Sourcecodes
• S-Box und P-Box
• Crypt::Blowfish – Perl Blowfish encryption module
• Blowfish PHP-Implementierung
• Online Blowfish-Verschlüsselung (PHP oder JavaScript)
• Blowfish JavaScript-Implementierung
• Blowfish Tcl-Implementierung, auch in der Tcllib enthalten
• Blowfish LabVIEW-Implementierung

Symmetrische Verschlüsselungsverfahren

Blockchiffren: 3DES (Triple DES) | A5/3 (KASUMI) | AES | Anubis | Blowfish | Camellia | CAST | DES | FEAL | FOX | IDEA | Lucifer | Magenta | MARS | MISTY1 | RC2 | RC5 | RC6 | SEED | Serpent | SHACAL | Skipjack | TEA | Twofish | XTEA 

Stromchiffren: A5/1 | A5/2 | Rabbit | RC4 | SEAL