18

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?

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

2 Answers2

18

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.

The Rig password hash adopted this term:

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

This article even shorts it to CIU.

  • 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:

List of password hashes and whether they have CIU

SEJPM
  • 45,265
  • 7
  • 94
  • 199
Sjoerd
  • 596
  • 3
  • 14
  • 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 05 '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 05 '17 at 23:36
  • 3
    [Argon2 doesn't natively support CIU](https://github.com/P-H-C/phc-winner-argon2/issues/214). An Argon2 implementation would have to jump through the same hoops as PBKDF2 and bcrypt to provide such functionality. Using the [Konscious .Net lib](https://github.com/kmaragon/Konscious.Security.Cryptography), 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 03 '18 at 20:54
1

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) ?

entrop-x
  • 372
  • 2
  • 7
  • 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 05 '17 at 13:45
  • 1
    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 05 '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 05 '17 at 16:47
  • 2
    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 05 '17 at 19:08
  • 1
    @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 05 '17 at 19:27
  • @tylo: of course it is not the same result, but the overall cost factor will be the desired cost factor. You're perfectly right that h(x,20) is different from g(x) = h(h(x,10),10), but both of them will have a cost factor of about 20. I had understood that the database already existed. Then there's no way to find h(x,20) without x but only h(x,10). But you can find another way to have a cost of 20, by building g(x). – entrop-x Dec 05 '17 at 19:30
  • Small nitpick: As far as I'm aware, "Cost of 10" usually doesn't mean "10 rounds" but $2^{10}$ rounds (at least for bcrypt). So doing it twice would only be (approximately) equivalent to hashing with a cost of 11. – Disenchanted Lurker Dec 06 '17 at 07:32