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.
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:
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.
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.
Each round uses the the initial password (key), you can't add additional rounds without it. So, for Bcrypt, the answer is no.
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.
I had the same requirement, and solved it in this manner:
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.
