# Efficient Symmetric Mutual Entity Authentication Protocol

I am looking for an Authentication protocol for access control. Let's say both the client and server would share a symmetric secret (256 bit key) and the client wants to access the server. Access should only be granted to a registered client the server shares a key with and both parties should know whom they've talked to.

It should provide:

• mutual authentication (client and server are both sure to talk to server resp. client)
• freshness property to encounter replay attacks
• efficiency: both parties should only have to execute a few cheap computations
• the authentication token should change for every authentication attempt
• the server should be prone (as much as possible) against DoS-attacks
• no replay or pre-play attacks

I couldn't find any protocol like this except Janson-Tsudik's 2PKDP which is patented. Thus, I had the idea to construct an own protocol from the protocols I have seen so far. I know this is probably the worst idea, especially because I am not a professional cryptographer.

But nevertheless I want to share my idea to know the pros and cons. I like the idea about Lamport's hash chains and want to use their hash values as one time authentication tokens (tickets). The advantages are mainly that the verification is really fast (just a hash-function) and the client needs to bring some information not yet known into the server. Unfortunately the major disadvantage is that the client has to precompute all N tickets. Thus I looked up one-way permutations with a trapdoor like for instance chameleon hash functions to be able to go in both directions of the hash chain (also known as infinite, re-initializable or renewable hash chains). Since I couldn't find any good implementation for such a function, I thought about just using RSA signatures: Client has a private key and the server his authenticated (beforehand) public key. The client initially generates a pseudorandom seed value which is then encrypted with the RSA private key (d, N), resulting in my first authentication ticket. Given that the server has also received the initial seed value, it can then upon receiving the first ticket check it by verifying it, i.e. decrypting it with the RSA public key. If the knowledge of the new ticket refers to being granted access, the open problems are how to accomplish mututal authentication and freshness and how to securely transmit the newly generated ticket to the server each time you log in. So far, I thought about something like:

1. client sends its client_id to server
2. server generates nonce N and sends it back
3. client calculates HMAC_T(N, client_id) xor T_new (where T is the last ticket and T_new the new one - and T is used as key for the hash-keyed MAC function)
4. server can compute the HMAC_T(N, client_id) since the old T is still available
5. server can thus deduce T_new
6. server can verify T_new by calculating: RSA_verify(T_new, (e, N)) == T (or in other words: decrypting T_new with the client's public RSA key and check if that yields in T.

Please note that the server needs to keep the last ticket saved because it's used for verifying the one handed with the next authentication request.

Please tell me in a merciless way which problems you see about it and where I haven't thought it through enough. Also if there is already a protocol/scheme that does what I want to, please point me into the right direction.

-
For what do you need the authentication? Knowing that I talk to $X$* itself is usually not enough if we don't know that whatever we talked about isn't also from $X$. So usually we either need to authenticate *a message or a communication channel (including all messages in both directions). For the latter, simply use TLS (with a preshared key cipher suite) instead of inventing your own. –  Paŭlo Ebermann Dec 20 '12 at 8:40
Thanks for your answer @PaŭloEbermann. If $X$ wanted to have access to server $S$, $X$ would need to provide $S$ a cryptographic evidence about his claimed identity so that $S$ knows whether to grant access or not. But I also want to have that the server $S$ proves his identity to $X$ so that the client itself knows it is accessing the right resource. I don't need to exchange any further information after access has been granted - thus I don't need to agree upon a symmetric encryption key which is used for efficient message encryption. But I want it to be as secure and efficient as possible. –  Martin Lundberg Dec 20 '12 at 11:45
What does access to the server mean to $X$? –  Paŭlo Ebermann Dec 20 '12 at 15:02
Personally I'd use a normal transport protocol such as SSL and add mutual authentication on top. I think some SSL implementations even support that. –  CodesInChaos Dec 21 '12 at 10:57

Asymmetric cryptography should be avoided when resources are scarce, keep in mind that 512bit keys are useless.

The kerberos protocol provides mutual authentication. A kerberos ticket is constructed using only a block cipher so an HMAC is not required in this design. Kerberos is designed to protect against ease-dropping and replay attacks. Kerberos tickets also timeout, which is an important design consideration that your proposed protocol lacks. Without the ability to timeout a malicious user may use an authentication token for a extended period of time.

Kerberos as a protocol satisfies all of your needs and is more secure and uses much less resources than your proposed protocol. Kerberos is in the public domain and you can implement it on nearly any device.

-
I cannot use Kerberos since I don't have synchronized clocks. Also a dedicated Kerberos server is not an option and Kerberos not really that efficient. @PaŭloEbermann: Let's say you'd use a smartcard as hotel room key where $X$ is the smartcard and $S$ the door of your room. As soon as $X$ has authenticated to $S$, access is granted and the door is opened. Now under the condition that the door is offline I also want to track which door has been opened by that particular smartcard key - i.e. to collect all access (attempts) in a dedicated database. –  Martin Lundberg Dec 21 '12 at 14:02
@Martin Lundberg Kerberos is probably more efficient than your protocol because its doesn't use RSA. I would avoid asymmetric cryptography as much as possible. Not having an accurate clock has other problems. How do you void keys at noon when their time is up? This is why kerberos tokens have a timestamp! –  Rook Dec 21 '12 at 16:44
@Martin Lundberg if you have a "server" then you can have a "time server". I think that not having time in your current protocol is a mistake. –  Rook Dec 21 '12 at 16:54
I just used the word "server" to make clear that it's the verifier that receives the authentication token and grants/denies access. I cannot rely on the availability of a cryptographically secure time on the verifier's system nor can I presume both the client and the verifier have a reliable online connection to synchronize their clocks. Also I want to point out that with my scheme the authentication token changes for every new access attempt. Isn't there another light-weight protocol for access control that isn't based on timestamps but offers strong mutual entity authentication? –  Martin Lundberg Dec 21 '12 at 22:02
Asymmetric crypto isn't that expensive, especially if you use ECDH instead of RSA. It's only an issue if you create really many connections in a short time (several thousand per second) or you're using a really weak device(embedded system). –  CodesInChaos Feb 28 '13 at 20:38

Please refer the well-known handbook of applied cryptography by Menezes et al.,you may find many symmetic key-based mutual authentication protocols (in Chapter 10), and more important, some pointers to the standards, e.g. ISO/IEC 9798 et al. Wish it helps.

-

SSL/TLS can be used with a pre-shared secret, which ensures mutual authentication and about all the properties you are looking for. The "raw PSK" cipher suites entail only symmetric cryptography and should be efficient even on very limited platforms. If you want perfect forward secrecy (i.e. protection of the confidentiality of past conversations even if the shared secret is stolen afterwards), then you will need some asymmetric cryptography, which the DHE_PSK cipher suites provide.

If the shared secret is of low entropy, vulnerable to exhaustive search (i.e. it is a password which an average human being accepts to remember and type), then you will need a password authenticated key exchange protocol, which, in the context of SSL/TLS, means SRP.

A rather important point is that designing a complete protocol is hard -- not only the authentication part, but also binding that securely to subsequent data transfers. SSL is the most well-known protocol in that category; every single known attack has been tried on it, and it was repaired when necessary, so it is now "state of the art". It thus makes sense, economically speaking, to use it. Also, this means that you may reuse existing implementations like GnuTLS (which, incidentally, supports PSK and SRP cipher suites).

-
When you use passwords as shared secrets, an important property of a such a protocol is not exposing the shared secret to offline search (against passive attackers). –  CodesInChaos Feb 28 '13 at 17:09

What about SRP? It has an additional property, that you do not need to keep the shared secret unprotected on the server. http://srp.stanford.edu/design.html

You did not specify if you want to restrict the number of roundtrips, but I guess with SRP they can be minimized.

-