The Sibyl

The problem: keeping shadow files secure

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.

Introduction: logging through an oracle

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.

Description

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

 base64(RSA_encrypt(crypt(password, salt))).

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

On the Authentication Server:

The a.s. receives a nonce (unique to this authentication process) from the Sibyl: n.
From the password database, the a.s. gets the real authentication token (which is RSA-encrypted with the Sibyl's public key): p1, and (if this exists) the salt used to crypt(3) this token.
The a.s. grabs the password entered by the logging user.
The a.s. encrypts n:saltpassword using the Sibyl's public key to get p2.
The a.s. generates another nonce m.
The a.s. sends a message of the form m;p1;p2 to the Sibyl.

On the Sibyl:

The Sibyl decrypts p1 and p2 to get u1 and u2.
It checks that u2 matches the (regexp) pattern /^n:(.*)$/ [that is: the nonce n followed by a colon and any number of characters] and sets v1=$1 (using Perl's regexp notation) [the set of characters after the colon].
If u1=v1 then it returns the message m:1 signed with the signing key. Otherwise, it returns the message m:0 signed with the same key.

signed

On the a.s.:

It receives the signed message from the Sibyl.
If the received message has been properly signed and the message is 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.

Implementation

The Sibyl requires the following two layers:

The hardware layer

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.

The software layer

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