I want to start with Blowfish because it is one of the algorithms that made strong encryption accessible to ordinary developers. Blowfish is a symmetric-key block cipher that operates on 64-bit blocks with a variable key length ranging from 32 to 448 bits. I find it appealing because it was designed to be fast, compact, and free for anyone to use, which made it hugely popular in the years before AES became the standard.
History and Background
I learned that Bruce Schneier designed Blowfish in 1993 as a fast, free alternative to existing encryption algorithms like DES, which was aging and limited by its short 56-bit key. Schneier wanted an algorithm that was unpatented and available for anyone to use without licensing restrictions, and he succeeded: Blowfish has never been patented, and its specification was placed in the public domain. Over time, Schneier and his colleagues went on to design Twofish as a successor intended for the AES competition, but Blowfish itself remained widely used for years afterward due to its simplicity and speed.
Problem Statement
The problem Blowfish set out to solve was providing strong, fast encryption without the licensing fees and export restrictions that encumbered other algorithms of the era. I see it as addressing three needs at once: security strong enough to resist the cryptanalysis techniques known in the early 1990s, speed suitable for software running on the general-purpose processors of the time, and freedom from patents so that any developer could implement it without legal concern.
Core Concepts
A few terms I rely on when discussing Blowfish:
- Feistel network: the same general structure I described for Twofish, where data is split into halves and one half is repeatedly transformed and mixed into the other across many rounds.
- P-array: an array of 18 subkeys, each 32 bits, derived from the encryption key and used throughout the rounds.
- S-boxes: four substitution boxes, each containing 256 32-bit entries, used inside the round function to provide non-linearity.
- Key schedule: the process of expanding a relatively short key into the full P-array and S-boxes, which in Blowfish’s case is unusually expensive by design.
How It Works
I break Blowfish’s operation into two phases: key setup and encryption.
- In key setup, I initialize the P-array and the four S-boxes with fixed values derived from the hexadecimal digits of pi.
- I then XOR the P-array entries with the key, repeating the key as many times as needed to cover all 18 entries.
- I encrypt an all-zero 64-bit block using the partially-initialized cipher and use the result to replace the first two P-array entries, then repeat this process, each time encrypting the output of the previous step to replace the next P-array or S-box entries, until all of the P-array and S-boxes have been set.
- Once key setup is complete, I encrypt data using a 16-round Feistel network: I split the 64-bit block into two 32-bit halves, and in each round, I XOR the left half with a P-array entry, pass it through the F function (built from the four S-boxes), XOR the result into the right half, then swap the halves.
- After 16 rounds, I undo the final swap and apply two more XOR operations with the last two P-array entries.
Working Principle
The heart of each round is the F function. I take the 32-bit left half after XORing with the round’s P-array entry, and split it into four 8-bit bytes. Each byte indexes into one of the four S-boxes. I add the outputs of the first two S-box lookups modulo $2^{32}$, XOR that with the third S-box lookup, and then add the fourth S-box lookup modulo $2^{32}$. This combination of additions and XORs across four different S-boxes gives Blowfish strong diffusion and non-linearity despite its relatively simple structure. The expensive key schedule, which requires encrypting data many times just to set up the S-boxes and P-array, is intentional: it makes brute-force key search and certain classes of attacks considerably more expensive.
Mathematical Foundation
The F function can be expressed as, given a 32-bit input split into bytes $a, b, c, d$:
$$F(x) = \left( (S_1[a] + S_2[b]) \bmod 2^{32} \right) \oplus S_3[c] , \boxplus , S_4[d] \pmod{2^{32}}$$
where $S_1, S_2, S_3, S_4$ are the four S-boxes, $\oplus$ denotes XOR, and $+$ / $\boxplus$ denote addition modulo $2^{32}$. Each round then computes:
$$L_{i+1} = R_i \oplus F(L_i \oplus P_i)$$ $$R_{i+1} = L_i \oplus P_i$$
for $i = 1$ to $16$, followed by a final unswap and whitening with $P_{17}$ and $P_{18}$.
Diagrams
flowchart TD
A[64-bit Plaintext] --> B[Split into Left 32-bit and Right 32-bit]
B --> C[Round 1: XOR with P1, F function, XOR into Right, Swap]
C --> D[Round 2 ... Round 16]
D --> E[Undo Final Swap]
E --> F[XOR with P17 and P18]
F --> G[64-bit Ciphertext]Pseudocode
function BLOWFISH_KEY_SETUP(key):
initialize P[0..17] with digits of pi
initialize S1, S2, S3, S4 with digits of pi
for i in 0 to 17:
P[i] = P[i] XOR next_32_bits_of(key, cyclic)
left, right = 0, 0
for i in 0 to 17 step 2:
left, right = BLOWFISH_ENCRYPT_BLOCK(left, right, P, S1, S2, S3, S4)
P[i] = left
P[i+1] = right
for box in [S1, S2, S3, S4]:
for i in 0 to 255 step 2:
left, right = BLOWFISH_ENCRYPT_BLOCK(left, right, P, S1, S2, S3, S4)
box[i] = left
box[i+1] = right
return P, S1, S2, S3, S4
function BLOWFISH_ENCRYPT_BLOCK(left, right, P, S1, S2, S3, S4):
for i in 0 to 15:
left = left XOR P[i]
right = right XOR F(left, S1, S2, S3, S4)
swap(left, right)
swap(left, right) // undo last swap
right = right XOR P[16]
left = left XOR P[17]
return left, right
Step-by-Step Example
I find it easiest to picture Blowfish encryption with a concrete but simplified trace. Suppose my 64-bit plaintext splits into L = 0xDEADBEEF and R = 0xCAFEBABE, and I have already completed key setup so my P-array and S-boxes are ready.
- In round 1, I XOR
LwithP[0], feed the result into the F function using the four S-boxes, and XOR the F function’s output intoR. - I swap
LandR. - I repeat this for rounds 2 through 16, each time using the next P-array entry.
- After round 16, I swap
LandRback to undo the last swap. - I XOR
RwithP[16]andLwithP[17]. - I concatenate
LandRto form the 64-bit ciphertext block.
Decryption uses the exact same algorithm but applies the P-array entries in reverse order, from P[17] down to P[0], which recovers the original plaintext because each round’s XOR and F function operations are self-inverting when reversed correctly.
Time Complexity
For a single 64-bit block, Blowfish always performs 16 fixed rounds, so encrypting one block takes $O(1)$ time relative to block size. For a message split into $n$ blocks, total encryption time is $O(n)$. The key setup phase is comparatively expensive: it requires 521 encryptions of a 64-bit block just to initialize the P-array and S-boxes, so I treat key setup as a fixed but noticeable $O(1)$ overhead that matters most when keys change frequently, such as in applications that rekey often.
Space Complexity
Blowfish requires storing the P-array (18 32-bit values) and four S-boxes (256 32-bit values each), totaling about 4 kilobytes of memory for the expanded key schedule. This is $O(1)$ space relative to the size of the data being encrypted, since the same tables are reused for every block regardless of message length. The per-block working memory is also constant, just the two 32-bit halves being processed.
Correctness Analysis
I reason about Blowfish’s correctness the same way I do for any Feistel cipher: each round’s operations (XOR with a subkey, apply the F function, XOR into the other half, swap) are exactly reversible if I know the round’s subkey and F function output, because XOR is self-inverse. Running the rounds with subkeys in reverse order undoes each round precisely, which means decryption with the correct key always recovers the original plaintext exactly, given the same key schedule that was used for encryption. This property is a core reason Feistel networks are popular in cipher design, since it does not require the round function itself to be invertible, only that I can recompute it during decryption.
Advantages
- I find Blowfish’s speed on 32-bit processors excellent, since it relies mainly on additions, XORs, and table lookups.
- It is free of patents and license fees, so I can use it in any application without legal concerns.
- Its variable key length up to 448 bits gives me flexibility to balance security and performance.
- The expensive key schedule adds resistance against certain brute-force and precomputation attacks.
Disadvantages
- Its 64-bit block size is now considered a weakness, since it makes Blowfish vulnerable to birthday-bound attacks (such as the SWEET32 attack) when large volumes of data are encrypted under the same key, which is why I would avoid it for large data transfers today.
- The expensive key setup makes Blowfish less suitable for applications that need to change keys very frequently, such as per-packet keying.
- It has largely been superseded by AES and its own successor, Twofish, in new designs, so I see less active development and fewer hardware accelerators supporting it today.
Applications
I have seen Blowfish used in older versions of software like OpenSSH as a selectable cipher, in the popular bcrypt password hashing scheme (which is actually built on Blowfish’s key schedule rather than pure encryption), in various database encryption tools, and in some VPN and file encryption utilities, particularly from the 1990s and 2000s. Its influence on bcrypt is one of its most lasting legacies, since bcrypt remains a common choice for hashing passwords today.
Implementation in C
#include <stdio.h>
#include <stdint.h>
/* Simplified illustrative Blowfish round structure. A real
implementation needs the full 18-entry P-array and four 256-entry
S-boxes initialized from the digits of pi, which I omit here for
brevity, using placeholder small tables instead. */
#define ROUNDS 16
#define SBOX_SIZE 256
uint32_t P[18];
uint32_t S1[SBOX_SIZE], S2[SBOX_SIZE], S3[SBOX_SIZE], S4[SBOX_SIZE];
uint32_t f_function(uint32_t x) {
uint8_t a = (x >> 24) & 0xFF;
uint8_t b = (x >> 16) & 0xFF;
uint8_t c = (x >> 8) & 0xFF;
uint8_t d = x & 0xFF;
uint32_t result = (S1[a] + S2[b]);
result ^= S3[c];
result += S4[d];
return result;
}
void blowfish_encrypt_block(uint32_t *left, uint32_t *right) {
uint32_t L = *left, R = *right;
for (int i = 0; i < ROUNDS; i++) {
L ^= P[i];
R ^= f_function(L);
uint32_t tmp = L; L = R; R = tmp;
}
/* undo final swap */
uint32_t tmp = L; L = R; R = tmp;
R ^= P[16];
L ^= P[17];
*left = L;
*right = R;
}
void init_placeholder_tables() {
for (int i = 0; i < 18; i++) P[i] = 0x9E3779B9u + i * 0x61C88647u;
for (int i = 0; i < SBOX_SIZE; i++) {
S1[i] = i * 0x01000193u;
S2[i] = i * 0x85EBCA6Bu;
S3[i] = i * 0xC2B2AE35u;
S4[i] = i * 0x27D4EB2Fu;
}
}
int main() {
init_placeholder_tables();
uint32_t left = 0xDEADBEEF;
uint32_t right = 0xCAFEBABE;
printf("Before: %08X %08X\n", left, right);
blowfish_encrypt_block(&left, &right);
printf("After: %08X %08X\n", left, right);
return 0;
}
Sample Input and Output
Starting with the 64-bit plaintext block L = DEADBEEF, R = CAFEBABE, running the illustrative program above through 16 rounds of XOR, F-function substitution, and swapping produces a very different pair of 32-bit words as output, showing how thoroughly Blowfish diffuses input bits even with placeholder tables. In a full implementation with correctly initialized S-boxes derived from the digits of pi and properly mixed with the real key, the ciphertext output would be cryptographically strong, and applying the same algorithm with subkeys in reverse order would recover the original plaintext exactly.
Optimization Techniques
A few techniques I have found useful:
- Performing the expensive key setup once and reusing the resulting P-array and S-boxes for many blocks, rather than repeating key setup per block.
- Using lookup tables efficiently, since the S-box lookups dominate the F function’s cost, and modern CPU caches handle Blowfish’s 4KB table well.
- Processing multiple independent blocks in parallel using multiple threads or SIMD lanes when encrypting large amounts of data in a mode like CTR.
- Avoiding Blowfish for data volumes large enough to approach its 64-bit block size birthday bound, and switching to a cipher with a 128-bit block size, like AES, instead.
Common Mistakes
I often see mistakes where developers use Blowfish’s default Electronic Codebook (ECB) mode without realizing it leaks patterns in the plaintext, since identical plaintext blocks always produce identical ciphertext blocks in that mode. Another common mistake is ignoring the 64-bit block size limitation and using Blowfish to encrypt very large files under a single key, which risks birthday-bound collisions as demonstrated by the SWEET32 attack. I also see confusion between Blowfish encryption and bcrypt, which uses Blowfish’s key schedule for password hashing but is not the same as using Blowfish to encrypt data.
Further Reading
- Schneier, B. “Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish).” https://www.schneier.com/academic/blowfish/
- Schneier on Security, Blowfish page: https://www.schneier.com/academic/blowfish/
- “Applied Cryptography” by Bruce Schneier, published by Wiley.
- SWEET32 attack paper, Bhargavan and Leurent: https://sweet32.info/
