I've noticed that SHA-512 password hashing leaks some information about the password length. There's a weak correlation between password length and time to hash. It's roughly linear, but in steps of 64 or so, and also dependent on salt length. I suppose a little extra length results in one extra block of hash input for each round.

To avoid leaking even this small amount of information, we could pad the password to a constant length before hashing it. The padding could be a reproducible secure hash of the password, salt, and/or number of rounds.

Since hashing the long padded password would take longer per round, we could use fewer rounds. Thus, overall, the hashing operation would not take longer (except for a little time to generate the padding).

(Of course, with the padding being a function of the password, one could dispense with the password and simply hash the padding instead. That seems risky, though; entropy might somehow be lost in the process.)

Does anyone see a problem with this padding idea? Do any attacks come to mind?

Edit: this is for a working system, but the target environment makes it difficult to use anything but Python and the standard library; there's no compiler, and adding precompiled libraries is problematic. Thus, crypt(3) is available, but better algorithms such as bcrypt, scrypt, and PBKDF2 are not — at least, not easily.

The idea with the padding is to pad with a constant string, hash that with a small number of rounds, and use the output as the padding for the full number of rounds.

  • $\begingroup$ If you want to hash the password to get your padding to get the hash to be constant-time, isn't that a bit of a hen-and-egg problem? Regardless, you may want to look into this question and answer for secure password hashing, if this isn't just a thought experiment. Still, an answer about the security of such a scheme would be interesting from a purely scientific point of view, if it will not be used in practise. $\endgroup$ – malexmave Mar 19 '16 at 15:32
  • $\begingroup$ Good points that I should have anticipated and dealt with in the original question. See edit. $\endgroup$ – Tom Zych Mar 19 '16 at 15:45
  • $\begingroup$ What are the benefits of using the hash as the padding, as opposed to using a fixed string of, say, zeroes, to get to the correct length? So you would go $h(salt\ ||\ password\ ||\ 0^n)$, where $n$ is the number of missing bits. Reduces complexity and, as far as I can see, achieves the same goal. $\endgroup$ – malexmave Mar 19 '16 at 15:47
  • $\begingroup$ You're right. I wasn't thinking clearly about the attack model. Using a hash instead of constant padding would not slow down a dictionary attack at all. $\endgroup$ – Tom Zych Mar 19 '16 at 15:54
  • $\begingroup$ With regards to the edit, I start to get the feeling that you are trying to chase a mosquito out of the room while ignoring the tiger sitting in the middle of it. $\endgroup$ – Maarten Bodewes Mar 20 '16 at 12:15

In general password hashing (algorithms such as bcrypt, PBKDF2) should contain a specific work factor. It might well be that repeating the hash multiple times will already obfuscate the hash time enough to make the padding redundant.

If you consider password hashing a requirement then reducing the number of rounds on the underlying compression function (e.g. the hash) doesn't make much sense as you would reduce the work load for both the regular user and an attacker.

For now assume that your passwords contain lots and lots of entropy so you may skip the issue of the work factor. In that case your scheme might be of some use.

You should however take really good care to avoid memory allocation issues.

Say an attacker could influence memory allocation. In that case asking for e.g. a block of memory of $c - l(p)$ bytes could be problematic (with $c$ being the total length of the input to the hash function and $l(p)$ being the password). In that case an attacker could guess a length $n$, and make sure only $n$ bytes are available within the memory page / cache block / whatever. Now the padding of $p$ would either allocate within the current page or it wouldn't. Page allocation / cache misses take a lot of time, so they can be relatively easily be detected. So the attacker has a method of checking if the password has a certain length.

You could work around this by copying the password into a preallocated block of memory. You then copy the required amount of pre-generated padding bytes after it.

(Of course, with the padding being a function of the password, one could dispense with the password and simply hash the padding instead. That seems risky, though; entropy might somehow be lost in the process.)

Heh, no, the size of the password is rather less important than the content of the password. Unless you assume the padding to contain the entire password, but in that case you forgot to define your protocol well.

and adding precompiled libraries is problematic.

So use the source code. I don't get it, is there an invisible man throwing up these invisible walls somewhere?

  • $\begingroup$ Funny enough the sample source code for Argon2 in the README starts with uint8_t *pwd = (uint8_t *)strdup(PWD);. Which could trigger a page fault. Then again, maybe the size of passwords should not be thought of as a secret in the first place, it's pretty easy to guess (with most people just keeping to the minimum size anyway). $\endgroup$ – Maarten Bodewes Mar 20 '16 at 12:13
  • $\begingroup$ @TomZych For some reason you seem to be able to program your own padding and even your own cryptographic hash, but you don't seem to be able to build any third party protocols or to copy open source code into your application. Many password hash algorithsms are pretty simple to code, once you have access to an implementation the underlying primitive (e.g. SHA-1 or SHA-2 for PBKDF2). $\endgroup$ – Maarten Bodewes Mar 20 '16 at 12:31
  • $\begingroup$ @TomZych You wouldn't slow down your hash much, while having huge memory requirements if you want to scale it up. Furthermore, you would just be accessing the data linearly. In a good memory hard password hash you specify the amount of memory and it will try and access all of it, all the time. So you'd be creating a less than ideal memory hard hash. $\endgroup$ – Maarten Bodewes Mar 20 '16 at 12:34

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.