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 Blowfish64 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.
bcrypt
function has 4 parameters. What's the definition of your 3-parameter bcrypt? $\endgroup$bcrypt(cost, salt, key, input)
. The design is sound when the password is fed inkey
, but that contradicts the comment "using an all 0 key". All zero input would make sense, but some other things would, e.g; input <- cost. I wish I knew where to look for the accepted practice. $\endgroup$