The Blowfish Encryption Algorithm  One Year Later
B. Schneier
Dr. Dobb's Journal, September 1995.
DES is the workhorse of cryptography algorithms, and it's long
time to replace the 19yearold standard. The recent design of a
$1M machine that could recover a DES key in 3.5 hours only
confirmed what everybody knew: DES's key size is far too small
for today.
The world only partly trusted DES because it survived the
scrutiny of the NSA. Experts trusted DES because it was a
published standard, and because it survived 20 years of intensive
cryptanalysis by cryptographers around the world. Cryptography is
like that: confidence in an algorithm grows as group after group
tries to break it and fails.
Candidates for a replacement are emerging, but none have taken
widespread hold. TripleDES is the conservative approach; IDEA
(used in PGP) is the most promising new algorithm. And there are
a bevy of unpatented alsorans: RC4 (once a trade secret of RSA
Data Security, Inc. but now publicly available on the Internet),
SAFER, and my own Blowfish.
I first presented Blowfish at that Cambridge Algorithms Workshop
("Description of a New VariableLength Key, 64bit Block
Cipher (Blowfish)," Fast Software Encryption, R. Anderson,
ed., Lecture Notes in Computer Science #809, SpringerVerlag,
1994) and in Dr. Dobbs Journal (April 1994). From the start
Blowfish was intended to be a completely freeunpatented,
unlicensed, and uncopyrightedalternative to DES. Since then it
has been analyzed by some people and has started to see use in
some systems, both public and private. This article presents new
Blowfish code, as well as updates on the algorithm's security.
DESCRIPTION OF BLOWFISH
Blowfish is a block cipher that encrypts data in 8byte blocks.
The algorithm consists of two parts: a keyexpansion part and a
dataencryption part. Key expansion converts a variablelength
key of at most 18 PBoxes x 32bits (576 bits) into several subkey
arrays totaling 4168 bytes:
4 Sboxes x 256 words x 4 bytes (4096 bytes) PLUS
18 PBoxes x 4 bytes (72 bytes)=(PasswordSpace of 576 bits).
Note:
The description in this article differs slightly from the one in
the April 1994 issue of Dr. Dobbs Journal; there were typos in
steps (5) and (6) of the subkey generation algorithm.
Blowfish has 16 rounds.
Each round consists of a keydependent permutation, and a key and
datadependent substitution. All operations are XORs and additions
on 32bit words. The only additional operations are four indexed
array data lookups per round.
Subkeys:
Blowfish uses a large number of subkeys. These keys must be
precomputed before any data encryption or decryption. The Parray
consists of 18 32bit subkeys: P1, P2,..., P18.
There are also four 32bit Sboxes with 256 entries each:
S1,0; S1,1; S1,2; ... ; S1,255;
S2,0; S2,1; S2,2; ... ; S2,255;
S3,0; S3,1; S3,2; ... ; S3,255;
S4,0; S4,1; S4,2; ... ; S4,255;
Encryption and Decryption:
Blowfish has 16 rounds. The input is a 64bit data element, x.
Divide x into two 32bit halves: xL, xR. Then, for i = 1 to 16:
xL = xL XOR Pi
xR = F(xL) XOR xR
Swap xL and xR
After the sixteenth round, swap xL and xR again to undo the last swap.
Then, xR = xR XOR P17 and xL = xL XOR P18.
Finally, recombine xL and xR to get the ciphertext.
Function F looks like this:
Divide xL into four eightbit quarters: a, b, c, and d.
Then, F(xL) = ((S1,a + S2,b mod 232) XOR S3,c) + S4,d mod 232.
Decryption is exactly the same as encryption, except that P1,P2,..., P18
are used in the reverse order.
Generating the Subkeys:
The subkeys are calculated using the Blowfish algorithm:
1. Initialize first the Parray and then the four Sboxes, in
order, with a fixed string. This string consists of the
hexadecimal digits of pi (less the initial 3): P1 = 0x243f6a88,
P2 = 0x85a308d3, P3 = 0x13198a2e, P4 = 0x03707344, etc.
2. XOR P1 with the first 32 bits of the key, XOR P2 with the
second 32bits of the key, and so on for all bits of the key
(limited up to P18). This gives a full Passphrase space of
576 bits wit(18 PBoxes x 32 bits) with the 16 rounds standart.
Repeatedly cycle through the key bits until the entire Parray
has been XORed with key bits.
Note: For every short key, smaller than halfKeySpace, there is at
least one equivalent longer key, up to full KeySpace but not exceding it;
for example: if A is a 32bit key, then AA, AAA, etc., are equivalent keys.
equaly for 64,96,...,up to 288 bit keys (576/2).
3. Encrypt the allzero string with the Blowfish algorithm, using
the subkeys described in steps (1) and (2).
4. Replace P1 and P2 with the output of step (3).
5. Encrypt the output of step (3) using the Blowfish algorithm
with the modified subkeys.
6. Replace P3 and P4 with the output of step (5).
7. Continue the process, replacing all entries of the P array,
and then all four Sboxes in order, with the output of the
continuouslychanging Blowfish algorithm.
In total, 521 iterations are required to generate all required
subkeys. Applications can store the subkeys rather than execute
this derivation process multiple times.
C Code:
C code for Blowfish starts on page xx. This is improved and
corrected code; the code in the April 1994 issue had some bugs
and was less efficient than this code. The code is also available
electronically; see "Availability," page xx.
CRYTPANALYSIS OF BLOWFISH
When I first presented Blowfish last year, Dr. Dobbs Journal
sponsored a cryptanalysis contest. There were five submissions in
total, and I am pleased to present the most interesting results
here.
John Kelsey developed an attack that could break 3round
Blowfish, but was unable to extend it. This attack exploits the F
function and the fact that addition mod 232 and XOR do not
commute. Vikramjit Singh Chhabra looked at ways of efficiently
implementing a bruteforce keysearch machine.
Serge Vaudenay examined a simplified variant of Blowfish, with
the Sboxes known and not keydependent. For this variant, a
differential attack can recover the Parray with 28r+1 chosen
plaintexts (r is the number of rounds). This attack is impossible
for 8round Blowfish and higher, since more plaintext is required
than can possibly be generated with a 64bit block cipher.
For certain weak keys that generate weak Sboxes (the odds of
getting them randomly are 1 in 214), the same attack requires
only 24r+1 chosen plaintexts to recover the Parray (again,
assuming the Sboxes are known). With unknown Sboxes, this
attack can detect whether a weak key is being used, but cannot
determine what it is (neither the Sboxes, the Parray, nor the
key itself). This attack only works against reducedround
variants; it is completely ineffective against 16round Blowfish.
Even so, the discovery of weak keys in Blowfish is significant. A
weak key is one for which two entries for a given Sbox 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 Sbox entries after you
generate a Blowfish key. I don't think it's necessary, though.
CONCLUSION
No one has come close to developing an attack that breaks
Blowfish. Even so, more cryptanalysis is required before
pronouncing the algorithm secure. I invite others to continue
analyzing the algorithm.
Home page

Counterpane

Applied Cryptography

EMail Security

Crypto Links
Bruce Schneier Bio

Blowfish

Twofish

Yarrow

Publications

Contact Counterpane