Here are a couple of challenge/response authentication algorithms that I came up with while working on popa3d (a POP3 server). The goal was to address the major drawback of existing simple C/R schemes such as APOP and CRAM-MD5 (where they would require storage of plaintext passwords or of plaintext-equivalents on the server, thereby possibly making the setup less secure than it would be with simple password authentication not involving C/R), yet not go all the way for public-key crypto (stay simple). This goal was achieved, although the algorithms do have certain limitations.
Hs(password, salt) is a slow and salted cryptographic hash function intended for password hashing (e.g., bcrypt).
H() is a cryptographic hash function (e.g., SHA-256). Its output size should be at least as large as that of Hs(). The H(a, b) notation specifies that the input to the hash function is the concatenation of a and b.
unique() is a new random number that is almost certainly unique (one that has not been generated before).
secret is a server-specific stored random number with large guessing entropy. For a given server, it should normally not change (except after a compromise).
xor is bitwise exclusive-OR.
= is assignment to the variable on the left hand side.
== is bitwise comparison for equality.
For each user's password, the server stores salt and hash = H(Hs(password, salt)) (but it must not store Hs(password, salt)). If valid username probing needs to be mitigated, the server also stores secret.
In order to successfully authenticate to the server, the client needs to know Hs(password, salt), or indeed it may/should calculate that from password when the password is entered by the user (maybe on each login).
challenge = unique(), passes it and the requested user's salt on to the client.response = H(H(Hs(password, salt)), challenge) xor Hs(password, salt), passes it on to the server.(H(H(hash, challenge) xor response) == hash), which means successful authentication.Obvious: it is possible to probe different candidate passwords against sniffed challenge/response pairs.
Also, it is possible to request salts for arbitrary accounts, and to start precomputation (and smart/partial storage, like with rainbow tables) of hashes for candidate passwords. At a later time, such precomputed hashes may be quickly tested against sniffed challenge/response pairs when some of the target users finally do log in, or/and they may be tested against hashes stored on the server when the server is finally compromised.
Aside from the obvious offline password cracking attacks on stolen hashes, it becomes possible to derive Hs(password, salt) from sniffed traffic. Then it is possible for the attacker to continue logging in to the server under the specific accounts for which C/R exchanges were sniffed even after the server's security is otherwise restored.
Note that things would be a lot worse with traditional/naive C/R schemes such as APOP and CRAM, where a temporary compromise of the server, even one that gets detected and corrected almost immediately, would result in a leak of all plaintext passwords (or plaintext-equivalents). With the enhanced C/R scheme described here, such a temporary compromise fully affects a portion of the accounts only - those legitimately logged into while the compromise is in effect.
This scheme is never worse than authentication with a password passed in plaintext: the server only needs to store such a cryptographic hash of the password that is not usable for successful authentication to the server. This is similar to how systems store cryptographic hashes of users' passwords when the authenticating clients are expected to “show” their passwords in plaintext (possibly communicating them over a “secure” channel, which is a separate matter). For comparison, both APOP and CRAM are worse than plaintext: they require the storage of plaintext passwords (APOP) or plaintext equivalents usable for successful authentication to the server (CRAM). Thus, with those schemes a temporary compromise of the server becomes fatal, requiring that all passwords (even “extra-strong” ones) be changed at once. 1) This drawback has been addressed in the C/R scheme described here.
Similarly to APOP and CRAM, a server does not need write access to its database in order to implement this C/R scheme.
APOP is described in RFC 1939. CRAM is described in RFC 2195 and RFC 2104.
Only the “inner” hash function should preferably be slow (bcrypt may be used for this purpose). The server's performance is not affected by the inner hash function.
To mitigate probing for valid usernames, the server may always compute fake_salt == H(secret, username), and truncate and format this fake_salt to be indistinguishable from a user's real salt (H() should be such that its output is large enough for that). Then if it is determined that the target username has no valid authentication record associated with it, the server should provide fake_salt instead of the non-existent real salt to the client. It should also take care to mitigate timing attacks on user database lookups, etc.
Hs(), unique(), =, and == are defined the same as above.
E(data, key) and D(data, key) are, respectively, encryption and decryption of data with the key using a block cipher.
For each user's password, the server stores challenge (initially computed with challenge = unique(), then modified using the algorithm below) and encrypted = E(password, Hs(password, challenge)). If valid username probing needs to be mitigated, the server also stores secret.
In order to successfully authenticate to the server, the client needs to know the password (maybe ask it from the user on each login).
challenge on to the client.response = Hs(password, challenge), passes it on to the server.(Hs(D(encrypted, response), challenge) == response), which will mean successful authentication, and if so proceeds with:password = D(encrypted, response);
new_challenge = unique();
new_encrypted = E(password, Hs(password, new_challenge));
zeroize(password);
atomic {
challenge = new_challenge;
encrypted = new_encrypted;
}
The authentication attempt is deemed to have succeeded after the actions listed above complete without an error.
The == comparison at step 3, being applied directly to the supplied and expected response values, where the expected one is not changed between authentication attempts, may allow for remote timing attacks. These may be mitigated in one of two ways: either the comparison should be constant time (but beware of compiler optimization) or the comparison may be applied to values neither of which is known to a remote attacker:
expected_response = Hs(D(encrypted, response), challenge); if (H(expected_response, expected_response) == H(expected_response, response) && expected_response == response) success;
where H() is defined like it was for the “read-only algorithm” above, or alternatively the block cipher's D() may be reused for this purpose. Either way, it is required that D() does not leak any hints on its data input via timings with different chosen values for key. The explicit expected_response == response check is there to deal with the extremely unlikely yet possible hash collisions; it should only be reached when the hash values match. 2)
Obvious: it is possible to probe different candidate passwords against sniffed challenge/response pairs.
Also, it is possible to request salts for arbitrary accounts, and to start precomputation (and smart/partial storage, like with rainbow tables) of hashes for candidate passwords. At a later time, such precomputed hashes may be quickly tested against sniffed challenge/response pairs when some of the target users finally do log in, or/and they may be tested against hashes stored on the server when the server is finally compromised.
Additionally, an active attack is possible: an attacker with access to “the wire” may intercept and not let a valid response through to the server, then reuse the response at a later time.
Aside from the obvious offline password cracking attacks on stolen hashes and being able to capture plaintext passwords of users trying to log in on the server itself (while it's still compromised), it becomes possible to decrypt and thus obtain plaintext passwords from response values for users logging in for the first time after the server security is otherwise restored.
This was an attempt to fit a C/R scheme with better properties into a traditional network protocol supporting C/R authentication. Thus, the improvements are intentionally limited to the server side. In practice, this could “fit” into the existing APOP protocol if the server could know the target username first (or when there's exactly one user on a server). Unfortunately, with APOP the username is passed along with the response to the challenge, which prevents this enhanced C/R scheme from being implemented. However, it might be implementable with other existing protocols.
A drawback is that this requires that the server performing authentication has read/write access to the authentication database.
Username probing is to be mitigated in a way similar to that for the “read-only algorithm”, except that fake challenge rather than fake salt values need to be computed (always) and provided (when appropriate).
As it turns out, the “read-only” algorithm described above is exactly the same as the main algorithm behind RFC 5802 (SCRAM) published in 2010 and building upon drafts dating back to 1997. I posted this algorithm to sci.crypt in 1999 being unaware of the RFC drafts, and no one pointed me at them until Simon Josefsson did in 2012. This appears to be independent discovery.
Paul Johnston independently came up with a challenge/response algorithm that also falls in this category.
Back to my pseudo homepage.