Blowfish

Blowfish
Blowfish
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

Blowfish 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.

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 die so genannten Rundenschlüssel P1 bis P18 und die Einträge in den S-Boxen erzeugt, insgesamt 4168 Byte.

Inhaltsverzeichnis

Funktionsweise

Die Abbildung zeigt den internen Aufbau von Blowfish. Der 64 Bit breite Klartextblock wird in zwei Hälften L1 und R1 geteilt. In jeder sogenannten Runde – es gibt insgesamt 16 Runden – wird die linke Hälfte des Datenblocks mit einem vorab berechneten 32 Bit breiten Rundenschlüssel P1 bis P16 XOR-verknüpft, dann wird das Ergebnis in die Rundenfunktion F eingegeben und deren Ausgabe mit der rechten Hälfte XOR-verknüpft und die Hälften anschließend vertauscht. Am Ende werden noch die beiden Hälften mit den Rundenschlüsseln P17 und P18 XOR-verknüpft:

 R_{i+1} = L_i \oplus P_i,
 L_{i+1} = R_i \oplus F(R_{i+1}) \quad (i \; \text{von} \; 1 \; \text{bis} \; 16)
 R_{18} = L_{17} \oplus P_{17}, \; L_{18} = R_{17} \oplus P_{18}

L18 und R18 bilden dann den Schlüsseltextblock. Die Entschlüsselung läuft exakt gleich ab, nur werden dabei alle Rundenschlüssel P1 bis P18 in umgekehrter Reihenfolge verwendet. Das beruht auf der Vertauschbarkeit der XOR-Verknüpfungen. XOR ist sowohl kommutativ als auch assoziativ. Es ist gleich, ob man eine Hälfte des Datenblocks erst mit einem Rundenschlüssel und dann mit der Ausgabe der Funktion F verknüpft oder umgekehrt.

In der Funktion F kommen die schlüsselabhängigen S-Boxen zum Einsatz. Der Eingabewert wird in vier Byte geteilt, mit denen jeweils ein Wert aus einer von vier 8 x 32 Bit S-Boxen ausgelesen wird. Diese Werte werden mittels XOR und Addition modulo 232 verknüpft:

 F(x) = \lbrace \lbrack \, S_1(x_{24..31}) \; + \; S_2(x_{16..23}) \, \rbrack \; \oplus \; S_3(x_{8..15}) \, \rbrace \; + \; S_4(x_{0..7}).

Dabei steht x_{a..b}\!\, für die Bits an den Positionen a bis b aus der Binärdarstellung des Wertes x.

Schlüsseleinteilung

Blowfish verwendet 18 Rundenschlüssel P mit je 32 Bit, und vier S-Boxen mit je 256 = 28 Einträgen von je 32 Bit. Die Initialisierung der P-Werte und der vier S-Boxen erfolgt mit einer fixen Zahlenfolge, die aus der hexadezimalen Ziffernfolge der Kreiszahl π abgeleitet wird. Davon ausgehend werden sowohl die P1 bis P18 als auch alle S-Boxen, S1 bis S4, in ihren Werten schlüsselabhängig verändert.

Dazu wird zuerst der Schlüssel in 32-Bit-Blöcke aufgeteilt. Danach wird jeder P-Wert 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, unter Verwendung der aktuellen P-Werte und der wie oben initialisierten S-Boxen. Die linke und rechte Hälfte des entstandenen Schlüsseltextes ersetzen dann den ersten und zweiten Eintrag der P-Box. Dann wird mit dem aktuellen Stand der P-Werte der Geheimtext aus dem letzten Schritt nochmals verschlüsselt, und der dritte und vierte Eintrag der P-Box wird ersetzt. Nachdem auf diese Weise alle P-Werte ersetzt wurden, kommen die Einträge der S-Boxen an die Reihe, wobei die jeweils nächste Verschlüsselung mit dem aktuellen Stand der S-Boxen gemacht wird. Es werden also insgesamt 521 Verschlüsselungen durchgeführt, bis die 18 P-Werte und die 1024 S-Box-Einträge ersetzt sind.

Danach bleiben die P-Werte und die Werte in den S-Boxen so lange konstant, bis ein neuer Schlüssel gewählt wird.

Als C++-Code geschrieben:

 uint32_t P[18];       // Rundenschlüssel
 uint32_t S[4][0x100]; // S-Boxen
 
 uint32_t f (uint32_t x) {
    uint32_t h = S[0][x >> 24] + S[1][x >> 16 & 0xff];
    return ( h ^ S[2][x >> 8 & 0xff] ) + S[3][x & 0xff];
 }
 
 void encrypt (uint32_t & L, uint32_t & R) {
    for (int i=0 ; i<16 ; i += 2) {
       L ^= P[i];
       R ^= f(L);
       R ^= P[i+1];
       L ^= f(R);
    }
    L ^= P[16];
    R ^= P[17];
    swap (L, R);
 }
 
 void decrypt (uint32_t & L, uint32_t & R) {
    for (int i=16 ; i > 0 ; i -= 2) {
       L ^= P[i+1];
       R ^= f(L);
       R ^= P[i];
       L ^= f(R);
    }
    L ^= P[1];
    R ^= P[0];
    swap (L, R);
 }
 
 void key_schedule (uint32_t key[], int keylen) {
    // ...
    // Initialisiere P[] und S[][] mittels der Kreiszahl Pi; hier ausgelassen
    // ...
    for (int i=0 ; i<18 ; ++i)
       P[i] ^= key[i % keylen];
    uint32_t L = 0, R = 0;
    for (int i=0 ; i<18 ; i+=2) {
       encrypt (L, R);
       P[i] = L; P[i+1] = R;
    }
    for (int i=0 ; i<4 ; ++i)
       for (int j=0 ; j<0x100 ; j+=2) {
          encrypt (L, R);
          S[i][j] = L; S[i][j+1] = R;
       }
 }

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 Schlüsseltext 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]

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 quelloffenes Windows-Programm zum Verschlüsseln von Dateien mittels Blowfish und Twofish ist Blowfish Advanced CS. Auch im OpenDocument-Datenformat ist Blowfish als Verschlüsselungsmethode aufgeführt. Ab PHP 5.3 ist Blowfish Bestandteil der crypt-Funktion.

Referenzen

  1. Mike Morgan: Blowfish can be cracked! (Fix included...). Veröffentlichung in der Newsgroup sci.crypt
  2. Serge Vaudenay (23. August 2006): On the Weak Keys of Blowfish (PostScript). Abgerufen am 31. Dezember 2007.
  3. Dahna McConnachie (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

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Blowfish-16 — Blowfish Feistelnetzwerk von Blowfish Entwickler Bruce Schneier Veröffentlicht 1993 Schlüssellänge 32 448 Bit (Standard 128 Bit) Block …   Deutsch Wikipedia

  • Blowfish-8 — Blowfish Feistelnetzwerk von Blowfish Entwickler Bruce Schneier Veröffentlicht 1993 Schlüssellänge 32 448 Bit (Standard 128 Bit) Block …   Deutsch Wikipedia

  • Blowfish — Résumé Concepteur(s) Bruce Schneier Première publication 1993 Dérivé de …   Wikipédia en Français

  • Blowfish — Создатель: Брюс Шнайер Создан: 1993 г. Опубликован: 1993 г. Размер ключа: от 32 до 448 бит Размер блока: 64 бит Число раундов: 16 Тип …   Википедия

  • Blowfish — Saltar a navegación, búsqueda En criptografía, Blowfish es un codificador de bloques simétricos, diseñado por Bruce Schneier en 1993 e incluido en un gran número de conjuntos de codificadores y productos de cifrado. Mientras que ningún analizador …   Wikipedia Español

  • blowfish — ☆ blowfish [blō′fish΄ ] n. pl. blowfish or blowfishes (see FISH) PUFFER (sense 2) …   English World dictionary

  • blowfish — low fish n. 1. a fish eaten as a delicacy, especially in Japan. It is highly dangerous because of a potent nerve poison (tetrodotoxin) in its ovaries and liver. Chefs require special training to learn how to remove the poisonous parts, and in… …   The Collaborative International Dictionary of English

  • Blowfish — Blowfish,   ein 1993 entwickeltes Verfahren zur Datenverschlüsselung. Es arbeitet mit Datenblöcken der Größe 64 bit sowie unterschiedlichen Schlüssellängen von 32 bis 338 bit und gilt als sicher …   Universal-Lexikon

  • blowfish — also blow fish, 1862, Amer.Eng., from BLOW (Cf. blow) (v.1) + FISH (Cf. fish) (n.). Then he described another odd product of the bay, that was known as the blow fish, and had the power of inflating himself with air when taken out of the water. [… …   Etymology dictionary

  • Blowfish — En criptografía, Blowfish es un codificador de bloques simétricos, diseñado por Bruce Schneier en 1993 e incluido en un gran número de suites de codificadores y productos de cifrado. Mientas que ningún analizador de cifrados de Blowfish efectivo… …   Enciclopedia Universal

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”