1
Authentication Protocols
曹天杰
Cao Tianjie
tjcao@cumt.edu.cn
中科院软件所信息安全国家重点实验室
2003.4.21
2
Introduction
? Cryptographic protocol
– Distributed algorithm
– Based on cryptographic building blocks
– To achieve a security related goal
? Examples,
– Entity Authentication
– Key Establishment:Key Distribution(Key enveloping,
Key transport),Key agreement
– Electronic Payment
– …
3
authentication
Alice Bob
How does Bob know that Alice is Alice,not Eve?
insecure channel
Eve
(Eve owns the channel!)
Hi! I’m Alice
4
authentication
? Authentication is a means by which identity is
established,
? It allows one party to gain assurances about the
identity of another party in a protocol,and that
the second has actively participated,
? The goal of authentication is to achieve all this
over an insecure channel with an active attacker
and no shared secrets,
? Note,authentication must be combined with key
exchange to avoid session hijacking (after
authentication),
5
objectives of identification protocols
? If Alice and Bob are both honest,A is able to
successfully authenticate herself to Bob,i.e,Bob
will complete the protocol having accepted Alice’s
identity,
? Bob cannot reuse an identification exchange with
Alice so as to impersonate her in conversations with
others,
? The probability that Eve can successfully
impersonate Alice to Bob is negligible (e.g,
computationally difficult),
? All the above remain true even if Eve has seen many
previous authentication sessions between Alice and
Bob,has had experience in authenticating herself
with both,and multiple authentication sessions are
run simultaneously,
6
basis of identification
? Something you know
– Passwords,PINs,secret keys,your mother’s
maiden name
? Something you have
– Magnetic cards,smart cards,physical keys,
handheld password generators,
? Something you are
– biometrics (DNA,signatures,fingerprints,
voice,retinal patterns,hand geometries,
typing dialect/profiling),
7
basis of identification
– Biometrics have major problems in real
world situations
? How do you revoke keys?
? Biology is messy
–We leave DNA,fingerprints everywhere
- just ask OJ
? How do you give a mugger your
fingerprint?
? How do you authenticate if he’s just hit
you in the eye?
8
attacks on authentication
? Impersonation
? Replay
? Interleaving
– impersonation involving selective
combination of information from one or
more previous or simultaneous sessions
? Reflection
– an interleaving attack involving sending
information from an ongoing authentication
session back to the originator
9
attacks on authentication
? Forced delay
– adversary intercepts a message and relays it
at some later point in time (note,not the
same as replay)
? Chosen-text
– attack on challenge-response where an
adversary chooses challenges in an attempt
to extract the secret key
10
Eve
Simple Authentication,1st
Attempt
Alice Bob Alice,KAB
= KAB
11
Simple Authentication,2nd
Attempt
Eve
Alice Bob Alice,{Hello}KAB
{Hello}KAB
Alice,{Hello}KAB = K
AB
12
Simple Authentication,3rd
Attempt
Eve
Alice Bob Alice,{Alice,T}KAB
Alice,{Alice,T}KAB
{Alice,T}KAB
Detects replay
= KAB
13
Authentication,Summary
? Proof of knowledge
– By text encrypted with secret key (authenticator)
– Not by secret key itself
? Proof of freshness
– By included timevarying parameter
– Timestamp,counter,nonce (challenge-response)
Alice Bob Alice,{Alice,N}K
AB
N
14
Variations / Extensions
? One-way vs mutual authentication
? Guaranteeing freshness,
– Timestamps,simple,but requires clock
synchronisation
– Nonces,requires more messages,but no
synchronised clocks
– Counters,extra state has to be kept
15
passwords
? Passwords are the simplest (and weakest)
means of authentication,
? Password authentication is where a secret is
shared between two parties,To authenticate,
one party reveals their identity and their
password,
? Passwords are typically stored hashed on a
server in a password file (so if the server is
compromised,the passwords still needs to be
cracked),
Alice Bob insecure channel
Eve
Hi! I’m Alice,my password is,internet”
16
passwords have major problems
? Passwords can be eavesdropped
– facilitates replay attacks
? Passwords are reusable
– facilitates impersonation attacks by verifier
? Passwords usually come from a small keyspace
– facilitates brute force attacks
? Extremely low entropy
– English only has ~1.3bits/byte of real information
– dictionary attacks are possible
? note dictionary attacks today allow 1M guesses/second+ !
? Humans are extremely poor random number generators
– makes dictionary attacks even easier (or unnecessary)
? Humans are pathetic at remembering passwords and often
reuse (or alternate between) old passwords
– Even years later
17
salting passwords
? Adding a t-bit salt to passwords strengthens them against dictionary and
brute force attacks,
? Public salt (e.g,UNIX passwords)
userA saltA h(passwordA | saltA)
userB saltB h(passwordB | saltB)
– salt is chosen at random
– an adversary must hash a guessed password p 2t times to find if
p is a valid password (when password cracking)
– only works if there are enough users so the salts are all used
? e.g under UNIX there 4096 possible salts but most systems
have much less than 4096 users
– does not protect against an eavesdropper or evil sysadmin
18
one time passwords
? Each password is only used once
– an attempt to foil eavesdroppers and replay attacks
? Many variations
– shared list of one-time passwords
? tick each password off the list as used
– challenge response table
? system has a list of questions,picks one at
random
– sequentially updated one-time passwords
? during authentication under key i,the user
creates and transmits to the system the key to
use next time (i+1)
– one-time sequences based upon a one-way
function
? e.g,Lamport’s one-time scheme
19
lamport’s one time passwords (s/key)
Setup,
? User Alice picks a random generator g and computes a
hash chain,
w = hn(g) = h(h(h(….h(g))))
? Alice sends w to the server,
? Alice sets count ← n-1
Authentication,
? Alice sends x = hcount(g) to the server
? Alice sets count ← count - 1
? The server verifies h(x) = w
? The server sets w ← x
20
lamport’s one time passwords (s/key)
? Advantages
– Prevents eavesdropping
– No secrets are stored on the server
? Disadvantages
– A limited number of authentications before a new
hash chain must be set up
– Vulnerable to a pre-play attack if unused passwords
are compromised
w
g h()
h()
h() auth 1
auth 2
auth n
21
challenge-response authentication
? One entity proves it’s identity to another by
demonstrating knowledge of a secret without revealing
the secret itself,
? Done by providing a response to a time variant challenge,
where the response is dependent on the challenge and
the secret,
? Time variant parameters may be used to counter replay
and interleaving attacks,to provide uniqueness or
timeliness guarantees (e.g,freshness),and to prevent
certain chosen-cyphertext attacks,
– nonces
– sequence numbers aka serial numbers,counters
– timestamps
22
challenge-response using symmetric techniques
? Symmetric cypher or MAC
? r’ prevents a chosen plaintext attack (and as a challenge)
? Both the user and the server share secret key k (bad)
? Prevents eavesdropping
Alice Bob
pick random r’
“hello”
nonce r
Ek(r|r’) or hk(r|r’) verify D
k contains r
pick random r
23
challenge-response using asymmetric techniques
? Public-key Encryption/Decryption
? Digital signatures e.g,
? No secrets stored on the server
? Unlimited usage
? Prevents eavesdropping
Alice Bob
“hello”
nonce r
signA(r) verify signature
pick random r
24
Key Establishment Problem
? Scalability
– One secret key for each pair of principals
– n principals ? ? n2 keys needed
? Key Establishment
– Key agreement versus key transport/distribution
? Key Distribution
– Key generation and distribution when needed
– Central server,Key Distribution Center (KDC)
25
Key Distribution
Alice Bob
KDC
A,B,N,{A,T}KA
Generates KAB
{B,N,KAB}KA,{A,KAB}KB
KAB
{A,T}KAB,{A,KAB}KB
KAB
= KA
= KB
26
Key Distribution
? Key Distribution Centre (KDC)
– distributes keys on demand
– Session keys,
? Session key is sent
– directly to the client,{B,N,KAB}KA
– indirectly,through a ticket to the server,
{A,KAB}KB
27
Safe and Private Messages
? Once session key has been distributed,it
can be used for sending,
– private messages,{message}KAB
cannot be read by eavesdroppers (even not
man-in-the-middle)
– safe messages:MAC(KAB,message)
cannot be modified by outsiders
28
Login procedure
? Cryptographic keys
– Random bit strings
– Hard to remember
– Use passwords instead
? Authentication Server (AS)
– Checks (weak) login password
– Returns strong cryptographic key
– Single Sign-On
29
Login Procedure
Alice
AS
KDC
A,N
{KDC,N,KA}KPW,
{A,KA}KKDC
= KA
= KKDC
= KPW Generates KA
{A,KA}KKDC
30
Login Procedure
1 2
3
4
5
6
1,Request KA
2,Ticket Granting Ticket
3,TGT + Authenticator
4,Ticket for B
5,Ticket for B +
Authenticator
6,(Optional) Authenticator
KDC AS
Alice Bob
31
Analyzing Authentication
protocol
? The first is to find flaws in those protocols
that are not correct,In general,there are two
main types of trivial attacks,replay attacks
and substitution attacks,
? The second is to establish convincingly the
correctness of those that are,
32
Notational Conventions(1)
A
System principal A ( Alice )
B
System principal B (Bob)
S
Trusted Key Server
A ? B,X
A sending a message X to B
A ? I(B),X
A sending a message X to B,but X be
intercepted by intruder I
I(A) ? B,X
Intruder I impersonating A sending a
message X to B
Na,Nb Nonces generated by A and B
33
Notational Conventions(2)
T
Timestamp
Ma,Mb
Serial numbers
X,Y
Concatenation of message X and Y
Kas,Kbs
Secret keys shared with S
Kab
Session key between A and B
{X}
k
Encrypt X using key k
[X]k
Decrypt X using key k
?
Bit-wise exclusive-or operation (XOR)
34
man in the middle
? Problem,(Diffie-Hellman)
Eve owns the channel!
Alice Bob
“hello I’m Alice”
gx mod p
gy mod p
Session key = h(gxy mod p)
Eve
“hello I’m Alice”
gw mod p
gz mod p
Session key = h(gwz mod p)
35
man in the middle
? Problem,(Key Exchange with Public Key Crypto)
Eve owns the channel!
Alice Bob
“Alice”,eA
{“launch missiles at Eve”} eY
Eve
“Bob”,eB
“Alice”,ey,Bob”,eY
{“disarm missile system”} eB
36
session hijacking
? Problem,
Eve owns the channel!
Alice Bob
“hello I’m Alice”
nonce r
signA(r) verify signature
pick random r
Eve
,thanks guys,I’ll take it from here”
37
EKE - encrypted key exchange
? Alice and Bob share a secret key k (bad!)
? A (possibly low entropy) shared secret k is used to form a high
entropy shared secret h(gxy)
? Prevents eavesdropping
? Prevents an active attack on Diffie-Hellman
? Forward secrecy
Alice Bob
“hello”
{gx mod p}k
random y
random x
{gy mod p}k
Session key = h(gxy mod p)
38
definitions
? A protocol is said to have perfect forward secrecy if compromise
of long term keys does not compromise past (short term)
session keys,
? A protocol is vulnerable to a known-key attack if compromise of
past session keys allows an attacker to compromise of future
session keys (including actively impersonating)
39
Attacking Authentication with
Key Distribution protocols
? Freshness Attacks
? Type Flaws
? Parallel Session Attacks
? Implementation Dependent Attacks
? Binding Attacks
? Encapsulation Attacks
? Other Forms of Attack
40
Freshness Attacks(1)
? A freshness attack occurs when a
message (or message component) from
a previous run of a protocol is recorded
by an intruder and replayed as a
message component in the current run
of the protocol,
41
Freshness Attacks(2)
Needham Schroeder Symmetric Key
? 1,A -> S, A,B,Na
? 2,S -> A, {Na,B,Kab,{Kab,
A}Kbs}Kas
? 3,A -> B, {Kab,A}Kbs
? 4,B -> A, {Nb}Kab
? 5,A -> B, {dec(Nb)}Kab
A B
S
42
Freshness Attacks(3)
Needham Schroeder Symmetric Key
? i.1,A -> S, A,B,Na
? i.2,S -> A, {Na,B,Kab,{Kab,A}Kbs }Kas
? i.3,A -> I(B), {Kab,A}Kbs
? assume that Kab is compromised
? ii.3,I(A) -> B, {Kab,A}Kbs
? ii.4,B -> I(A), {Nb}Kab
? ii.5,I(A) -> B, {dec(Nb)}Kab
? Bit-string attack
A B
S
43
Type Flaws(1)
? A message consists of a sequence of
components each with some value (for
example,the name of a principal,the value
of a nonce,or the value of a key),The
message is represented at the concrete level
as a sequence of bits,
? A type flaw arises when the recipient of a
message accepts that message as valid but
imposes a different interpretation on the bit
sequence than the principal who created it,
44
Type Flaws(2)
Andrew Secure RPC
? 1,A -> B, A,{Na}Kab
? 2,B -> A, {succNa,Nb}Kab
? 3,A -> B, {succNb}Kab
? 4,B -> A, {K?ab,N?b}Kab
45
Type Flaws(3)
Andrew Secure RPC
? i.1,A -> B, A,{Na}Kab
? i.2,B -> A, {succNa,Nb}Kab
? i.3,A -> I(B), {succNb}Kab
? i.4,I(B) -> A,{succNa,Nb}Kab
? Freshness attacks
46
Type Flaws(4)
Otway Rees
? 1,A -> B, M,A,B,{Na,M,A,B}Kas
? 2,B -> S, M,A,B,{Na,M,A,B}Kas,{Nb,
M,A,B}Kbs
? 3,S -> B, M,{Na,Kab}Kas,{Nb,Kab}Kbs
? 4,B -> A, M,{Na,Kab}Kas
A B
S
47
Type Flaws(5)
Otway Rees
? i1,A -> I(B), M,A,B,{Na,M,A,B}Kas
? i4,I(B) -> A, M,{Na,M,A,B}Kas
A B
S
48
Type Flaws(6)
Otway Rees
? i1,A -> B, M,A,B,{Na,M,A,B}Kas
? i2,B -> I(S), M,A,B,{Na,M,A,B}Kas,
{Nb,M,A,B}Kbs
? i3,I(S) -> B, M,{Na,M,A,B}Kas,{Nb,M,
A,B}Kbs
? i4,B -> A, M,{Na,M,A,B}Kas
A B
I(S)
49
Parallel Session Attacks(1)
one-way authentication protocol,
? 1,A -> B, {Na}Kab
? 2,B -> A, {Na+1}Kab
50
Parallel Session Attacks(2)
one-way authentication protocol,
? i1,A -> I(B), {Na}Kab
? ii1,I(B) -> A, {Na}Kab
? ii2,A -> I(B), {Na+1}Kab
? i2,I(B) -> A, {Na+1}Kab
A I(B)
51
Parallel Session Attacks(3)
Wide Mouthed Frog
? 1,A -> S, A,{Ta,B,Kab}Kas
? 2,S -> B, {Ts,A,Kab}Kbs
A B
S
52
Parallel Session Attacks(4)
Wide Mouthed Frog
? i.1,A -> S, A,{Ta,B,Kab}Kas
? i.2,S -> B, {Ts,A,Kab}Kbs
? ii.1,I(B) -> S, B,{Ts,A,Kab}Kbs
? ii.2,S -> A, {T’s,B,Kab}Kas
? iii.1,I(A) -> S, A,{T’s,B,Kab}Kas
? iii.2,S -> B, {T??s,A,Kab}Kbs
? Replay attack
A B
S
53
Implementation Dependent
Attacks
Stream Ciphers
? 1,A -> B, {Na}Kab
? 2,B -> A, {Na+1}Kab
? On average the nonce will be odd half of the
time and so this form of attack has a half
chance of succeeding,
54
Binding Attacks(1)
? Suppose your public key is Ky and an
intruder's public key is Ki,
? if the intruder can convince others that your
public key is Ki then they will encrypt secret
information using Ki and this will be readable
by the intruder,
55
Binding Attacks(2)
? 1,C -> AS, C,S,Nc
? 2,AS -> C, AS,{AS,C,Nc,Ks}
? The certication authority AS is the repository
for principals? public keys,
? Here,a prospective client C wants to
communicate with S and needs the public
key Ks of S,
1asK?
56
Binding Attacks(3)
? i1,C -> I(AS), C,S,Nc
? ii1,I(C) -> AS, C,I,Nc
? ii2,AS) ->I(C), AS,{AS,C,Nc,Ki}
? i2,I(AS) -> C, AS,{AS,C,Nc,Ki}
? This attack was identied by Hwang and Chen,
They suggest that this problem can be solved by
explicitly including the identier of the requested
server S in message (2),
1asK?
1asK?
57
Encapsulation Attacks(1)
? In a great many protocols a principal A may
arrange for a second principal B to encrypt
some data chosen by A,
? As a rule such data should be regarded as
'user data' and carefully considered as a
vehicle for cryptosystem dependent attacks,
58
Encapsulation Attacks(2)
? Davis and Swick,key translation protocol
? 1,B -> A, {A,msg}Kbt
? 2,A -> T, {A,msg}Kbt,B
? 3,T -> A, {msg,B}Kat
? A accepts message (3) as proof that B sent the
message msg to him via T,
? However,if msg begins with a principal identier C
then message (3) may be passed off as a
message (1) but riginated by A and intended for C,
Since B chooses the contents of msg he can
arrange this,
59
Encapsulation Attacks(3)
? Davis and Swick,key translation protocol
? i1,B -> A, {A,msg}Kbt
? i2,A -> T, {A,msg}Kbt,B
? i3,T -> A, {msg,B}Kat
? ii1,B(A) -> C, {msg,B}Kat ……,
60
Encapsulation Attacks(4)
? Davis and Swick,key translation protocol
? i2,B(A) -> T, {A,msg}Kbt,B
? i3,T -> B(A), {msg,B}Kat
? ii1,B(A) -> C, {msg,B}Kat ……,
61
Needham Schroeder
Symmetric Key(1)
Needham Schroeder Symmetric Key
? 1,A -> S, A,B,Na
? 2,S -> A, {Na,B,Kab,{Kab,A}Kbs}Kas
? 3,A -> B, {Kab,A}Kbs
? 4,B -> A, {Nb}Kab
? 5,A -> B, {dec(Nb)}Kab
? Freshness attacks A B
S
62
Needham Schroeder
Symmetric Key(2)
“bit-string” attack
? i.1,A ? S, A,B,Na
? i.2,S ? A, {Na,B,Kab,{Kab,A}Kbs}Kas
? i.3,A ? I(B), {Kab,A}Kbs
? i.4,I(B) ? A, Ni
? i.5,A ? I(B), { [Ni]Kab - 1 }Kab
? Freshness attacks
63
Needham Schroeder
Symmetric Key(3)
Denning-Sacco shared key
? 1,A -> S, A,B
? 2,S -> A, {B,Kab,T,{Kab,A,
T}Kbs}Kas
? 3,A -> B, {Kab,A,T}Kbs
? This protocol is subject to a mutiplicity
attack
A B
S
64
Needham Schroeder
Symmetric Key(4)
Lowe modified Denning-Sacco shared key
? 1,A -> S, A,B
? 2,S -> A, {B,Kab,T,{Kab,A,T}Kbs}Kas
? 3,A -> B, {Kab,A,T}Kbs
? 4,B -> A, {Nb}Kab
? 5,A -> B, {dec(Nb)}Kab
?,bit-string” attack A B
S
65
Needham Schroeder
Symmetric Key(5)
Amended Needham Schroeder Symmetric Key
? 1,A -> B, A
? 2,B -> A, {A,Nb}Kbs
? 3,A -> S, A,B,Na,{A,Nb}Kbs
? 4,S -> A, {Na,B,Kab,{Kab,Nb,A}Kbs}Kas
? 5,A -> B, {Kab,Nb,A}Kbs
? 6,B -> A, {Nb}Kab
? 7,A -> B, {dec(Nb)}Kab
?,bit-string” attack
A B
S
66
Needham-Schroeder Public
Key (1)
? 1,A -> B, {Na,A}KPb
? 2,B -> A, {Na,Nb}KPa
? 3,A -> B, {Nb}KPb
A B
67
Needham-Schroeder Public
Key (2)
? i.1,A -> I, {Na,A}KPi
? ii.1,I(A) -> B, {Na,A}KPb
? ii.2,B -> I(A), {Na,Nb}KPa
? i.2,I -> A, {Na,Nb}KPa
? i.3,A -> I, {Nb}KPi
? ii.3,I(A) -> B, {Nb}KPb
A I B
68
Needham-Schroeder Public
Key (3)
? Lowe?s fixed version of Needham-Schroder
Public Key
? 1,A -> B, {Na,A}KPb
? 2,B -> A, {Na,Nb,B}KPa
? 3,A -> B, {Nb}KPb
69
Otway Rees (1)
? 1,A -> B, M,A,B,{Na,M,A,B}Kas
? 2,B -> S, M,A,B,{Na,M,A,B}Kas,
{Nb,M,A,B}Kbs
? 3,S -> B, M,{Na,Kab}Kas,{Nb,
Kab}Kbs
? 4,B -> A, M,{Na,Kab}Kas
? Type attack
A B
S
70
Otway Rees (2)
? i.1,A -> B, M,A,B,{Na,M,A,B}Kas
? i.2,B -> S, M,A,B,{Na,M,A,B}Kas,{Nb,
M,A,B}Kbs
? i.3.1,S -> I(B), M,{Na,Kab}Kas,{Nb,
Kab}Kbs
? ii.2,B -> S, M,A,B,{Na,M,A,B}Kas,{Nb,
M,A,B}Kbs
? ii.3,S -> I(B), M,{Na,K?ab}Kas,{Nb,
K?ab}Kbs
? i.3.2,I(S) -> B, M,{Na,Kab}Kas,{Nb,
K?ab}Kbs
? i.4,B -> A, M,{Na,Kab}Kas
71
AK protocol
? A key agreement protocol is said to provide
implicit key authentication (of B to A) if A is
assured that no other entity besides B can
possibly ascertain the value of the secret key,
? A key agreement protocol that provides mutual
implicit key authentication is called an
authenticated key agreement protocol (or AK
protocol),
72
AKC protocol
? A key agreement protocol provides key
confirmation (of B to A) if A is assured that B
possesses the secret key,
? A protocol that provides mutual key
authentication as well as mutual key confirmation
is called an authenticated key agreement with key
confirmation protocol (or an AKC protocol),
73
security attributes(1)
? 1,Known-key security,Each run of the protocol
should result in a unique secret session key,The
compromise of one session key should not
compromise other session keys,
? 2,Forward secrecy,If long-term private keys of
one or more of the entities are compromised,the
secrecy of previously established session keys
should not be affected,
74
security attributes(2)
? 3,Key-compromise impersonation,The compromise of
an entity A?s long-term private key will allow an
adversary to impersonate A,but it should not enable the
adversary to impersonate other entities to A,
? 4,Unknown key-share resilience,An entity A should not
be able to be coerced into sharing a key with any entity
C when in fact A thinks that she is sharing the key with
another entity B,
? 5,Key control,Neither entity should be able to force the
session key to be a preselected value,
Authentication Protocols
曹天杰
Cao Tianjie
tjcao@cumt.edu.cn
中科院软件所信息安全国家重点实验室
2003.4.21
2
Introduction
? Cryptographic protocol
– Distributed algorithm
– Based on cryptographic building blocks
– To achieve a security related goal
? Examples,
– Entity Authentication
– Key Establishment:Key Distribution(Key enveloping,
Key transport),Key agreement
– Electronic Payment
– …
3
authentication
Alice Bob
How does Bob know that Alice is Alice,not Eve?
insecure channel
Eve
(Eve owns the channel!)
Hi! I’m Alice
4
authentication
? Authentication is a means by which identity is
established,
? It allows one party to gain assurances about the
identity of another party in a protocol,and that
the second has actively participated,
? The goal of authentication is to achieve all this
over an insecure channel with an active attacker
and no shared secrets,
? Note,authentication must be combined with key
exchange to avoid session hijacking (after
authentication),
5
objectives of identification protocols
? If Alice and Bob are both honest,A is able to
successfully authenticate herself to Bob,i.e,Bob
will complete the protocol having accepted Alice’s
identity,
? Bob cannot reuse an identification exchange with
Alice so as to impersonate her in conversations with
others,
? The probability that Eve can successfully
impersonate Alice to Bob is negligible (e.g,
computationally difficult),
? All the above remain true even if Eve has seen many
previous authentication sessions between Alice and
Bob,has had experience in authenticating herself
with both,and multiple authentication sessions are
run simultaneously,
6
basis of identification
? Something you know
– Passwords,PINs,secret keys,your mother’s
maiden name
? Something you have
– Magnetic cards,smart cards,physical keys,
handheld password generators,
? Something you are
– biometrics (DNA,signatures,fingerprints,
voice,retinal patterns,hand geometries,
typing dialect/profiling),
7
basis of identification
– Biometrics have major problems in real
world situations
? How do you revoke keys?
? Biology is messy
–We leave DNA,fingerprints everywhere
- just ask OJ
? How do you give a mugger your
fingerprint?
? How do you authenticate if he’s just hit
you in the eye?
8
attacks on authentication
? Impersonation
? Replay
? Interleaving
– impersonation involving selective
combination of information from one or
more previous or simultaneous sessions
? Reflection
– an interleaving attack involving sending
information from an ongoing authentication
session back to the originator
9
attacks on authentication
? Forced delay
– adversary intercepts a message and relays it
at some later point in time (note,not the
same as replay)
? Chosen-text
– attack on challenge-response where an
adversary chooses challenges in an attempt
to extract the secret key
10
Eve
Simple Authentication,1st
Attempt
Alice Bob Alice,KAB
= KAB
11
Simple Authentication,2nd
Attempt
Eve
Alice Bob Alice,{Hello}KAB
{Hello}KAB
Alice,{Hello}KAB = K
AB
12
Simple Authentication,3rd
Attempt
Eve
Alice Bob Alice,{Alice,T}KAB
Alice,{Alice,T}KAB
{Alice,T}KAB
Detects replay
= KAB
13
Authentication,Summary
? Proof of knowledge
– By text encrypted with secret key (authenticator)
– Not by secret key itself
? Proof of freshness
– By included timevarying parameter
– Timestamp,counter,nonce (challenge-response)
Alice Bob Alice,{Alice,N}K
AB
N
14
Variations / Extensions
? One-way vs mutual authentication
? Guaranteeing freshness,
– Timestamps,simple,but requires clock
synchronisation
– Nonces,requires more messages,but no
synchronised clocks
– Counters,extra state has to be kept
15
passwords
? Passwords are the simplest (and weakest)
means of authentication,
? Password authentication is where a secret is
shared between two parties,To authenticate,
one party reveals their identity and their
password,
? Passwords are typically stored hashed on a
server in a password file (so if the server is
compromised,the passwords still needs to be
cracked),
Alice Bob insecure channel
Eve
Hi! I’m Alice,my password is,internet”
16
passwords have major problems
? Passwords can be eavesdropped
– facilitates replay attacks
? Passwords are reusable
– facilitates impersonation attacks by verifier
? Passwords usually come from a small keyspace
– facilitates brute force attacks
? Extremely low entropy
– English only has ~1.3bits/byte of real information
– dictionary attacks are possible
? note dictionary attacks today allow 1M guesses/second+ !
? Humans are extremely poor random number generators
– makes dictionary attacks even easier (or unnecessary)
? Humans are pathetic at remembering passwords and often
reuse (or alternate between) old passwords
– Even years later
17
salting passwords
? Adding a t-bit salt to passwords strengthens them against dictionary and
brute force attacks,
? Public salt (e.g,UNIX passwords)
userA saltA h(passwordA | saltA)
userB saltB h(passwordB | saltB)
– salt is chosen at random
– an adversary must hash a guessed password p 2t times to find if
p is a valid password (when password cracking)
– only works if there are enough users so the salts are all used
? e.g under UNIX there 4096 possible salts but most systems
have much less than 4096 users
– does not protect against an eavesdropper or evil sysadmin
18
one time passwords
? Each password is only used once
– an attempt to foil eavesdroppers and replay attacks
? Many variations
– shared list of one-time passwords
? tick each password off the list as used
– challenge response table
? system has a list of questions,picks one at
random
– sequentially updated one-time passwords
? during authentication under key i,the user
creates and transmits to the system the key to
use next time (i+1)
– one-time sequences based upon a one-way
function
? e.g,Lamport’s one-time scheme
19
lamport’s one time passwords (s/key)
Setup,
? User Alice picks a random generator g and computes a
hash chain,
w = hn(g) = h(h(h(….h(g))))
? Alice sends w to the server,
? Alice sets count ← n-1
Authentication,
? Alice sends x = hcount(g) to the server
? Alice sets count ← count - 1
? The server verifies h(x) = w
? The server sets w ← x
20
lamport’s one time passwords (s/key)
? Advantages
– Prevents eavesdropping
– No secrets are stored on the server
? Disadvantages
– A limited number of authentications before a new
hash chain must be set up
– Vulnerable to a pre-play attack if unused passwords
are compromised
w
g h()
h()
h() auth 1
auth 2
auth n
21
challenge-response authentication
? One entity proves it’s identity to another by
demonstrating knowledge of a secret without revealing
the secret itself,
? Done by providing a response to a time variant challenge,
where the response is dependent on the challenge and
the secret,
? Time variant parameters may be used to counter replay
and interleaving attacks,to provide uniqueness or
timeliness guarantees (e.g,freshness),and to prevent
certain chosen-cyphertext attacks,
– nonces
– sequence numbers aka serial numbers,counters
– timestamps
22
challenge-response using symmetric techniques
? Symmetric cypher or MAC
? r’ prevents a chosen plaintext attack (and as a challenge)
? Both the user and the server share secret key k (bad)
? Prevents eavesdropping
Alice Bob
pick random r’
“hello”
nonce r
Ek(r|r’) or hk(r|r’) verify D
k contains r
pick random r
23
challenge-response using asymmetric techniques
? Public-key Encryption/Decryption
? Digital signatures e.g,
? No secrets stored on the server
? Unlimited usage
? Prevents eavesdropping
Alice Bob
“hello”
nonce r
signA(r) verify signature
pick random r
24
Key Establishment Problem
? Scalability
– One secret key for each pair of principals
– n principals ? ? n2 keys needed
? Key Establishment
– Key agreement versus key transport/distribution
? Key Distribution
– Key generation and distribution when needed
– Central server,Key Distribution Center (KDC)
25
Key Distribution
Alice Bob
KDC
A,B,N,{A,T}KA
Generates KAB
{B,N,KAB}KA,{A,KAB}KB
KAB
{A,T}KAB,{A,KAB}KB
KAB
= KA
= KB
26
Key Distribution
? Key Distribution Centre (KDC)
– distributes keys on demand
– Session keys,
? Session key is sent
– directly to the client,{B,N,KAB}KA
– indirectly,through a ticket to the server,
{A,KAB}KB
27
Safe and Private Messages
? Once session key has been distributed,it
can be used for sending,
– private messages,{message}KAB
cannot be read by eavesdroppers (even not
man-in-the-middle)
– safe messages:MAC(KAB,message)
cannot be modified by outsiders
28
Login procedure
? Cryptographic keys
– Random bit strings
– Hard to remember
– Use passwords instead
? Authentication Server (AS)
– Checks (weak) login password
– Returns strong cryptographic key
– Single Sign-On
29
Login Procedure
Alice
AS
KDC
A,N
{KDC,N,KA}KPW,
{A,KA}KKDC
= KA
= KKDC
= KPW Generates KA
{A,KA}KKDC
30
Login Procedure
1 2
3
4
5
6
1,Request KA
2,Ticket Granting Ticket
3,TGT + Authenticator
4,Ticket for B
5,Ticket for B +
Authenticator
6,(Optional) Authenticator
KDC AS
Alice Bob
31
Analyzing Authentication
protocol
? The first is to find flaws in those protocols
that are not correct,In general,there are two
main types of trivial attacks,replay attacks
and substitution attacks,
? The second is to establish convincingly the
correctness of those that are,
32
Notational Conventions(1)
A
System principal A ( Alice )
B
System principal B (Bob)
S
Trusted Key Server
A ? B,X
A sending a message X to B
A ? I(B),X
A sending a message X to B,but X be
intercepted by intruder I
I(A) ? B,X
Intruder I impersonating A sending a
message X to B
Na,Nb Nonces generated by A and B
33
Notational Conventions(2)
T
Timestamp
Ma,Mb
Serial numbers
X,Y
Concatenation of message X and Y
Kas,Kbs
Secret keys shared with S
Kab
Session key between A and B
{X}
k
Encrypt X using key k
[X]k
Decrypt X using key k
?
Bit-wise exclusive-or operation (XOR)
34
man in the middle
? Problem,(Diffie-Hellman)
Eve owns the channel!
Alice Bob
“hello I’m Alice”
gx mod p
gy mod p
Session key = h(gxy mod p)
Eve
“hello I’m Alice”
gw mod p
gz mod p
Session key = h(gwz mod p)
35
man in the middle
? Problem,(Key Exchange with Public Key Crypto)
Eve owns the channel!
Alice Bob
“Alice”,eA
{“launch missiles at Eve”} eY
Eve
“Bob”,eB
“Alice”,ey,Bob”,eY
{“disarm missile system”} eB
36
session hijacking
? Problem,
Eve owns the channel!
Alice Bob
“hello I’m Alice”
nonce r
signA(r) verify signature
pick random r
Eve
,thanks guys,I’ll take it from here”
37
EKE - encrypted key exchange
? Alice and Bob share a secret key k (bad!)
? A (possibly low entropy) shared secret k is used to form a high
entropy shared secret h(gxy)
? Prevents eavesdropping
? Prevents an active attack on Diffie-Hellman
? Forward secrecy
Alice Bob
“hello”
{gx mod p}k
random y
random x
{gy mod p}k
Session key = h(gxy mod p)
38
definitions
? A protocol is said to have perfect forward secrecy if compromise
of long term keys does not compromise past (short term)
session keys,
? A protocol is vulnerable to a known-key attack if compromise of
past session keys allows an attacker to compromise of future
session keys (including actively impersonating)
39
Attacking Authentication with
Key Distribution protocols
? Freshness Attacks
? Type Flaws
? Parallel Session Attacks
? Implementation Dependent Attacks
? Binding Attacks
? Encapsulation Attacks
? Other Forms of Attack
40
Freshness Attacks(1)
? A freshness attack occurs when a
message (or message component) from
a previous run of a protocol is recorded
by an intruder and replayed as a
message component in the current run
of the protocol,
41
Freshness Attacks(2)
Needham Schroeder Symmetric Key
? 1,A -> S, A,B,Na
? 2,S -> A, {Na,B,Kab,{Kab,
A}Kbs}Kas
? 3,A -> B, {Kab,A}Kbs
? 4,B -> A, {Nb}Kab
? 5,A -> B, {dec(Nb)}Kab
A B
S
42
Freshness Attacks(3)
Needham Schroeder Symmetric Key
? i.1,A -> S, A,B,Na
? i.2,S -> A, {Na,B,Kab,{Kab,A}Kbs }Kas
? i.3,A -> I(B), {Kab,A}Kbs
? assume that Kab is compromised
? ii.3,I(A) -> B, {Kab,A}Kbs
? ii.4,B -> I(A), {Nb}Kab
? ii.5,I(A) -> B, {dec(Nb)}Kab
? Bit-string attack
A B
S
43
Type Flaws(1)
? A message consists of a sequence of
components each with some value (for
example,the name of a principal,the value
of a nonce,or the value of a key),The
message is represented at the concrete level
as a sequence of bits,
? A type flaw arises when the recipient of a
message accepts that message as valid but
imposes a different interpretation on the bit
sequence than the principal who created it,
44
Type Flaws(2)
Andrew Secure RPC
? 1,A -> B, A,{Na}Kab
? 2,B -> A, {succNa,Nb}Kab
? 3,A -> B, {succNb}Kab
? 4,B -> A, {K?ab,N?b}Kab
45
Type Flaws(3)
Andrew Secure RPC
? i.1,A -> B, A,{Na}Kab
? i.2,B -> A, {succNa,Nb}Kab
? i.3,A -> I(B), {succNb}Kab
? i.4,I(B) -> A,{succNa,Nb}Kab
? Freshness attacks
46
Type Flaws(4)
Otway Rees
? 1,A -> B, M,A,B,{Na,M,A,B}Kas
? 2,B -> S, M,A,B,{Na,M,A,B}Kas,{Nb,
M,A,B}Kbs
? 3,S -> B, M,{Na,Kab}Kas,{Nb,Kab}Kbs
? 4,B -> A, M,{Na,Kab}Kas
A B
S
47
Type Flaws(5)
Otway Rees
? i1,A -> I(B), M,A,B,{Na,M,A,B}Kas
? i4,I(B) -> A, M,{Na,M,A,B}Kas
A B
S
48
Type Flaws(6)
Otway Rees
? i1,A -> B, M,A,B,{Na,M,A,B}Kas
? i2,B -> I(S), M,A,B,{Na,M,A,B}Kas,
{Nb,M,A,B}Kbs
? i3,I(S) -> B, M,{Na,M,A,B}Kas,{Nb,M,
A,B}Kbs
? i4,B -> A, M,{Na,M,A,B}Kas
A B
I(S)
49
Parallel Session Attacks(1)
one-way authentication protocol,
? 1,A -> B, {Na}Kab
? 2,B -> A, {Na+1}Kab
50
Parallel Session Attacks(2)
one-way authentication protocol,
? i1,A -> I(B), {Na}Kab
? ii1,I(B) -> A, {Na}Kab
? ii2,A -> I(B), {Na+1}Kab
? i2,I(B) -> A, {Na+1}Kab
A I(B)
51
Parallel Session Attacks(3)
Wide Mouthed Frog
? 1,A -> S, A,{Ta,B,Kab}Kas
? 2,S -> B, {Ts,A,Kab}Kbs
A B
S
52
Parallel Session Attacks(4)
Wide Mouthed Frog
? i.1,A -> S, A,{Ta,B,Kab}Kas
? i.2,S -> B, {Ts,A,Kab}Kbs
? ii.1,I(B) -> S, B,{Ts,A,Kab}Kbs
? ii.2,S -> A, {T’s,B,Kab}Kas
? iii.1,I(A) -> S, A,{T’s,B,Kab}Kas
? iii.2,S -> B, {T??s,A,Kab}Kbs
? Replay attack
A B
S
53
Implementation Dependent
Attacks
Stream Ciphers
? 1,A -> B, {Na}Kab
? 2,B -> A, {Na+1}Kab
? On average the nonce will be odd half of the
time and so this form of attack has a half
chance of succeeding,
54
Binding Attacks(1)
? Suppose your public key is Ky and an
intruder's public key is Ki,
? if the intruder can convince others that your
public key is Ki then they will encrypt secret
information using Ki and this will be readable
by the intruder,
55
Binding Attacks(2)
? 1,C -> AS, C,S,Nc
? 2,AS -> C, AS,{AS,C,Nc,Ks}
? The certication authority AS is the repository
for principals? public keys,
? Here,a prospective client C wants to
communicate with S and needs the public
key Ks of S,
1asK?
56
Binding Attacks(3)
? i1,C -> I(AS), C,S,Nc
? ii1,I(C) -> AS, C,I,Nc
? ii2,AS) ->I(C), AS,{AS,C,Nc,Ki}
? i2,I(AS) -> C, AS,{AS,C,Nc,Ki}
? This attack was identied by Hwang and Chen,
They suggest that this problem can be solved by
explicitly including the identier of the requested
server S in message (2),
1asK?
1asK?
57
Encapsulation Attacks(1)
? In a great many protocols a principal A may
arrange for a second principal B to encrypt
some data chosen by A,
? As a rule such data should be regarded as
'user data' and carefully considered as a
vehicle for cryptosystem dependent attacks,
58
Encapsulation Attacks(2)
? Davis and Swick,key translation protocol
? 1,B -> A, {A,msg}Kbt
? 2,A -> T, {A,msg}Kbt,B
? 3,T -> A, {msg,B}Kat
? A accepts message (3) as proof that B sent the
message msg to him via T,
? However,if msg begins with a principal identier C
then message (3) may be passed off as a
message (1) but riginated by A and intended for C,
Since B chooses the contents of msg he can
arrange this,
59
Encapsulation Attacks(3)
? Davis and Swick,key translation protocol
? i1,B -> A, {A,msg}Kbt
? i2,A -> T, {A,msg}Kbt,B
? i3,T -> A, {msg,B}Kat
? ii1,B(A) -> C, {msg,B}Kat ……,
60
Encapsulation Attacks(4)
? Davis and Swick,key translation protocol
? i2,B(A) -> T, {A,msg}Kbt,B
? i3,T -> B(A), {msg,B}Kat
? ii1,B(A) -> C, {msg,B}Kat ……,
61
Needham Schroeder
Symmetric Key(1)
Needham Schroeder Symmetric Key
? 1,A -> S, A,B,Na
? 2,S -> A, {Na,B,Kab,{Kab,A}Kbs}Kas
? 3,A -> B, {Kab,A}Kbs
? 4,B -> A, {Nb}Kab
? 5,A -> B, {dec(Nb)}Kab
? Freshness attacks A B
S
62
Needham Schroeder
Symmetric Key(2)
“bit-string” attack
? i.1,A ? S, A,B,Na
? i.2,S ? A, {Na,B,Kab,{Kab,A}Kbs}Kas
? i.3,A ? I(B), {Kab,A}Kbs
? i.4,I(B) ? A, Ni
? i.5,A ? I(B), { [Ni]Kab - 1 }Kab
? Freshness attacks
63
Needham Schroeder
Symmetric Key(3)
Denning-Sacco shared key
? 1,A -> S, A,B
? 2,S -> A, {B,Kab,T,{Kab,A,
T}Kbs}Kas
? 3,A -> B, {Kab,A,T}Kbs
? This protocol is subject to a mutiplicity
attack
A B
S
64
Needham Schroeder
Symmetric Key(4)
Lowe modified Denning-Sacco shared key
? 1,A -> S, A,B
? 2,S -> A, {B,Kab,T,{Kab,A,T}Kbs}Kas
? 3,A -> B, {Kab,A,T}Kbs
? 4,B -> A, {Nb}Kab
? 5,A -> B, {dec(Nb)}Kab
?,bit-string” attack A B
S
65
Needham Schroeder
Symmetric Key(5)
Amended Needham Schroeder Symmetric Key
? 1,A -> B, A
? 2,B -> A, {A,Nb}Kbs
? 3,A -> S, A,B,Na,{A,Nb}Kbs
? 4,S -> A, {Na,B,Kab,{Kab,Nb,A}Kbs}Kas
? 5,A -> B, {Kab,Nb,A}Kbs
? 6,B -> A, {Nb}Kab
? 7,A -> B, {dec(Nb)}Kab
?,bit-string” attack
A B
S
66
Needham-Schroeder Public
Key (1)
? 1,A -> B, {Na,A}KPb
? 2,B -> A, {Na,Nb}KPa
? 3,A -> B, {Nb}KPb
A B
67
Needham-Schroeder Public
Key (2)
? i.1,A -> I, {Na,A}KPi
? ii.1,I(A) -> B, {Na,A}KPb
? ii.2,B -> I(A), {Na,Nb}KPa
? i.2,I -> A, {Na,Nb}KPa
? i.3,A -> I, {Nb}KPi
? ii.3,I(A) -> B, {Nb}KPb
A I B
68
Needham-Schroeder Public
Key (3)
? Lowe?s fixed version of Needham-Schroder
Public Key
? 1,A -> B, {Na,A}KPb
? 2,B -> A, {Na,Nb,B}KPa
? 3,A -> B, {Nb}KPb
69
Otway Rees (1)
? 1,A -> B, M,A,B,{Na,M,A,B}Kas
? 2,B -> S, M,A,B,{Na,M,A,B}Kas,
{Nb,M,A,B}Kbs
? 3,S -> B, M,{Na,Kab}Kas,{Nb,
Kab}Kbs
? 4,B -> A, M,{Na,Kab}Kas
? Type attack
A B
S
70
Otway Rees (2)
? i.1,A -> B, M,A,B,{Na,M,A,B}Kas
? i.2,B -> S, M,A,B,{Na,M,A,B}Kas,{Nb,
M,A,B}Kbs
? i.3.1,S -> I(B), M,{Na,Kab}Kas,{Nb,
Kab}Kbs
? ii.2,B -> S, M,A,B,{Na,M,A,B}Kas,{Nb,
M,A,B}Kbs
? ii.3,S -> I(B), M,{Na,K?ab}Kas,{Nb,
K?ab}Kbs
? i.3.2,I(S) -> B, M,{Na,Kab}Kas,{Nb,
K?ab}Kbs
? i.4,B -> A, M,{Na,Kab}Kas
71
AK protocol
? A key agreement protocol is said to provide
implicit key authentication (of B to A) if A is
assured that no other entity besides B can
possibly ascertain the value of the secret key,
? A key agreement protocol that provides mutual
implicit key authentication is called an
authenticated key agreement protocol (or AK
protocol),
72
AKC protocol
? A key agreement protocol provides key
confirmation (of B to A) if A is assured that B
possesses the secret key,
? A protocol that provides mutual key
authentication as well as mutual key confirmation
is called an authenticated key agreement with key
confirmation protocol (or an AKC protocol),
73
security attributes(1)
? 1,Known-key security,Each run of the protocol
should result in a unique secret session key,The
compromise of one session key should not
compromise other session keys,
? 2,Forward secrecy,If long-term private keys of
one or more of the entities are compromised,the
secrecy of previously established session keys
should not be affected,
74
security attributes(2)
? 3,Key-compromise impersonation,The compromise of
an entity A?s long-term private key will allow an
adversary to impersonate A,but it should not enable the
adversary to impersonate other entities to A,
? 4,Unknown key-share resilience,An entity A should not
be able to be coerced into sharing a key with any entity
C when in fact A thinks that she is sharing the key with
another entity B,
? 5,Key control,Neither entity should be able to force the
session key to be a preselected value,
