We present a different approach for storing shadow files: using a separate server for checking the correctness of the password introduced by the user, taking advantage of symmetric key encryption.
In summary: instead of keeping the hash (as crypt(3) does, or SHA1) of
the password in the shadow file, store an OAEP RSA-cyphertext of the
password (using a public encryption key) and, each time the user tries
to log in, ask someone (the owner of the private key) if the
OAEP-encryption of the password issued by the logging user matches the
stored cyphertext. That is: use an oracle to ask if the user has
entered the correct password or not. This oracle is the Sibyl.
Because dictionary attacks and rainbow tables cannot be just defeated using complicated hash functions and salts: users always find the weakest possible password for any scheme.
We are concerned about dictionary attacks on the shadow file (or on any database containing hashed authentication tokens). The advent of rainbow tables and fast, cheap computing has weakened the ability of hashes to keep "passwords" safe.
However, the security issue does not lie on the hashing functions, but on the fact that despite any security measures, end users find always a way to use simple passwords (even more, each set of password requirements admits several "simplest" examples, which will be used frequently by different users and will be easily found when using a "dictionary" or a rainbow table).
Our approach uses the random nature of OAEP, which essentially adds more than 80 bits of randomness to the cyphertext, making both dictionary and rainbow tables attacks infeasible (in order to obtain the same cyphertext, the attacker needs to try the same password as the user and use the same random bits when encrypting).
The source code of this project is on github
For an overview of the Sibyl you should watch the presentation we gave at NoConName 2011 (Sorry, it is in Spanish only):
These are the slides used on the presentation:
These are the slides used on the presentation given at NoConName 2013