Simple Authentication Protocols I
CS 3IS3
Ryszard Janicki
Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada
Acknowledgments: Material based on Information Security by Mark Stamp (Chapters 9.1-9.3)
Ryszard Janicki
Simple Authentication Protocols I 1/32
Protocols
Human protocols – the rules followed in human interactions Example: Asking a question in class
Networking protocols – rules followed in networked communication systems
Examples: HTTP, FTP, etc.
Security protocol – the (communication) rules followed in a security application
Examples: SSL, IPSec, Kerberos, etc.
Protocol flaws can be very subtle
Several well-known security protocols have significant flaws Including WEP, GSM, and IPSec
Implementation errors can also occur Some implementation of SSL
Not easy to get protocols right. . .
Ryszard Janicki
Simple Authentication Protocols I 2/32
Ideal Security Protocol
Must satisfy security requirements Requirements need to be precise
Efficient
Minimize computational requirement Minimize bandwidth usage, delays. . .
Robust
Works when attacker tries to break it Works if environment changes (slightly)
Easy to implement, easy to use, flexible. . . Difficult – if not impossible – to satisfy all of these!
Ryszard Janicki
Simple Authentication Protocols I 3/32
Popular Simple Protocols
Secure Entry to CIA Building
1 Insert badge into reader
2 Correct badge?
Yes? go to 3
No? Get shot by security guard
3 Enter PIN
4 Correct PIN? Yes? Enter
No? Get shot by security guard
ATM Machine Protocol
1 Insert ATM card
2 Correct card and insert properly?
Yes? go to 3
No? go to 1 (ATM may eat card after a few failures)
3 Enter PIN
4 Correct PIN?
Yes? Conduct your transaction(s) No? Machine (eventually) eats card
Ryszard Janicki
Simple Authentication Protocols I 4/32
Authentication
Alice must prove her identity to Bob
Alice and Bob can be humans or computers
May also require Bob to prove he’s Bob (mutual authentication)
Probably need to establish a session key May have other requirements, such as
Public keys, symmetric keys, hash functions, . . .
Anonymity, plausible deniability,perfect forward secrecy, etc.
Authentication on a stand-alone computer is relatively simple For example, hash a password with a salt
“Secure path”, attacks on authentication software, keystroke logging, etc., can be issues
Authentication over a network is challenging Attacker can passively observe messages
Attacker can replay messages
Active attacks possible (insert, delete, change)
Ryszard Janicki
Simple Authentication Protocols I 5/32
Simple Authentication
Simple Authentication
“I’m Alice”
Prove it
My password is “frank”
Alice
Bob
Simple and may be OK for standalone system Simple and may be OK for standalone system
But highly insecure for networked system Subject to a replay attack (next)
But highly insecure for networked system
o Subject to a replay attack (next 2 slides) Also, Bob must know Alice’s password
o Also, Bob must know Alice’s password
Part 3 Protocols 13
Ryszard Janicki
Simple Authentication Protocols I 6/32
Authentication Attack
Authentication Attack: A reply attack
Part 3 Protocols 14 ——————————————————————-
“I’m Alice”
Prove it
My password is “frank”
Trudy
Bob
No real prevention! Also password can be stolen.
“I’m Alice”
Prove it
My password is “frank”
Alice
Bob
Authentication Attack
Trudy
This is an example of a repla
Ryszard Janicki
y attack
Simple Authentication Protocols I 7/32
Two Other Simple Authentications
More efficient, but the same problem as previous version
More efficient, but…
“I’m Alice”
… same problem as previous version
Prove it h(Alice’s password)
rt 3 Protocols Alice
16
Bob
Pa
This approach hides Alice’s password
This approach hides Alice’s password From both Bob andTrudy
o From both Bob and Trudy
But still subject to replay attack
I’m Alice, my password is “frank”
Alice
Bob
But still subject to replay Ryszard Janicki
attack
Simple Authentication Protocols I 8/32
Better Authentication
Challenge-Response I
To prevent replay, use challenge-response Goal is to ensure “freshness”
Suppose Bob wants to authenticate Alice Challenge sent from Bob to Alice
Challenge is chosen so that. . .
Replay is not possible
Only Alice can provide the correct response Bob can verify the response
To ensure freshness, one can employ a nonce Nonce = number used once
What to use for nonces?
That is, what is the challenge?
What should Alice do with the nonce? That is, how to compute the response?
How can Bob verify the response? Should we use passwords or keys?
machines: keys, humans: passwords
Ryszard Janicki
Simple Authentication Protocols I 9/32
Challenge-Response
…encryption is much better here (why?)
Challenge-Response II
Nonce is the challenge Nonce is the challenge
The hash is the response The hash is the response
Nonce prevents replay (ensures freshness)
NonPcaesspwroerdveisntssomretphlianyg(Aelnicseurkensowfsreshness)
Generic Challenge-Response
Password is something Alice knows Generic Challenge-Response
Note: Bob must know Alice’s password to verify
Note: Bob must know Alice’s pwd to verify
Part 3 Protocols
“I’m Alice” Nonce
20
Bob
Alice
Something that could only be from Alice, and Bob can verify
In practice, how to achieve this?
In practice, how to achieve this? Hashed password works, but. . .
Hashed password works, but…
. . . encryption is much better here
“I’m Alice” Nonce
h(Alice’s password, Nonce)
Bob
Alice
Ryszard Janicki
Simple Authentication Protocols I 10/32
Authentication with Symmetric Key
Encrypt plaintext P with key K: C = E(P,K) Decrypt ciphertext C with key K: P = D(C,K)
Here, we are concerned with attacks on protocols, not attacks on cryptography
So, we assume cryptographic algorithms are secure
Alice and Bob share symmetric key K
Key K known only to Alice and Bob
Authenticate by proving knowledge of shared symmetric key
How to accomplish this?
Cannot reveal key, must not allow replay (or other) attack,
must be verifiable, . . .
Ryszard Janicki
Simple Authentication Protocols I 11/32
Authenticate Alice Using
Authenticate Alice Using Symmetric Key
Symmetric Key
Alice, K
“I’m Alice” R E(R,K)
Bob, K
Secure method for Bob to authenticate Alice But, Alice does not authenticate Bob
Secure method for Bob to authenticate Alice
But, Alice does not authenticate Bob So, can we achieve mutual authentication?
So, can we achieve mutual authentication? Part 3 Protocols 24
Ryszard Janicki
Simple Authentication Protocols I 12/32
Mutual Authentication?
Mutual Authentication?
What’s wrong with this picture?
W“hAaltic’es” wcoruoldngbewTirtudhy t(ohrisanpybicodtyurelese?)!
“Alice” could be Trudy (or anybody else)! Part 3 Protocols 25
Alice, K
“I’m Alice”, R E(R,K)
E(R,K)
Bob, K
Ryszard Janicki
Simple Authentication Protocols I 13/32
Mutual Authentication
Since we have a secure one-way authentication protocol. . . The obvious thing to do is to use the protocol twice
Mutual Authentication
Once for Bob to authenticate Alice
O
ob
f
en
nce
This has got to work. . .
or
Ali
ce
to a
tic
ate
B
Alice, K
“I’m Alice”, RA RB, E(RA, K)
E(RB, K)
Bob, K
This provides mutual authentication. . .
This provides mutual authentication… . . . or does it? Subject to reflection attack
uth
…or does it? Subject to reflection attack
o Next slide
Ryszard Janicki
Simple Authentication Protocols I 14/32
Mutual Authentication Attack
Mutual Authentication Attack
1. “I’m Alice”, RA 2. RB, E(RA, K)
Trudy
Bob, K
3. “I’m Alice”, RB 4. RC, E(RB, K)
Trudy
Bob, K
Part 3 Protocols 28
Ryszard Janicki
Simple Authentication Protocols I 15/32
Symmetric Key Mutual Authentication
Our one-way authentication protocol is not secure for mutual authentication
Protocols are subtle!
Symmetric Key Mutual
In this case, “obvious” solution is not secure
Also, if assumptions or environment change, protocol may not
This is a common source of security failure be secureAuthentication
For example, Internet protocols
Mutual Authentication:
“I’m Alice”, RA RB, E(“Bob”,RA,K)
E(“Alice”,RB,K)
Alice, K
Bob, K
Do these “insignificant” changes help?
Do these “insignificant” changes help? Yes!
Ryszard Janicki
Simple Authentication Protocols I 16/32
Yes!
Public Key Notation
Encrypt M with Alice’s public key: {M}Alice Sign M with Alice’s private key: [M]Alice Then
[{M}Alice]Alice = M {[M]Alice}Alice = M
Anybody can use Alice’s public key Only Alice can use her private key
Ryszard Janicki
Simple Authentication Protocols I 17/32
Public Key Authentication
Is this secure?
We may try to prevent this by having two key pairs
Not secure! Trudy can get Alice to decrypt anything!
Trudy can get Alice to decrypt anything! Pa
“I’m Alice”
rt 3 Protocols Alice
Prevent this by having two key pairs
R [R]Alice
32
Bob
Is this secure?
Same a previous – should have two key pairs
Not secure! Trudy can get Alice to sign anything!
“I’m Alice” {R}Alice
R
Public Key AuthenticatioBonb Alice
Trudy can get ARlysizcardeJantickoi
siSgimnple aAuntheyntticahtioinnPrgoto!cols I 18/32
Session Keys
Generally, a bad idea to use the same key pair for encryption and signing
Instead, should have. . .
. . . one key pair for encryption/decryption and signing/verifying signatures. . .
. . . and a different key pair for authentication
Usually, a session key is required
A symmetric key for current session Used for confidentiality and/or integrity
How to authenticate and establish a session key (i.e., shared symmetric key)?
When authentication completed, Alice and Bobshare a session key
Trudy cannot break the authentication. . .
. . . and Trudy cannot determine the session key
Ryszard Janicki
Simple Authentication Protocols I 19/32
Authentication and Session Key
“I’m Alice”, R {R, K}Alice
{R +1, K}Bob
Alice Bob Is this secure?
Is this secure?
o Alice is authenticated and session key is secure Alice is authenticated and session key is secure
o Alice’s “nonce”, R, useless to authenticate Bob The key K is acting as Bob’s nonce to Alice
Alice’s “nonce”, R, useless to authenticate Bob
o The key K is acting as Bob’s nonce to Alice No mutual authentication
No mutual authentication
Part 3 Protocols
Ryszard Janicki
36
Simple Authentication Protocols I
20/32
Authentication & Session Key
and Session Key Public Key Authentication
o See the next slide…
Public Key Authentication and Session Key I
Is this secure?
Mutual authentication (good), but. . .
o … session key is not protected (very bad) “I’m Alice”, R
Part 3 Protocols {[R, K] } Bob Alice
Alice {[R +1, K]Alice}Bob
Is this secure?
and Session Key o Mutual authentication (good), but…
. . . session key is notprotected (very bad)
37
Bob
Is this secure?
Is this secure?
No! It is subject to subtle ‘Man in the Middle’ attack
“I’m Alice”, R [R, K]Bob
[R +1, K]Alice
Alice
Bob
No! It’s subject to subtl Ryszard Janicki
e MiM attack
Simple Authentication Protocols I 21/32
Public Key Authentication
Public Key Authentication and Session Key II
and Session Key
Man in the Middle Attack:
1. “I’m Alice”, R 4. { }Alice
Alice 5. {[R +1, K]Alice}Bob
Trudy
2. “I’m Trudy”, R 3. {[R, K]Bob}Trudy
6. time out Bob
Trudy can get [R, K]
Public Key Authentication
and K from 3. Alice uses this same key K
Trudy can get [R,K]Bob and K from 3.
Bo
Alice uses this same key K
And Aalicne dthinSks eshse’stiaolking tKo Beoyb
And Alice thinks she’s talking to Bob Secure Solution:
Part 3 Protocols 39
“I’m Alice”, R
[{R, K}Alice]Bob [{R +1, K}Bob]Alice
Alice
Bob
Anyone can see {R,K}Alice and {R +1,K}Bob. Is this secure?
b
Ryszard Janicki
Simple Authentication Protocols I 22/32
Seems to be OK
Timestamps
A timestamp Tis derived from current time
Timestamp scan be used to prevent replay Used in Kerberos, for example
Timestamps reduce number of messages (good) A challenge that both sides know in advance
“Time” is a security-critical parameter (bad)
Clocks not same and/or network delays, so must allow for
clock skew – creates risk of replay How much clock skew is enough
Ryszard Janicki
Simple Authentication Protocols I 23/32
Secure Public Key Authentication with Timestamp T Public Key Authentication
with Timestamp T “I’m Alice”, {[T, K]Alice}Bob
{[T +1, K]Bob}Alice
Alice Bob
Secure mutual authentication
Secure mutual authentication? Session key secure?
Seems to be OK
Part 3 Protocols
Ryszard Janicki
42
Simple Authentication Protocols I
24/32
Insecure PwubitlichKTeyiAmuethsenttaicmatipon Twith Timestamp T
“I’m Alice”, [{T, K}Bob]Alice [{T +1, K}Alice]Bob
Public Key Authentication
Alice Bob
with Timestamp T
Trudy can use Alice’s public key to find {T,K} and
Secure authentication and session key? Bob then. . .
Part
Trudy can use Alice’s public key to find
{T, K}
3 Protocols Trudy
“I’m Trudy”, [{T, K} ] and then… Bob Trudy
[{T +1, K}Trudy]Bob
Bob
Trudy obtains Alice-Bob session key K
Trudy obtains Alice-Bob session key K
Note: Trudy must act within clock skew
Note: Trudy must act within clock skew
43
Bob
Ryszard Janicki
Simple Authentication Protocols I 25/32
Public Key Authentication
Sign and encrypt with nonce. . .
Insecure
Encrypt and sign with nonce. . .
Secure
Sign and encrypt with timestamp. . .
Secure
Encrypt and sign with timestamp. . .
Insecure
Protocols can be subtle!
Ryszard Janicki
Simple Authentication Protocols I 26/32
Public Key Authentication
Another Secure Public Key Authentication with
Timestamp T
with Timestamp T “I’m Alice”, [{T, K}Bob]Alice
[{T +1}Alice]Bob
Is this “encrypt and sign” secure? o Yes, seems to be OK
Does “sign and encrypt” also work here?
Alice
Bob
Secure mutual authentication
Part 3 Protocols
Ryszard Janicki
Simple Authentication Protocols I 46 27/32
Perfect Forward Secrecy
Consider this “issue”. . .
Alice encrypts message with shared key K and sends ciphertext
to Bob
Trudy records ciphertext and later attacks Alice’s (or Bob’s) computer to recover K
Then Trudy decrypts recorded messages
Perfect forward secrecy (PFS): Trudy cannot later decrypt recorded ciphertext
Even if Trudy gets key K or other secret(s) Is PFS possible?
Suppose Alice and Bob share key K
For perfect forward secrecy, Alice and Bob cannot use K to encrypt
Instead they must use a session key KS and forget it after it was used
Can Alice and Bob agree on session key KS in a way that provides PFS?
Ryszard Janicki
Simple Authentication Protocols I 28/32
Naïve Session Key Protocol
Na ̈ıve Session Key Protocol
Trudy could record E(K , K) Trudy could record E(KS,K) S
E(KS, K) E(messages, KS)
Alice, K
Bob, K
If Trudy later gets K then she can get K If Trudy later gets K then she can get KS S
o Then Trudy can decrypt recorded messages No perfect forward secrecy in this case
Then Trudy can decrypt recorded messages
No perfect forward secrecy in this case Part 3 Protocols 49
Ryszard Janicki
Simple Authentication Protocols I 29/32
Perfect Forward Secrecy
Perfect Forward Secrecy (Method 1)
We can use Diffie-Hellman for PFS
We can use Diffie-Hellman for PFS Recall: public g and p
Recall: public g and p
ga mod p gb mod p
Alice, a
Bob, b
BuBtuDtiffiDief-fHiel-lmHaenllmisasnubisjesctubtojeMctiMto(MaiMn in the Middle) Perfect Forward Secrecy
How to get PFS and prevent MiM?
How to get PFS and prevent MiM?
Part 3 Protocols
Alice: K, a
E(ga mod p, K) E(gb mod p, K)
5
Bob: K, b
Session key K = g mabod p
Session keSy K = g mod p
Alice forgets a, Bob forgets b
Alice forgets a, Bob forgets b
S
ab
This is known as Ephemeral Diffie-Hellman NeitThheirsAislickenonworn BaosbEcpahnemlaeterralreDcoifvfeire-KHellman
Neither Alice nor Bob can later recover K S
Are there other ways to achieve PFS?
S
0
Ryszard Janicki
Simple Authentication Protocols I 30/32
Are there other ways to achieve PFS?
Diffie-Hellman
Recall: Diffie-Hellman Man-In-the-Middle (MiM) Attack
Subject to man-in-the-middle (MiM) attack
ga mod p gt modp
gt mod p gb modp
Alice, a
Trudy, t
Bob, b
Part 1 Cryptography 126 How to prevent MiM attack?
at at
mod p with Alice
Trudy shares secret g
An attacker Trudy shares secret g mod p with Alice
Trudy shares secret gbt mod p with Bob Trudy shares secret gbt mod p with Bob
Alice and Bob don’t know Trudy is MiM Alice and Bob don’t know Trudy is MiM
Encrypt Diffe-Hellman exchange with symmetric key Encrypt Diffie-Hellman exchange with public key Sign Diffie-Hellman values with private key
You MUST be aware of MiM attack on Diffie-Hellman Key Exchange. We will discuss this issue later at the end of this course.
Ryszard Janicki
Simple Authentication Protocols I 31/32
Mutual Authentication, Session Key and PFS
Mutual Authentication, Session Key and PFS
“I’m Alice”, RA RB, [RA, gb mod p]Bob
[RB, ga mod p]Alice
Alice
Bob
Session key is K = gab mod p Session key is K = gab mod p
Alice forgets a and Bob forgets b Alice forgets a and Bob forgets b
If Trudy later gets Bob’s and Alice’s secrets, recover session key K
If Trudy later gets Bob’s and Alice’s secrets, she cannot
she cannot recover session key K
Part 3 Protocols 52
Ryszard Janicki
Simple Authentication Protocols I 32/32