Known-plaintext attack on Blowfish in ECB mode

Question

The protection scheme I faced recently seems so weak nowadays that a simple exhaustive key search would be enough to recover the user key in an acceptable amount of time (it's OK, since almost no practical benefit could be gained from knowing the plaintext), but I'm just curious whether the key recovery could be accomplished even faster and more intelligently.

• The scheme consists of using Blowfish encryption with 40-bit key, with ECB mode of operation — i. e. no initialization vector, no feedback. This is countered by having a separate key for each document (or related set of documents), and by compression of documents.
• On the other side, those documents are always ZIP archives with a single file packed in them, generally with the most simple capabilities. As a result, the first 32 bits (one Blowfish word) always contain the ZIP's local file header signature; the following 32 bits are usually constant for a given data producer, i. e. can be compared against a fixed value or can be verified partially. Further data is varying, but can be verified for plausibility as well.

The question is: does the knowledge an exact value of single block of plaintext give any advantage to key recovery — beyond the ability to easily check for a match in brute-force attack? Every discussion on that topic that I found claimed that Blowfish can't be reversed, but provided no proof for this; moreover, those topics were concerned about other modes than ECB and substantially longer keys. Then I started searching for discussions on recovery of subkeys instead of the original user-supplied key, and found this recent paper:

• “All Subkeys Recovery Attack on Block Ciphers: Extending Meet-in-the-Middle Approach”, Takanori Isobe and Kyoji Shibutani, Sony Corporation
• presentation of the same paper for Symposium On Applied Computing, 2012

The full paper seemed too general for me, with little explanation on used symbols. The only thing I understood is that for key length of 40 bits there should be more than one 64-bit block of known plaintext, which is not the case for me. The other bad thing is that I didn't notice anything about the round-wise subkeys (the P-array) there — they were talking about substitution boxes only. The last slides of presentation put me in even much more confusion, since they claim that subkey recovery attack is effective with keys longer than 292 bits.

PS. Regarding the speed of brute-force attack against Blowfish. My initial implementation in .Net performed about 2800 checks per second, reimplementation in pure C with heavy inlining raised the bar up to 27'500 in a single thread and about 200'000 in 10 threads on a Core i7-2600 with hyper-threading — that's just 64 days for a complete range scan. And, although Blowfish is believed to be GPU-unfriendly, an OpenCL bcrypt implementation shows even more performance, the more so that bcrypt is a heavier form of Blowfish.

Answer 1

If there was a full 64-bit block of known plaintext, there would be a very fast attack using precomputation. You can build a precomputed table of all $2^{40}$ ciphertexts. Once you've got the precomputed table, recovering a key (given a ciphertext) would require just a single lookup in the table, so recovering a key would be extremely fast. Storing that table would require something like 5 Terabytes of storage, which isn't too bad: it might cost you \$300 or so to buy 5 TB of storage. The precomputation takes $2^{40}$ trial encryptions (key schedule + a single block encryption using Blowfish), e.g., 64 days for your implementation. Once you've built the precomputed table, cracking each file/ciphertext could be done almost instantaneously.

If 5 TB of storage feels like too much, a variant of this would be to use the Hellman time-space tradeoff (or, if you prefer the "hyped" version, "rainbow tables"). That attack also requires a precomputation that takes about the same amount of time: $2^{40}$ trial encryptions. However, its storage costs are much lower: storage for a table containing about $2^{27}$ entries (instead of $2^{40}$ entries), which corresponds to about 700 MB of storage. The trade-off is that cracking each file/ciphertext takes a bit longer: about $2^{27}$ Blowfish trial encryptions, or about 700 seconds. So, once you've built the precomputed table, cracking each file/ciphertext can be done very quickly: not instantaneously, but much faster than exploring the entire space of all $2^{40}$ keys.

These precomputation attacks are not of any benefit if you only have a single file to crack, but if you expect that you'll want to crack multiple files/ciphertexts, then the precomputation attacks can be beneficial: they allow you to amortize the cost of the precomputation across many different files/ciphertexts.

However, you say that you only have 32 bits of known plaintext, not a full 64-bit block of known plaintext, so these precomputation attacks are presumably not applicable to your particular setting.

---

FYI, the Isobe-Shibutani paper is not going to be helpful to you. Their basic attack on reduced-round Blowfish takes at least $2^{160}$ steps of computation and thus is completely impractical -- not to mention that it only attacks a reduced-round variant of Blowfish with 8 rounds, whereas the real Blowfish uses 16 rounds. Their attack on the full 16-round Blowfish takes $2^{288}$ steps of computation, so is ridiculously impractical. In short: that paper is completely irrelevant to any real-world attempt to mount key-recovery attacks on Blowfish.

Answer 2

Regarding your brute-force Blowfish attack: I believe I may be familiar with the protection scheme you describe. It turns out that it may be even more broken that you'd expect from the description, in that a) the actual keyspace may be rather more limited than 40 bits and b) the author may not have been terribly aware of the consequences of using the blowfish packing algorithm on short plaintexts.

The upshot is that key recovery using the Bouncy Castle managed .NET implementation from C# takes <60s on my venerable laptop.