Asym-key authentication

We have seen that one technique to authenticate and perform session key establishment is to have a centralized KDC service that shares a symmetric key with any registered users. While this solution makes sense in a local, controlled environment (such as a computer science department or a private company), it cannot scale to a wide area network such as the Internet, where entities cannot be all registered under a centralized server.

Asymmetric-key protocols are more suitable in this setting, as they allow for authentication and key-establishment without the presence of on-line servers. We discuss how the previous techniques need to be modified when asymmetric-key cryptography is employed.

Asymmetric key authentication protocols

Let us start from a basic, flawed, unilateral authentication protocol based on timestamps inspired to the one we proposed for symmetric-key encryption:

A \rightarrow B: E_{PK_B}(A, t_A)

Alice sends her name and a valid timestamp to Bob, both encrypted under Bob’s public key PK_B. This protocol is far from being correct, since any user can send the very same message to Bob, given that PK_B is public. So, for example, the attacker can easily pretend to be Alice as follows:

E \rightarrow B: E_{PK_B}(A, t_E)

Asymmetric-key encryption never proves the knowledge of a secret as it only requires the knowledge of PK_B. Decryption, instead, can be done only when the private key is known. Thus, a correct unilateral authentication protocol can be obtained by challenging Alice to decrypt something. The more natural way to achieve this is to adopt a Nonce-based authentication scheme:

\begin{array}{l} B\rightarrow A: E_{PK_A}(N_B,B) \\ A\rightarrow B: N_B \end{array}

Bob sends a nonce N_B encrypted together with his identifier under the public key of Alice. Only knowing Alice’s private key, it is possible to decrypt the nonce and send back its value in the clear. This proves the knowledge of a secret that only Alice is assumed to possess and provides authentication. The presence of the time-variant nonce prevents possible replays. The reason why it is important to specify the identifier in the first message is to prevent man-in-the-middle attacks. We illustrate this subtle issue on the following mutual-authentication protocol.

The Needham-Schroeder public-key protocol

The unilateral authentication protocol above can be extended in order to provide mutual authentication. Moreover, by never sending nonces in the clear, they can be used as sub-keys to produce a fresh session key shared between Alice and Bob.

\begin{array}{lrcl} 1. & B \rightarrow A & : & E_{PK_A}(N_B,B)\\ 2. & A \rightarrow B & : & E_{PK_B}(N_B,N_A) \\ 3. & B \rightarrow A & : & E_{PK_A}(N_A)\end{array}

The protocol works as follows:

  1. Bob challenges Alice to decrypt the nonce, as in the unilateral protocol above;
  2. Alice sends back Bob’s nonce encrypted under the Bob’s public key, together with her challenge N_A;
  3. Bob answers to Alice’s challenge by sending back her nonce encrypted under her public key.

Alice and Bob compute a session key as k_s = f(N_A,N_B).

Inspecting this protocol in detail we observe that in message 2 there is no indication of Alice identity. This gives the possibility to mount the following man-in-the-middle attack. We assume the attacker starts running a session where he authenticates with Bob honestly, i.e., by claiming his real identity E. This session is used against Alice to impersonate Bob.

\begin{array}{cccccrcll} 1a. &  & & E &\leftarrow & B & : & E_{PK_E}(N_B,B) \\1b. & A &\leftarrow & E(B) & &  & : & E_{PK_A}(N_B,B)& \mbox{(E decrypts and re-encrypts under Alice's public key)}\\ 2b. & A & \rightarrow & E(B) & & & : & E_{PK_B}(N_B,N_A) \\ 2a. & & & E & \rightarrow & B & : & E_{PK_B}(N_B,N_A) & \mbox{(E fowards the message to Bob)} \\3a. & & & E & \leftarrow & B & : & E_{PK_E}(N_A)\\3b. & A  & \leftarrow& E(B) && & : & E_{PK_A}(N_A) & \mbox{(E decrypts and re-encrypts under Alice's public key)}\end{array}

Since Bob has no information about who generated message 2, the attacker can forward it to obtain the decryption of Alice’s nonce. Notice that Alice is convinced to authenticate with Bob and the attacker knows both the nonces which allows him to compute the session key.

Adding Alice identifier in the second message would prevent Bob sending the nonce to the attacker as he would notice that the message is not coming from E:

\begin{array}{cccccrcll} 1a. &  & & E &\leftarrow & B & : & E_{PK_E}(N_B,B) \\1b. & A &\leftarrow & E(B) & &  & : & E_{PK_A}(N_B,B)& \mbox{(E decrypts and re-encrypts under Alice's public key)}\\ 2b. & A & \rightarrow & E(B) & & & : & E_{PK_B}(N_B,N_A,\mathbf{A}) \\ 2a. & & & E & \rightarrow & B & : & E_{PK_B}(N_B,N_A,\mathbf{A}) & \mbox{(E fowards the message to Bob)} \\ & & &  &  &  &  & & \mbox{(Bob refuses since the identifier is different from E)} \end{array}

This patched protocol is known in literature as the Needham-Schroeder-Lowe public-key protocol, from the name of Gavin Lowe who discovered the attack and proposed the fix.

Signature-based authentication protocols

Another way to provide authentication and key-establishment using asymmetric-key is combining asymmetric-key encryption and digital signatures. Encryption is needed to protect key confidentiality while signature gives authentication. We start from the the basic, flawed unilateral protocol:

A \rightarrow B: E_{PK_B}(A, t_A, k_s)

We add a signature from Alice to prove Alice identity. This, in fact, replaces Alice identifier. The timestamp can be sent in the clear. We include Bob’s identifier in the signature since, as we have discussed, it is important to specify the intended receiver of the authenticated exchange. We obtain the following protocol:

A \rightarrow B: t_A, E_{PK_B}( k_s,  sign_{A}( B, t_A, k_s ))

The problem with this solution is that the message to encrypt will be typically bigger than the size of one block (for RSA, bigger than the modulus since the signature is already, by itself, as big as the modulus). Implementing this protocol would amount to adopt some encryption mode such as CBC, with strong integrity guarantees.

A solution might be to separate encryption and signature as follows:

A \rightarrow B: t_A, E_{PK_B}(k_s), sign_{A}( B, t_A, k_s )

A symmetric key is typically much smaller than one encryption block for asymmetric key cryptography (for example, we might have a 1024 bits RSA modulus and a 128 or 256 bits AES symmetric key). The problem with this solution is that signatures sometimes allow for computing the signed message. For example, a “raw” signature implemented as RSA encryption under the private key (with no hash) can be decrypted using the public key, giving the message in the clear and thus the value of the session key. This protocol can be adopted only when the signature scheme prevents the computation of the signed message.

A general solution is thus to first encrypt and then sign.

A \rightarrow B: t_A, E_{PK_B}(k_s,A), sign_{A}( B, t_A, E_{PK_B}(k_s,A))

Since signature can be implemented using hashes we do not have length issues with this protocol. Notice that Alice identifier has been included in the encrypted message since, as usual, we want messages to be explicit about the parties involved in the protocol. More specifically, this prevents that an attacker intercepts the message and sign the (encrypted) key himself. This could be exploited in settings where the protocol gives credit (such as recharging a prepaid card, or getting an award for submitting the solution to a problem). By signing the session key the attacker will get credit for whatever is sent by Alice encrypted under k_s. Adding the identifier clearly prevents this attack since Bob will check that the identifier of the signature is the same as the one included in the encrypted message.

Remark. We have seen in numerous examples that when developing an authentication protocols it is important to specify the identifier which is not already implicit in the key. For example if we encrypt under Bob’s public key it is good to specify A. If Alice is signing it is good to include B in the signature.

X.509 strong authentication protocols

If we run the above unilateral authentication protocol twice we basically obtain the X.509 strong two-way authentication protocol :
\begin{array}{l} A \rightarrow B: t_A, E_{PK_B}(k^A_s,A), sign_{A}( B, t_A, E_{PK_B}(k^A_s,A)) \\ B \rightarrow A: t_B, E_{PK_A}(k^B_s,B), sign_{B}( A, t_B, E_{PK_A}(k^B_s,B))\end{array}

Alice and Bob compute a session key as k_s = f(k^A_s,k^B_s).

Mutual authentication can also be achieved based on nonces as follows:
\begin{array}{l} B \rightarrow A: N_B \\ A \rightarrow B: N_A, E_{PK_B}(k^A_s,A), sign_{A}( B, N_A, N_B, E_{PK_B}(k^A_s,A)) \\ B \rightarrow A: E_{PK_A}(k^B_s,B), sign_{B}( A, N_B, N_A, E_{PK_A}(k^B_s,B))\end{array}

which is very close to the X.509 strong three-way authentication protocol described here.