Combining Password Hash Plus Limited Preimage Data To Improve Password Hash Security

[Devmond]

Hi All,

I am posting this question here with the hope that web security pros can chime in.

The question was prompted by my effort to deal with weak password hashing in the Jetty application container's default web app security options.

• Password hashes protect against plain passwords, meaning access to a credential database doesn't automatically mean the ability to use those credentials to access corresponding accounts.

• In doing so however, we are then faced with the issue of pre-computed hashes, whose preimage string could be used to access user accounts even when a user's actual password differs, because of hash collision. There are rainbow tables with such pre-computed hashes.

• The mitigations are now a number of hashing schemes intended to make it expensive for an attacker to compute these hashes thus dissuade someone from trying.

In addition to existing mitigations, has there been any consideration given to the idea of pairing hashes with limited password data to counteract hash exploits?

What if the option is added to include a limited set of randomly extracted characters from the source password (preimage) along with the position of said characters, then store that information along with the hash. In other words, in addition to what we do now: MD5:PASSWORD_HASH (jetty example), the developer would optionally append one or more sequences of: PasswordCharacterPasswordCharacterPosition.

Below is an example of what the resulting password hash entry could look like. The hash length is fixed so we know the t at the end is the first source password(preimage) data character, the integer after is the position of that character within the source password, the : is a delimiter for the limited password data sequence.

MD5:3bcc3177cb5efa4d7341d42af8f06418t2:%7

When a user attempts to authenticate, you validate the hash per usual then additionally validate that those randomly saved password characters are indeed present in the password at the corresponding positions. This would largely nuke the utility of rainbow tables since exploiting hashes is now coupled with the need to in essence know something about the actual source password that was used to create it.

Of course the password data does reveal some bit of information about the password for anyone who has access to the database, but with a strong enough password this should be a non-issue I think (correct me on this). I imagine there is some scheme that can indicate by how much a password is weaken if you reveal characters and their corresponding position?

Now rubbing my Darwin beard as I wait for the take down :)

[tanishapritha]

Hey @Devmond,

I’m interested in working on this issue. I suggest using hash chaining to improve password security. Here’s how it would work:

First, hash the password with SHA256.
Then, take that hash and apply SHA512 to it.
The final result is what we store as the password hash.
This makes it harder for attackers because they would need to break both hashes, not just one.

If this approach works, I’m ready to get started. Let me know if I can work on this issue with this approach. Also, if I should think of alternate approaches.

Thanks!

[Devmond]

@tanishapritha

My point in the main post was to simply propose a potential light-weight (ex using md5) option to deal with password hashing, there are already good solutions. Think of my proposal as just another potential approach in the canon.

I don't believe simply stringing hashes together addresses the weakness associated with rainbow tables. Basically you can just derive additional tables by recomputing the hashes in an existing table, ie if I already have a table for sha256 and I know a target entity is applying sha512 to sha256 hashes, then I'll just do the same for my existing table to get a new table that can then be cross compared against the targets db extract.

The core issue is that computing conventional hashes is relatively cheap (computationally) and one can exploit the fact that hash function output does collide (2+ inputs outputting the same hash). Making hash computations prohibitively expensive is the approach current effective password hashing solutions rely on.

My suggested scheme requires a password submitter demonstrates awareness of the original password in order to authenticate, fetching a known password from a rainbow table that happens to have a hash that matches(via collision) the original password's hash would not be enough, you'll need to know the original password too and you prove that by providing a password that can be matched to the stored partial-password-data.

In any case, if you want to work on security in Jetty contact the team: jetty/jetty.project#11489