Padding password before SHA-512 hashing to avoid info leak via timing

Question

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.

Answer 1

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?