Authentication

As noted above, authentication is a means for proving your identity, and is based on what you have, what you know, and what you are. Basic authentication mechanisms typically require a person to present one of the above to a gatekeeper system, which verifies the presented credential matches the information in a database.

These systems may be password systems, basic biometric systems, or keycard systems. These each have faults - relying only on one aspect lends to a weakness in the scheme. These weaknesses are:

• What you know: Even if you choose a good password, ultimately the gatekeeper knows the same secret you do. Someone can compromise the gatekeeper's database and pretend to be you.
• What you have: something you have can be taken. Until you report it stolen, anyone can pretend to be you.
• What you are: cannot be changed. If someone copies your fingerprints, they can pretend to be you forever.

Strong authentication schemes will not only incorporate two or more basic authentication mechanisms, but will be based around challenge/response. The gatekeeper will challenge the user, who must prove that they know enough to generate a valid response. An example is RSA authentication in ssh. The user must have a key, and know its passphrase. The gatekeeper only has the public half of the key, and the user proves, through public key cryptography, that they have access to the private key.

In essence, authentication is an appeal to a shared secret to prove that you are one of the secret sharers. In terms of physical locks and keys, this is relatively straightforward: Only if you have the key, can you open the lock. Thus, anyone who has opened the lock must have the key. Designing communication protocols for authentication, however, requires subtlety, due to the difficulty in proving you know a secret without disclosing the secret itself.

A good example of how not to do this is given by early central locking systems for cars. There are two components: the verifier in the car, and a keyfob, which share a radio signal password. On triggering the keyfob, it will transmit this radio signal to the car, which checks to see if it corresponds to its stored password; if so, the car unlocks.

Unfortunately, anyone with the ability to monitor radio signals can listen in for the password; they can then unlock the car by replaying the signal. This scenario also demonstrates how cryptography is not the same as security: suppose we tried to secure this system by encrypting the password P. Then we obtain a ciphertext, M say, which is to be transmitted by the keyfob to the verifier, where it is decrypted, and, if the result is P, the car unlocks. Our man with the radio scanner can still harvest the signal M, and this suffices as, even though the intruder is oblivious to P, the response of the car to a signal of M is to unlock.

A traditional lock and key presents a problem (the lock) which requires a solution (the key). However, in the system above the verifier and keyfob are not analogous to the lock and key, and so the vulnerability arises. Whilst the verifier (the lock) presents a problem, its solution (the key) is not the keyfob, but the appropriate radio signal. Thus the keyfob's transmission of this signal is equivalent to leaving your car keys on the roof of the car; that is, making the solution publically available.

To resolve this we introduce a challenge-response system. Here the verifier is active rather than passive; it generates fresh problems that can only be solved by a secret sharer. We can abstract and formalise the system as follows. Let V (the verifier) and A (Alice) be the participants, and let K_va be a secret key known only to them. A message written as M will be assumed to be clear to all, whilst {M}_K will indicate a message M encrypted with key K - only holders of key K can retrieve M itself from this signal, although note for later that any intruder still has access to the signal {M}_K (be it a radio signal, network data packet or so on). Finally, we require the notion of a nonce N - a number used once, or randomly generated signal. Then the challenge response system works as follows

Challenge-response authentication
V → A: N_v
A → V: {N_v}_Kva

That is, the verifier broadcasts a challenge N_v which anyone can receive; but only someone holding the shared secret K_va (in this case, only Alice) can respond with N_v encrypted by that key. Thus on receiving such a response, the verifier knows Alice is present. An eavesdropper can collect as many {N}_Kva as they like to no avail- since none of those N will be used again, they will never be a valid response.

This of course assumes genuinely fresh nonces¹ for each challenge; moreover, we require an unpredictable nonce, or a vulnerability exists as follows. Suppose an intruder I can tell what the next nonce will be, N_next say. Then the following sequence will allow I to authenticate as A:

Replay Attack
I sends a challenge to A, pretending to be V (written I(V))

I(V) → A: N_next
A → I(V): {N_next}_Kva

I returns to V and, impersonating A, triggers a challenge, which will be N_next

V→ I(A): N_next
I(V) → V: (N_next}_Kva

Now the verifier has received the correct response to its challenge, and thus assumes the respondent to be Alice when it is in fact the intruder; i.e., a central locking system exploited in this way would unlock for someone other than the keyfob holder. Note that I still has no knowledge of K_va, nor any need for it, underlining that the cryptography employed can be secure as you like yet the system as a whole can still be insecure.

Nonetheless, with secure crypto based on a secret shared key and unpredictable unrepeated challenges, the challenge-response system is a secure means for A to authenticate herself to V. There is an obvious limitation, that of the need for a shared secret. For central locking this can be manufactured into the car and keyfob; in effect, buying the car establishes the key. Designing communication protocols for key establishment is harder, since without such prior arrangements you need to somehow secure an insecure channel by communicating over that channel. Less obvious is the problem that challenge-response does not generalise to mutual authentication: that is, authenticating V to A as well as A to V. Again, prior arrangement (buying the car) means that one-way verification suffices for the central locking system: the locking system authenticates to Alice by virtue of being in her car! But for situations such as online shopping (where both vendor and purchaser need to be able to trust the other) or more dramatic examples such as friend-or-foe systems, it turns out that running challenge-response in both directions is flawed.

---

Reference: Formal analysis of Cryptographic Protocols Taught Postgraduate course, Laboratory for Foundations of Computer Science, University of Edinburgh.
¹Quit sniggering at the back, Britnoders!