3
$\begingroup$

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:

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.

|improve this question
$\endgroup$
  • $\begingroup$ The aforementioned OpenCL bcrypt implementation is the one from JohnTheRipper: wiki arcicle — I just ran out of karma to post this link. $\endgroup$ – Anton Samsonov Apr 8 '13 at 18:03
  • 2
    $\begingroup$ There are some reasons that ECB is bad, but key recovery from known plaintext is not one of them - it is as hard there as with other modes of operation. $\endgroup$ – Paŭlo Ebermann Apr 8 '13 at 20:16
  • $\begingroup$ Where did you encounter this? What application uses this scheme? $\endgroup$ – D.W. Sep 4 '13 at 5:01
  • $\begingroup$ Actually, @PaŭloEbermann, ECB mode can be much worse than other modes for key-recover attacks (because it makes it easier to do time-space tradeoffs, if you have a full block of known plaintext). However that doesn't seem to apply here. $\endgroup$ – D.W. Sep 4 '13 at 5:04
  • $\begingroup$ Anton, The updated IHO data protection standard S-63 v.1.1 is describing use of padding algo "DES in CBC mode" which potentially will get in the way. I will very much be interested to hear if you made any progress in your "go" at IHOs standard. $\endgroup$ – user8817 Oct 10 '13 at 9:55
3
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ For a given fileset, the first 64-bit block of plaintext is a constant value; it may differ between filesets, but is still limited to a small number of possible values. I heard about “rainbow tables” in context of hash reversal, but have no idea about how it may be applied to this case with Blowfish. $\endgroup$ – Anton Samsonov Sep 6 '13 at 13:14
  • $\begingroup$ When you say “trial decryption”, do you mean a single block processing with an initialized state, or a brute-force trial which require its own initialization? If the latter one, then it seems no better than brute-force approach, as each document is encrypted with its own key. (Perhaps, I'm wrong here, as I didn't get you idea.) $\endgroup$ – Anton Samsonov Sep 6 '13 at 13:16
  • $\begingroup$ @AntonSamsonov, each step is one trial decryption of one block of data (e.g., the key setup + the decryption operation of Blowfish). The way that "rainbow tables" work is by inverting some one-way function $f(x)$. If $c$ is a Blowfish encryption of a known plaintext $p$, we can define $f(k) = E_k(p)$ and then use rainbow tables to find the $k$ such that $f(k)=c$. $\endgroup$ – D.W. Sep 6 '13 at 17:19
  • $\begingroup$ @d-w, do you mean what we need to compute all $2^{40}$ possible ciphertexts for a given plaintext, and then just perform a reverse lookup on that “table” to recover the key of any document? Well, it may be an improvement, provided that we could will be able to build the reverse dictionary. But how does that $2^{27}$ fit in then? $\endgroup$ – Anton Samsonov Sep 6 '13 at 17:33
  • 1
    $\begingroup$ @AntonSamsonov, I've edited my answer to explain in greater detail. For more detail, please read about the Hellman time-space tradeoff and rainbow tables to make sure you understand them before diving into this any further. $\endgroup$ – D.W. Sep 6 '13 at 19:44
1
$\begingroup$

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.

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ What protection scheme are you referring to? (Is there some reason to keep it secret?) $\endgroup$ – D.W. Sep 4 '13 at 5:03
  • 2
    $\begingroup$ It's not a secret, just was not relevant. I was talking about the protection used for marine nautical charts, adopted by International Hydrographic Agency (publication S-63) more than 10 years ago from a proprietary system already in use by late 1990-s — thus the Blowfish and small key size. I don't know about Anonymous Coward's topic, but in my case the full keyspace is assumed. Of course, 40 bits are too few nowadays, but, as I said, there is actually little to no benefit from decrypting the data, as commercial systems expect encrypted input. $\endgroup$ – Anton Samsonov Sep 6 '13 at 13:26
  • 2
    $\begingroup$ Brute-forcing a 40 bit key in 60 seconds on a CPU sounds unrealistically fast, especially since Blowfish has a rather slow key-setup. I would have expected several hours at minimum. $\endgroup$ – CodesInChaos Sep 8 '13 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.