Key Exchange and Public-Key Cryptography Overview
Basic key exchange
Trusted 3
rd
parties
Online Cryptography Course Dan Boneh
Key management
Problem: n users. Storing mutual secret keys is difficult
Total: O(n) keys per user
A better solution
Online Trusted 3
rd
Party (TTP)
TTP
Generating keys: a toy protocol
Alice wants a shared key with Bob. Eavesdropping security only.
Bob
(k
B
)
Alice
(k
A
)
TTP
k
AB
k
AB
(E,D) a CPA-secure cipher
choose
random k
AB
Generating keys: a toy protocol
Alice wants a shared key with Bob. Eavesdropping security only.
Eavesdropper sees:
E(k
A
, “A, B” ll k
AB
)
;
E(k
B
, “A, B” ll k
AB
)
(E,D) is CPA-secure
⇒
eavesdropper learns nothing about k
AB
Note: TTP needed for every key exchange, knows all session keys.
(basis of Kerberos system)
Toy protocol: insecure against active attacks
Example: insecure against replay attacks
Attacker records session between Alice and merchant Bob
–
For example a book order
Attacker replays session to Bob
–
Bob thinks Alice is ordering another copy of book
Key question
Can we generate shared keys without an
online
trusted 3
rd
party?
Answer: yes!
Starting point of public-key cryptography:
•
Merkle (1974), Diffie-Hellman (1976), RSA (1977)
•
More recently: ID-based enc.
(BF 2001)
, Functional enc.
(BSW 2011)
End of Segment
Basic key exchange
Merkle Puzzles
Online Cryptography Course Dan Boneh
Key exchange without an online TTP?
Bob
Alice
Goal: Alice and Bob want shared key, unknown to eavesdropper
•
For now: security against eavesdropping only (no tampering)
eavesdropper ??
Can this be done using generic symmetric crypto?
Merkle Puzzles
(1974)
Answer: yes, but very inefficient
Main tool
: puzzles
•
Problems that can be solved with some effort
•
Example: E(k,m) a symmetric cipher with k
∈
{0,1}128
–
puzzle(P) = E(P, “message”)
where P = 0
96
ll b
1
… b
32
–
Goal: find P by trying all 2
32
possibilities
Merkle puzzles
Alice
: prepare 2
32
puzzles
•
For i=1, …, 2
32
choose random
P
i
∈
{0,1}32
and
x
i
, k
i
∈
{0,1}128
set
puzzle
i
⟵
E( 0
96
ll
P
i
,
“Puzzle # x
i
” ll k
i
)
•
Send puzzle
1
, … , puzzle
2
32
to Bob
Bob
: choose a random puzzle
j
and solve it. Obtain ( x
j
, k
j
)
.
•
Send x
j
to Alice
Alice
: lookup puzzle with number x
j
. Use k
j
as shared secret
In a figure
Alice’s work: O(n)
(prepare n puzzles)
Bob’s work: O(n)
(solve one puzzle)
Eavesdropper’s work: O( n
2
)
Bob
Alice
puzzle
1
, … , puzzle
n
x
j
k
j
k
j
(e.g. 2
64
time)
Impossibility Result
Can we achieve a better gap using a general symmetric cipher?
Answer: unknown
But: roughly speaking,
quadratic gap is best possible if we treat cipher as
a black box oracle
[IR’89, BM’09]
End of Segment
Basic key exchange
The Diffie-Hellman
protocol
Online Cryptography Course Dan Boneh
Key exchange without an online TTP?
Bob
Alice
Goal: Alice and Bob want shared secret, unknown to eavesdropper
•
For now: security against eavesdropping only (no tampering)
eavesdropper ??
Can this be done with an exponential gap?
The Diffie-Hellman protocol
(informally)
Fix a large prime p (e.g. 600 digits)
Fix an integer g in {1, …, p}Alice
Bob
choose random
a
in {1,…,p-1}choose random
b
in {1,…,p-1}k
AB
= g
ab
(mod p)
=
(
g
a
)
b
=
A
b
(mod p)
B
a
(mod p)
=
(
g
b
)
a
=
Security
(much more on this later)
Eavesdropper sees: p, g, A=g
a
(mod p), and B=g
b
(mod p)
Can she compute g
ab
(mod p) ??
More generally: define DH
g
(g
a
, g
b
) = g
ab
(mod p)
How hard is the DH function mod p?
How hard is the DH function mod p?
Suppose prime p is n bits long.
Best known algorithm (GNFS): run time exp( )
cipher key size
modulus size
80 bits
1024 bits
128 bits
3072 bits
256 bits (AES)
15360
bits
As a result: slow transition away from (mod p) to elliptic curves
160 bits
256 bits
512 bits
Elliptic curve
Diffie-Hellman
Insecure against man-in-the-middle
As described, the protocol is insecure against
active
attacks
Alice
Bob
MiTM
Another look at DH
⋯
g
a
g
b
g
c
g
d
K
AC
=g
ac
K
AC
=g
ac
An open problem
⋯
g
a
g
b
g
c
g
d
K
ABCD
K
ABCD
K
ABCD
K
ABCD
End of Segment
Basic key exchange
Public-key encryption
Online Cryptography Course Dan Boneh
Establishing a shared secret
Bob
Alice
Goal: Alice and Bob want shared secret, unknown to eavesdropper
•
For now: security against eavesdropping only (no tampering)
eavesdropper ??
This segment: a different approach
Public key encryption
E
D
Alice
Bob
Public key encryption
Def
: a public-key encryption system is a triple of algs. (G, E, D)
•
G(): randomized alg. outputs a key pair (pk, sk)
•
E(pk, m): randomized alg. that takes m
∈
M and outputs c
∈
C
•
D(sk,c): det. alg. that takes c
∈
C and outputs m
∈
M or
⊥
Consistency:
∀
(pk, sk) output by G :
∀
m
∈
M: D(sk, E(pk, m) ) = m
Semantic Security
For b=0,1 define experiments EXP(0) and EXP(1) as:
Def:
E =
(G,E,D) is sem. secure (a.k.a IND-CPA) if for all efficient A:
Adv
SS
[A,
E
] =
|
Pr[EXP(0)=1] – Pr[EXP(1)=1]
|
< negligible
Chal.
b
Adv. A
(pk,sk)
G()
EXP(b)
Establishing a shared secret
Alice
Bob
(pk, sk)
⟵
G()
choose random
x
∈
{0,1}128
Security
(eavesdropping)
Adversary sees
pk, E(pk, x)
and wants
x
∈
M
Semantic security
⇒
adversary cannot distinguish
{pk, E(pk, x), x
}
from
{pk, E(pk, x), rand
∈
M
}
⇒
can derive session key from x.
Note: protocol is vulnerable to man-in-the-middle
Insecure against man in the middle
As described, the protocol is insecure against
active
attacks
Alice
Bob
MiTM
(pk, sk)
⟵
G()
(pk’, sk’)
⟵
G()
choose random
x
∈
{0,1}128
Public key encryption: constructions
Constructions generally rely on hard problems from
number theory and algebra
Next module:
•
Brief detour to catch up on the relevant background
Further readings
•
Merkle Puzzles are Optimal,
B. Barak, M. Mahmoody-Ghidary, Crypto
’
09
•
On formal models of key exchange (sections 7-9)
V. Shoup, 1999
End of Segment
Now that we know how two users can protect data using a shared key, the next question is how these two users generate a shared key. This question will take us into the world of public-key crypto.
In this module we will look at a few toy key exchange protocols as a way to introduce the main ideas of public-key crypto.
We will come back to key exchange and design secure key exchange protocols after we build a few more public-key tools.
Explore the challenges of key management, the use of trusted third parties in generating shared keys, the limitations of toy protocols in secure key exchange, and the evolution of public-key cryptography techniques like Merkle Puzzles, Diffie-Hellman, and RSA. Learn how to achieve secure key exchange without relying on online trusted third parties through innovations in public-key cryptography.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Online Cryptography Course Dan Boneh Basic key exchange Trusted 3rd parties Dan Boneh
Key management Problem: n users. Storing mutual secret keys is difficult Total: O(n) keys per user Dan Boneh
A better solution Online Trusted 3rd Party (TTP) TTP Dan Boneh
Generating keys: a toy protocol Alice wants a shared key with Bob. Eavesdropping security only. Bob (kB) Alice (kA) TTP Alice wants key with Bob choose random kAB ticket kAB kAB (E,D) a CPA-secure cipher Dan Boneh
Generating keys: a toy protocol Alice wants a shared key with Bob. Eavesdropping security only. Eavesdropper sees: E(kA, A, B ll kAB ) ; E(kB, A, B ll kAB ) (E,D) is CPA-secure eavesdropper learns nothing about kAB Note: TTP needed for every key exchange, knows all session keys. (basis of Kerberos system) Dan Boneh
Toy protocol: insecure against active attacks Example: insecure against replay attacks Attacker records session between Alice and merchant Bob For example a book order Attacker replays session to Bob Bob thinks Alice is ordering another copy of book Dan Boneh
Key question Can we generate shared keys without an online trusted 3rd party? Answer: yes! Starting point of public-key cryptography: Merkle (1974), Diffie-Hellman (1976), RSA (1977) More recently: ID-based enc. (BF 2001), Functional enc. (BSW 2011) Dan Boneh
End of Segment Dan Boneh
Online Cryptography Course Dan Boneh Basic key exchange Merkle Puzzles Dan Boneh
Key exchange without an online TTP? Goal: Alice and Bob want shared key, unknown to eavesdropper For now: security against eavesdropping only (no tampering) Alice Bob eavesdropper ?? Can this be done using generic symmetric crypto? Dan Boneh
Merkle Puzzles (1974) Answer: yes, but very inefficient Main tool: puzzles Problems that can be solved with some effort Example: E(k,m) a symmetric cipher with k {0,1}128 puzzle(P) = E(P, message ) where P = 096 ll b1 b32 Goal: find P by trying all 232 possibilities Dan Boneh
Merkle puzzles Alice: prepare 232 puzzles For i=1, , 232 choose random Pi {0,1}32and xi, ki {0,1}128 set puzzlei E( 096 ll Pi, Puzzle # xi ll ki) Send puzzle1, , puzzle232 to Bob Bob: choose a random puzzlej and solve it. Obtain ( xj, kj ). Send xj to Alice Alice: lookup puzzle with number xj . Use kj as shared secret Dan Boneh
In a figure puzzle1, , puzzlen Alice Bob xj kj kj Alice s work: O(n) Bob s work: O(n) (prepare n puzzles) (solve one puzzle) (e.g. 264 time) Eavesdropper s work: O( n2 ) Dan Boneh
Impossibility Result Can we achieve a better gap using a general symmetric cipher? Answer: unknown But: roughly speaking, quadratic gap is best possible if we treat cipher as a black box oracle [IR 89, BM 09] Dan Boneh
End of Segment Dan Boneh
Online Cryptography Course Dan Boneh Basic key exchange The Diffie-Hellman protocol Dan Boneh
Key exchange without an online TTP? Goal: Alice and Bob want shared secret, unknown to eavesdropper For now: security against eavesdropping only (no tampering) Alice Bob eavesdropper ?? Can this be done with an exponential gap? Dan Boneh
The Diffie-Hellman protocol (informally) Fix a large prime p (e.g. 600 digits) Fix an integer g in {1, , p} Alice Bob choose random ain {1, ,p-1} choose random bin {1, ,p-1} = (ga)b=Ab(mod p) Ba(mod p) = (gb)a= kAB = gab(mod p) Dan Boneh
Security (much more on this later) Eavesdropper sees: p, g, A=ga (mod p), and B=gb (mod p) Can she compute gab (mod p) ?? More generally: define DHg(ga, gb) = gab (mod p) How hard is the DH function mod p? Dan Boneh
How hard is the DH function mod p? Suppose prime p is n bits long. Best known algorithm (GNFS): run time exp( ) Elliptic Curve size 160 bits 256 bits 512 bits cipher key size 80 bits 128 bits 256 bits (AES) modulus size 1024 bits 3072 bits 15360 bits As a result: slow transition away from (mod p) to elliptic curves Dan Boneh
Elliptic curve Diffie-Hellman Dan Boneh
Insecure against man-in-the-middle As described, the protocol is insecure against active attacks Alice Bob MiTM Dan Boneh
Another look at DH Facebook ga gb gc gd Alice David Bob Charlie d a b c KAC=gac KAC=gac Dan Boneh
An open problem Facebook ga gb gc gd Alice David Bob Charlie d a b c KABCD KABCD KABCD KABCD Dan Boneh
End of Segment Dan Boneh
Online Cryptography Course Dan Boneh Basic key exchange Public-key encryption Dan Boneh
Establishing a shared secret Goal: Alice and Bob want shared secret, unknown to eavesdropper For now: security against eavesdropping only (no tampering) Alice Bob eavesdropper ?? This segment: a different approach Dan Boneh
Public key encryption Alice Bob E D Dan Boneh
Public key encryption Def: a public-key encryption system is a triple of algs. (G, E, D) G(): randomized alg. outputs a key pair (pk, sk) E(pk, m): randomized alg. that takes m M and outputs c C D(sk,c): det. alg. that takes c C and outputs m M or Consistency: (pk, sk) output by G : m M: D(sk, E(pk, m) ) = m Dan Boneh
Semantic Security For b=0,1 define experiments EXP(0) and EXP(1) as: pk Chal. Adv. A b m0 , m1 M : |m0| = |m1| (pk,sk) G() c E(pk, mb) b {0,1} EXP(b) Def: E =(G,E,D) is sem. secure (a.k.a IND-CPA) if for all efficient A: AdvSS [A,E] = |Pr[EXP(0)=1] Pr[EXP(1)=1] | < negligible Dan Boneh
Establishing a shared secret Alice Bob (pk, sk) G() Alice , pk choose random x {0,1}128 Dan Boneh
Security (eavesdropping) and wants x M Adversary sees pk, E(pk, x) Semantic security adversary cannot distinguish { pk, E(pk, x), x } from { pk, E(pk, x), rand M } can derive session key from x. Note: protocol is vulnerable to man-in-the-middle Dan Boneh
Insecure against man in the middle As described, the protocol is insecure against active attacks Alice (pk, sk) G() Bob MiTM (pk , sk ) G() Alice , pk choose random x {0,1}128 Bob , E(pk, x) Bob , E(pk , x) Dan Boneh
Public key encryption: constructions Constructions generally rely on hard problems from number theory and algebra Next module: Brief detour to catch up on the relevant background Dan Boneh
Further readings Merkle Puzzles are Optimal, B. Barak, M. Mahmoody-Ghidary, Crypto 09 On formal models of key exchange (sections 7-9) V. Shoup, 1999 Dan Boneh
End of Segment Dan Boneh
