Authentication Mechanisms

After publishing my previous post, I had thought that I would not be coming back to Crypto for a while. However, today evening Sebastiaan posted on SCRAM on one of the Directi mailing lists, and I got compelled to write down this one.

Authentication in Cryptography has two aspects: data authentication and entity authentication. Data authentication is addressed using HMACs and Digital Signatures (discussed in my previous post). What we are talking about here is entity authentication: how does one entity get to know that the other entity is actually what is claims to be. This in turn has two aspects:

1. Alice and Bob are communicating in “real time” – the typical way of authentication here is by Alice issuing a challenge to which only Bob can respond.
2. Alice and Bob are sending messages to each other which are delivered after an appreciable delay since a message may be stored and forwarded thru multiple devices. Here since Alice can’t wait for Bob to respond to the challenge, the interest is only in validity of origin of data.

Here we are talking about the first kind of authentication. The goals of an entity authentication / identification protocol are as follows:

1. Bob should be able to successfully authenticate himself to Alice.
2. A third party should not be able to impersonate Bob to authenticate itself as Bob to Alice
3. Alice should not be able to use the data used in authenticating Bob to impersonate Bob to a third party.

 

Passwords

A password is a shared secret between two entities. By sending across the shared secret, one entity can prove to the other that it is indeed the possessor of the secret and hence the valid entity. However, sending the shared secret across as a mechanism for authentication is fairly weak. Here are some inherent weaknesses in the scheme:

1. Passwords are easy to guess (or brute force) since they are unlikely to be very long or use a random sequence or be chosen from a large alphabet set.
2. Passwords do not change frequently so brute forcing them becomes easier since there is a huge time window available.
3. A password is a shared secret between the two entities. Any entity that is able to intercept the password being sent by Bob over the wire can now use the password to authenticate itself to Alice.
4. In systems that store password in clear text, this is even worse, since privileged insiders or administrators now have access to the shared secret.

 

Some of these issues can be addressed to some extent thru the following:

1. Enforce a password policy that requires a long length, and inclusion of numbers or special symbols. This makes a brute force / dictionary / exhaustive search attack harder, but not impossible.
2. Make the user change the password frequently – while good in principle, in practice this does not help in a huge way since most password changing policies provide a lot of time (30-45 days) for a dedicated hacker.
3. Encrypt the password, preferably using a one-way function so that even if the algorithm, key and the Ciphertext are all available to the privileged user, he cannot get to know the shared secret.
4. Salting the one way function by using a randomly generated number as a key also makes a dictionary attack harder.

However, the biggest drawback of the fixed password approach is that it is open to a replay attack. So it cannot be used over an open network, but must require a trusted connection.

 

Challenge Response Identification

The idea of a Challenge  Response scheme is simple: Both Alice and Bob have a shared secret. To authenticate Bob, Alice makes him a challenge. To respond to the challenge, the shared secret is required which only Bob has. Thus by sending the response, Bob proves that he is the possessor of the shared secret without ever sending across the shared secret. There are multiple ways of doing challenge response:

 

Symmetric key Challenge Response using Encryption

Here the assumption is that Alice and Bob exchange the shared secret a priori. Let’s  suppose the shared key is K. Then:

1. Alice generates a random number n1, and sends it to Bob.
2. Bob applies the encryption algorithm to generate n2 = EA(n1, K) and sends it to Alice
3. Alice apples the decryption algorithm to compute n3 = DA(n2, K)
4. If n1 = n3, Bob indeed owns the shared secret and is who he claims to be.

The EA is typically a function like modular exponentiation which is easy to compute, but hard to reverse. Also, data integrity must be ensured in all transmission by using a HMAC.

 

Symmetric key Challenge Response using One-Way functions

In case the usage of an Encryption / Decryption routine is infeasible (because of computing cost maybe), it is possible to achieve the same using one-way functions as well:

1. Alice generates a random number n1, and sends it to Bob.
2. Bob applies the one-way function H to generate n2 = H(n1, K) and sends it to Alice
3. Alice also applies the one-way function H to generate n3 = H(n1, K)
4. If n1 = n3, Bob indeed owns the shared secret and is who he claims to be.

 

Asymmetric Challenge Response

1. Alice generates a random number n1 and sends it to Bob
2. Bob encrypts the random number n1 using his private key to generate n2 and sends it over to Alice
3. Alice decrypts n2 using Bob’s public key and obtains n3
4. If n1 = n3, Bob indeed owns the public key under his name

 

Zero Knowledge Protocols

Since in all the cases above, Bob responds with some response based on the secret key, there is a theoretical risk of information leakage. Zero knowledge protocols seek to address this by enabling a claimant to demonstrate knowledge of the secret without revealing any information whatsoever.  The basic idea is that the claimant must answer two questions: one involving demonstrating the knowledge of the secret, and the second is a simple question to prevent cheating. The series of steps is repeated several times (typically 40) to reduce the probability of cheating, and only if all answers are correct is the entity authenticated. The math involved in doing this is detailed but straight forward, and it is also easy to understand how the protocol works without revealing any information. You can read about it any standard cryptography textbook.

 

SASL Mechanisms

With that backgrounder, let’s come back to the issue of SCRAM-MD5 where we started. Basically SASL is a framework for entity and data authentication supporting multiple mechanisms including anonymous, plain-text, one-time-password, CRAM, Digest and now SCRAM. Let’s quickly examine these (please do not take the descriptions below as accurate – they are greatly simplified):

1. Anonymous: As the name suggests, the purpose of the mechanism here is for an entity to be able to use the service without proving its identity. The claimant basically sends a single string indicating that it wants to access the service anonymously. The server if it has that capability (which typically is checked by the client before sending the anonymous auth request) allows the entity to use the service anonymously.
2. Pla
   in
   -text: The plain-text mechanism is expected to be used over a secure pipe provided by a lower layer which takes care of confidentiality and integrity. Basically, the client sends over the username and password in plain text over TLS. The problem here is that in the absence of a secure lower layer, the entity can be easily compromised. Also, there is no mutual authentication.
3. OTP: One time passwords are a simple concept:
   • The user provides the password.
   • The client receives a non-secret seed from the server and appends the password with the seed
   • The result is passed thru a hash function (typically MD5, SHA1 and MD4 also allowed) and then reduced to 64-bits. This result is called S
   • This secret S is now run thru the hash function N-times, then N-1 times, N-2 times, and so on to produce multiple one time passwords.
   • Every time authentication needs to be done, the OTP along with the sequence number and the hashing function used are send over to the server
   • The adversary cannot invert the hash function and hence cannot recover the original password
   • The server applies the same hash function the same number of times and if it gets the same data, authenticates the user.
   • Good: makes replay attack difficult
   • Bad: Server stores password, no mutual auth. Open to dictionary attack. Hard to maintain sequence in the event of communication failure. Open to a pre-play attack.
4. CRAM:
   • Server sends a challenge string
   • Client responds with username followed by a message digest created by hashing the challenge string using the password as a key
   • Server performs the same computation on its side, and if it obtains the same message digest, authenticates the user
   • Good: Not open to replay. No disclosure of password
   • Bad: No mutual auth. Open to a dictionary attack if a CRAM exchange is captured. Server needs to store passwords (hopefully encrypted).
5. Digest:
   • Server stores one way hash of username and password H1 = Hash(username, password)
   • On request of a resource, server calculates hash of resource and the method required to access it H2 = Hash(resourceURI, method)
   • Server sends a nonce to client
   • Client calculates H1 = Hash(username, password), H2 = (resource URI, method)
   • Client generates Response = Hash(H1, nonce, H2) and sends it back to the server
   • Server does the same calculation at its end and if both are identical, the user is authenticated.
   • Good: Server does not store password, but a one-way hash
   • Bad: Usage of MD5 as a hashing function. Many security settings are optional. Open to a man in the middle attack.
6. SCRAM: It is tedious to describe the protocol in brief since it involves multiple repeated computations. Best to read the draft. The key improvements over Digest and CRAM, etc. are:
   • Server stores salted one way hash of password
   • Mutual authentication
   • Channel bindings
   • Can be used as a GSS API mechanism as well. GSS API is like SASL – a generic security framework.
   • Server cannot impersonate the client to other servers
   • Permits the use of a server-authorized proxy without requiring the proxy to have super-user rights with the backend server

I am mentioning the last two points in good faith. Have not studied the protocol deeply enough to arrive at how these two conclusions are valid.