# Can one efficiently iterate valid bcrypt hash output values?

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.

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).