bcrypt - collision-resistance against chosen salt and work factor?

Question

Would it be difficult to find (cost, salt, input, password0, password1) such that

bcrypt(cost, salt, password0, input) = bcrypt(workfactor, salt, password1, input)

and

password0 != password1

where cost is not too small?

(If no, then the combination of bcrypt with PAKE described in this answer would be insecure.)

Answer 1

The answer to the original question would have been: Yes, it would be impossibly difficult to exhibit workfactor, salt, password0, password1 such that bcrypt(workfactor, salt, password0) = bcrypt(workfactor, salt, password1); but even if that was feasible, it would not matter much, because in normal use at least one of the password is unknown to an adversary matter only in certain protocols where it could allow ruling out two passwords in one try.

As to the question as now worded: No, it would not be too difficult to exhibit workfactor, salt, password0, password1, input such that bcrypt(workfactor, salt, password0, input) = bcrypt(workfactor, salt, password1, input); but that's only because input is left malleable, rather than set to "OrpheanBeholderScryDoubt"! In any reasonable use of bcrypt, input is built as three distinct 64-bit constants (or at least values not malleable to the degree in the question).

---

The original reference on bcrypt gives it as:

bcrypt(cost, salt, pwd)
    state :=­ EksBlowshSetup(cost, salt, key)
    ctext := "OrpheanBeholderScryDoubt"
    repeat (64)
        ctext := EncryptECB (state, ctext)
    return Concatenate(cost, salt, ctext)

with text around suggesting that the pwd input maps to key (how exactly is unspecified), and that the 24-characters "OrpheanBeholderScryDoubt" maps to three 64-bit blocks constituting ctext. Predictably, implementations have varied on the mapping from pwd to key, including in ways introducing a serious weakness. Perhaps the initial value of ctext has varied also. Further, how Concatenate formats the output has varied (including in an effort to encode the variations used in the rest).

If Blowfish is a good cipher, 64 iterations of Blowfish is also a good cipher (better by some metrics, maybe slightly worse by the cycle structure), and thus for any three distinct constant 64-bit plaintexts, the ciphertexts per that Blowfish⁶⁴ should be three values indistinguishable from random, except for being distinct. By design of Blowfish and bcrypt, finding a collision with random salt and key should be expected to require over $2^{96}$ evaluations of EksBlowshSetup, thus $2^{97+\mathtt{cost}}$ ExpandKey operations, which is beyond feasible.

---

But for whatever reason, bcrypt's wikipedia entry as I read it now states that bcrypt computes a hash from a given input as follows:

bcrypt(cost, salt, key, input)
    state := EksBlowfishSetup(cost, salt, key)
    ctext := input
    repeat (64)
        ctext := EncryptECB(state, ctext) //encrypt using standard Blowfish in ECB mode
    return Concatenate(cost, salt, ctext)

Notice the fourth parameter input and the uncertainty on if the password is fed to key (the original intend) or input. In the following I assume this 4-arguments definition, with password in the question mapped to key.

The crux is that the current statement of the question (not the originally intended and likely usual blowfish setup) leaves the choice of input, including as a 64-bit value repeated three times, which makes collision search feasible:

• set cost to the lowest possible value;
• set salt to some short admissible constant;
• for j from $0$ to $2^{20}-1$, compute and store state[j] := EksBlowfishSetup(cost, salt, key) where key corresponds to a password obtained as j translated to an acceptable password as 5 hexadecimal digits and an appropriate suffix; that will require a reasonable 4GiB of RAM, and bearable CPU time.
• repeat for i increasing, starting from $0$:
  • for j from 0 to $2^{20}-1$:
    • set ctext to i converted to a 64-bit bitstring;
    • repeat 64 times:
      • set ctext := EncryptECB(state[j], ctext); the encryption is over a single block;
    • if that ctext was previously obtained for the same i and earlier j, then derive password0 from that earlier j, derive password1 from the current j, and set input as the 192-bit bitstring formed by three times i converted to a 64-bit bitstring; we have found a collision!
    • else, remember ctext and the corresponding j in some easily searched table (which will require only a small fraction of the RAM used previously);
  • having had no luck with this i, empty the table, proceed to next i.

For each i tested, we are looking for collision among $2^{20}$ random-like 64-bit values, and that has odds about $2^{20+20-1-64}=2^{-25}$. Thus we are expected to succeed after about $2^{25}$ loops on i, that is $2^{45}$ loops on i and j, that is $2^{51}$ encryptions, which is considerable but feasible. Twice more memory makes a machine nearly twice as efficient, and to some degree it is possible to substitute hard disk or SSD for the part of the RAM used to store state[j], with some minor complications. Also, this can be distributed trivially, each machine using as much memory as it has available.

---

Update: I have checked two implementations of bcrypt.

jBCrypt is per the original bcrypt definition, but has two issues: because it is written in Java (which is not fully compiled at least in the most common practice, and lacks built-in idioms for unsigned 8-bit variables), speed is likely significantly worst than something native, which in the particular context means proportionally less secure; also, in that version at least, cost of 31 is accepted but degenerates to less security than the minimum cost of 4, because 1<<31 is negative in Java. Oh wait, I'm not the first to step on that, here's a corrected version.

In PHP, the accepted practice is delegating bcrypt password hashing to a native implementation of crypt (see this Bcrypt.php or that highly-praised answer), which is a sound way to solve the speed issue. I was told crypt goes to crypt.c then crypt_blowfish.c. I now have located "OrpheanBeholderScryDoubt", and the code referencing it is per the original bcrypt definition. Speed is likely quite decent. I like the idea of checking the code at runtime with a quick Known Answer Test, which also stands a good chance of overwriting sensitive values; and some modest but likely useful attempts to reduce other sources of leakage.