[Cryptography] Password rules and salt

Arnold Reinhold agr at me.com
Sun May 21 07:31:55 EDT 2017

On Friday, 19 May 2017 15:26 Jerry Leichter wrote:

>> Recent comments by Jerry Leichter and Ray Dillinger about the length of the salt used tohash passwords brings to mind a suggestion made years ago by a colleague, perhaps in jest.  We were talking about the insanity and inanity of password rules and the difficulty of generating good passwords in the presence of arbitrary and site-specific rules for what is a valid password.
>> He suggested that instead, any string is valid as a password, as long as it has never been used before as a password by anyone.   Aside from the cost of implementing and using a database to enforce this rule, it seems to me to be sort of pleasing notion.  It would be best to keep the DB secret, of course,  just to prevent it, and especially recent entries to it, from becoming fodder for dictionary attacks.
> Many years ago, David Wittenberg and I developed and patented (for DEC; the patent wasn't renewed after 17 years and has lapsed) a solution to this problem:  Keep track of used passwords in a Bloom filter, *using cryptographically secure hash functions* to prove the filter.  This has the following properties:  If a password has been used, it will definitely be caught by the filter; if the password hasn't been used, there is a small probability it will be caught anyway; even someone who sees the individual updates to the filter can't determine what's been added to it.

Bloom filters are a really cool way to enforce a global no-reuse password policy, but such a policy is neither necessary nor sufficient for password security. It’s not necessary because a random password with enough entropy is unlikely to be reused often and if adequate salt is used, the likelihood of detecting any repetition from stored hashes is very low. And such a policy is insufficient because it won't detect closely related passwords. In current systems that insist on passwords changes and make sure that the new password doesn’t match ones previously used, users learn how to make small changes to the older password and these changes often follow predictable patterns. Password cracking programs can mimic these patterns. A policy blocking reuse on a global basis will no doubt be evaded in the same way, so cracking programs that look for variations on common passwords will still succeed too often.

Then there is the problem of getting the password information to the Bloom filter. A cryptographic hash of the password is not protective, since knowledge of the hash allows rapid guessing. Worse, the hash used for the Bloom filter cannot include salt, since salt would defeat the function of the filter (the same password hashed with different salts will set different bits in the filter). Unsalted hashes are exceptionally dangerous as they are subject to precomputed database attacks, such as Rainbow tables. One could try to use an encrypted channel to send the hashes to the filter, but that is subject to all sorts of problems, The system maintaining the Bloom filter is yet another potential point of failure, one with access to password hashes from many systems. Even assuming the hashes are sent to the filter unaccompanied by any account-identifying information, knowledge of when an account was created or its password was changed would greatly narrow down the possible hashes and underlying passwords. 

One thing that might be of use would be a Bloom filter with entries for all the passwords generated by known cracking programs. That would not have any issues with forming hashes of actual user passwords and the filter could be updated with new common passwords and their variations periodically. There might be versions of the filter for different amounts of cracking program running time. Organizations could download a filter and use it to test user-created passwords locally. Bolting a Bloom filter to several open source password crackers and letting them run seems easy enough. This might be a good student project. 

The real problem with password based authentication is the difficulty of securely storing information needed to validate passwords. Forcing users to jump through more password hoops is not the best way to solve the safe storage issue, but that’s another discussion.

Arnold Reinhold

More information about the cryptography mailing list