- Blowfish-8
-
Blowfish Feistelnetzwerk von Blowfish_svg.png)
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-PermutationDer 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.
Inhaltsverzeichnis
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 P1 bis P18, 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 P1 bis P18 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 P17 und P18 der linken oder rechten Pfade verknüpft.
Die Entschlüsselung läuft dabei exakt gleich ab, nur werden dabei alle Rundenschlüssel P1 bis P18 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 28r + 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 24r + 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, P1 bis P18, als auch alle S-Boxen, S1 bis S4, 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 RAnschließ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 RAnschließ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) = ( ( S1(x24…31) + S2(x16…23) mod 232 ) xor S3(x8…15) ) + S4(x0…7) mod 232
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
- ↑ Mike Morgan: Blowfish can be cracked! (Fix included...). Veröffentlichung in der Newsgroup sci.crypt
- ↑ Vaudenay, Serge (23. August 2006). On the Weak Keys of Blowfish (PostScript). Abgerufen am 31. Dezember 2007.
- ↑ 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
.svg)
Wikimedia Foundation.
