2
$\begingroup$

I am currently developing a protocol which would be able to "upgrade" the strength of a bcrypt password hashes without the knowledge of the user-password so a system may upgrade it without user interaction.

Bcrypt requires the password as input to calculate the hash, if you already have a hash, there is no way to "calculate some more rounds" to increase the work-factor (see here).

Example

So the idea is to just chain the bcrypt hash with a stronger work-factor und using the old bcrypt hash as input like:

bcryptHashOld = bcrypt(pw, 4);
bcryptStronger = bcrypt(bcryptHashOld, 10);

Which would be the theoretical strength of 2^4 = 16 and additionally 2^10= 1024 => 1040 iterations.

Is there any issue with this protocol, ie. hashing the hash WITHOUT the user password? Does the work-factor increase as I have shown in the example above?

Theoretical Problem Statement

As SEJPM added in the comment a better problem statement would be: "whether chaining two PRFs yields another PRF and whether this chain can be evaluated using less work than two successive PRF calls. In formulas: Whether $F_{k1}(F′_{k2}(m))$ is a PRF that requires evaluations of $F$ and $F′$ to be evaluated"

(Note: I'm not asking how to increase the work factor, but if this approach is cryptographically sound)

$\endgroup$
4
  • 1
    $\begingroup$ From a theoretical point of view this question is equivalent to asking whether chaining two PRFs yields another PRF and whether this chain can be evaluated using less work than two successive PRF calls. In formulas: Whether $F_{k_1}(F'_{k_2}(m))$ is a PRF that requires evaluations of $F$ and $F'$ to be evaluated. $\endgroup$
    – SEJPM
    Dec 18, 2018 at 17:03
  • $\begingroup$ In terms composition of hashing, we have already had two question and answers; 1 2 $\endgroup$
    – kelalaka
    Dec 18, 2018 at 17:15
  • $\begingroup$ Well, the answer is simple, but not Cryptography. In the upgrade stage, when user login first time, they send you their password, so check with old, then migrate to new style while the system has the password. $\endgroup$
    – kelalaka
    Dec 18, 2018 at 17:34
  • $\begingroup$ @kelalaka Thanks for the input, but I am not really interested in the collision resistance but as SEJPM stated, "whether this chain can be evaluated using less work than two successive PRF"; I am also aware of lazy upgrading the hash, but that is not the approach Im investigating. $\endgroup$
    – Patrick
    Dec 18, 2018 at 18:39

1 Answer 1

3
$\begingroup$

First there are a few technical hurdles to deal with. Nominally, bcrypt takes three inputs: the password itself, a work factor, and a salt. To hash or to verify a password, you need the salt. Usual bcrypt implementations generate the salt randomly when first processing a password, and encode the salt along with actual function output into an aggregate string. If you use the whole string from the first bcrypt as input to the second bcrypt, then the final output will not contain the first salt, and you will never be able to recompute that hash for password verification.

Also, bcrypt works over "passwords" that it uses as sequences of up to 72 bytes. However, since passwords are normally text, some (most) implementations will accept a character string. In the C language, a character string stops at the first character of value zero. If the first bcrypt output, in binary, happens to contain a byte of value zero at the start, then in fine you will get the bcrypt hash of an empty string, and the hashed password will match one in 256 input passwords, which is bad. This is the kind of mistake that destroys your security but has a high chance of not being detected in unit tests.

You could avoid the "byte zero" effect by encoding the bcrypt output into a character string, e.g. with Base64 or hexadecimal. This enlarges the output, and can bring you dangerously close to the input size limitations for the second bcrypt. Compounding the effect, some bcrypt implementations have lower limits (56, 55 and even 51 bytes maximum size have been spotted in the wild) and may silently truncate the input.

All of that being said, yes, you could expand a bcrypt instance by cascading a second one, assuming that you take care to manage salts externally (it's unclear whether using the same salt for both bcrypt would be safe, so you might have to manage a longer aggregate salt).

However, it's better to start with a password hashing function that already includes work factor increases as a design feature. In the password hashing competition, at least Makwa had that feature (Makwa is not "the" winner of PHC, but it got a "special recognition" and, like many other candidates, was not broken).

$\endgroup$
1
  • $\begingroup$ Thanks for your answer. I have the logistics of bcrypt handled with my custom implementation. My POC is currently github.com/patrickfav/bkdf. Regarding the salt, interesting thought: do you have any further pointers about issues when reusing it? Would it make sense to run the salt through a PRF with a counter to generate a new salt for each chained iteration derived from the base salt? $\endgroup$
    – Patrick
    Dec 19, 2018 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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