*Bruce is the author of Applied Cryptography: Protocols, Algorithms, and Source Code in C (John Wiley, 1994). This article is based on a paper he presented at the Cambridge Algorithms Conference. Bruce can be contacted at schneier@ chinet.com.*

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: x_{L} and x_{R}. Then, for i=1 to 16:

x_{L}=x_{L} XOR P_{i}

x_{R}=F(x_{L}) XOR x_{R}

Swap x_{L} and x_{R}

Function F looks like this: Divide x_{L} into four eight-bit quarters: a, b, c, and d. F(x_{L})=((S_{1,a}+S_{2,b} mod 2^{32})XOR S_{3,c})+
S_{4,d} mod 2^{32}; 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.

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

- 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 .
- 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 P
_{18}). Cycle through the key bits repeatedly until the entire P-array has been XORed. - Encrypt the all-zero string with the Blowfish algorithm, using the subkeys described in steps #1 and #2.
- Replace P
_{1}and P_{2}with the output of step #3. - Encrypt the all-zero string using the Blowfish algorithm with the modified subkeys.
- Replace P
_{3}and P_{4}with the output of step #4. - 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.

*DDJ's *Blowfish Cryptanalysis Contest

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

- Success of the attack. How much more efficient is the attack than brute force?
- Type of attack. Is it ciphertext only, known plaintext, or chosen plaintext?
- Type of algorithm. Is the attack against full Blowfish or a simplified version of the algorithm?

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

/* 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);

/* 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; short numread; 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) { numread = fread(&data, 4, 1, SubkeyFile); printf("%d : %d : %.4s\n", numread, i, &data); if (numread != 1) { return DATAERROR; } else { P[i] = data; } } for (i = 0; i < 4; ++i) { for (j = 0; j < 256; ++j) { numread = fread(&data, 4, 1, SubkeyFile); printf("[%d, %d] : %.4s\n", i, j, &data); if (numread != 1) { 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; }

Copyright © 1994, *Dr. Dobb's Journal*