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,
, 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 _{0}* and

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, ,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 signify
addition modulo 2^{32}:

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 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 _{1}*, the next 32 bits
with

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 _{1}* and

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 , *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 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.