The Blowfish cipher

Blowfish is a block cipher Bruce Schneier designed in 1993 as a free, fast replacement for DES. It encrypts 64-bit blocks in 16 Feistel rounds with a key anywhere from 32 to 448 bits, and Schneier put it in the public domain. For a decade it was the cipher to grab when a developer wanted something good and unpatented. It lives on today in a very different job inside bcrypt, one of the standard ways to store passwords. The 64-bit block is why you shouldn't pick it for anything new.

How it works

Blowfish is a Feistel network like DES. Split the 64-bit block into two 32-bit halves, run 16 rounds, and in each round mix a function of one half and a round key into the other. Two features set it apart.

• A simple, fast round function. The 32-bit half is cut into four bytes. Each byte is looked up in its own S-box of 256 entries, and the four results are combined with two additions and one XOR. That's nearly all the work in a round, which made Blowfish very quick in 1990s software.
• Key-dependent S-boxes. The S-boxes and the 18 round keys (the "P-array") aren't fixed tables. They start as the hexadecimal digits of π and then get overwritten by the key schedule, which encrypts a stream of zeros with Blowfish itself over and over and writes the output into the tables. In all, the cipher runs 521 times and chews through about 4 KB of data before the first real block can be encrypted.

That slow key setup annoyed programs that change keys often, and it turned out to be a gift for password hashing. The slower it is to try a key, the slower a guessing attack goes, and Blowfish makes you pay 4 KB of encryption for every new key.

Where the 521 comes from

The key schedule fills the 18-word P-array and the four S-boxes of 256 words each, 1,042 words in all. It fills them two words at a time, encrypting a 64-bit block and writing the two halves of the result into the next two slots. The P-array takes 18 ÷ 2 = 9 encryptions and the S-boxes take 4 × 256 ÷ 2 = 512, so 9 + 512 = 521 encryptions, or 521 × 8 = 4,168 bytes of data, the "about 4 KB". The S-boxes occupy 4 × 256 × 4 = 4,096 bytes and the P-array 72, which is the cipher's memory footprint of a little over 4 KB. A cipher with a key setup that slow is poor at encrypting many short messages under many keys, and good at making guessing expensive.

Eksblowfish and bcrypt

In 1999 Niels Provos and David Mazières turned that expense into a feature. Their Eksblowfish ("expensive key schedule Blowfish") repeats the key schedule a number of times set by a cost parameter, so the work doubles every time the cost goes up by one. Built into the password hash bcrypt, it has made guessing passwords slow for twenty years. A cost of 12 means 2¹² key setups for each guess. It's the same idea as PBKDF2, which cipher.ink uses with 600,000 iterations, only built from a block cipher instead of a hash.

Why it's retired

• The 64-bit block. As with Triple DES, a 64-bit block means repeated blocks after about 2³² blocks of data, and the birthday attacks called Sweet32 (2016) apply. GnuPG advises against using Blowfish for files larger than 4 GB.
• Weak keys. Serge Vaudenay showed in 1996 that for a class of weak keys, 14 rounds can be told apart from random. Nobody has published a practical attack on the full 16 rounds with an ordinary key, but the weakness is there.
• Reduced-round attacks. A second-order differential attack (Rijmen, 1997) breaks four rounds.
• Memory. It needs just over 4 KB of RAM. That's fine on a desktop and too much for the smallest embedded chips.

Schneier's own advice is to use Twofish, his AES finalist, instead (Twofish). Alexander Pukall's Blowfish2 (2005) is a variant with a 128-bit block. The default today is AES.

Common questions