Authentication Protocols

Exam Information

• The upcoming exam will cover the second part of the course, focusing on public key cryptography.
• The exam will only cover topics taught in class.
• Assignment 5 grades will be available before the exam.
• Assignment 6 grades may not be available before the exam.
• A study guide will be provided over the weekend.

Authentication Protocols

• Focus has been on ensuring secrecy and integrity of messages.
  • Private key setting: Private key cryptosystems for encryption, Message Authentication Codes (MACs) for integrity.
  • Public key setting: Public key systems for encryption, digital signature schemes for integrity.
• Today's topic: Authentication protocols for authenticating users, not messages
• Authentication: Proving you are who you claim to be (e.g., logging into a computer).
• Alice and Bob can be humans or computers; authentication can be one-way or mutual.
• Mutual authentication: Both parties prove their identities to each other.
• Session key: A key used only for the current session, discarded afterward; not a long-term key.
• Additional requirements:
  • Use of symmetric or public keys only.
  • Use of only a hash function.
  • Anonymity, plausibility, deniability, and other constraints.
• Problem: Verifying identity of the person you are talking to online.
• Example: Minnesota state senator case where he thought he was communicating with an underage girl, but it was an FBI agent. Illustrates the importance of authenticating users.

Authentication on Standalone vs. Networked Computers

• Standalone computer: Authentication via login name and password; relatively straightforward.
• Network: More complex; sending login and password over the network in plain form is insecure.
• Replay attack: Observing network traffic and reusing the captured information to impersonate someone.
• Adversary types:
  • Passive: Can only observe network traffic.
  • Active: Can modify network traffic.

Simple Authentication Protocol

1. Alice says, "I am Alice."
2. Bob says, "Prove it."
3. Alice sends her password, "Frank."

• Problem: Password is sent in plain text over the network.
• Vulnerable to replay attack.

Replay Attack Example

1. Alice says, "I am Alice."
2. Bob says, "Prove it."
3. Alice sends her password, "Frank."

• Trudy (troublemaker) observes the communication.
• Trudy learns Alice's password.
• Trudy contacts Bob, says "I am Alice," and provides the password "Frank."
• Bob verifies the password and grants Trudy access.

Preventing Replay Attacks

• Improved protocol (but still insecure):
  • Alice sends, "I am Alice, and my password is Frank."
  • Still vulnerable to replay attack.

Using Hash Functions

1. Alice says, "I am Alice."
2. Bob says, "Prove it."
3. Alice sends a hash of her password, $H(password)$.

• Bob computes $H(Alice's Password)$ and compares with Alice's sent hash.
• Since H is preimage resistant, it's difficult for Trudy to determine the password from $H(password)$.
  *Problem: Trudy can still replay the hashed password.

Challenge-Response Protocol

• Bob issues a unique challenge to Alice that only Alice can answer.
• Prevents replay attacks because the challenge is different each time.
• Uses a nonce (number used only once).

Nonce-Based Protocol

1. Alice says, "I am Alice."
2. Bob sends a nonce, $N$.
3. Alice sends $H(password || N)$, where $||$ is concatenation.

• Bob computes $H(Alice's Password || N)$ and compares it with Alice's sent hash.
• Trudy cannot replay the response because the nonce is different each time.
  *Bob needs to know Alice's password.

Challenge-Response Protocol Requirements

• Challenge must be new each time.
• Response must be something only Alice can produce.
• Response must be verifiable by Bob.

Using Symmetric Key Encryption

• Notation: $E<em>k(p) = c$ (encryption of plaintext p with key k gives ciphertext c), $D</em>k(c) = p$ (decryption).

• Assumptions: Underlying cryptosystem is secure.

Symmetric Key Authentication Protocol

• Alice and Bob share a common key, $K_{AB}$, known only to them.

1. Alice says, "I am Alice."
2. Bob sends a random number (nonce), $R$.
3. Alice sends $E<em>{K</em>{AB}}(R)$.

• Bob encrypts $R$ with $K_{AB}$ and compares with Alice's response.
• Secure method for Bob to authenticate Alice.
• Alice does not authenticate Bob.

Mutual Authentication

• Both Alice and Bob authenticate each other.

Attempted Mutual Authentication Protocol (Insecure)

1. Alice says, "I am Alice" and sends a random number $R$.
2. Bob sends $E<em>{K</em>{AB}}(R)$.
3. Alice sends $E<em>{K</em>{AB}}(R)$.

• Problem: Alice can send back the same message she received from Bob without knowing $K_{AB}$.
• Anyone can impersonate Alice.

Secure Mutual Authentication Protocol

1. Alice says, "I am Alice" and sends random number $R_A$.
2. Bob sends $E<em>{K</em>{AB}}(R_A)$.
3. Bob sends a random number $R_B$.
4. Alice sends $E<em>{K</em>{AB}}(R_B)$.

• Alice authenticates Bob by verifying $E<em>{K</em>{AB}}(R_A)$.
• Bob authenticates Alice by verifying $E<em>{K</em>{AB}}(R_B)$.

Grandmaster Chess Analogy

*One can draw with grandmasters in chess without knowing strategy using simple mimicking tactics.

Insecurity of Authentication Protocol Illustrated

*An attack can occur with concurrent sessions and Trudy mimicking moves in sessions

Mutual Authentication Protocol

1. Alice says, "I am Alice" and sends random number $R_A$.
2. Bob sends $E<em>{K</em>{AB}}(Bob || R_A)$.
3. Bob sends a random number $R_B$.
4. Alice sends $E<em>{K</em>{AB}}(Alice || R_B)$.

Mutual Authentication with Public Key Encryption

• Notation:
  • ${M}_{Alice}$ means M is encrypted with Alice's public key.
  • $[M]_{Alice}$ means M is signed with Alice's private key.

1. Alice says, "I am Alice" .
2. Bob sends ${R}_{Alice}$.
3. Alice sends $R$.

• Problem: Alice is decrypting a message, which could be exploited.
  *Bob is authenticating Alice but it opens the door to Trudy getting Alice to decrypt a message for her.
  *Must use two different key pairs to avoid exploitation.

Public Key Authentication using Digital Signatures

1. Alice says, "I am Alice" .
2. Bob sends random number $R$.
3. Alice sends $[R]_{Alice}$.

• Bob verifies Alice's signature.
• Only one-way authentication.
• Alice is signing a message, which could have unintended consequences.

Session Keys

• After authentication, a session key is used for secure communication.
• Often a symmetric key.
• Perfect forward secrecy: If the secret key is later compromised, previous communications remain secure.

Session Key Exchange (Insecure)

1. Alice says, "I am Alice" and gives random number $R_A$.
2. Bob selects session key $K$ and sends ${R<em>A || K}</em>{Alice}$.
3. Alice sends ${R<em>A + 1 || K}</em>{Bob}$.

• Problem: Does not achieve mutual authentication.
• Anyone could send the second message.

Mutual Authentication and Session Key Exchange

1. Alice says, "I am Alice" and gives random number $R_A$.
2. Bob selects session key $K$ and sends $[R<em>A || K]</em>{Bob}$.
3. Alice sends $[R<em>A + 1 || K]</em>{Alice}$.

• Provides mutual authentication.
• However, session key is sent in plain text (signed but not encrypted).

Secure Mutual Authentication and Session Key Exchange

1. Alice says, "I am Alice" and gives random number $R_A$.
2. Bob selects session key $K$ and sends ${{[R<em>A || K]</em>{Bob}}_{Alice}}$.
3. Alice sends ${{[R<em>A + 1 || K]</em>{Alice}}_{Bob}}$.

• Provides mutual authentication and a secret session key.

Alternative Approach

1. Alice sends random number $R_A$.
2. Bob selects session key $K$ and sends $[{ {R<em>A || K}</em>{Alice}}]_{Bob}$.
3. Alice sends $[{{R<em>A + 1 || K}</em>{Bob}}]_{Alice}$.

• Also provides secure session key and mutual authentication.

Perfect Forward Secrecy

• Even if long-term keys are compromised, past session keys remain secret.

Perfect Forward Secrecy in Private Key Setting

• Alice and Bob share common key $K_{AB}$.
• Trudy records all ciphertext messages.
• Later, Trudy learns $K_{AB}$.
• Goal: Trudy should not be able to decrypt recorded messages.

Session Key Exchange (Insecure for Perfect Forward Secrecy)

• Alice encrypts session key $K<em>S$ with $K</em>{AB}$ and sends to Bob.
• All subsequent messages encrypted with $K_S$.
• Problem: Trudy can decrypt the first message to obtain $K_S$.

Using Diffie-Hellman for Perfect Forward Secrecy

• Use Diffie-Hellman key exchange to establish session key.
• Alice sends $g^a \mod p$ to Bob.
• Bob sends $g^b \mod p$ to Alice.
• Session key is $g^{ab}$.
• Ephemeral: Alice and Bob forget $a$ and $b$ after the session.
  *Man in the Middle Attack is possible