# Is it possible to increase the cost of BCrypt or PBKDF2 when its already calculated and without the original password?

I just wanted to know if you can increase the cost (iterations) of those two algorithms off-line. I want to increase the cost every year of my users passwords.

One solution is to recalculate them when the user logs in, but a user may have not logged in that period, and I don't want to wait till he logs in.

This could be done with password stretching (ex. iterating over a sha-256 hash), but I'm not aware if this is possible with BCrypt and/or PBKDF2. Thank you.

-
Interesting question! –  martinstoeckli Jun 10 '12 at 18:55
A better solution then trying to do this would to simply lock out the user's account after a year. This would allow you to increase the cost of the user's password to the current cost when they reset their password. –  Ramhound Jun 12 '12 at 16:11
Ramhound, most of the time it's the business that decides if users can be blocked after a certain time. Imagine if Facebook decides to do that just to increase the cost of its password hashes. –  skantos Jun 15 '12 at 12:49
Possible Duplicate: security.stackexchange.com/q/32361/665 –  Hendrik Brummermann Apr 8 '13 at 7:06

I had the same requirement, and solved it in this manner:

• Hash the salt and password in the usual manner with PBKDF2 and a work factor that's currently 16 (ie 2^16 iterations). Store the salt, hash, work factor, etc as a row in a database table.
• Asynchronously (ie not affecting the end-user) do this 3 more times, increasing the work factor by 1 each time. So now I have 4 database rows for that user, with work factors of 16, 17, 18, and 19 respectively.
• I always use the row with the lowest work factor to verify the password, but every 2 years I delete the row with the lowest work factor.
-

PBKDF2 and Bcrypt do not support increasing the cost, starting from the output at a given iteration count, without knowledge of the password. There is no intrinsic reason for that; a password hashing process could allow for such offline stretching while still be "good". But these algorithms happen not to allow it.

What can be done is the following: a normal bcrypt or PBKDF2 output includes the salt s, the iteration count i, and the hash output v. In bcrypt implementations, the three values are often encoded into printable characters (with a Base64-like encoding); see for instance this answer. Assuming you have s and v, you can store the following:

• the salt s;
• an iteration count i;
• an extra iteration count j;
• the value h(h(h(...h(h(v))...))) which is the result of hashing v repeatedly, with a secure hash function h, done j times.

For password verification, you have to recompute the bcrypt/PBKDF2 from the given password (using s and i), and then hash the resulting value j times, to see if it matches the stored value.

This is mostly secure, if you use a strong hash function for h, like SHA-256. It can be shown that the repeated hashing reduces the space of possible values, but should reach an inner "cycle" of size roughly sqrt(N) if the hash output values are in a space of size N; moreover, if that cycle is small enough to be explored exhaustively, then a collision on the hash function h can be computed (see this page for a nice diagram). Thus, if h is collision-resistant (like SHA-256), then the scheme above is safe.

The important point is that you can increase j afterwards, in an offline way. However, note that this kind of stretching relies on the computing cost involved in doing many extra hash function computations. Unfortunately, usual hash functions like SHA-256 map really well on what GPU can do; thus, the advantage obtained that way over the attacker might not be as great as initially wished for. In other words, using the stretching described above voids any advantage of bcrypt over PBKDF2 (see this answer for a discussion on this subject). You could apply it as a temporary measure, until the said user comes back, so that the bcrypt step could be done again with a higher iteration count (i).

Moreover, the scheme I describe above is homemade crypto, and that's bad. I can get away with it because I am totally awesome, but this cannot be promoted on a general basis.

-
+1 for `the scheme I describe above is homemade crypto, and that's bad. I can get away with it because I am totally awesome, but this cannot be promoted on a general basis` –  Francisco Presencia Apr 2 '14 at 22:18
If one has a variable-length field to hold password info, I would suggest that an extensible approach would be to have the field hold a function and an expected result (salt could be added as part of the function). One could then increase the complexity of the password function by wrapping the function in another one, and feeding the "result" to that same function and storing that result. –  supercat Aug 22 '14 at 22:21
For example, if one has a function H[str,n] which takes a string, munges it n times, and returns the result, then a password entry might start out saying, in essence, "adding [salt] to the password and hashing it 10,000 times with scheme X should yield [hashXresult]". If it needs to be strengthened, it could be changed to "adding [salt] to the password, hashing it with 10,000 times with scheme X, and then 20,000 times with scheme Y, should yield [result of hashing hashXresult 20,000 times with scheme Y]". –  supercat Aug 22 '14 at 22:25
Obviously if one uses such an approach one needs to be careful to ensure that one never stores any overly-easy challenges in the password field, but other than that I don't see any problem. Do you? –  supercat Aug 22 '14 at 22:26

Imagine that it were possible to lengthen the number of rounds of a key without the original password. If that were the case, it would be possible to build a rainbow table that maps from the output after 1 iteration to the output after 1000 iterations. The table would make it quick to reverse 1000 iterations.

Given that table, a cracker could reverse 1000 iterations down to 1 and then just try to crack the PBKDF with just 1 iterations. That would weaken the algorithm.

-
You can always build a rainbow-table, since the number of iterations is not secret, but you need time to do it. When you added a unique salt for each password, the attacker will have to build a rainbow-table for each password (the cost factor doesn't change anything). Building a full rainbow-table for one password doesn't make sense, because you are faster with brute forcing. –  martinstoeckli Aug 31 '12 at 16:02
Let's say we have a function `bcrypt(pwd, rounds)`. We store passwords as `bcrypt(pwd, 1000)`. You are saying that an attacker can calculate `bcrypt(pwd, 1)` for any `bcrypt(pwd, 1000)`, and then crack them with an iteration count of 1. Do you realize that once the attacker did the conversion for `bcrypt(*, 1000)` to `bcrypt(*, 1)`, he already has the plaintext? The point of adding iterations is that they take time, and the point of a PRF in password hashing functions is that it is not reversible. –  Luc Jan 18 '14 at 18:27
I think Eyal is on to something here. Assume you're attacking several passwords that have no salts but are bcrypt'd with X rounds, X < 1000. You could create or purchase a rainbow table that works in the usual way, but uses a 1000 round bcrypt as the hash function. Now expend a relatively small amount of time to lengthen every hash to 1000 rounds total, and look up the results in the rainbow table in the usual manner. It's slightly contrived but it would be a slight weakness. –  ZoFreX Jul 16 '14 at 21:57

As p____h mentions, the Eksblowfish algorithm uses the key (and salt) in every round, only updating, and eventually returning, the final state.* Thus, without the original key you can't increase the number of rounds.

The PBKDF2 framework defines its inner loop similarly:

``````F(P,S,c,i) = U1 ^ U2 ^ ... ^ Uc
U1 = PRF(P,S || INT_msb(i))
U2 = PRF(P,U1)
...
Uc = PRF(P,Uc-1)
``````

and so faces the same problem.

One possible alternative is if you have an old hash in your database use it as the key for a new stronger hash and then discard it. You'd have to record the old salt and work factor values (these are normally recorded in the final output). When the user logged in you'd take the old salt, and old work value, calculate the intermediate hash and use that as the key for the secondary hash (which would have the secondary salt and work factor stored with it). If the password checked out you could then calculate a new stronger hash directly from the passphrase and mark the user as updated.

N.B. Cryptography can sometimes be counter-intuitive. I have not, nor am I qualified to, analyze the increase in difficulty -- if any -- resulting from such chaining.

After calling InitState to fill a new key schedule with the digits of , EksBlowfishSetup calls ExpandKey with the salt and key. This ensures that all subsequent state depends on both, and that no part of the algorithm can be precomputed without both salt and key. Thereafter, ExpandKey is alternately called with the salt and then key for iterations. For all but the first invocation of ExpandKey, the second argument is a block of 128 0 bits. This more closely resembles the original blowfish key schedule, and also allows EksBlowfishSetup to be implemented more efficiently on CPU architectures with few registers.

-
Thanks Bradley for taking the time to read the paper, it's much more clearer now. –  skantos Jun 15 '12 at 12:43

bcrypt depends on Eksblowfish alghoritm which is defined as:

``````Eksblowfish(cost, salt, key)
state = InitState()
state = ExpandKey(state, salt, key)
repeat (2^cost)
state = ExpandKey(state, 0, key)
state = ExpandKey(state, 0, salt)
return state
``````

This code shows the number of iterations. As bcrypt usage is: `bcrypt(cost, salt, key)`, the `cost` variable is log2 of iterations. So adding one to `cost` doubles the time.

@skantos, That code does not have a `key=` line, so the answer would be no in almost all cases. –  George Bailey Jul 6 '12 at 14:32