[Cryptography] Password rules and salt

[Jerry Leichter]

> 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.

                                                        -- Jerry