A hobby of mine seems to be authentication protocols. Getting an authentication protocol right is surprisingly hard both in theory and practice. And I like pulling them apart and understanding them.
The Authentication Mechanism Trilemma
As I already wrote in an older blog post about CRAM-MD5, an authentication protocol should fulfill the following non-functional requirements:
- It does not reveal any secret on the communication channel.
- The server stores nothing that would allow an attacker to recover a secret.
- It must be simple to implement.
As said in my CRAM-MD5 post, it seems to be a "choose two" triangle situation (sometimes called a trilemma). Complicated protocols like Kerberos might be good at 1. and 2. but you won't implement it in a day. Asymmetric cryptography also is pretty complicated and requires management of key material by the user.
Plaintext authentication like HTTP BasicAuth or SSH password authentication allows the server to only store strongly hashed secrets (2.) and are simple to implement (3.), but of course the plaintext password goes through the wire (if the underlying encryption channel is protected that may be ok, though).
CRAM-MD5 on the other hand is good at 1. and 3. - It's a challenge-response based mechanism that can be implemented on top of only an existing MD5 implementation in about day - it's not much more then a HMAC on a nonce. But it requires that the server stores the secret that can be used to create the authentication proofs. That stored secret is only an unsalted MD5 hash of the secret - which can easily be reversed nowadays. Using a different hash function won't fix that problem because the specification has no room for salts.
Recently I stumbled upon SCRAM which is a big improvement over CRAM. SCRAM stands for "Salted Challenge Response Authentication Mechanism". It's specified in RFC5802 for SASL and RFC7804 for HTTP. The complexity is low enough that you can reasonably implement it in a few days. All you need is a hash function and a HMAC and PBKDF2 implementation on top of that. HMAC and PBKDF2 are simple enough to implement on your own, if you have to.
Through a few nice crypto tricks SCRAM solves the trilemma (not perfectly, but to some degree).
When the user registers at the server or otherwise sets up a new password, the server derives a client specific
and puts it together with some parameters into a database as
SaltedPassword := Hi(password, salt, ic) ClientKey := HMAC(SaltedPassword, "Client Key") ServerKey := HMAC(SaltedPassword, "Server Key") StoredKey := H(ClientKey) ServerRecord := StoredKey,ServerKey,salt,ic
Let's go through these steps, one by one:
First we calculate
SaltedPassword by passing the password through an iterative password hashing function
The specific function specified here is PBKDF2 with HMAC as the underlying hash function.
It uses the parameters
salt which is a user specific random string and
ic which is the iteration count.
Then we derive the child keys
ServerKey by applying two fixed one-way functions on the parent key
These one-way functions are simple HMACs with the known "secrets" "Client Key" and "Server Key".
Everyone who knows
SaltedPassword can recreate
But you cannot recover the parent key
SaltedPassword from either of the child keys.
This, by the way, is one neat crypto trick to remember.
ServerKey is later used by the server to prove to the client that the server knows about the same password as the client.
ServerRecord is what the server needs to put into its database so that it can later check proofs from clients and issue proofs to clients.
The structure of the key setup is a little key-tree where each branch is a key derivation with a one-way function.
password salt,ic | | +----+----+ | v +----SaltedPassword----+ | | v v ClientKey ServerKey | v StoredKey
Notice how the server only stores one part of the root (
salt,ic) and the leafs (
The next step is to construct a challenge that will be "signed" by both server and client.
To create that challenge the client first sends the server its requested username and a random nonce.
The server in response sends the
salt and iteration count
ic and another random nonce to the client.
This all together is the
AuthMessage := username,client-nonce,salt,ic,server-nonce
Then the client creates the proof for the server:
ClientSignature := HMAC(StoredKey, AuthMessage) ClientProof := ClientKey XOR ClientSignature
Or as an ascii art drawing:
server client nonce nonce username salt,ic password | | | | | | +------+----+----+------+ +---+---+ | | | v | SaltedPassword | | | v | ClientKey--+ | | | v v | AuthMessage----+----StoredKey | | | v | ClientSignature-------XOR | v ClientProof
The client can recalculate the
StoredKey using the
ic from the
AuthMessage and the original password from the user.
ClientProof is what the client sends to the server. Now when the server receives a proof from a client as
it needs to check it. It does so by also calculating
ClientSignature and extracting
ClientKey' from the XOR.
ClientKey' := ClientProof' XOR ClientSignature
StoredKey' := H(ClientKey')
Now it can compare
StoredKey and if they match, it knows the client proof is valid.
They brilliant detail here is the construction of
As you can see from the definition above, it's calculated from
ClientKey must never go over the wire because otherwise an observing attacker could impersonate the client.
To prevent that, it is encrypted by using
ClientSignature as an one-time-pad.
ClientSignature is a pseudo-random value from an HMAC calculation that depends on at least the client nonce, this should be a perfectly safe encryption.
But why can't we just send the
ClientSignature in the first place?
Because when an attacker obtains a
ServerRecord from the server it knows the
StoredKey and could impersonate the client.
By having the client prove knowledge of the
ClientKey, obtaining the
StoredKey from the server database is not enough to impersonate the client.
Another way to understanding the mechanism is to think of it as follows:
Like in plaintext authentication, the client shows the password in the form of the directly derived
ClientKey to the server.
This allows the server to only store a password hash.
But instead of transmitting the
ClientKey over the wire in plaintext, it is encrypted under a session key (
is derived from the nonces and the password hash.
For completeness we should continue with the protocol as the server-to-client authentication is still open.
When the client has proven to the server, that it is legitimate, the server must send a
ServerSignature to the client:
ServerSignature := HMAC(ServerKey, AuthMessage)
The client can check the
ServerSignature by also calculating it from the users password (and
ic) and comparing the results.
This could prevent bogus login pages from attackers where the evil server doesn't really check the users password but keeps interacting with the user to trick him into further actions.
';--you have been pwned?
So what can an attacker do with a stolen
Sadly there is one weakness in the protocol that can easily be spotted (and is also lined out in the RFCs):
If an attacker obtains the
StoredKey from the server and learns about the
ClientProof from an authentication exchange,
he can calculate the
ClientSignature and subsequently the
ClientKey he can then impersonate the client to the server.
I have simplified a few things that are not essential for understanding the basic mechanism but important for getting the implementation conforming and precise. So if you head out to implement SCRAM, go read the RFCs. There are also two issues that are important when implementing authentication protocols in general: timing side-channels and crypto hygiene.
Timing Side-Channels Analysis
If you don't know what a timing side-channel attack is, please read the wikipedia article before going any further. It will be a revelation.
The hash function, HMAC and
Hi/PBKDF2 implementation should be constant time. But that's usually the case for even naive implementations.
Another weak point usually are comparisons (memcmp,strcmp) during proof verification.
In particular, when the server compares
StoredKey for equality, a timing side-channel could leak information about the
But for that to work, the attacker has to control
StoredKey' is the hash
H(ClientProof' XOR ClientSignature), the attacker has to know
ClientSignature to extract any usable information from the timing side-channel.
ClientSignature in turn depends on
StoredKey and is unknown to the attacker.
As you can see, SCRAM is so well designed that it makes it hard to mess up and I think it may even be completely resistant to timing side-channel attacks. I would nonetheless make the server side verification comparison constant time, just to be on the safe side. The usual technique to XOR both values and checking the result to be all zeroes should work well since the compared strings are constant length.
Another best practice in crypto implementations is to overwrite secrets with zeroes as soon as they are not needed anymore. This protects against local attackers who may be able to observe memory. In the days of Spectre attacks this is relevant more then ever.
ClientKey' that is calculated on the server during verification is something that should be deleted as quickly as possible.
While you are at that, know your tools - a simple memset is not enough.
It is not trivial to overwrite memory that is not used afterwards because compilers may consider that useless writes and optimize them away.
Recovering from a Database Breach
Another aspect that is possible with SCRAM is to recover from a database breach.
When an attacker has stolen the
ServerRecords, that doesn't mean the users password needs to be changed.
It only means that the
ServerKey need to be replaced.
In order to do that, you need multiple
ServerRecords for one user and store all but one in a safe place (like an offline/write-only database).
So if you have a breach and have cleaned up the mess, you can pull out one of the spare
ServerRecords for the users from the offline database
and you and your users are safe again without users having to change their passwords.
For that to be safe, you have to make sure to use a different
salt for every user and
The Authentication Trilemma Solution
So how does SCRAM solve the "chose two" trilemma from above.
I think you could say that it trades in a little bit of 1. for a lot of 2. .
By transferring the encrypted
ClientKey to the server, the server learns about
and in case of a previous database breach an attacker can also learn about
In return the server can store strongly hashed passwords in the form of
StoredKey which require costly brute force attacks to crack.
I think this is a good trade-off.