Authentication is the process of binding an identity to a user (or service). There is a distinction between authentication and identification. Identification is simply the process of asserting an identity: asking you to identify yourself (for example, entering a login name). Authentication is the process of proving that the identification is correct. Authorization is the process of determining whether the user is permitted to do something.

Combined Authentication & Key Exchange

The biggest problem with symmetric cryptography has been key distribution. For Alice and Bob to communicate, they must share a secret key that no adversaries can get. However, Alice cannot send the key to Bob since it would be visible to adversaries. She cannot encrypt it because Alice and Bob do not share a key yet.

For two parties to communicate using symmetric ciphers they need to share the same key. Since we don’t trust the network (traffic may be intercepted or snooped), we cannot send keys over the network directly. A key can be shared in several ways:

1. Share the key via some trusted mechanism outside of the network, such are reading it over the phone or sending a flash drive via UPS.

2. Use a public key algorithm. Either use a Diffie-Hellman algorithm to enable both parties to compute a common key or encrypt a session key with the other sides’ public key. Either mechanism assumes that we have some way of validating that the public key truly belongs to the user.

3. Use a trusted third party, with which all parties can communicate securely, to set up the session.

Key exchange using a trusted third party

We will explore the use of a trusted third party. A trusted third party is a trusted system that has everyone’s key. Hence, only Alice and the trusted party (whom we will call Trent) have Alice’s secret key. Only Bob and Trent have Bob’s secret key. Note that there needs to be a setup process for Trent to acquire these keys. This might involve users presenting themselves to some administrator, who would validate their ID and have them enter a password, which can then get hashed into a key.

The simplest way of using a trusted third party is to ask it to come up with a session key and send it to the parties that wish to communicate. For example, Alice sends a message to Trent requesting a session key to communicate with Bob. This message identifies that it came for Alice and the rest of it (the request) is encrypted with Alice’s secret key so that Trent can tell the message could have only come from Alice if he can decrypt it with Alice’s secret key.

Trent generates a random session key and encrypts it with Alice’s secret key. He also encrypts the same session key with Bob’s secret key. Alice gets both of these encrypted values and sends the key encrypted for Bob over to Bob. Now Alice and Bob have a session key that was encrypted with each of their secret keys. They can each decrypt the message using their respective secret keys to obtain the session key. Now they can communicate by encrypting messages with that session key.

This simple scheme is vulnerable to replay attacks. An eavesdropper, Eve, can record messages from Alice to Bob and replay them at a later time. Eve might not be able to decode the messages but she can confuse Bob by sending him seemingly valid encrypted messages.

The second problem is that Alice sends Bob an encrypted session key but Bob has no idea that it’s Alice who is communicating with him. While Trent authenticated Alice (simply by being able to decrypt her request) and authorized her to talk with Bob (by generating the session key), that information has not been conveyed to Bob. Bob simply knows that someone who has been authorized by Trent is now communicating with him. We can fix this easily by having the encrypted message contain Alices’s ID.

Needham-Schroeder: nonces

The Needham-Schroeder protocol improves the basic key exchange protocol by adding nonces to messages. A nonce is simply a random string – a random bunch of bits (the name is an abbreviation for number used once).

As in our previous dialogue, Alice sends a request to Trent, asking to talk to Bob. The message does not have to be encrypted. As part of this request she sends a nonce.

Trent responds with a message that contains:

• Alice’s ID
• Bob’s ID
• the same nonce
• a session key
• a ticket: a message encrypted for Bob containing Alice’s ID and the same session key

This entire message from Trent is encrypted with Alice’s secret key. Alice can validate that the message is a response to her message because:

• It is encrypted for her: nobody but Alice and Trent has Alice’s secret key.
• It contains the same nonce as in her request, so it is not a replay of some earlier message, which would have had a different randomly-generated nonce.

Alice sends the ticket (the message encrypted with Bob’s key) to Bob. He can decrypt this using his key and knows:

• The message must have been generated by Trent since only Trent and Bob know Bob’s key and and thus only Trent could have constructed a meaningful message encrypted with Bob’s key.
• He will be communicating with Alice because Trent placed Alice’s ID in that ticket.
• The session key, since Trent placed that in the ticket as well. Alice has this session key too.

Bob can now communicate with Alice but he will first authenticate Alice to be sure that he’s really communicating with her. He’ll be convinced it’s Alice if she can prove that she has the same session key Bob does.

To perform this authentication, Bob creates another nonce, encrypts it with the session key, and sends it to Alice. Alice decrypts the message, subtracts one from the nonce, encrypts the result, and sends it back to Bob. By doing this, she demonstrated that she could decrypt a message using the session key and return back a known modification of the message.

Needham-Schroeder is a combined authentication and key exchange protocol.

Denning-Sacco modification: timestamps to avoid key replay

One flaw in the Needham-Schroeder algorithm is when Alice sends the ticket to Bob. The ticket is encrypted with Bob’s secret key and contains Alice’s ID as well as the session key. If an attacker happened to record an old conversation session and was able to decrypt the session key¹, she can replay the transmission of an old ticket to Bob. Bob won’t remember that he received that same session key in the distant past. Thus, he will proceed to validate “Alice” by asking her to prove that she indeed knows the session key. In this case, Eve, our eavesdropper, does know it; it’s why she sent the ticket to Bob. Bob completes the authentication and thinks he is talking with Alice when in reality he is talking to Eve.

A fix for this was proposed by Denning & Sacco: add a timestamp to the ticket. When Trent creates the ticket that Alice will give to Bob, it is a message encrypted for Bob and contains Alice’s ID, the session key, and a timestamp.

When Bob decrypts a ticket that he receives, he checks the timestamp. If it is significantly older than the current time (e.g., more than a few seconds old), Bob will simply discard the ticket, assuming that he is getting a replay attack.

Otway-Rees protocol: session IDs instead of timestamps

A challenge with timestamps is that their use relies on all entities having synchronized clocks. If Bob’s clock is significantly off from Trent’s, he may falsely accept or falsely reject a ticket that Alice presents to him. Time synchronization also becomes a possible attack vector for this protocol. If an attacker can change Bob’s concept of time, she may be able to convince Bob to accept an older ticket. To do this, she may create fake NTP (network time protocol) responses to force Bob’s clock to synchronize to a different value or, if Bob is paranoid and uses a GPS receiver to synchronize time, spoof GPS signals.

A technique to avoid the replay of the ticket without using timestamps is to add a session ID to each message. Think of a session ID as a number that uniquely identifies each sequence of messages within one authentication session.

The Otway-Rees protocol demonstrates this, using a session ID to associate all the messages and using nonces to avoid replay attacks. The nonces ensure that there is no replay attack on Trent’s response even if an attacker sends a message to Bob with a new session ID and old encrypted session keys (that were cracked by the attacker).

The protocol differs a bit from Needham-Schroeder but is conceptually similar. The key difference in the message sequence is that Alice initiates a communication with Bob rather than Trent and Bob then relays the request to Trent:

1. Alice sends a message to Bob that contains:

   • A session ID
   • The sender (Alice’s) and receiver (Bob’s) IDs.
   • A message encrypted with Alice’s secret key that contains Alice’s and Bob’s IDs, a nonce (r₁), and the session ID.

2. Bob sends Trent a request to communicate with Alice, containing:

   • Alice’s entire message
   • A message encrypted with Bob’s secret key that also contains the session ID and Bob’s nonce (r₂).

3. Trent now knows that Alice wants to talk to Bob since the session ID is inside her encrypted message and that Bob agrees to talk to Alice since that same session ID is inside his encrypted message. The session key also convinces him that neither Bob’s encrypted message nor Alice’s encrypted message are replay attacks, although the entire message might be one (it doesn’t matter if it is in this step).

4. Trent creates a random session key encrypted for Bob and the same key encrypted for Alice. He sends both of these to Bob, along with the session ID. The session key encrypted for Alice also contains Alice’s nonce (r₁) and the session key encrypted for Bob contains Bob’s nonce (r₂).

5. When Bob receives the message, he can decrypt the part that is encrypted with his secret key. This gives him the session key and he can check that the message contains r₂ and is thus a response to the request he sent. He sends the message that’s encrypted for Alice to her along with the session ID.

6. Alice does the same thing. She decrypts the message and gets the session key. She can check that the message contains r₁ and is thus a response to the request she created.

7. Bob and Alice can now communicate using the shared keys

Kerberos

Kerberos is a trusted third party authentication, authorization, and key exchange protocol using symmetric cryptography and based closely on the Needham-Schroeder protocol with the Denning-Sacco modification (the use of timestamps).

When Alice wands to talk with Bob (they can be users and services), she first needs to ask Kerberos. If access is authorized, Kerberos will send her two messages. One is encrypted with Alice’s secret key and contains the session key for her communication with Bob. The other message is encrypted with Bob’s secret key. Alice cannot read or decode this second message. It s a ticket. It contains the same session key that Alice received but is encrypted for Bob. Alice will send that to Bob. When Bob decrypts it, he knows that the message must have been generated by an entity that knows its secret key: Kerberos. Now that Alice and Bob both have the session key, they can communicate securely by encrypting all traffic with that session key.

To avoid replay attacks, Kerberos places a timestamp in Alice’s response and in the ticket. For Alice to authenticate herself to Bob, she needs to prove that she was able to extract the session key from the encrypted message Kerberos sent her. She proves this by generating a new timestamp, encrypting it with the session key, and sending it to Bob. Bob now needs to prove to Alice that he can decode messages encrypted with the session key. He takes Alice’s timestamp, adds one (just to permute the value), and sends it back to Alice, encrypted with their session key.

Since your secret key is needed to decrypt every service request you make of Kerberos, you’ll end up typing your password each time you want to access a service. Storing the key in a file to cache it is not a good idea. Kerberos handles this by splitting itself into two components that run the same protocol: the authentication service (AS) and the ticket granting service (TGS). The authentication service handles the initial user request and provides a session key to access the TGS. This session key can be cached for the user’s login session and allows the user to send requests to the TGS without re-entering a password. The TGS is the part of Kerberos that handles requests for services. It also returns two messages to the user: a different session key for the desired service and a ticket that must be provided for that service.

Kerberos has been around for a long time, starting with MIT’s Project Athena in 1987 but based on Needham and Schroeder’s earlier work. Jerome H. Saltzer of MIT has written a great two-page history On the Origin of Kerberos. Despite its age, it is a component of many operating systems:

• Windows Server: [This Microsoft article discusses Kerberos in Windows Server.]
• Various Linux distributions: Ubuntu, Red Hat, Debian, Arch, Gentoo, and others.
• Varous BSD distributions: FreeeBSD, OpenBSD, NetBSD.
• IBM z/OS
• ChromeOS/Chromium

It’s also supported by popular cloud platforms:

• Microsoft Azure: [Entra ID using Kerberos to enable passwordless single sign-on](https://learn.microsoft.com/en-us/entra/identity/authentication/howto-authentication-passwordless-security-key-on-premises
• Google Cloud
• Amazon Web Services

Public key authentication

Public key authentication relies on the use of nonces, similar to the way they were used to authenticate users using the Needham-Schroeder protocol. A nonce is is generated on the fly and used to present to the other party as a challenge for them to prove that they are capable of encrypting something with a specific key that they possess. The use of a nonce is central to public key authentication.

If Alice wants to authenticate Bob, she needs to have Bob prove that he possesses his private key (private keys are never shared). To do this, Alice generates a nonce (a random bunch of bits) and sends it to Bob, asking him to encrypt it with his private key. If she can decrypt Bob’s response using Bob’s public key and sees the same nonce, she will be convinced that she is talking to Bob because nobody else will have Bob’s private key. Mutual authentication requires that each party authenticate itself to the other: Bob will also have to generate a nonce and ask Alice to encrypt it with her private key.

Note that this authentication only convinces you that the other side has the private key that corresponds to a public key that you have. If Alice wants to ensure that she really has Bob’s public key and not an imposter’s, she needs to get the key from a trusted source or get the key in the form of an X.509 certificate that was issued by a trusted CA and whose signature she verified.

If we want to add key exchange, Alice can create a random session key, encrypt it with Bob’s public key, and send it to Bob. Only Bob can decrypt the session key using his private key. Recall the earlier discussion on forward secrecy. To obtain forward secrecy, Bob and Alice will use their public-private keys only for authentication and then use disposable keys, such as a Diffie-Hellman key pair to establish a shared session key.

User Authentication

Authentication factors

The three factors of authentication are:

1. something you have (such as a key or a card),
2. something you know (such as a password or PIN),
3. and something you are (biometrics).

Combining these into a multi-factor authentication scheme can increase security against the chance that any one of the factors is compromised. Multi-factor authentication must use two or more of these factors. Using two passwords, for example, is not sufficient and does not qualify as multi-factor.

Password Authentication Protocol

The classic authentication method is the use of reusable passwords. This is known as the password authentication protocol, or PAP. The system asks you to identify yourself (login name) and then enter a password. If the password matches that which is associated with the login name on the system then you’re authenticated.

Password guessing defenses

To avoid having an adversary carry out a password guessing attack, we need to make it not feasible to try a large number of passwords. A common approach is to rate-limit guesses. When the system detects an incorrect password, it will wait several seconds before allowing the user to try again. Linux, for example, waits about three seconds. After five bad guesses, it terminates and restarts the login process.

Another approach is to completely disallow password guessing after a certain number of failed attempts by locking the account. This is common for some web-based services, such as banks. However, the system has now been made vulnerable to a denial-of-service attack. An attacker may not be able to take your money but may inconvenience you by disallowing you to access it as well.

Hashed passwords

One problem with the password authentication protocol is that if someone gets hold of the password file on the system, then they have all the passwords. The common way to thwart this is to store hashes of passwords instead of the passwords themselves. This takes advantage of the one-way property of the hash: anyone who sees the hash still has no way of computing your password.

To authenticate a user, the system simply checks if hash(password) = stored_hashed_password. If someone got hold of the password file, they’re still stuck since they won’t be able to reconstruct the original password from the hash. They’ll have to resort to an exhaustive search (also known as a brute-force search) to search for a password that hashes to the value in the file. The hashed file should still be protected from read access by normal users to keep them from performing an exhaustive search.

A dictionary attack is an optimization of the search that tests common passwords, including dictionary words, known common passwords, and common letter-number substitutions rather than every possible combination of characters. Moreover, an intruder does not need to perform such search on each hashed password to find the password. Instead, the results of a dictionary search can be stored in a file and later searched to find a corresponding hash in a password file. These are called precomputed hashes. To guard against this, a password is concatenated with a bunch of extra random characters, called salt. These characters make the password substantially longer and would make a table of precomputed hashes insanely huge and hence not practical. Such a table would need to go far beyond a dictionary list and create hashes of all possible passwords that are augmented with these additional random characters.. The salt is not a secret – it is stored in plaintext in the password file in order to validate a user’s password. Its only function is to make using precomputed hashes impractical and ensure that even identical passwords do not generate the same hashed results. An intruder would have to select one specific hashed password and do a brute-force or dictionary attack on just that password, adding salt to each guess prior to hashing it.

Password recovery options

Passwords are bad. They are not incredibly secure. English text has a low entropy (approximately 1.2–1.5 bits per character) and are often easy to guess. Password files from some high-profile sites have been obtained to validate just how bad a lot of people are at picking passwords. Over 90% of all user passwords sampled are on a list of the top 1,000 passwords. The most common password is password. People also tend to reuse passwords. If an attacker can get passwords from one place, there is a good chance that many of those passwords will work with other services.

Despite many people picking bad passwords, people often forget them, especially when they are trying to be good and use different passwords for different accounts. There are several common ways of handling forgotten passwords, none of them great:

Email them:

This used to be a common solution and is somewhat dying off. It requires that the server is able to get the password (it is not stored as a hash). It exposes the risk that anyone who might see your email will see your password.

Reset them:

This is more common but requires authenticating the requestor to avoid a denial of service attack. The common thing to do is to send a password reset link to an email address that was entered when the account was created. We again have the problem that if someone has access to your mail, they will have access to the password reset link and will be able to create a new password for your account. In both these cases, we have the problem that users may no longer have the same email address. Think of the people who switched from Comcast to get Verizon FiOS and switched their comcast.net addresses to verizon.net (note: avoid using email addresses tied to services or locations that you might change).

Provide hints:

This is common for system logins (e.g. macOS and Windows). However, a good hint may weaken the password or may not help the user.

Ask questions:

It is common for sites to ask questions (“what was your favorite pet’s name?”, “what street did you live on when you were eight years old?”). The answers to many of these questions can often be found through some searching or via social engineering. A more clever thing is to have unpredictable answers (“what was your favorite pet’s name?” “Osnu7$Qbv999”) but that requires storing answers somewhere.

Rely on users to write them down:

This is fine as long as the thread model is electronic-only and you don’t worry about someone physically searching for your passwords.

One-time Passwords

The other problem with reusable passwords is that if a network is insecure, an eavesdropper may sniff the password from the network. A potential intruder may also simply observe the user typing a password. To thwart this, we can turn to one-time passwords. If someone sees you type a password or gets it from the network stream, it won’t matter because that password will be useless for future logins.

There are three forms of one-time passwords:

1. Sequence-based. Each password is a function of the previous password. S/Key is an example of this.

2. Challenge-based. A password is a function of a challenge provided by the server. CHAP is an example of this.

3. Time-based. Each password is a function of the time. TOTP and RSA’s SecurID are example of this.

Sequence-based: S/Key

S/Key authentication allows the use of one-time passwords by generating a list via one-way functions. The list is created such that password n is generated as f(password[n-1]), where f is a one-way function. The list of passwords is used backwards. Given a password password[p], it is impossible for an observer to compute the next valid password because a one-way function f makes it improbably difficult to compute the inverse function, f^-1(password[p]), to get the next valid password, password[p-1].

Challenge-based: CHAP

The Challenge-Handshake Authentication Protocol (CHAP) is an authentication protocol that allows a server to authenticate a user without sending a password over the network.

Both the client and server share a secret (essentially a password). A server creates a random bunch of bits (called a nonce) and sends it to the client (user) that wants to authenticate. This is the challenge.

The client identifies itself and sends a response that is the hash of the shared secret combined with the challenge. The server has the same data and can generate its own hash of the same challenge and secret. If the hash matches the one received from the client, the server is convinced that the client knows the shared secret and is therefore legitimate.

An intruder that sees this hash cannot extract the original data. An intruder that sees the challenge cannot create a suitable hashed response without knowing the secret. Note that this technique requires passwords to be accessible at the server and the security rests on the password file remaining secure.

Challenge-based: Passkeys

Passkey authentication is an implementation of public key authentication that is designed to eliminate the use of passwords. A user first logs onto a service via whatever legacy login protocol the service supports: typically a username-password or the additional use of a time-based one-time password or SMS authentication code. After that, the user’s device generates a public-private key pair for that specific service. The public key is sent to the service and associated with the user, much like a password was in the past. Note that the public key is not secret. The private key is stored on the user’s device.

Once passkey authentication is set up, the user logs in by providing their user name. The server generates a random challenge string (at least 16 bytes long) and sends it to the user. The user’s device retrieves the private key for the desired service. This is generally stored securely on the device and unlocked via Face ID, Touch ID, or a local password. None of this information, including the private key, is sent to the server. Using the private key, the device creates a digital signature for the challenge provided by the service and sends the result to the service.

The server looks up the user’s public key, which was registered during enrollment, and verifies the signature against the challenge (that is, decrypts the data sent by the user and sees if it matches a hash of the original challenge string). If the signature is valid, the service is convinced that the other side holds a valid private key that corresponds to the public key that is associated with the user and is, therefore, the legitimate user.

Time-based: TOTP

With the Time-based One Time Password (TOTP) protocol, both sides share a secret key. To authenticate, a user runs the TOTP function to create a one-time password. The TOTP function is a hash:

password := hash(secret_key, time) % 10^{password_length}

The resultant hash is taken modulo some number that determines the length of the password. A time window of 30 seconds is usually used to provide a reasonably coarse granularity of time that doesn’t put too much stress on the user or requirements for tight clock synchronization. The service, who also knows the secret key and time, can generate the same hash and hence validate the value presented by the user.

TOTP is often used as a second factor (proof that you have some device with the secret configured in it) in addition to a password. The protocol is widely supported by companies such as Amazon, Dropbox, Wordpress, Microsoft, and Google.

Hash-based Onet Time Passwords

Hash-based One Time Passwords (HOTP) are similar in concept to time-based one time passwords but use an incrementing counter instead of the time of day. As with TOTP, both sides store a shared secret. With HOTP, they also store a counter. The password is a hash of the secret and the counter. For a successful authentication, the user’s counter and the server’s counter are both incremented.

The YubiKey authenticator is a popular example of a device that implements HOTP (it also supports other authentication protocols, including TOTP). It implements the RFC 4226 HOTP algorithm to generate a one-time password, which can be prefixed by a hardware ID. This identifies the device, which can be used to link the key to a user. For HOTP, it applies the SHA-1 hash on a secret key and a counter and converts the result to a printable format.

Man-in-the-middle attacks

Authentication protocols can be vulnerable to man-in-the-middle (MITM) attacks. In this attack, Alice thinks she is talking to Bob but is really talking to Mike (the man in the middle, an adversary). Mike, in turn talks to Bob. Any message that Alice sends gets forwarded by Mike to Bob. Mike forwards any response from Bob gets back to Alice. This way, Mike allows Alice and Bob to carry out their authentication protocol. Once Bob is convinced he is talking with Alice, Mike can drop Alice and communicate with Bob directly, posing as Alice … or stay around and read their messages, possibly changing them as he sees fit.

The protocols that are immune to this are those where Alice and Bob establish an encrypted channel using trusted keys. For example, with Kerberos, both Alice and Bob get a session key that is encrypted only for each of them. Mike cannot find it even if he intercepts their communications.

With public key cryptography, Mike can take over after Bob is convinced he is talking with Alice. To avoid a man-in-the-middle attack Alice will have to send Bob a session key. If she uses public key cryptography to do the key exchange, as long as the message from Alice is signed, Mike will not be able to decrypt the session key or forge a new one.