Blowfish

from Wikipedia, the free encyclopedia
Blowfish
Blowfish
Feistel network from Blowfish
developer Bruce Schneier
Released 1993
Key length 32–448 bit (standard 128 bit)
Block size 64 bit
structure Feistel cipher
Round 16
Best known cryptanalysis

Blowfish ( German  puffer fish ) is a symmetrical block encryption algorithm that was designed by Bruce Schneier in 1993 and first published in April 1994 in Dr. Dobb's Journal was published. It was published unpatented and in the public domain and can therefore be used freely.

As a block cipher, Blowfish has a fixed block length of 64 bits, is based on a Feistel network , which guarantees the reversibility between encryption and decryption, and has key-dependent S-boxes . The key length can be between 32 bits and 448 bits. From these key bits, the so-called round keys P 1 to P 18 and the entries in the S-boxes are generated, a total of 4168 bytes , before the encryption or decryption begins .

functionality

The illustration shows the internal structure of Blowfish. The 64-bit wide plain text block is divided into two halves and . In each so-called round - there are a total of 16 rounds - the left half of the data block is XOR- linked with a 32-bit wide round key P 1 to P 16 calculated in advance , then the result is entered into the round function F and its output with the right half XOR-linked and then swapped the halves. At the end, the two halves are XOR-linked with the round keys P 17 and P 18 :

and then form the cipher text block. The decryption is exactly the same, except that all round keys P 1 to P 18 are used in reverse order. This is based on the interchangeability of the XOR links. XOR is both commutative and associative . It does not matter whether half of the data block is first linked with a round key and then with the output of function F or vice versa.

The key-dependent S-boxes are used in function F. The input value is divided into four bytes, each of which is used to read a value from one of four 8 × 32 bit S-boxes. These values ​​are linked modulo using XOR and addition :

.

Here stands for the bits at positions a to b from the binary representation of the value x .

Key division

Blowfish uses 18 round keys P with 32 bits each and four S-boxes with 256 each = 2 8 entries of 32 bits each. The P-values ​​and the four S-boxes are initialized with a fixed number sequence derived from the hexadecimal number sequence of the circle number π . The decimal places of π are pseudo-random and independent of the rest of the algorithm, so the requirements for an unsuspicious constant are met. Starting from this, both the round keys P 1 to P 18 and all S-boxes, S 1 to S 4 , are changed in their values ​​depending on the key.

To do this, the key is first divided into 32-bit blocks. Then each P value is XORed with the 32-bit blocks of the key. The blocks of the key alternate one after the other. Then a block with 64 zero bits is encrypted using the current P values ​​and the S-boxes initialized as above. The left and right halves of the resulting ciphertext then replace the first and second entries in the P-Box. Then the ciphertext from the last step is encrypted again with the current status of the P values, and the third and fourth entries in the P box are replaced. After all P values ​​have been replaced in this way, the S-Box entries come in turn, with the next encryption being made with the current status of the S-Boxes. A total of 521 encryptions are carried out until the 18 P values ​​and the 1024 S-Box entries are replaced.

The P values ​​and the values ​​in the S boxes then remain constant until a new key is selected.

Written as C ++ code:

 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 (uint8_t key[], int keylen) {
    int i;
    int j=0;
    int k;
    // ...
    // Initialisiere P[] und S[][] mittels der Kreiszahl Pi; hier ausgelassen
    // Es ist zu beachten, dass Pi in big-endian Reihenfolge eingelesen wird
    // ...
    for ( i=0 ; i<18 ; ++i)
    {
     /* Der Schlüssel wird byteweise gelesen, und */
     /* in big-endian Reihenfolge mit *P verrechnet */
     uint32_t tmp=0;
     for(k=0;k<4;k++)
     {
      tmp<<=8;
      tmp|=key[j];
      j=j+1;
      if(j>=keylen) j=0;
     }
     P[i] ^= tmp;
    }
    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 and Security

There is no known effective attack on Blowfish full-round encryption. A so-called sign extension bug was found in a publication of the C code.

Serge Vaudenay found a known plaintext attack in 1996 that required 2 8 r + 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 recognized and broken with just 2 4 r + 1 plaintext pairs. However, this attack cannot be used against regular Blowfish, as it requires knowledge of the key-dependent S-boxes.

In his doctoral thesis, Vincent Rijmen presents a differential second order attack that can break Blowfish with a maximum of 4 rounds. Apart from the brute force method , there is no known way to break the algorithm with 16 rounds.

Bruce Schneier notes that he recommends the newer Twofish algorithm, although Blowfish is still in widespread use.

Since Blowfish uses a block size of 64 bit (AES uses 128 bit blocks), a birthday attack is possible - especially in the HTTPS or OpenVPN context. In 2016, the SWEET32 attack showed how a birthday attack can be used to restore plaintext. The SWEET32 attack works with encryption methods such as Blowfish, which work with a block size of 64 bits.

Examples

In the GNU Privacy Guard Blowfish and Twofish implemented and can be activated on demand. The Cryptographic File System (CFS) is an encrypted file system for UNIX based on NFS and also supports Blowfish. An open source Windows program for encrypting files using Blowfish, Twofish and other algorithms such as B. AES is Blowfish Advanced CS. Blowfish is also listed as an encryption method in the OpenDocument data format . From PHP 5.3, Blowfish is part of the crypt function. Blowfish is also implemented in the free OpenSSL crypto library . The VPN software OpenVPN also uses Blowfish as a symmetrical component by default.

In Release 7.4 released at the end of 2016, OpenSSH removed Blowfish support, as well as many other weak ciphers.

See also

literature

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

Web links

Individual evidence

  1. Schneier on Security: The Blowfish Encryption Algorithm. Retrieved February 23, 2018 .
  2. Bruce Schneier: Description of a new variable-length key, 64-bit block cipher (Blowfish) . In: FSE 1993 (=  Lecture Notes in Computer Science ). tape 809 . Springer, 1994, p. 201 ( schneier.com ).

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

    "I chose the digits of Pi as the initialization of the subkeys for two reasons: because it is a random sequence unrelated to the algorithm, and because it can either be stored as part of the algorithm or calculated if necessary."

  3. Mike Morgan: Blowfish can be cracked! (Fix included ...) . Newsgroup sci.crypt
  4. Serge Vaudenay: On the Weak Keys of Blowfish ( PostScript ) 23. August 2006. Retrieved on December 31 of 2007.
  5. Dahna McConnachie: Bruce Almighty: Schneier preaches security to Linux faithful . In: Computerworld . S. 3. December 27, 2007. Archived from the original on October 5, 2008. Retrieved on December 31, 2007: “At this point, though, I'm amazed it's still being used. If people ask, I recommend Twofish instead. "
  6. Karthikeyan Bhargavan, Gaëtan Leurent: On the Practical ( In- ) Security of 64-bit Block Ciphers - Collision Attacks on HTTP over TLS and OpenVPN . ACM CCS 2016. August 2016.
  7. Official OpenSSL documentation: Blowfish ( Memento from February 14, 2014 in the Internet Archive )
  8. Official OpenVPN documentation
  9. OpenSSH 7.4 Release Notes