Authentication

Authentication Notes

Recap of Memory Attacks and Defenses

• Malicious User Input

  • Malicious reads

  • Malicious writes

System Security Model

• Need to define who has access to what (Policy)

• Authentication and authorization

• Implemented with Cryptographic Protocols (Mechanisms)

• From now on, system is considered as a whole

• Today's focus: Authentication

Overview of Authentication

• Introduction to Authentication Concepts

• Guard Model: mediating access to resources

• Crypto Refresher: foundational cryptographic primitives

• Machine to Machine Authentication (Key Sharing)

• User to Machine Authentication

  • Password authentication

  • Multifactor authentication

  • Biometric authentication

• Kerberos and Single Sign On

Guard Model

• System has resources to protect.

• Security principals request access:

  • User

  • Machine

• Guard mediates access:

  • Reads policy

  • Writes to Audit logs

  • Grants access

Gold Standard of Guard Model

• Authentication

• Authorization

• Audit

Security Principles

• Single Mediator

• TCB (Trusted Computing Base): Guard is TCB

• Should minimize TCB

Authentication

• Principal proves their identity.

• Convincing proof based on:

  • Something it knows

  • Something it has

  • Something it is

• Security goals:

  • B cannot convince C that it is A

• How to authenticate a person who:

  • Never met you before?

  • Met you before?

Types of Authentication

• User to machine: User authenticates to AWS.

• Machine to machine: Services authenticate each other.

Crypto Refresher

• Need to analyze the security of authentication methods.

• Existing Building Blocks of Authentication:

  • Encryption

  • Hash

  • Signatures

  • Protocols

• Security Guarantees

• Assumptions

• Complexity of brute-force attacks

• Information theory

Symmetric Encryption

• Correctness: $Decrypt(K, Encrypt(K, M)) = M$

• Security: Indistinguishability, negligible advantage over random chance to guess a plaintext.

• Brute force attack?

• Symmetric in Practice

  • AES

  • Block cipher modes of operation

    • ECB

    • CBC

    • CTR

AES: Widely-used Block Cipher Algorithm

• Successor to (US-selected) DES

• Officially adopted for US government work; voluntarily adopted by the private sector

• Winning cipher was Rijndael (pronounced Rhine-doll)

  • Belgian designers: Joan Daemen & Vincent Rijmen

• Adopted by NIST in Nov 2001

• Key size: {128, 192, 256}-bit

• High-speed cipher

  • Software: 28 cycles/byte

  • Intel’s AES-NI: 3.5 cycles/byte

Block Cipher Modes of Operation

• ECB: Electronic codebook

• CBC: Cipher block chaining

• CTR: Counter mode

Electronic Code Book Mode (ECB)

• Natural approach for encryption: Given a message M, split M up into blocks of size $b$ bits (where $b$ = input size of block cipher), $M<em>1, …, M</em>n$

• Last block includes “padding.”

• $E<em>K(M) = E</em>K(M<em>1) || E</em>K(M<em>2) || … || E</em>K(M_n)$

  • $||$: concatenation

• $C<em>j = F</em>K(P<em>j) = E</em>K(P_j)$

• $P<em>j = F^{-1}</em>K(C<em>j) = D</em>K(C_j)$

• Advantages

  • Simple to compute

  • Computation is parallelizable

• Disadvantages

  • Same plaintext always corresponds to the same ciphertext.

  • Traffic analysis yields which ciphertext blocks are equal, revealing which plaintext blocks are equal.

  • Adversary may be able to guess part of plaintext and decrypt parts of a message if the same ciphertext block occurs.

Problems of ECB Mode

• Semantic security: If the adversary had to guess the value of a single plaintext bit, they can guess at best at random.

• Simply put, even when the plaintext is the same, the resulting ciphertext must be completely different.

Cipher Block Chaining (CBC)

• $C<em>j = F</em>K(P<em>j ⊕ C</em>{j-1}) = E<em>K(P</em>j ⊕ C_{j-1})$

• $P<em>j = F^{-1}</em>K(C<em>j) ⊕ C</em>{j-1} = D<em>K(C</em>j) ⊕ C_{j-1}$

• $C_0 = IV$ called initialization vector

• Advantages

  • Semantic security

• Disadvantages

  • Encryption cannot be parallelized (but decryption can)

Counter Mode (CTR)

• $X_1 = IV$ called initialization vector

• $X<em>j = X</em>1 + j – 1$

• $C<em>j = F</em>K(X<em>j) ⊕ P</em>j = E<em>K(X</em>j) ⊕ P_j$

• $P<em>j = F</em>K(X<em>j) ⊕ C</em>j = E<em>K(X</em>j) ⊕ C_j$

• Advantages

  • Semantic security

  • Can be parallelized

Asymmetric Encryption

• Also known as public-key encryption

• Correctness: $Decrypt(SK, Encrypt(PK, M)) = M$

• Security: Indistinguishability, negligible advantage over random chance to guess a plaintext.

• Brute Force Attack, Factoring

• Asymmetric in Practice: RSA, ElGamal

Public-key encryption

• Receiver (Alice) generates $(pk, sk)$ and sends $pk$ to Bob OR publicizes her $pk$ (e.g., her webpage, central database).

• Assume that intended parties receive pk via authenticated channels (what if there’s no such channel? Covered via PKI)

• Anyone with pk can encrypt the message.

• Only the one with $sk$ can decrypt the message.

• Cannot decrypt with pk (Eve may encrypt but can’t decrypt).

Digital Signature

• Only the one with $sk$ can generate signature $σ$ for message $m$.

• Anyone with $pk$ can verify the signature.

• Public verifiability

• Non-repudiation: signed document becomes proof that Alice indeed signed the document.

• Assume that intended parties receive pk via authenticated channels (e.g., PKI)

Hash

• Security

  • Pre-image resistance: Non-invertibility (one-way function)

  • Collision resistance: Finding two messages that generate the same hash value should be difficult.

• Why this is important?

Message Authentication Code (MAC)

(For content and parties) (using a symmetric key)

• Security

  • No valid tag without a shared key $K$.

• MAC in Practice: HMAC, CBC-MAC

Digital Signature

• Correctness: Same as asymmetric key

• Security

  • Only the private key owner can create (Non-repudiation)

  • Cannot forge

• In practice: RSA

Machine to Machine Authentication (Key Sharing)

• Recall Guard Model: Principal is a software client, Guard is a server

• Assumption:

  • Public key crypto available

  • Public keys valid and available

• Goal: Attacker cannot impersonate

Sharing a symmetric key for communication

• Use public-key encryption

• Protocol

  • Alice generates symmetric key

  • Alice sends:

    • Encrypted symmetric key

    • Digital signature of symmetric key

  • Bob decrypts symmetric key

  • Verifies Alice’s signature and decrypted content

• Attack Model: Network Attacker, Bob?

Attack: Bob impersonates Alice

• Pass signature verification

• $H(Dec(SK<em>{res}, C)) = Verif(SK</em>a, Sign)$

• Need to produce the signature of Alice

• Resend same

• Content in signature and encryption Should match

• Use Decrypted content

• Defense: Add receiver details (e.g., ID) to signature

Prove ownership of a shared key

• Shared key already generated (e.g., DH key agreement protocol)

• Mutual proof of ownership

• Protocol

  • Both generate random number

  • Each encrypt the random number with a shared key

  • Both decrypt and verify the random number

• Attack Model: Network Attacker, Alice, Bob

Attack: Charlie impersonates Alice

• Need to produce Encryption of $R_b$

• Cannot do without $K_{ab}$

• Ask Bob to create it

• Defense: No interleaving, Keep track of sessions

Machine to Machine Authentication Summary

• Cryptographic Protocols

  • Works well if done right

  • Mechanism/policy issues may arise

• What was the issue with two previous attacks?

• Protocol Design verification is important

User to Machine Authentication

• Recall Guard Model: Principal is a human (can be sloppy, limited memory), Guard is a server

• Human Matters (Security Principle): Usability and convenience!

• Weak Mechanisms (Easy Protocols): Password (or multifactor)

• Goal: Attacker cannot impersonate

User to Machine Authentication: Prove the identity with something known

• Registration

• Authentication

• Recovery

• Protocol

• Attacker Model: Network attacker, Server

Threat Model: User to Machine Authentication

Threat 1: Guess

• Guess user password with Available information

• Best Practice:

  • Hard to guess

  • Easy to remember

• Practice: do not even pick a password

• Strong password:

  • Letter, Number, Special character

  • Start with base word

  • Add substitutions

  • More randomness

• Attack:

  • Still guess if not long enough

• Best Practice

  • Easy to remember long enough password

Threat 2: Phishing

• Impersonate a server/website to the user

  • Similar url

  • Similar website content

• Attack: Homoglyphs attack

• Best Practice:

  • Do not click on random links

  • Look for domain name on browser

  • Look for https sign/padlock

  • Checks in browser

Threat 3: Attacking Storage

• Read and interpret password storage/server

• Best Practice:

  • Store password hash (/etc/shadow)

• Attack: Invert Hash

  • Given $H(M) = c$, find a corresponding $M$

  • Theoretically exponential time, practically can manage

• Attack: Dictionary attack

  • Given $H(M) = c$, check all possible $M$’s from dictionary

  • Less expensive than hash brute force: Poor man’s brute force, Large table

• Attack: Rainbow table (Efficient way to store dictionary of hashes)

• Store password hash salt value: $H(M || r) = H(‘dileepa’ || 12345)$

  • Dictionary attack is harder

• Nested Hashing: $H(H(H…$

  • Long time for brute force

• Slow hash function

Threat 4: Attacking Network

• Read, Resend, Modify messages in Network

• Best Practice:

  • Send encrypted password for verification

  • Do not send password for verification

  • Challenge/response (2nd protocol in Machine Authentication)

• Attack: Server knows the password, At least at registration, Server can impersonate the user

• Best Practice

  • Secure remote password (Password-authenticated Key Exchange)

  • Register some form of hash

One-way hash chain

• Versatile cryptographic primitive

• Construction

  • Pick random $r_N$ and public one-way function $F$

  • $r<em>i = F(r</em>{i+1})$

  • Secret value: $r<em>N$, public value: $r</em>0$

• Properties

  • Use in reverse order of construction: $r<em>0, r</em>1, …, r_N$

  • Infeasible to derive $r<em>i$ from rj (j<i)

S/KEY

One-time password authentication using a one-way hash chain

• Consider a setting where a user authenticates herself with password $W$ over an insecure communication channel.

• Password registration must be done in a secure way.

Multifactor Authentication

Password Augmented with Something You Have

• Password Threat

  • Guess

  • Phish

• Best practice: Augment with something you have (Phone, Hardware token, dongle)

SMS OTP

• User logins with password

• Server sends OTP to mobile, valid for $X$ minutes

• Server stores OTP until it expires

• Attack

  • Network attacker: SMS is plaintext

  • Phone malware

• Goal: Intercept OTP

Time-based OTP

• Token and Server share

  • Key $K$, Synchronized clock

  • $X = F(K, time)$

  • Example $F$: SHA256, AES

  • Server computes same

• Attacker: monitor network, See sequence of $X<em>0, X</em>1,..X_{n}$

• Goal: Attacker cannot guess $X_{n+1}$

Counter-based OTP

• Token and Server share

  • Key $K$, Shared counter $C$

  • $X = F(K, C)$

  • Increase $C$

• Attacker: monitor network, See sequence of $X<em>0, X</em>1,..X_{n}$

• Goal: Attacker cannot guess $X_{n+1}$

Time-based vs Counter-based OTP

• Time based: Time difference between generation and receipt

• Counter based: Some responses being lost in network

• Allow any token within a window

• Attack: Easier to guess

Challenge Response

• Server, Token share $K$

• Server sends challenge $r$

• User types response $F(K, r)$

• Attacker: monitor network, See sequence of $X<em>0, X</em>1,..X_{n}$

• Goal: Attacker cannot guess $X_{n+1}$

• Attack: Man in the middle

  • Best practice: Have url of server as part of the token, Sign the hash

Biometric Authentication

Password Augmented with Something You Are

• Augment with something you are: Fingerprint, Face image, Keystroke, Gait etc.

• In device, Over the network

• Attack: Replay, Theft, Coercion

Passkey

• Based on public-key cryptography

• Authentication without password

• Use biometrics etc. for (local) user verification

Key Distribution Center (KDC)

• A KDC facilitates mediated authentication.

• The KDC stores the secret keys it previously established securely with each user.

• If there are n users, then there are n keys.

• When Alice (Bob) wants to establish a secure channel to Bob (Alice), (s)he first establishes a secure connection with the KDC.

• KDC next sends a randomly generated session key $K_{AB}$ to Alice (Bob).

• Alice and Bob next use $K_{AB}$ to secure communication.

• From Alice’s point of view, since she trusts KDC, the user who has $K_{AB}$ must be Bob, and vice-versa.

KDC vs PKI

• KDC plays similar roles as the CA in PKI in managing keys.

• A KDC distributes keys to two users who have not met before, revokes users, verifies the users during registration, etc.

• KDC: symmetric keys. PKI: asymmetric keys.

• A KDC knows all the secret keys it shares with the users.

• In PKI, a CA does not know the private key of any user, even if it has signed the user’s certificate.

• KDC must be online at least during the key distribution phase.

• CA can be offline after certificates are issued.

Mediated Authentication with KDC

• The Needham-Schroeder Authentication protocol is designed for Key Distribution Center (KDC) to “mediate” a session key between two users.

• Variants of the Needham-Schroeder authentication protocol are adopted in various applications

  • E.g., Kerberos, used in Windows Service Active Directory

• KDC keeps a shared secret with each user.

• KDC is a trusted “big-brother”. It knows all the secrets and is always online.

Needham-Schroeder protocol

1. Alice → KDC: “IDA wants to talk to IDB” $|| N1$

2. KDC → Alice: $E(K<em>{a,kdc}, N1 || “IDB” || K</em>{a,b} || ticket)$

   • where $ticket = E(K<em>{b,kdc}, K</em>{a,b} || “IDA”)$

3. Alice → Bob: $ticket || E(K_{a,b}, N2)$

4. Bob → Alice: $E(K_{a,b}, N2 - 1, N3)$

5. Alice → Bob: $E(K_{a,b}, N3 - 1)$

• $K_{a,kdc}$: A long-term key (master key) shared by Alice and KDC.

• $K_{b,kdc}$: A long-term key (master key) shared by Bob and KDC.

• $K_{a,b}$: The session key to be generated.

• Steps (3), (4) & (5) are for mutual authentication of Alice and Bob.

Kerberos

• Kerberos authentication protocol is based on Needham-Schroeder.

• History:

  • Kerberos is an authentication service developed as part of Project Athena at MIT.

  • Version 4 is designed at MIT in 1987 (Because version 4 uses DES, which is regulated by US’s export law.)

  • Version 5, designed by John Kohl and Clifford Neuman, appeared as RFC 1510 in 1993 (obsoleted/superseded by RFC 4120 in 2005). Version 5 does not restrict the type of encryption used.

  • Windows Server employed a variant of Kerberos as their default authentication method.

  • Designed to be transparent to users and enable Single Sign-on

Kerberos Authentication Process

Consider the scenario where the user C logs in to a workstation, and later C wants to access the network resource V. There are 6 steps involved.

• First, user C logs in to a workstation. The workstation then carries out these 2 steps:

  1. Using credential that is derived from user C’s password, user C (the workstation performs this on behalf of the user) convinces AS that he is authentic.

  2. AS gives user C a ticket, t1. The workstation should “forget” the password and keep only t1 and a derived key.

• Now, user C wants to access resource V (e.g., printer).

  3. Using credential based on t1, user C convinces TGS that he had successfully login.

  4. TGS gives C another ticket t2.

  5. Using credential based on t2, user C convinces resource V that he is authorized to use the resources.

  6. One more step to ensure that V is not impersonated.

Note that there is no communication between TGS and AS. In many configurations, TGS and AS reside in the same server.

Kerberos v4 Message Exchange

• $K_c$: C’s key shared with AS

• $K_{tgs}$: TGS’s key shared with AS

• $K_{c,tgs}$: Session key for C and TGS

• $Ticket_{tgs}$: Ticket Granting Ticket

• $K_v$: V’s key shared with TGS

• $K_{c,v}$: Session key for C and V

• $Ticket_v$: Service Granting Ticket