Secure storage of the
shadow file and, in general, of any database of secret authentication tokens (think of passwords of users of a Web-based service) is one of
the main security concerns of a Systems Administrator.
With the advent of rainbow tables and cheap fast hardware, this problem has become especially relevant: today, dictionary attacks take negligible time (and the fact is that users will end up using passwords as simple as possible).
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 asymmetric 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.
The Sibyl is a device which answers if two OAEP RSA-encoded cyphertexts correspond to the same plane text, optimized (security-wise) for authentication algorithms in situations in which the database of authentication tokens —the password database— is deemed unsafe (which, as a matter of fact, means always). It may be thought of as an oracle, hence its name.
It works as one of the classical Greek Oracles: they issue an answer which makes sense only depending on the question and which reveals no real information (just a bit of it). Technically, it is used to check whether an OAEP RSA-encrypted text (generated from, say, a password entered by a user at login) and another OAEP RSA-cyphertext (which is stored in the machine the user is trying to log in) correspond to the same plaintext. The login machine must ask the Sibyl, who just replies "yes" or "no" (the Sibyl, obviously, holds the private RSA key to be able to do this), revealing no information on the plaintext.
It comprises two layers: a hardware item and a piece of software which implements a client-server architecture between the authenticating computer (the one the password database is stored on) and the hardware item. The diagram below shows a possible implementation.
The Sibyl is connected to the Authentication Server (a.s.), which is —in the simplest case— the computer the user is trying to log in to. There are two private/public key pairs: the encryption pair and the signing pair (this is essential for the security of the protocol). The private keys are stored only on the Sibyl, whereas the a.s. has access to both public keys. On the a.s., the authentication tokens are stored (in our proof-of-concept) as base64 encoded RSA-encrypted
crypt(3) passwords preceded by the salt used in the
crypt(3) process. That is, each entry in the
shadow database (if this is the case, it needs not be a shadow file or a Unix Login service) would look like:
user:$1$SOvM5$Rada783R/783478dadfa... (till 2048 binary bits, say):...
Which is the username followed by the salt (
$1$SOvM5$) and the output of
Whenever a user tries to log in on the a.s., the following steps take place (first of all, the Authentication Server connects to the Sibyl):
p1, and (if this exists) the
passwordentered by the logging user.
n:saltpasswordusing the Sibyl's public key to get
m;p1;p2to the Sibyl.
u2matches the (regexp) pattern
/^n:(.*)$/[that is: the nonce
nfollowed by a colon and any number of characters] and sets
v1=$1(using Perl's regexp notation) [the set of characters after the colon].
v1then it returns the message
m:1signed with the signing key. Otherwise, it returns the message
m:0signed with the same key.
m:1, then grant authentication. In any other case deny authentication.
A more technical sequence diagram would look like this.
All the process depends on the nature of the authentication database. There should be different implementations for Linux (using the standard
crypt command), for OS X (which stores both the NETLAN and a SHA-1 encoding of the password), for OpenBSD (which uses blowfish), etc. Of course, it can be implemented in a SQL database storing passwords for logging purposes, or in any service storing authentication tokens which need to be kept as secret as possible.
A physical (possibly a virtual one serves, as well, if security is not compromised) computer, which must be different from the authentication server. Our proof-of-concept is a Bifferboard, suitable for small-sized networks (no more than a few logins every hour). Login takes about five seconds using this device (the process requires three RSA "private encryption" operations).
This is what we actually call the Sibyl.
There is a server side, running on the Sibyl, and a client-side, running on the authentication server.
The sever side is always the same: a daemon listening for connections from the a.s. and performing the dialogue described above.
In the proof-of-concept, the part running on the a.s. is a PAM module. But this might well be a dedicated server, a set of daemons in layers, different processes for different logon services...