Can one efficiently iterate valid bcrypt hash output values?

Question

bcrypt is an intentionally slow hash algorithm. In my last protocol idea, I wanted to use it to expand a password and then only transfer the bcrypt-hashed password.

An efficient attack on this would be an ability to iterate all bcrypt hashes (or only these from passwords in a dictionary, maybe $2^{12}$ ones) without actually bcrypting the passwords.

The output of bcrypt consists of the security parameter (an integer), the used salt (128 bits), and the actual hash (192 bits), which is the result of 64 iterated Blowfish ECB encryptions of the ASCII string "OrpheanBeholderScryDoubt", where the key and s-boxes were expensively created by the (costly) EksBlowfishSetup instead of the normal BlowfishSetup.

Assume we have a quite high security parameter, like 12 (meaning $2^{12}$ iterations in the setup phase).

To make it easier, assume that either the salt is fixed, or we want to enumerate all valid actual hashes for all salts (without paying attention to which salt is used for which hash).

Is there any method of enumerating all the hashes without actually running the bcrypt algorithm, or enumerating the whole 192-bit output space?

What I could see is simply enumerating all possible blowfish states (e.g. subkeys + S-boxes) before doing the 64-times encryption with each such state. But if I understand right, this state consists of a $576$ bit P-array (the subkeys), and $4·265·32=32768$ bits of S-boxes. This is a much larger space than the hash output space ($192$ bits), thus we then simply could assume that every possible hash occurs at least for one such state, and simply enumerate the whole $192$ bit space. Not really a win.

Answer 1

bcrypt uses Blowfish, which is a block cipher (albeit with a much enlarged key schedule). As such, Blowfish implements a permutation of the space of 64-bit blocks; and there should be no way to distinguish Blowfish (using a random key) from a permutation extracted at random, with uniform probability, from the set of permutations over 64-bit blocks (there are $2^{64}!$ such permutations).

The best cryptanalysis result so far, about precisely distinguishing Blowfish from a random permutation, is due to Vaudenay: some Blowfish keys can be detected (and thus making the block cipher distinguished from a random permutation) if the number of rounds is reduced to 14 (from 16 for the "normal" Blowfish). There is no attack on the full Blowfish, and even if there was, it would only be about the weak keys (about one key in $2^{15}$ is weak).

Therefore we cannot guess anything about the Blowfish instance, that would not apply to a randomly chosen permutation. This still allows a small remark: since this is ECB encryption, i.e. encryption of three distinct 64-bit blocks, we know that the hash result must consist of three distinct 64-bit blocks, concatenated together. This implies that the space of possible hash values has size $2^{64}(2^{64}-1)(2^{64}-2)$, which is $2^{192}-3\cdot2^{128}+2\cdot2^{64}$, i.e. very slightly lower than $2^{192}$ (but not by a significant amount).

The trickier part of your question is about bypassing the key schedule. The point of bcrypt is to make processing of a single password as slow as possible for the attacker, but not intolerably slow for the honest systems. The use of Blowfish is a good idea here: the key schedule of Blowfish is optimized for systems which have a few Kbytes of fast RAM, and that's a PC. Implementing Blowfish on, say, a FPGA or ASIC, would be a painful experience; and the RAM requirement is likely to impair performance on GPU as well. This still requires that the key schedule itself is not amenable to hidden optimization, that the attacker may use. To my knowledge, there is no known result on the security of the "expanded key schedule" used in bcrypt.

Note that this algorithm is of the kind which uses self-modifying lookup tables, like MD2 and RC4, which are notoriously difficult to analyze: we do not benefit from the usual tools such as differential or linear cryptanalysis. MD2 and RC4 turned out to have weaknesses, but it took an awful lot of time, and nothing currently suggests that Blowfish could have such weaknesses. We still lack a proper mathematical framework to discuss the security of such constructions. So the absence of published results just means that nobody found an actual break; it does not mean that there are known reasons why such a break may or may not exist. My feeling is that the extended key schedule used in bcrypt is robust for what it is used for (i.e. an unavoidable mass of computations for each password guess).

So my answer to your question ("Is there any method...") is: no.