Cryptographic Protocols
Security & Networks
• • • •
Today’s Lecture
Protocols in Alice and Bob notation Attacks on Protocols
Forward Secrecy
Goals and Protocols
A sends a message m to B
•
written as:
A → B : “I’m Alice”
“I’m Alice”
A Simple Protocol
Alice
Bob
•
1. A→B:“Hello” 2. B→A:“Offer” 3. A → B : “Accept”
Rules
We write down protocols as a list of messages sent between principals, e.g.
Alice
“I’m Alice”
Bob
A Simple Protocol
A → B : “I’m Alice”
Message “I’m Alice” can be read by an attacker.
A Simple Protocol
Elvis
Alice
“I’m Alice”
Bob
The attacker can pretend to be anyone.
E(A) → B : “I’m Alice”
{_}Kab means symmetric key encryption
Alice
A Simple Protocol
{“I’m Alice”}Kab
Bob
A → B : {“I’m Alice”}Kab
If Alice and Bob share a key Kab, then Alice can encrypt her message.
A Simple Protocol
A → B : {“I’m Alice”}Kab
E(A) → B : {“I’m Alice”}Kab
• •
Attacker can intercept and replay messages. Assume the attacker “owns” the network.
A Nonce
Number that is only used once (often used in a challenge/response setting).
1. A
2. {Na}Kab
Alice
Bob
3. {Na + 1}Kab, {Pay Elvis €5}Kab 1. A→B:A
2. B→A:{Na}Kab
3. A→B:{N +1} ,{PayElvis€5}
a Kab Kab
B: Since Na + 1 was encrypted
using the shared key with A, I am sure she wants to pay Elvis €5.
1. A
2. {Na}Kab
Alice
Bob
A Nonce
3. {Na + 1}Kab, {Pay Elvis €5}Kab 4. A
5. {Na2}Kab
6. {Na2 + 1}Kab, {Pay Bob €5}Kab
1. A
2. {Na}Kab
Alice
Bob
A Nonce
3. {Na + 1}Kab, {Pay Elvis €5}Kab 4. A
5. {Na2}Kab
6. {Na2 + 1}Kab,
Elvis 6’. {Na2 + 1}Kab,
{Pay Bob €5}Kab {Pay Elvis €5}Kab
A Better Protocol
1. A
2. {Na}Kab
Alice
Bob
3. {Na + 1}Kab, {Pay Elvis €5}Kab 1. A→B:A
2. B→A:{Na}Kab
3. A→B:{Na+1}Kab,{PayElvis€5}Kab
A Better Protocol
1. A
2. {Na}Kab
Alice
3. {Na, Pay Elvis €5}Kab 1. A→B:A
2. B→A:{Na}Kab
3. A → B : {Na, Pay Elvis €5}Kab
Bob
A Better Protocol
1. A 2. Na
3. {Na, Pay Elvis €5}Kab 1. A→B:A
2. B→A:Na
3. A → B : {Na, Pay Elvis €5}Kab
Alice
Bob
What can Bob be sure of after such a protocol run?
a) He is talking to Alice
b) A wants to send Elvis €5
c) A’s messages are fresh
(not replayed)
Key Establishment Protocol
This protocol was possible because A and B shared a key. Often, the principals need to set up a session key using a
Key Establishment Protocol.
•
• •
To be sure they are communicating with the correct principal,
they must either know each others public keys or use a
Trusted Third Party (TTP).
The Needham-Schroeder Public Key Protocol
Assume Alice and Bob know each others public keys,
can they set up a symmetric key?
EX(_) means public key encryption
1. A → B : EB(Na, A) 2. B → A : EA(Na, Nb) 3. A→B:EB(Nb)
A: “The only person who could know
Na is the person who decrypted the first message.”
B: “The only person who could know
Nb is the person who decrypted the second message.”
Na and Nb can then be used to generate a symmetric key.
Goals: Alice and Bob are sure they are talking to each other and only they know the key.
An Attack Against the NH Protocol
The attacker C acts as a man-in-the-middle: 1. A → C : EC(Na, A)
1) C(A) → B : EB(Na, A)
2) B → C(A) : EA(Na, Nb) 2. C → A : EA(Na, Nb)
3. A→C:EC(Nb)
3) C(A) → B : EB(Nb)
An Attack Against the NH Protocol
The attacker C acts as a man-in-the-middle: 1. A → C : EC(Na, A)
1) C(A) → B : EB(Na, A)
2) B → C(A) : EA(Na, Nb) 2. C → A : EA(Na, Nb)
3. A→C:EC(Nb)
3) C(A) → B : EB(Nb)
Corrected Version
A very simple fix:
1. A → B : EB(Na, A) 2. B → A : EA(Na, Nb) 3. A→B:EB(Nb)
Corrected Version
A very simple fix:
1. A → B : EB(Na, A)
2. B → A : EA(Na,Nb,B) 3. A→B:EB(Nb)
1. A → B : EB(Na, A)
2. B → A : E (N , N , B)
A a b 3. A→B:EB(Nb)
Forward Secrecy
What about governments?
After the protocol runs, governments can legally force people to handover their private keys.
Can they read messages
encrypted using key(Na, Nb)?
a) Yes b) No
4. B → A : {M}key(Na,Nb)
Secure against the “standard” attacker:
intercept, replay, delete, alter
1. A → B : EB(Na, A)
2. B → A : E (N , N , B)
A a b 3. A→B:EB(Nb)
Forward Secrecy
What about governments?
After the protocol runs, governments can legally force people to handover their private keys.
4. B → A : {M}key(Na,Nb)
Secure against the “standard” attacker:
intercept, replay, delete, alter
1. A → B : EB(Na, A)
2. B → A : E (N , N , B)
A a b 3. A→B:EB(Nb)
Forward Secrecy
What about governments?
After the protocol runs, governments can legally force people to handover their private keys.
Can we protect against this?
4. B → A : {M}key(Na,Nb)
Secure against the “standard” attacker:
intercept, replay, delete, alter
Forward Secrecy
A protocol has Forward Secrecy if it keeps the message secret from an attacker who has:
•
•
Protection against a government that can force people to give up their keys, or hackers that might steal them.
A recording of the protocol run
The long term keys of the principals.
1. A→B:gx 2. B→A:gy
Station-to-Station Protocol
Station-to-Station Protocol
1. A→B:gx
2. B → A : gy, {SB(gy, gx)}gxy
3. A → B : {SA(gy, gx)}gxy 4. B→A:{M}gxy
x, y, gxy are not stored after the protocol run.
A and B’s keys don’t let the attacker read M. STS has forward secrecy.
SX(_) means signed by X
•
• •
•
• •
What if Alice and Bob don’t know each other’s public keys
to start off with?
Certificates
Could meet face-to-face and set up keys.
Or get a trusted third party (TTP) to sign their identity and public key:
a certificate.
See browser certs
Full Station-to-Station Protocol
1. A→B:gx
2. B → A : gy, CertB, {SB(gy, gx)}gxy
3. A → B : CertA, {SA(gy, gx)}gxy
The “full” STS protocol adds certificates for A and B.
•
•
These contain their public key signed by a TTP,
so Alice and Bob don’t have to know each other’s public key.
The Needham-Schroeder key establishment protocol
A and B use trusted third party S to establish a key Kab: 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 : {Nb + 1}Kab
The Needham-Schroeder key establishment protocol
Alice can reuse an old 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 : {Nb + 1}Kab
…much later
1) A→B:{Kab,A}Kbs
2) B → A : {Nb}Kab
3) A→B:{Nb+1}Kab
•
•
•
Key Freshness: the key established is new (either from some trusted third party or because it uses a new nonce).
Some Key Establishment Goals
Key Exclusivity: the key is only known to the principals in the protocol. Good Key: the key is both fresh and exclusive.
A Hierarchy of Goals
Good Key
Fresh Key
Key Exclusivity
•
Far-end Operative: A knows that “B” is currently active.
For instance B might have signed a nonce generated by A, e.g. 1. A→B:Na
2. B→A:SB(Na)
Not enough on its own (e.g. Needham-Schroeder protocol).
Authentication Goals
•
Once Authentication: A knows that B wishes to communicate with A.
For instance, B might have the name A in the message, e.g. 1. B→A:SB(A)
Authentication Goals
Entity Authentication
Both of these together give:
Entity Authentication: A knows that B is currently active and wants to communicate with A.
e.g.
1. A→B:Na
2. B → A : SB(A,Na)
•
Good Key
A Hierarchy of Goals
Entity Authentication
Fresh Key
Key Exclusivity Far-end Operative Once Authentication
The Highest Goal
A protocol provides Mutual Belief in a key K for Alice with respect to Bob if, after running the protocol, Bob can be sure that:
K is a good key with A
Alice can be sure that Bob wishes to communicate with Alice using K Alice knows that Bob believes that K is a good key for B.
• • •
A Hierarchy of Goals
Mutual Belief in Key
Good Key
Fresh Key
Key Exclusivity Far-end Operative Once Authentication
Entity Authentication
NH
Public Key Protocol
Remember the man-in-the-middle attack against the NH Public Key Protocol: 1. A → C : EC(Na, A)
Which goals does the unfixed protocol provide?
1) C(A) → B : EB(Na, A)
2) B → C(A) : EA(Na, Nb) 2. C → A : EA(Na, Nb)
3. A→C:EC(Nb)
3) C(A) → B : EB(Nb)
a) Fresh Key
b) Key Exclusivity
c) Far-end Operative d) Once Authentication
• • • •
Today’s Lecture
Protocols in Alice and Bob notation Attacks on Protocols
Forward Secrecy
Goals and Protocols