Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Security

The Blowfish Encryption Algorithm


APR94: The Blowfish Encryption Algorithm

The Blowfish Encryption Algorithm

Bruce Schneier

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 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 [pi].
  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 1: Blowfish is a Feistel network consisting of 16 rounds.

Figure 2: Blowfish function F.

DDJ's Blowfish Cryptanalysis Contest

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;
   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


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.