Most password hashes have a cost parameter that indicates how long the algorithm should take. Is there an algorithm where you can increase that cost for a particular hash, without access to the plaintext password?

So I have existing hashes in the database with cost=10, and I want to upgrade these to cost=20, without access to the plaintext password.

This isn't possible for PBKDF2 and bcrypt, because these use the password in each iteration. Is there any algorithm that supports this? Is there a specific name for this property?

• For most purposes, you can just use the hashed password from the old algorithm as the input for the new algorithm. – Mark Dec 5 '17 at 21:29

This is called Client-Independent Update, according to the Catena paper.

It is desirable to be able to compute a new password hash (with some higher security parameter) from the old one (with the old and weaker security parameter), without having to involve user interaction, i.e., without having to know the password. We call this feature a client-independent update of the password hash.

Client-independent update: Our design supports client independent update, i.e., server can increase the security parameter without knowing the password.

• Battcrypt and Parallel have CIU or are easily modified to have it.
• POMELO mentions that you could just run the algorithm twice to get CIU.
• Yescrypt seems to have CIU.

An overview:

• Interesting to see Argon2i with a tick in that column. I wonder if any language has implemented the CIU feature (it would be an interesting addition to PHP's password_* functions, which now include Argon2i support). – IMSoP Dec 5 '17 at 20:50
• The suggested way to do it with Argon2 is simply to rehash using the previous hash as the password. – Frank Denis Dec 5 '17 at 23:36
• Argon2 doesn't natively support CIU. An Argon2 implementation would have to jump through the same hoops as PBKDF2 and bcrypt to provide such functionality. Using the Konscious .Net lib, I confirmed it. I hashed a string twice with Argon2d. Same inputs except #1 used 4 iterations and #2 used 10. Next I hashed #1's output using 6 iterations. The 4 + 6 hash did not equal the 10 hash. (CIU also failed when attempting independent mem-size & parallelism upgrades.) – Granger Jan 3 '18 at 20:54

Naively, I would say: can you not just concatenate both operations ? If you add a second hash operation of cost 10 to the existing hash, won't that give you a total cost of 20 ? I mean: if CP is the clear text password, and you've stored the H1P = h1(CP) hashes of them with cost 10, can you not calculate H2P = h2(H1P) = h2(h1(CP)) with also cost 10, to obtain a total cost of 20 ? Eventually even using the same function (so h1 = h2) ?

• In general, this does not work, because password hashes are not just the round function. For example if there is a final step like $h(last\_output, some\_constant)$ would break that. Also, if some of the input actually depends on the number of total rounds, that also means you can't reuse the old hash at all. – tylo Dec 5 '17 at 13:45
• I wasn't talking about just the round function, but of the total procedure of producing a hash from a password in the first place. If you have a password, there's a function that turns this into the stored hash, right ? It includes rounds and what not, but at the end of the day, you get out the thing that you store. Apply this entire function once more (eventually adding the same salt), as if the previous result were a new password. Pretty basic in fact. – entrop-x Dec 5 '17 at 15:43
• That is not the same thing though, if there is an explicit cost factor as input to the function. Let's call it $h(x,y)$ for input $x$ and cost factor $y$. Then we got that $h(x,20)$ is not equal to $h(h(x,10),10)$. And that was asked for in the question, which asked for a way to get from $h(x,10)$ to $h(x,20)$. Of course there should also be salts, but we can consdier that as part of the input $x$. – tylo Dec 5 '17 at 16:47
• In general, that wouldn't give the same result. But the interesting question is using $h(h(x, 10), 10)$ as sort of an alternate format with cost approximately equal to $h(x, 20)$. You can arrange to update it to the proper format when you get access to the password, i.e. when the user logs in. – ilkkachu Dec 5 '17 at 19:08
• @ikkachu: yes, that was my idea: you're stuck with a database of hashed passwords, and somehow you'd like to find a way to make the algorithm harder, what can you do ? I had read the question that way. It is of course better to design a system that has a modifiable hardness, but if you already have a given setup with too low hardness, what do you do, now that you only have hashes of passwords ? – entrop-x Dec 5 '17 at 19:27