5
$\begingroup$

As explained in my previous question, I want to develop a scheme which would be able to increase the password hash strength without the user password.

According to Thomas Pornin it should be safe to chain BCrypt hashes to generate a new, more expensive hash. I disregarded the handling for the salt in the previous question so he warned to be careful about that.

To reiterate, I basically want to do the following:

bcrypt_hash_0 = bcrypt(pw, salt_0, work_factor_0);
bcrypt_hash_1 = bcrypt(bcrypt_hash_0, salt_1, work_factor_1);
...
bcrypt_hash_n = bcrypt(bcrypt_hash_n-1, salt_n, work_factor_n);

Possible Handling for the Salt

Let's assume I have a BCrypt function, where I can manually choose the salt. salt_0 is the salt for the initial hash, salt_1 the used salt for the chained hash which produces bcrypt_hash_1 and so on.

Option 0: Reuse the Same Salt

The most simple approach is just to reuse the same salt. This makes it quite easy to handle but it is unclear if this approach introduces severe security issues (is there a research on that?)

Option 1: Create a New Salt

The naive fix to Option 0 would be to create a new random 16 byte salt for each iteration. Unfortunately, this increases the hash output message since in addition to salt_0, the new salt_1 must be appended (etc.). This is probably fine for a single chain, but using it to chain multiple hashes, the message will get quite impractical. From the security side, it should be safe, as it uses an unrelated new salt (?).

Option 2: Derive a New Salt from the Old One (CTR)

Assume the scheme allows for chaining up to 255 hashes. We already introduced HKDF to the scheme and could use the following simple derivation:

salt_n = hkdf_expand(salt_n-1, n, 16)

where n is a counter; the n-th Bcrypt chained hash; by using n as the info parameter we create a new salt for each iteration.

By having n be up to 255, do we "use up" some entropy? Would it be sound to say we lose 1 byte of the 16-byte source salt (aka salt_0)?

Option 2.1: Derive a New Salt from the Old One (CTR+Hash)

As an enhancement of the previous scheme, which would allow deriving all future salts from the source salt, we could incorporate the previous chained hash:

salt_n = hkdf_expand(salt_n-1, n | bcrypt_hash_n-1, 16)

I'm not sure this has some actual security benefits because a salt can be public. It would make it as expensive as calculating the hash to get the salt of the specific round basically.

Question

Which of these schemes would be safe to use? The goal is to keep the output Bcrypt hash as small as possible, without compromising the security of BCrypt (in reasonable ways)

$\endgroup$
  • 1
    $\begingroup$ just increment the salt? $salt_i = salt_{i-1}+1$, where $1 < i \leq n$ $\endgroup$ – kelalaka Dec 26 '18 at 16:46
  • $\begingroup$ @kelalaka is that better than deriving a salt with hkdf_expand using the n as info param? $\endgroup$ – patrickf Dec 26 '18 at 16:47
  • 1
    $\begingroup$ This is just another idea. I cannot compare it's security, however, to be on the safe side you can choose $\operatorname{HKDF\_expand}$. Less storage, and increased the work factor in total. $\endgroup$ – kelalaka Dec 26 '18 at 16:50
2
+50
$\begingroup$

I am not aware of any research for this problem and it is difficult to declare anything as safe without a good reason. Probably that's why everyone holds back with answers.

Suppose, however, the main attack against these BCrypt hashes is a dictionary attack, probably with custom hardware, I can't see a weakness in any of the solutions. Reusing the salt for different passwords weakens a scheme. That is not the case here. For other attacks (cache-timing...) this shouldn't matter.

But you sail in unknown waters.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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