Blowfish is optimized for applications where the key does not change often, like a communications link or an automatic file encryptor. It is significantly faster than DES when implemented on 32-bit microprocessors with large data caches, such as the Pentium and the PowerPC. Blowfish is not suitable for applications, such as packet switching, with frequent key changes, or as a one-way hash function. Its large memory requirement makes it infeasible for smart card applications.

Description of Blowfish

Blowfish is a 64-bit block cipher with a variable-length key. The algorithm consists of two parts: key expansion and data encryption. Key expansion converts a key of up to 448 bits into several subkey arrays totaling 4168 bytes.

Data encryption consists of a simple function iterated 16 times. Each round consists of a key-dependent permutation, and a key- and data-dependent substitution. All operations are additions and XORs on 32-bit words. The only additional operations are four indexed array data lookups per round.

Blowfish uses a large number of subkeys. These keys must be precomputed before any data encryption or decryption.

The P-array consists of 18 32-bit subkeys:

P₁, P₂,..., P₁₈

Four 32-bit S-boxes have 256 entries each:

S_1,0, S_1,1,..., S_1,255

S_2,0, S_2,1,..., S_2,255

S_3,0, S_3,1,..., S_3,255

S_4,0, S_4,1,..., S_4,255

The exact method used to calculate these subkeys will be described later in this section.

Figure 14.2  Blowfish.

Blowfish is a Feistel network (see Section 14.10) consisting of 16 rounds. The input is a 64-bit data element, x. To encrypt:

Divide x into two 32-bit halves: x_L, x_R

For i = 1 to 16:

x_L = x_L ⊕ P_i

x_R = F(x_L) ⊕ x_R

Swap x_L and x_R

Swap x_L and x_R (Undo the last swap.)

x_R = x_R ⊕ P₁₇

x_L = x_L ⊕ P₁₈

Recombine x_L and x_R

Figure 14.3  Function F.

Function F is as follows (see Figure 14.3):

Divide x_L into four eight-bit quarters:

a, b, c, and d F(x_L) = ((S_1,a + S_2,b mod 2³²) ⊕ S_3,c) + S_4,d mod 2³²

Decryption is exactly the same as encryption, except that P₁, P₂,..., P₁₈ are used in the reverse order.

Implementations of Blowfish that require the fastest speeds should unroll the loop and ensure that all subkeys are stored in cache. See [568] for details.

The subkeys are calculated using the Blowfish algorithm. The exact method follows.

(1)  Initialize first the P-array and then the four S-boxes, in order, with a fixed string. This string consists of the hexadecimal digits of p.

(2)  XOR P₁ with the first 32 bits of the key, XOR P₂ with the second 32-bits of the key, and so on for all bits of the key (up to P₁₈). Repeatedly cycle through the key bits until the entire P-array has been XORed with key bits.

(3)  Encrypt the all-zero string with the Blowfish algorithm, using the subkeys described in steps (1) and (2).

(4)  Replace P₁ and P₂ with the output of step (3).

(5)  Encrypt the output of step (3) using the Blowfish algorithm with the modified subkeys.

(6)  Replace P₃ and P₄ with the output of step (5).

(7)  Continue the process, replacing all elements of the P-array, and then all four S-boxes in order, with the output of the continuously changing Blowfish algorithm.

In total, 521 iterations are required to generate all required subkeys. Applications can store the subkeys—there’s no need to execute this derivation process multiple times.

Security of Blowfish

Serge Vaudenay examined Blowfish with known S-boxes and r rounds; a differential attack can recover the P-array with 2^{8r + 1} chosen plaintexts [1568]. For certain weak keys that generate bad S-boxes (the odds of getting them randomly are 1 in 2¹⁴), the same attack requires only 2^{4r + 1} chosen plaintexts to recover the P-array. With unknown S-boxes this attack can detect whether a weak key is being used, but cannot determine what it is (neither the S-boxes nor the P-array). This attack only works against reduced-round variants; it is completely ineffective against 16-round Blowfish.

Of course, the discovery of weak keys is significant, even though they seem impossible to exploit. A weak key is one in which two entries for a given S-box are identical. There is no way to check for weak keys before doing the key expansion. If you are worried, you have to do the key expansion and check for identical S-box entries. I don’t think this is necessary, though.

I know of no successful cryptanalysis against Blowfish. To be safe, do not implement Blowfish with a reduced number of rounds.

Kent Marsh Ltd. has incorporated Blowfish in their FolderBolt security product for Microsoft Windows and Macintosh. It is also part of Nautilus and PGPfone.

14.4 SAFER

SAFER K-64 stands for Secure And Fast Encryption Routine with a Key of 64 bits [1009]. James Massey produced this nonproprietary algorithm for Cylink Corp. and it is incorporated into some of their products. The government of Singapore is planning to use this algorithm—with a 128-bit key [1010]—for a wide variety of applications. There are no patent, copyright, or other restrictions on its use.

The algorithm has a block and key size of 64 bits. It is not a Feistel network like DES (see Section 14.10), but an iterated block cipher: The same function is applied for some number of rounds. Each round uses two 64-bit subkeys, and the algorithm only uses operations on bytes.

Description of SAFER K-64

The plaintext block is divided into eight byte-length sub-blocks: B₁, B₂,..., B₇, B₈. Then the sub-blocks go through r rounds. Finally, an output transformation is applied to the sub-blocks. Each round uses two subkeys: K_{2i - 1} and K_2i.

Figure 14.4 shows one round of SAFER K-64. First, sub-blocks are either XORed or added with bytes of subkey K_{2i - 1}. Then, the eight sub-blocks are subjected to one of two nonlinear transformations:

y = 45^x mod 257. (If x = 128, then y = 0.)

y = log₄₅ x. (If x = 0, then y = 128.)