Blowfish (cipher)

• 14 rounds are vulnerable to a class of weak keys, for a pseudo-random permutation

Blowfish is a symmetric block cipher, designed in 1993 by Bruce Schneier and first published in April 1994 in Dr. Dobb 's Journal. He was released into the public domain and can be freely used.

Blowfish block cipher than a fixed block length of 64 bits, based on a Feistelnetzwerk, which guarantees the reversibility between encryption and decryption, and key-dependent S-boxes has. The key length can be between 32-bit and 448-bit. These key bits before the encryption or decryption of the so-called round keys P1 to P18, and the entries are generated in the S-boxes, a total of 4168 bytes.

Operation

The figure shows the internal structure of Blowfish. The 64 -bit plaintext block is divided into two halves. In every so-called round - there are a total of 16 rounds - is the left half of the data block with a pre-computed 32 -bit round keys P1 to P16 XORed, the result is input to the round function F, and the issue with the right half of XOR linked, and the halves then reversed. The two halves together with the round keys P17 and P18 are XORed At the end yet:

And then form the ciphertext block. The decryption runs exactly the same, just all round keys are thereby P1 to P18 used in reverse order. This is due to the interchangeability of the XOR operations. XOR is both commutative and associative. It does not matter if you linked to one half of the data block only with a round key and then use the output of the function F, or vice versa.

In the function F, the key-dependent S-boxes are used. The input value is divided into four bytes, with each of which a value of one of the four 8 x 32-bit S-boxes is read out. These values ​​are combined using XOR and addition modulo:

Stands for the bits at the positions a to b in the binary representation of the value x.

Key schedule

Blowfish uses 18 round key P with 32 bits each, and four S-boxes of 256 = 28 entries of 32 bits each. The initialization of the P- values ​​and the four S-boxes is done with a fixed number sequence, which is derived from the hexadecimal digit sequence number of the circle π. The decimal places of π are pseudo- randomly and independently from the rest of the algorithm, so the demands on an unsuspecting constant fulfilled .. Of these, starting both the round keys P1 to P18 as well as all S-boxes, S1 to S4, changed key dependent in their values.

For this, the key is divided into 32 -bit blocks first. Thereafter, each P- value is XORed with the 32 -bit blocks of the key. Here, the blocks of the key switch a row. Thereafter, a block with 64 zero bits is encrypted using the current values ​​of P, and the above initialized S-boxes. The left and right halves of the resulting ciphertext then replace the first and second entry of the P-box. Then, the ciphertext from the previous step is encrypted again with the state of the values ​​of P, and the third and the fourth entry of the P-box is replaced. After all P values ​​were replaced in this way, the entries of the S-boxes come to the series, with the next respective encryption is done with the current state of the S-boxes. There are thus performed a total of 521 encryptions until the 18 P - values ​​and the 1024 S-box entries are replaced.

Thereafter, the p - values ​​and the values ​​in the S-boxes remain constant until a new key is selected.

As a C code written:

Uint32_t P; / / Round key   uint32_t S [ 0x100 ]; / / S-boxes     uint32_t f ( uint32_t x ) {      uint32_t h = S [ x >> 24] S [x >> 16 & 0xff ];      return ( h ^ S [ x >> 8 & 0xff ] ) S [ 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;      R ^ = P;      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;      R ^ = P;      swap ( L, R);   }     void key_schedule ( uint32_t key [ ], int keylen ) {      / / ...      / / Initialize P [] and S [ ] [ ] using the circle of pi; omitted here      / / ...      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;         }   } cryptanalysis

There is no known effective attack on the Blowfish encryption with full number of rounds. A so-called sign- extension bug has been found in a publication of the C code.

Serge Vaudenay started in 1996 with a known- plaintext attack which requires 28r 1 known pairs of plaintext and ciphertext to break the encryption. The parameter r denotes the number of rounds. He also discovered a class of weak keys that can be detected and broken with only 24r 1 plaintext pairs. However, this attack can not be used against the regular Blowfish, as it requires knowledge of the key-dependent S-boxes.

Vincent Rijmen is in his doctoral thesis before a differential second-order attack that can Blowfish with at most 4 rounds break. In addition to the brute- force method is no way known to break the algorithm with 16 rounds.

Bruce Schneier notes that it recommends to the more recent Twofish algorithm, although Blowfish is still in wide use.

Examples

In the GNU Privacy Guard Blowfish and Twofish are implemented and can be activated on request. The Cryptographic File System ( CFS) is a program that runs on NFS encrypted file system for UNIX, and also supports Blowfish. An open source Windows application to encrypt files using Blowfish, Twofish and other algorithms such as Blowfish Advanced CS is AES. In the OpenDocument file format Blowfish is listed as the encryption method. As of PHP 5.3 Blowfish is part of the crypt function. Blowfish is also implemented in the free OpenSSL crypto library.

Credentials

" I chose the digits of pi as the initial subkey table for two Reasons: because it is a random sequence not related to the algorithm, and Because It Could Either be stored as part of the algorithm or derived when needed. "

• 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.
• Bruce Schneier: The Blowfish Encryption Algorithm - One Year Later, Dr. Dobb 's Journal, 20 ( 9), p. 137, September 1995.
• Serge Vaudenay: On the weak keys of Blowfish Encryption Software Fast ( FSE'96 ), LNCS 1039, D. Gollmann, Ed, Springer - Verlag, 1996, pp. . 27 - 32