Introduction

Blowfish is a block cipher designed by Bruce Schneier, intended for replacing DES. It requires no license and has no practical cryptanalysis for the full 16-round implementation. It is a good algorithm to study as it shares many features common in various block cipher algorithms:

• Key permutation
• S-boxes
• Feistel network
• Combination of algebraic groups

Key Permutation and S-Boxes

S-Boxes provide the non-linear transform required.

For Blowfish the key and s-boxes initialization is done by first filling the memory with hexadecimal value of Pi.

Feistel Network

Many well-known block cipher use Feistel network to provide diffusion and confusion, two important properties to provide security.

Diffusion works by removing or decreasing any advantage gained by knowing statics about plaintext and ciphertext. Specifically, a small change in the plaintext should cause dramatic change in the ciphertext output so that cryptanalysis isn't possible by feeding known plaintext. Typically this is achieved by using a cryptographically secure round function and executing it over multiple rounds, and this is the case for Blowfish, which consists of 16 rounds.

Confusion works by protecting the key, such that it isn't possible to recover the encryption key from ciphertext. In Blowfish this is achieved using several key-dependent S-boxes and permutations over different algebraic groups.

Block cipher employing Feistel network have the same sequence of instructions for encryption and decryption, with the only difference being the order of subkeys being used. Usually for each round a block is divided into two halves, where the first half is XOR'd with second half that has been processed by the round function and the corresponding subkey.

Blowfish uses 64-bit blocks (PT), an array of 18 32-bit subkeys (P) and 4 32-bit 256-entry S-boxes (S0, S1, S2, and S3). So on a 32-bit architecture machine we can describe the Feistel network as follows:

uint64_t R(uint64_t PT, uint32_t *P) {
  uint32_t i = 0;
  uint32_t xL = (PT & 0xffffffff00000000) >> 32;
  uint32_t xR = PT & 0x00000000ffffffff;

  for (i = 0; i < 16; ++i) {
    xL = xL ^ P[i];
    xR = func(xL) ^ xR;
    swap(&xL, &xR);
  }

  swap(&xL, &xR); // undo the last swap
  xR = xR ^ P[16];
  xL = xL ^ P[17];

  return ((xL << 32) | xR);
}

inline void swap (uint32_t *a, uint32_t *b) {
  uint32_t t = *a;

  *a = *b;
  *b = t;
}

inline uint32_t func(uint32_t xL, 
  uint32_t *S0, uint32_t *S1, uint32_t *S2, uint32_t *S3) {
  uint8_t a = (xL & 0xff000000) >> 24;
  uint8_t b = (xL & 0x00ff0000) >> 16;
  uint8_t c = (xL & 0x0000ff00) >> 8;
  uint8_t d = xL & 0x000000ff;

  return ((S0[a] + S1[b]) ^ S2[c]) + S3[d];
}

Combination of Algebraic Groups

References

• Description of a New Variable-Length key, 64-Bit Block Cipher (Blowfish) by Bruce Schneier
• Test vectors for your implementation