Live Journal about blowfish |

When I first presented Blowfish last year, Dr. Dobb’s Journal sponsored a cryptanalysis contest. There were five submissions in total, and I am pleased to present the most interesting results here.

John Kelsey developed an attack that could break 3-round Blowfish, but was unable to extend it. This attack exploits the F function and the fact that addition mod 232 and XOR do not commute. Vikramjit Singh Chhabra looked at ways of efficiently implementing a brute-force keysearch machine.

Serge Vaudenay examined a simplified variant of Blowfish, with the S-boxes known and not key-dependent. For this variant, a differential attack can recover the P-array with 28r+1 chosen plaintexts (r is the number of rounds). This attack is impossible for 8-round Blowfish and higher, since more plaintext is required than can possibly be generated with a 64-bit block cipher.

For certain weak keys that generate weak S-boxes (the odds of getting them randomly are 1 in 2¹⁴), the same attack requires only 24r+1 chosen plaintexts to recover the P-array (again, assuming the S-boxes are known). With unknown S-boxes, this attack can detect whether a weak key is being used, but cannot determine what it is (neither the S-boxes, the P-array, nor the key itself). This attack only works against reduced-round variants; it is completely ineffective against 16-round Blowfish.

Even so, the discovery of weak keys in Blowfish is significant. A weak key is one for which two entries for a given S-box are identical. There is no way to check for weak keys before doing the key expansion. If you are worried, you have to do the key expansion and check for identical S-box entries after you generate a Blowfish key. I don’t think it’s necessary, though.

Conclusion

No one has come close to developing an attack that breaks Blowfish. Even so, more cryptanalysis is required before pronouncing the algorithm secure. I invite others to continue analyzing the algorithm.

DES is the workhorse of cryptography algorithms, and it’s long past time to replace the 19-year-old standard. The recent design of a $1M machine that could recover a DES key in 3.5 hours only confirmed what everybody knew: DES’s key size is far too small for today.

The world only partly trusted DES because it survived the scrutiny of the NSA. Experts trusted DES because it was a published standard, and because it survived 20 years of intensive cryptanalysis by cryptographers around the world. Cryptography is like that: confidence in an algorithm grows as group after group tries to break it and fails.

Candidates for a replacement are emerging, but none has taken widespread hold. Triple-DES is the conservative approach; IDEA (used in PGP) is the most promising new algorithm. And there is a bevy of unpatented also-rans: RC4 (once a trade secret of RSA Data Security, Inc. but now publicly available on the Internet), SAFER, and my own Blowfish.

I first presented Blowfish at the Cambridge Algorithms Workshop (“Description of a New Variable-Length Key, 64-bit Block Cipher (Blowfish),” Fast Software Encryption, R. Anderson, ed., Lecture Notes in Computer Science #809, Springer-Verlag, 1994) and in Dr. Dobb’s Journal (April 1994). From the start Blowfish was intended to be a completely free–unpatented, unlicensed, and uncopyrighted–alternative to DES. Since then it has been analyzed by some people and has started to see use in some systems, both public and private. This article presents new Blowfish code, as well as updates on the algorithm’s security.