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 keydependent Sboxes . The key length can be between 32 bits and 448 bits. From these key bits, the socalled round keys P _{1} to P _{18} and the entries in the Sboxes are generated, a total of 4168 bytes , before the encryption or decryption begins .
functionality
The illustration shows the internal structure of Blowfish. The 64bit wide plain text block is divided into two halves and . In each socalled round  there are a total of 16 rounds  the left half of the data block is XOR linked with a 32bit 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 XORlinked and then swapped the halves. At the end, the two halves are XORlinked 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 keydependent Sboxes 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 Sboxes. 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 Sboxes with 256 each = 2 ^{8} entries of 32 bits each. The Pvalues and the four Sboxes are initialized with a fixed number sequence derived from the hexadecimal number sequence of the circle number π . The decimal places of π are pseudorandom 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 Sboxes, S _{1} to S _{4} , are changed in their values depending on the key.
To do this, the key is first divided into 32bit blocks. Then each P value is XORed with the 32bit 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 Sboxes initialized as above. The left and right halves of the resulting ciphertext then replace the first and second entries in the PBox. 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 SBox entries come in turn, with the next encryption being made with the current status of the SBoxes. A total of 521 encryptions are carried out until the 18 P values and the 1024 SBox 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]; // SBoxen
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 bigendian Reihenfolge eingelesen wird
// ...
for ( i=0 ; i<18 ; ++i)
{
/* Der Schlüssel wird byteweise gelesen, und */
/* in bigendian 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 fullround encryption. A socalled 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 keydependent Sboxes.
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
 Twofish , successor to Blowfish
 Puffy, the blowfish , mascot of the OpenSSH
literature
 Vincent Rijmen: Cryptanalysis and design of iterated block ciphers . doctoral dissertation, October 1997.
 Bruce Schneier: Description of a New VariableLength Key, 64bit Block Cipher (Blowfish) . Fast Software Encryption 1993, pp. 191204, 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. SpringerVerlag, 1996, pp. 2732.
Web links
 Bruce Schneiers description of the algorithm including several source codes
 SBox and PBox
 Perl Blowfish encryption module
 Blowfish PHP implementation
 Online Blowfish encryption (PHP or JavaScript)
 Blowfish JavaScript implementation
 Blowfish Tcl implementation, also included in the Tcllib
 Blowfish LabVIEW implementation
 Standard Cryptographic Algorithm Naming for Blowfish
 Blowfish Advanced CS ( Memento from February 19, 2013 in the Internet Archive )
Individual evidence
 ↑ Schneier on Security: The Blowfish Encryption Algorithm. Retrieved February 23, 2018 .

↑ Bruce Schneier: Description of a new variablelength key, 64bit 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."
 ↑ Mike Morgan: Blowfish can be cracked! (Fix included ...) . Newsgroup sci.crypt
 ↑ Serge Vaudenay: On the Weak Keys of Blowfish ( PostScript ) 23. August 2006. Retrieved on December 31 of 2007.
 ↑ 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. "
 ↑ Karthikeyan Bhargavan, Gaëtan Leurent: On the Practical ( In ) Security of 64bit Block Ciphers  Collision Attacks on HTTP over TLS and OpenVPN . ACM CCS 2016. August 2016.
 ↑ Official OpenSSL documentation: Blowfish ( Memento from February 14, 2014 in the Internet Archive )
 ↑ Official OpenVPN documentation
 ↑ OpenSSH 7.4 Release Notes