Eksblowfish Algorithm

 

  

Figure 2: Eksblowfish, expensive key schedule blowfish, is a cost parameterizable and salted variation of the blowfish block cipher.

We now describe a cost parameterizable and salted block cipher that we call eksblowfish for expensive key schedule blowfish. Eksblowfish is designed to take user-chosen passwords as keys and resist attacks on those keys. As its base we use the blowfish [15] block cipher by Schneier, which is well-established and has been fairly well analyzed.

Blowfish is a 64-bit block cipher, structured as a 16-round Feistel network [14]. It uses 18 32-bit subkeys, $P_1,\ldots,P_{18}$, which it derives from the encryption key. The subkeys are known collectively as the P-Array.

Blowfish encrypts by splitting a 64-bit input block into two 32-bit halves, L₀ and R₀. The most-significant half, L₀, is XORed with subkey P₀, and used as input for a function F. The result of that function is XORed with the least-significant half, R₀. The two halves are then swapped, and the whole process repeated another 15 times for a total of 16 iterations. Thus, for $1 \leq i \leq 16$, letting $\oplus$ denote XOR:

After 16 rounds, the two halves are swapped again (undoing the effect of the 16th swap), and each half is XORed with another 32-bit subkey:

This process is illustrated graphically in Figure 1.

The function F in Blowfish uses four arrays, $S_1,\ldots, S_4$,derived from the encryption key. Each array contains 256 32-bit words. The arrays act as substitution boxes or S-boxes, replacing an 8-bit input with a 32-bit output. F splits its 32-bit input into four 8-bit bytes, a, b, c, and d, with a the most significant byte. It replaces each byte by the contents of an S-box, and combines the results as follows: Letting $\boxplus$ signify addition modulo 2³²:

$$F(a,b,c,d) = \big((S_1[a] \boxplus S_2[b]) \oplus S_3[c]\big) \boxplus S_4[d].$$

Eksblowfish encrypts identically to Blowfish. The two differ in the functions they use to transform encryption keys into subkeys and S-boxes. Figure 2 sketches EksBlowfishSetup, the algorithm used by eksblowfish. EksBlowfishSetup has three input parameters: a cost, a salt, and the encryption key. It returns a set of subkeys and S-boxes, also known as a key schedule.

The cost parameter controls how expensive the key schedule is to compute. The salt is a 128-bit value that modifies the key schedule so that the same key need not always produce the same result, as motivated by Section 3. Finally, the key argument is a secret encryption key, which can be a user-chosen password of up to 56 bytes (including a terminating zero byte when the key is an ASCII string).

EksBlowfishSetup begins by calling InitState, a function that copies the digits of the number $\pi$ first into the subkeys, then into the S-boxes.

ExpandKey(state, salt, key) modifies the P-Array and S-boxes based on the value of the 128-bit salt and the variable length key. First it XORs all the subkeys in the P-array with the encryption key. The first 32 bits of the key are XORed with P₁, the next 32 bits with P₂, and so on. The key is viewed as being cyclic; when the process reaches the end of the key, it starts reusing bits from the beginning to XOR with subkeys.

Subsequently, ExpandKey blowfish-encrypts the first 64 bits of its salt argument using the current state of the key schedule. The resulting ciphertext replaces subkeys P₁ and P₂. That same ciphertext is also XORed with the second 64-bits of salt, and the result encrypted with the new state of the key schedule. The output of the second encryption replaces subkeys P₃ and P₄. It is also XORed with the first 64-bits of salt and encrypted to replace P₅ and P₆. The process continues, alternating between the first and second 64 bits salt. When ExpandKey finishes replacing entries in the P-Array, it continues on replacing S-box entries two at a time. After replacing the last two entries of the last S-box, S₄[254] and S₄[255], ExpandKey returns the new key schedule.

In computing ExpandKey(state, 0, key), a block of 128 0 bits is used instead of the salt. This is equivalent to a single iteration of the standard blowfish key schedule. The call to ExpandKey(state, 0, salt) simply treats the salt as a 16-byte key.

After calling InitState to fill a new key schedule with the digits of $\pi$, EksBlowfishSetup calls ExpandKey with the salt and key. This ensures that all subsequent state depends on both, and that no part of the algorithm can be precomputed without both salt and key. Thereafter, ExpandKey is alternately called with the salt and then key for $2^\mathit{cost}$ iterations. For all but the first invocation of ExpandKey, the second argument is a block of 128 0 bits. This more closely resembles the original blowfish key schedule, and also allows EksBlowfishSetup to be implemented more efficiently on CPU architectures with few registers.

We hope that the unpredictable and changing content of the P-array and S-Boxes will reduce the applicability of yet unknown optimizations. Additionally the eksblowfish S-Boxes require 4 KB of constantly accessed and modified memory. Thus, the S-Boxes cannot be shared across key schedules--separate S-Boxes must exist for every simultaneous execution. This vastly limits the usefulness of any attempts to pipeline the Feistel network in hardware.