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.