Blowfish is a symmetric encryption algorithm developed by Bruce Schneier to replace Data Encryption Standard (DES). At the time of its development, most encryption algorithms were protected by patents, government secrecy, or company intellectual property. Schneier placed Blowfish in the public domain making it freely available for anyone to use.

Blowfish is a 16-round Feistel cipher. It’s block size is 64-bit and key sizes range from 32 to 448 bits. In this article, we’ll first take a look at the Blowfish algorithm (encryption, decryption and key schedule), and then discuss its advantages and disadvantages.

Encryption with Blowfish

Encryption with Blowfish has two main stages: sixteen iterations of the round function and an output operation.

Diagram of Blowfish Encryption. Overall structure on the left, zoomed in view of round function on the right.

In this section, we’ll assume we are given the round keys and the value of the S-boxes. Details of how the round keys are generated and S-boxes initialized is covered in the key schedule section.

Blowfish round function

The round function in Blowfish encryption has four stages (see diagram above):

1. Key whitening of the left side of the input with the rth round key
2. Application of the S-Boxes and combination of their results
3. Exclusive-or of the right side of the input with the output of the F function (key whitening, S-Boxes and combination of S-Box output)
4. Swapping the sides of the output

In the key-whitening stage, the left side of the input is exclusive-ored with the round key for the given round.

The S-Boxes perform an 8-bit to 32-bit mapping. The S-Boxes are set as part of the key generation algorithm. The output of an S-Box for an input of n is the nth value in the S-Box.

The outputs of the S-Boxes are combined through a mixture of addition and exclusive-or. The outputs of the first two S-Boxes are added together modulo 2³². The result is exclusive-ored to the output of the third S-Box and the result of that is added modulo 2³² to the output of the fourth S-Box. More formally, the result, R, of applying this sequence to input, I, is reached through the following equation (where a[0:5] refers to the first 5 bits of a):

A = S0(I[0:8]) + S1(I[8:16]) mod 2**32
B = A ^ S2(I[16:24]))
R = B + S3(I[24:32]) mod 2**32

Like other Feistel functions, the output of this is exclusive-ored with the other side of the input (the right side in this case) and the two sides of the input are swapped before entering the next round.

Blowfish output function

The final stage of the Blowfish cipher involves two steps: reversing the final swap and performing output whitening. In output whitening, the right side of the output (after being swapped) is exclusive-ored with the seventeenth round key and the left side is exclusive-ored with the eighteenth round key. The result of this is the Blowfish ciphertext.

Blowfish Key Schedule (and S-box generation)

Initial values

The Blowfish key schedule relies heavily on the Blowfish encryption algorithm described in the previous section. The key schedule uses a value, P, consisting of eighteen words which contain (in order) the first eighteen words of the binary representation of the fractional part of pi. For example, the hexadecimal representation of pi begins with 3.243F6A8885A308D313198A2E037073, therefore P₁=0x243F6A88, P₂=0x85A308D3, etc. This value, P, will become the round keys used in encryption.

Next, set the initial values of the S-Boxes in the same manner beginning with the 19th word of the fractional part of pi. The ordering should be that the entire first S-Box is filled in order before moving on to the next and so on.

Since P contains 18 words and the S-Boxes each contain 256 words, a total of 18 + 4*256 = 1042 pi words are used, each 32-bit in size.

Generating Round Keys and S-box

Generation of the round key is performed in rounds where each round generates two round key values. The process is as follows:

1. Initialize P and S-Boxes as described above
2. Exclusive-or P₁ with the first 32 key bits, P₂ with the next 32 bits and so on until all of the key has been exclusive-ored (since the key is shorter than P, parts of it will be used multiple times to cover all of P)
3. Set the initial input to zero
4. Encrypt the input using the current version of P as the round keys
5. Set the first two unreplaced values of P to the value of the ciphertext from step 4
6. Set the input to the ciphertext from step 4
7. Repeat steps 4 through 6 until all of P has been replaced
8. Use the resulting value of P as the round keys in encryption
9. Repeat steps 4 through 6, replacing values of the S-Boxes two at a time until all S-Box values have been replaced.

Since P contains 18 words and the S-Boxes each contain 256 words, there is a total of 18 + 4*256 = 1042 values to replace, which will take 521 iterations of steps 4 through 6 of the above algorithm to complete.

The Blowfish key schedule: The encryption operation is same as the one described in the previous section. Output splitting and entering into two boxes indicates updating the next two values of P or the relevant S-Box. Lines that loop back and join with a previous line indicate that on the next iteration, the updated value is used.

Since the S-Box values are used in all rounds of encryption and are set last, it is necessary to complete the key schedule before performing encryption (other ciphers like AES would allow the generation of round key i+1 while round i is being run).

Decryption with Blowfish

Because Blowfish is a Feistel cipher, the same structure can be used for encryption and decryption as long as the round keys are used in reverse order.

It is important to note that the encryption structure must be used in the same order, i.e. the final exclusive-or should not be performed before beginning the round functions. This exclusive-or from encryption will be undone in decryption by the first exclusive-or in the round function.

The reason why the decryption works is the same as why decryption works for any Feistel structure cipher. (Although the F function is an involved function, it is still a fixed function, and the cipher behaves like any Feistel structure cipher).

That is, each half of the plaintext is alternately exclusive-ored with a round key and exclusive-ored with the output of the F function (ignoring the switches in sides of the halves since they do not change the value of the half). This is true in both encryption and decryption, and hence each exclusive-or during decryption un-does the most recent exclusive-or performed during encryption. (and is the reason that, in decryption, the final exclusive-or should not be performed before beginning the round functions).

Advantages of Blowfish

Blowfish is in the public domain, allowing it to be freely used for any purpose.

After the key schedule has completed, Blowfish is a relatively fast block cipher due to the small number of rounds (sixteen) and the simplicity of the round operation (a few modular additions and exclusive-ors).

Disadvantages of Blowfish

The key schedule in Blowfish is rather time-consuming (equivalent to encryption of about 4 KB of data). However, this can be an advantage in some circumstances as protection against brute-force attacks.

The small block size of Blowfish (64 bits) is more vulnerable to birthday attacks than the 128 bits used by AES.

The creator of Blowfish, Bruce Schneier, recommends that Blowfish be abandoned in favor of Twofish, a cipher of which he was part of the development team. Twofish will be discussed in a later article.