# The Blowfish Encryption Algorithm

### Bruce Schneier

Blowfish is a block-encryption algorithm designed to be fast (it encrypts data on large 32-bit microprocessors at a rate of 26 clock cycles per byte), compact (it can run in less than 5K of memory), simple (the only operations it uses are addition, XOR, and table lookup on 32-bit operands), secure (Blowfish's key length is variable and can be as long as 448 bits), and robust (unlike DES, Blowfish's security is not diminished by simple programming errors).

The Blowfish block-cipher algorithm, which encrypts data one 64-bit block at a time, is divided into key-expansion and a data-encryption parts. Key expansion converts a key of at most 448 bits into several subkey arrays totaling 4168 bytes. Data encryption consists of a simple function iterated 16 times. Each iteration, called a "round," consists of a key-dependent permutation and a key- and data-dependent substitution.

### Subkeys

Blowfish uses a large number of subkeys that must be precomputed before any data encryption or decryption. The P-array consists of 18 32-bit subkeys, P1, P2...P18, and there are four 32-bit S-boxes with 256 entries each: S1,0, S1,1... S1,255; S2,0, S2,1...S2,255; S3,0, S3,1...S3,255; S4,0, S4,1...S4,255.

### Encryption

Blowfish is a Feistel network consisting of 16 rounds; see Figure 1. The input is a 64-bit data element, x. Divide x into two 32-bit halves: xL and xR. Then, for i=1 to 16:

xL=xL XOR Pi
xR=F(xL) XOR xR
Swap xL and xR

After the sixteenth iteration, swap xL and xR 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 eight-bit quarters: a, b, c, and d. F(xL)=((S1,a+S2,b mod 232)XOR S3,c)+ S4,d mod 232; see Figure 2.

Decryption is exactly the same as encryption, except that P1, P2_P18 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. For the purposes of illustration, I've implemented Blowfish in C; Listing One (page 98) is blowfish.h, and Listing Two (page 98) is blowfish.c. A required data file is available electronically; see "Availability," page 3.

### Generating the Subkeys

The subkeys are calculated using the Blowfish algorithm, as follows:

1. Initialize first the P-array and then the four S-boxes, in order, with a fixed random string. This string consists of the hexadecimal digits of .
2. XOR P1 with the first 32 bits of the key, XOR P2 with the second 32 bits of the key, and so on for all bits of the key (up to P18). Cycle through the key bits repeatedly until the entire P-array has been XORed.
3. Encrypt the all-zero 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 all-zero string using the Blowfish algorithm with the modified subkeys.
6. Replace P3 and P4 with the output of step #4.
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 rather than re-executing this derivation process.

### Design Decisions

The underlying philosophy behind Blowfish is that simplicity of design yields an algorithm that is easier both to understand and to implement. Hopefully, the use of a streamlined Feistel network (the same structure used in DES, IDEA, and many other algorithms), a simple S-box substitution, and a simple P-box substitution, will minimize design flaws.

For details about the design decisions affecting the security of Blowfish, see "Requirements for a New Encryption Algorithm" (by B. Schneier and N. Fergusen) and "Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)" (by B. Schneier), both to be included in Fast Software Encryption, to be published by Springer-Verlag later this year as part of their Lecture Notes on Computer Science series. The algorithm is designed to be very fast on 32-bit microprocessors. Operations are all based on a 32-bit word and are one-instruction XORs, ADDs, and MOVs. There are no branches (assuming you unravel the main loop). The subkey arrays and the instructions can fit in the on-chip caches of both the Pentium and the PowerPC. Furthermore, the algorithm is designed to be resistant to poor implementation and programmer errors.

I'm considering several simplifications to the algorithm, including fewer and smaller S-boxes, fewer rounds, and on-the-fly subkey calculation.

### Conclusions

At this early stage, I don't recommend implementing Blowfish in security systems. More analysis is needed. I conjecture that the most efficient way to break Blowfish is through exhaustive search of the keyspace. I encourage all cryptanalytic attacks, modifications, and improvements to the algorithm.

However, remember one of the basic rules of cryptography: The inventor of an algorithm is the worst person to judge its security. I am publishing the details of Blowfish so that others may have a chance to analyze it.

Blowfish is unpatented and will remain so in all countries. The algorithm is hereby placed in the public domain and can be freely used by anyone.

#### Figure 2: Blowfish function F.

The only way to inspire confidence in a cryptographic algorithm is to let people analyze it. It is in this spirit that DDJ is pleased to announce the Blowfish Cryptanalysis Contest, our third reader contest in recent years.

We'd like you to cryptanalyze Bruce Schneier's Blowfish algorithm presented in this issue. Give it your best shot. Break it, beat on it, cryptanalyze it. The best attack received by April 1, 1995 wins the contest.

The contest rules are simple. It's open to any individual or organization. Governments are encouraged to enter. Even the NSA can compete and win the prize (their budget isn't what it used to be; they can probably use the money). But since we will publish the results, classified entries will not be permitted. To officially enter the contest, your entry must be accompanied by a completed and signed entry form. These are available electronically (see "Availability," page 3) or we'll be glad to mail or fax you a hardcopy.

We're not going to publish messages encrypted in Blowfish and some random key, because we think that would be too difficult.

Partial results--those attacks that don't break the algorithm but instead prove that it isn't as strong as we thought it was--are just as useful and can be entered.

Your entry does not have to consist of code. Instead, your entry can be a paper describing the attack. The attack does not have to completely break the Blowfish algorithm, it can simply be more efficient than a brute-force attack. The attack can be against either the complete algorithm or a simplified version of the algorithm (fewer rounds, smaller block size, simpler S-boxes, and the like).

We'll select a winner based on the following criteria:

Bruce Schneier, frequent DDJ contributor, author of Applied Cryptography, and inventor of the Blowfish algorithm will referee the contest.

The contest results will be published in the September 1995 issue of Dr. Dobb's Journal, in which we'll discuss and summarize the winning programs, the weaknesses of the Blowfish algorithm, and any modifications of the algorithm.

We'll be providing a number of awards for the winners. The grand-prize winner will receive a \$750 honorarium. Honorariums of \$250 to the second-place winner and \$100 to the third-place winner will also be awarded.

--editors

#### [LISTING ONE]

```
/* Blowfish.h */

#define MAXKEYBYTES 56              /* 448 bits */

short opensubkeyfile(void);
unsigned long F(unsigned long x);
void Blowfish_encipher(unsigned long *xl, unsigned long *xr);
void Blowfish_decipher(unsigned long *xl, unsigned long *xr);
short InitializeBlowfish(char key[], short keybytes);

```

#### [LISTING TWO]

```

/* Blowfish.c */

#include <dos.h>
#include <graphics.h>
#include <io.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <alloc.h>
#include <ctype.h>
#include <dir.h>
#include <bios.h>
#include <Types.h>

#define  N  16
#define  noErr 0
#define  DATAERROR -1
#define  KEYBYTES 8
#define  subkeyfilename "Blowfish.dat"

static unsigned long P[18];
static unsigned long S[4,256];
static FILE*         SubkeyFile;

short opensubkeyfile(void) /* read only */
{
short error;
error = noErr;
if((SubkeyFile = fopen(subkeyfilename,"rb")) == NULL) {
error = DATAERROR;
}
return error;
}
unsigned long F(unsigned long x)
{
unsigned short a;
unsigned short b;
unsigned short c;
unsigned short d;
unsigned long  y;

d = x & 0x00FF;
x >>= 8;
c = x & 0x00FF;
x >>= 8;
b = x & 0x00FF;
x >>= 8;
a = x & 0x00FF;

y = ((S[0, a] + (S[1, b] % 32)) ^ S[2, c]) + (S[3, d] % 32);
/* Note: There is a good chance that the following line will execute faster */
/* y = ((S[0,a] + (S[1, b] & 0x001F)) ^ S[2, c]) + (S[3,d] & 0x001F); */
return y;
}
void Blowfish_encipher(unsigned long *xl, unsigned long *xr)
{
unsigned long  Xl;
unsigned long  Xr;
unsigned long  temp;
short          i;

Xl = *xl;
Xr = *xr;
for (i = 0; i < N; ++i) {
Xl = Xl ^ P[i];
Xr = F(Xl) ^ Xr;

temp = Xl;
Xl = Xr;
Xr = temp;
}
temp = Xl;
Xl = Xr;
Xr = temp;

Xr = Xr ^ P[N];
Xl = Xl ^ P[N + 1];

*xl = Xl;
*xr = Xr;
}
void Blowfish_decipher(unsigned long *xl, unsigned long *xr)
{
unsigned long  Xl;
unsigned long  Xr;
unsigned long  temp;
short          i;

Xl = *xl;
Xr = *xr;

for (i = N + 1; i > 1; --i) {
Xl = Xl ^ P[i];
Xr = F(Xl) ^ Xr;

/* Exchange Xl and Xr */
temp = Xl;
Xl = Xr;
Xr = temp;
}
/* Exchange Xl and Xr */
temp = Xl;
Xl = Xr;
Xr = temp;

Xr = Xr ^ P[1];
Xl = Xl ^ P[0];

*xl = Xl;
*xr = Xr;
}
short InitializeBlowfish(char key[], short keybytes)
{
short          i;
short          j;
short          k;
short          error;
unsigned long  data;
unsigned long  datal;
unsigned long  datar;
/* First, open the file containing the array initialization data */
error = opensubkeyfile();
if (error == noErr) {
for (i = 0; i < N + 1; ++i) {
printf("%d : %d : %.4s\n", numread, i, &data);
return DATAERROR;
} else {
P[i] = data;
}
}
for (i = 0; i < 4; ++i) {
for (j = 0; j < 256; ++j) {
printf("[%d, %d] : %.4s\n", i, j, &data);
return DATAERROR;
} else {
S[i, j] = data;
}
}
}
fclose(SubkeyFile);
j = 0;
for (i = 0; i < 18; ++i) {
data = 0x00000000;
for (k = 0; k < 4; ++k) {
data = (data << 8) | key[j];
j = j + 1;
if (j > keybytes) {
j = 0;
}
}
P[i] = P[i] ^ data;
}
datal = 0x00000000;
datar = 0x00000000;
for (i = 0; i < 18; i += 2) {
Blowfish_encipher(&datal, &datar);

P[i] = datal;
P[i + 1] = datar;
}
for (j = 0; i < 4; ++j) {
for (i = 0; i < 256; i += 2) {
Blowfish_encipher(&datal, &datar);

S[j, i] = datal;
S[j, i + 1] = datar;
}
}
} else {
printf("Unable to open subkey initialization file : %d\n", error);
}
return error;
}
```