An analysis of Blowfish cribbed from 'Pengo.'

An explanation of why I believe in the Blowfish algorithm (minted by Bruce Schneier in 1995.)

Blowfish is a Feistel network. I would like to begin with a discussion of a much simpler Feistel network, older and better investigated. Having talked about it, I will note how similarities between Vigenere and Blowfish give me confidence that Blowfish is reliable.

I first learned Vigenere as a lossy version, but later learned a lossless implementation in 'The Code Book,' by Simon Singh. I wrote an implementation of the lossless kind in GFA BASIC on an Atari 520ST, around 1995. I used it in the following manner to conclude that Vigenere is not a 'group.'

I made a message of 6 E's. I used looping to build a file containing 6 character key space of cryptograms of 'eeeeee,' exhaustively - IE; the file comprised a table of all possible encryptions of the 'eeeeee' message with a six character password.

I then used my knowledge (acquired by experimentation,) that double encrypting with Vigenere results in the unicity distance spreading entropy over the product of the prime factors of the key lengths. IE; a two character password and a three character password give a six character repeating pattern if you run all e's through the Turing Machine. However, a 10 char password and a 6 char password would yield a 5 x 2 x 3 = 30 char unicity distance.

I then searched the "cryptogram space" file, for the resulting 6 char string and found that it was mathematically absent. I was intuitively dismayed that a pattern similar to the naked human eye was present, brought to my attention by a portion matching my 1 step cryptogram, and the remainder matching the first chars of the next entry in the 2 step file. I am not completely sure what to make of this.

I'll now denote that Vigenere is cryptanalyzed by lining up the message in rows of unicity distance length, and performing statistical analysis on the resulting 'Rogue's Gallery' of substitution ciphers. To summarize, Vigenere is a set f(x) such that f(x) yields q and f(q) yields k, but there exists no value 'g' such that f(g) yields k.

By comparison, Blowfish is a Feistel network in not 2, but 16 rounds. The most important question I can ask about Blowfish is, If f(x) yields f'(x) and f'(x) yields f2(x) ... f15(x) yields f16(x) (badly noted, but asking for human understanding,) IS THERE a (or some,) Y such that f(y) yields f16(x). If there is not, we can argue that Blowfish is not a group, leaving us to wonder if there is even an analog of statistical analysis that can be employed on some binary rogues gallery to cryptanalyze it?

Under those conditions, things would still be difficult for cryptanalysis because the implementation with which I am familiar does not neglect aggressive compression before encryption, as an efficiency measure. Goodbye statistical characteristics.

To compound the difficulties, experimentation on the resulting block cipher does the following;a string of e's yields an apparent substitution simplicity. Introduce exactly 1 q in the 'stream,' of e's and observe that (specifically in the 56 bit implementation,) the resulting entropy cascades over three characters. I suppose that means three blocks, leaving me mystified as to how it actually decrypts. The relevant conclusion is that comparing letter pairs really doesn't get me anywhere with it either.

I have a cognitive dissonance that results from asking 'what is the unicity distance of (a block cipher) Blowfish.' I blindly trust the current AES as a black box because it is no longer new. The implementation I use has a random number generator written by 'some Polack.' Since NSA tried to sabotage AES, I infer they can't really break it conveniently.

In closing, please note that Blowfish derivative, TwoFish, is now an AES candidate with NIST.