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