Private Key Cryptography

Report
Lecture 5:
Protocols - Authentication and Key Exchange*
CS 392/6813: Computer Security
Fall 2008
Nitesh Saxena
*Adopted from a previous lecture by Gene Tsudik
Course Admin



HW#3 due at midnight of tomorrow (Friday)
HW#4 will be posted very soon
HW#2 is being graded


Thanks for your patience!
HW solutions will be posted soon

7/17/2015
Sorry again for the delay, thanks for your
patience!
Module 4 - Protocols: Authentication and Key Exchange
2
Exam – you love it the most 

Midterm is in-class on 10/23/08 (thursday)




7/17/2015
Includes lecture material until 10/16/06
Closed book, closed notes
Emphasis, of course, is not on memorizing!
About 2 hour long
Module 4 - Protocols: Authentication and Key Exchange
3
Outline of Today’s lecture

Today we try to put everything together





Encryption (public-key/private-key)
MACs
Signing
Key-Distribution
Secure protocols (for secure communication)

Authentication




We studied it somewhat while talking about key distribution
(Authenticated-) Key Exchange
Designing secure protocols is hard – we’ll only be
able to learn the basics today
We’ll use the white-board extensively today – be
prepared to take notes
7/17/2015
Module 4 - Protocols: Authentication and Key Exchange
4
Protocol


A protocol is a set of rules using which two or
more entities exchange messages
It consists of messages and rounds
7/17/2015
Module 4 - Protocols: Authentication and Key Exchange
5
Messages and Rounds
A message is a unit of information send
from one entity to other
A round is a basic unit of protocol time


1.
Wake up because of
1.
2.
3.
2.
3.
4.
5.
7/17/2015
Alarm (or clock)
Intial start or
Receipt of message(s) from other(s)
Compute something
Send message(s) to other(s)
Repeat 2-3 if needed
Wait for message(s) or clock
Module 4 - Protocols: Authentication and Key Exchange
6
Types of Adversaries

Passive


Eavesdrop, delay, drop, replay messages
Active

7/17/2015
Eavesdrop, delay, drop, replay and modify
messages
Module 4 - Protocols: Authentication and Key Exchange
7
Model



N parties
Any party can initiate the protocol with any
other party
Each party can be running a number of
sessions with any other party at any point
7/17/2015
Module 4 - Protocols: Authentication and Key Exchange
8
Adversary and Security Model



Different session should use different keys
Compromise of one session should not lead
to the compromise of any other session
What exactly the adversary can do


It can engage any party to start a session (or
more) with any other party
“Simply forwarding” adversary is NOT an
adversary



7/17/2015
Why?
Message authentication (m’)
Key exchange
Module 4 - Protocols: Authentication and Key Exchange
9
Properties of a Secure Protocol

Correctness

If entities taking part in the protocol behave
honestly, (and also if there are no transmission
errors) the protocol achieves its desired goal


In other words, if everything works as expected, does
the protocol satisfy its desired goal?
Security

No adversary can defeat the goal of the protocol
(with a significantly high probability)


7/17/2015
Adversary could be passive or active, depending upon
the application (we consider the latter)
We won’t consider denial-of-service attacks
Module 4 - Protocols: Authentication and Key Exchange
10
Authentication

Origin Authentication


Entity Authentication



Verification of the origin/source of the message
Verification of the identity of the sender of the
message
We focus on the latter
Authentication can be unilateral or mutual
7/17/2015
Module 4 - Protocols: Authentication and Key Exchange
11
Basis for Authentication

Something you know


Something you have


e.g., a PIN, a password
e.g., an access key or a card; a certificate; a smart
card; an RFID tag
Something you are

7/17/2015
e.g., biometric (such as fingerprint)
Module 4 - Protocols: Authentication and Key Exchange
12
Weak Authentication

PINs, Passwords provide weak authentication




Widely used in practice


1.
2.
3.
Security is based upon how hard the the pin/password is to guess
Usually, the passwords are short and weak
Vulnerable to dictionary attacks
Unix, kerberos, web emails,……
Protocol (A authenticates B using a password P, that A shares
with B)
A B:
B A:
A B:
Hi, this is A!
r (random challenge)
H(p,r)
Problem?
7/17/2015
Module 4 - Protocols: Authentication and Key Exchange
13
Strong Authentication


An entity authenticates to the other by proving the
knowledge of a secret associated with that entity,
without revealing anything meaningful about the
secret itself
Can be achieved through:






Private/Public Key Encryption
MAC
Digital signatures
Strong because the security reduces to the security
of the underlying cryptographic primitive, which is
assumed to be hard to break
Our focus in the rest of the lecture
We’ll study both private-key and public-key based
authentication
7/17/2015
Module 4 - Protocols: Authentication and Key Exchange
14
Symm. Encryption-based authentication

Uses encryption to authenticate Alice to Bob
(assuming Alice-Bob have established a shared
secret K, say through Kerberos)
A auth B
1.
2.
3.
A  B:
B  A:
A  B:
Hi Bob, this is Alice!
r (a challenge)
EncK(r,B) (response)
Why not simply send EncK(r) in msg 3?
7/17/2015
Module 4 - Protocols: Authentication and Key Exchange
15
Security of the previous protocol

An attacker needs to come up with a valid
response


Impossible if encryption is secure
r must not be re-used by Bob

7/17/2015
Why?
Module 4 - Protocols: Authentication and Key Exchange
16
Freshness


Assurance that message has not been used
previously and originated within an
acceptably recent timeframe
Two methods:


7/17/2015
Nonce (Number used once)
Timestamps
Module 4 - Protocols: Authentication and Key Exchange
17
Nonces



One-time random number
We depended on B to make sure r is a good
nonce
Main property is “one-time-ness”, so could
use even a counter (but must keep state)


Starting value must still be random and
unpredictable
Choose nonces “randomly” from a large space
(such as 2128) to avoid re-use and for
unpredictability – good RNG
7/17/2015
Module 4 - Protocols: Authentication and Key Exchange
18
Timestamps

Inclusion of date/time-stamp in the message
allows recipient to check it for freshness


A  B: EncK(T,B)


Need to be protected with cryptographic means
Results in fewer messages
But, requires synchronized clocks

7/17/2015
hard to achieve in practice!
Module 4 - Protocols: Authentication and Key Exchange
19
Encryption-based Mutual Authentication
(1)


1.
2.
3.
7/17/2015
Run two copies of the uni-lateral
authentication protocol  4 rounds
We can piggyback common flows
A  B:
B  A:
A  B:
A, rA
EncK(rB, rA, A)
EncK(rA, rB)
Module 4 - Protocols: Authentication and Key Exchange
20
Encryption-based Mutual Authentication
(2)
1.
2.
7/17/2015
A  B:
B  A:
A, EncK(T,B)
EncK(T+1,A)
Module 4 - Protocols: Authentication and Key Exchange
21
MAC-based Authentication
1.
2.
3.

7/17/2015
A  B:
B  A:
A  B:
A, rA
rB, HMACK(rB, rA, A)
HMACK(rA, rB,B)
Faster than enc-based protocols
(computationally)
Module 4 - Protocols: Authentication and Key Exchange
22
Session Key Exchange with KDC –
Needham-Schroeder Protocol

A -> KDC
IDA || IDB || N1
(Hello, I am Alice, I want to talk to Bob, I need a session Key and here
is a random nonce identifying this request)

KDC -> A
E
KA(
K || IDB || N1 || E
KB(K
|| IDA))
Encrypted(Here is a key, for you to talk to Bob as per your request N1
and also an envelope to Bob containing the same key)

A -> B
E
KB(K
|| IDA)
(I would like to talk using key in envelope sent by KDC)

B -> A
E K(N2)
(OK Alice, But can you prove to me that you are indeed Alice and know
the key?)


A -> B
E K(f(N2)) (Sure I can!)
Last two steps - challenge-response. Commonly used
to thwart replay attack.
7/17/2015
Module 4 - Protocols: Authentication and Key Exchange
23
Session Key Exchange with KDC –
Needham-Schroeder Protocol (corrected
version with mutual authentication)

A -> KDC: IDA || IDB || N1
(Hello, I am Alice, I want to talk to Bob, I need a session Key and here
is a random nonce identifying this request)

KDC -> A: E
KA (
K || IDB || N1 || E
KB(TS1,
K || IDA))
Encrypted(Here is a key, for you to talk to Bob as per your request N1
and also an envelope to Bob containing the same key)

A -> B: E K(TS2,B), E
KB(TS1,
K || IDA)
(I would like to talk using key in envelope sent by KDC; here is an
authenticator)

B -> A: E K(TS2+1,A)
(OK Alice, here is a proof that I am really Bob)
7/17/2015
Module 4 - Protocols: Authentication and Key Exchange
24
Version 4 summary
7/17/2015
Module 4 - Protocols: Authentication and Key Exchange
25
Public-key based authentication
(Needham-Shroeder (NS) pk-based)

1.
2.
3.
7/17/2015
Assuming public keys are distributed
through CA(s)
A  B:
B  A:
A  B:
Encpkb(rA, A)
Encpka(rA, rB)
Encpkb(rB)
Module 4 - Protocols: Authentication and Key Exchange
26
Attack and fix on PK-based NS protocol

Attack:

Fix:
1.
2.
3.
7/17/2015
A  B:
B  A:
A  B:
Encpkb(rA, A)
Encpka(rA, rB,B)
Encpkb(rB)
Module 4 - Protocols: Authentication and Key Exchange
27
Signature-based authentication
(assuming public keys are distributed
through CA)
A auth B

A  B:

B  A:

A  B:
Hi Bob, this is Alice!
r (a challenge)
SigSKa(r,B) (response)
A auth B, B auth A (run two copies; piggyback
common flows)



7/17/2015
A  B:
B  A:
A  B:
A, rA (could sign this too)
rB, SigSKb(rB, rA, A)
SigSKa(rA,rB,B)
Module 4 - Protocols: Authentication and Key Exchange
28
Authenticated Key Exchange (AKE)
Public-key operations are costly
Why not


1.
2.
7/17/2015
use public-key mutual authentication protocols to
exchange a symmetric key
use this symmetric key with a symmetric
encryption to secure subsequent communication
Module 4 - Protocols: Authentication and Key Exchange
29
Security Notion for AKE




Launch protocol between any pair
Reveal all session key except one
Try to distinguish the key of the unrevealed
session from random
This captures: the compromise of other
sessions should not lead to the compromise
of any other session
7/17/2015
Module 4 - Protocols: Authentication and Key Exchange
30
A
B
A
A
1.
2.
3.
4.
 B:
 A:
 B:
and B
A, rA, EncPKb(K) (must sign this too??)
rB, SigSKb(rB, rA, A)
SigSKa(rA, rB, B)
output K as the authenticated key
Such a protocol can be instantiated using RSA
encryption/signing


The way SSL/SSH establishes key

7/17/2015
But, generally only the server authenticates the client, not
vice versa
Module 4 - Protocols: Authentication and Key Exchange
31
X.509 Authentication – One-way.

Establishes the following



7/17/2015
Identity of A and message was generated by A
Message was intended for B
Integrity and originality of message.
Module 4 - Protocols: Authentication and Key Exchange
32
X.509 Authentication – Two-way.

One-Way plus the above which establishes the
following



7/17/2015
Identity of B and message was generated by B
Message was intended for A
Integrity and originality of message.
Module 4 - Protocols: Authentication and Key Exchange
33
X.509 Authentication – Three-way.
7/17/2015
Module 4 - Protocols: Authentication and Key Exchange
34
Diffie-Hellman (DH) Key Exchange
1.
2.
A  B:
B  A:
Ka = ga mod p
Kb = gb mod p
4.
A outputs Kab = Kba
B outputs Kba = Kab

Note Kab = Kba = gab mod p
3.
7/17/2015
Module 4 - Protocols: Authentication and Key Exchange
35
Security of DH key exchange


No authentication of either party
Secure only against a passive adversary

Under the computational Diffie-Hellman
assumption


Given (g, ga,gb), hard to compute gab
Not secure against an active attacker

7/17/2015
Man-in-the-middle attack…
Module 4 - Protocols: Authentication and Key Exchange
36
Authenticated DH Key Exchange
aka: Station-to-Station Protocol
2.
A  B:
B  A:
3.
A  B:
1.
4.
5.
7/17/2015
Ka = ga mod p
Certb, Kb = gb mod p
SigSKb(Ka, Kb)
Certa, SigSKa(Kb,Ka)
A outputs Kab = Kba
B outputs Kba = Kab
Module 4 - Protocols: Authentication and Key Exchange
37
Summary

Designing secure protocols is not easy




Becomes harder in a concurrent setting, where there are
multiple parties, executing multiple instances of the
protocols simultaneously
Becomes even harder as the number of parties increase; nparty or group setting
Use the protocols that are well-studied and
standardized
While designing a protocol, consider



7/17/2015
Reflection attacks
Replay attacks
Eliminating any symmetry in the messages
Module 4 - Protocols: Authentication and Key Exchange
38
Further Reading





Unix password security
http://www.ja.net/CERT/Belgers/UNIX-passwordsecurity.html
MIT Kerberos site:
http://web.mit.edu/kerberos/www/
Kerberos RFC: RFC-1510
X.509 page http://www.ietf.org/html.charters/pkixcharter.html
Ten Risks of PKI - http://www.schneier.com/paperpki.html
7/17/2015
Module 4 - Protocols: Authentication and Key Exchange
39

similar documents