What is The Sibyl?

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

What's next?

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