security engineering - University of Sydney

Report
ELEC5616
computer and network security
matt barrie
[email protected]
CNS2010
lecture 6 :: key management
1
key management
•
Suppose we have a symmetric key network:
kab
Alice
Bob
kad
kbd
kac
kbc
Carol
•
•
kcd
Alice, Bob, Carol and Dave want to talk to each other
For secure communication, for n parties, we require
n
2
( )
•
Dave
=
n(n-1)
2
keys
Key distribution and management becomes a major issue!
CNS2010
lecture 6 :: key management
2
definitions
•
Key establishment is any process whereby a shared secret
becomes available to two or more parties, for subsequent
cryptographic use.
•
Key management is the set of processes and mechanisms
which support key establishment and the maintenance of
ongoing keying relationships between parties, including
replacing older keys with newer ones:
– key agreement
– key transport
CNS2010
lecture 6 :: key management
3
key distribution centre
•
Naïve solution:
Alice
ka
kc
Bob
kb
KDC
kd
Carol
•
(1)
(2)
(3)
(4)
•
All parties share a
key with the KDC
Dave
Protocol:
Alice → KDC
KDC → Alice
Alice → Bob
Bob
:
:
:
:
“want to talk with Bob”
KDC picks random key kab, sends Eka[kab], Ekb[kab, “ticket a-b”]
Alice decrypts Eka[kab], sends ticket to Bob
Bob decrypts ticket
Alice and Bob now share secret key kab.
CNS2010
lecture 6 :: key management
4
problems with naïve approach
•
Naïve solution:
Alice
ka
kc
Bob
kb
KDC
kd
Carol
•
All parties share a
key with the KDC
Dave
Problems:
–
–
–
–
CNS2010
Single point of failure, the KDC (a juicy target to attack)
No authentication
Poor scalability
Slow
lecture 6 :: key management
5
merkle’s puzzles
•
•
•
Ralph Merkle (Stanford, 1974)
Merkle’s puzzles are a way of doing key exchange between
Alice and Bob without the need for a KDC
Protocol:
(1)
Alice creates lots of puzzles Pi = Epi[“This is puzzle #Xi”, ki]
where i = 1 .. 220, |pi| = 20 bits (weak), |ki| = 128 bits (strong)
Xi, pi and ki are chosen randomly and different for each i.
(2)
Alice sends all puzzles Pi to Bob.
(3)
Bob picks a random puzzle j є {1 … 220} and solves Pj by brute force
(i.e. search on key pj). This recovers Xj and kj from the puzzle.
(4)
Bob sends Xj to Alice in the clear.
(5)
=>
Alice looks up the index j of Xj (from a table) to get kj.
Alice and Bob now both share a secret key kj.
CNS2010
lecture 6 :: key management
6
merkle’s puzzles
P6
P2
P7
P5
P11
Alice
Makes
220
puzzles
P1
P13
P3
P4
P12
Bob
P14
P9
Picks a random puzzle
Pj and breaks it.
Pi = Epi[“This is puzzle #Xi”, ki]
Sends Xj back to Alice
Alice looks up Xj
Shared secret is kj
Eve ???
Shared secret is kj
Only knows the
puzzles and Xj
CNS2010
lecture 6 :: key management
7
attack on merkle’s puzzles
•
Eve must break on average half the puzzles to find Xj (hence kj)
– Time required to do so for 220 puzzles = 219 x 219 = 238
•
If Alice and Bob can try 10,000 keys/second :
– It will take a minute for each of them to perform their steps (219 for Bob)
– Plus another minute to communicate the puzzles on a 1.544MB (T1) link
•
With comparable resources, it will take Eve about a year to
break the system.
•
Note: Merkle’s Puzzles uses a lot of bandwidth (impractical!)
CNS2010
lecture 6 :: key management
8
diffie-hellman key exchange
•
•
•
Diffie-Hellman (Stanford, 1976)
Worldwide standard used in smart cards, etc.
Protocol:
Consider the finite field Zp = <0, … p-1> where p is prime (p is about 300 digits long)
Let g є Zp (the generator)
(1)
(2)
(3)
(4)
(5)
Alice
Bob
Alice → Bob
Bob → Alice
Alice and Bob
:
:
:
:
:
Alice chooses a random large integer a є Zp
Bob choses a random large integer b є Zp
Alice sends Bob ga (mod p)
Bob sends Alice gb (mod p)
compute gab
: Alice computes (gb)a = gab (mod p)
: Bob computes (ga)b = gab (mod p)
=> Alice and Bob now share secret gab
CNS2010
lecture 6 :: key management
9
diffie-hellman key exchange
Alice
p, g, ga (mod p)
Bob
gb (mod p)
Computes gab (mod p)
Computes gab (mod p)
Eve ???
Only knows p, g, ga, gb
CNS2010
lecture 6 :: key management
10
strength of diffie-hellman
•
The strength of Diffie-Hellman is based upon two issues:
– given p, g, ga, it is difficult to calculate a (the discrete logarithm problem)
– given p, g, ga, gb it is difficult for Eve to calculate gab (the Diffie-Hellman
problem)
– we know that DL  DH but it is not known if DH  DL.
•
Essentially, the strength of the system is based on the
difficulty of factoring numbers the same size as p.
•
The generator, g, can be small
•
Do not use the secret gab directly as a session key
– it is better to either hash it or use it as a seed for a PRNG – not all bits of
the secret have a flat distribution
CNS2010
lecture 6 :: key management
11
references
•
Handbook of Applied Cryptography
– read §1, §2-2.4.4, §2.5 - 2.5.3
•
Stallings (3rd Ed)
– 6.3 – 6.4
CNS2010
lecture 6 :: key management
12

similar documents