CS计算机代考程序代写 Cryptographic Protocols

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