Symmetric Key Cryptography
Key Distribution Problem
• Secret key cryptography
• The two parties must share the same key.
• The key must be protected from access by others
• Frequent key changes desirable
• The success of the cryptographic system depends
on the security of the Key distribution process
1
Some possible methods of distributing key
-Alice selects and physically delivers to Bob
-A third party selects and delivers to both Alice and
Bob
-Alice selects and transmits to Bob a new key
encrypted using the old key
-A third party selects and transmits the key to Alice
and Bob using encrypted links
2
Observations(issues arising from possible methods)
• Options 1 and 2 call for manual delivery
• may be reasonable for link-to-link but awkward for end-
to-end
• scale of problem depends on number of communicating
pairs
• Option 3 is suitable for link-to-link and end-to-end
• but if one key is compromised, all subsequent keys are
compromised
• initial distribution of large number of keys still manual
3
Key Distribution Methods
1. Key distribution center (KDC) technique for end to end
communication(use of third party)
Two methods without third party
2. Merkles Puzzle
3. Diffie-Helman Algorithm
4
KDC EXPLAINED
5
The KDC concept
Key selection and distribution is the responsibility of a
KDC
Every user, e.g. Alice, has a secure link with the KDC.
The link is secured by encryption using a master key,
Kma
For every session between two parties, Alice and Bob,
the KDC issues a session key, Ksab on request from one
of the parties.
• The key is relayed to both parties on the secure links
6
The KDC concept: Key issue steps
• Alice sends a request to the KDC for a session key to be used for a
secure session with Bob
• The KDC responds with a message encrypted with Kma for Alice. The
message contains
The Session key, Ksab
Original request message
A message for Bob
7
The KDC concept: Key issue steps
The message for Bob is encrypted using Kmb
and contains
The session key, Ksab
Alice’s ID
8
The KDC concept: Key issue steps
• Alice
• decrypts the message from KDC,
• verifies request,
• stores the session key
• forwards to Bob the the latter’s message
• Bob
• decrypts the message forwarded by Alice
• verifies Alice’s ID and
• extracts the session key.
9
The KDC concept: Key issue steps
• Alice and Bob now have the session key and may begin their secured
communication session.
10
The KDC concept: Key issue steps
Issues of authentication/integrity:
• Can an intruder masquerade as the KDC and spoof Alice?
• Where is the proof to Bob of Alice’s identity?
11
Key Exchange Problem
• Physical Exchange option
• Use trusted physically secure courier system
Frequent key changes may be very costly
Infrequent key changes loss of security
How trustworthy is the trusted party (courier)? how secure?
KDC option
Need for trusted KDCs
Requirement for “registration” with a KDC
Substantial communication overhead
KDC bottleneck
Require secure exchange of master-keys
Reading assignment:
a)Kerberos
b) Certificate Authority
12
Key Exchange without a third party
• Merkle’s Puzzles Key Exchange System
• Diffie-Hellman Exponential Key Exchange System
13
Merkle’s Puzzle’s Key Exchange System
Alice:
• Create 1 million encryption keys.
• Hide each key in a “puzzle”
(e.g. encrypt each with a short 20bit key).
• Unscrambling each puzzle takes approx 2 mins.
• Send the 1 million “puzzles” to Bob
14
Merkle’s Puzzle’s Key Exchange System
Bob:
• Receive “puzzles” and pick any one
• Unscramble it revealing the key inside, Ks
• Encrypt a mutually agreed upon message (eg block
of zeros) with this key
• Send back to Alice
15
Merkle’s Puzzle’s Key Exchange System
Alice:
• Try each of the one million keys on the received
message (brute force)
• The key that successfully reveals the mutually
agreed upon message will be Ks
Alice and Bob:
• Use Ks as the session key for the subsequent
communication
16
Diffie-Hellman Exponential Key Exchange System
Concept:
• The two participants each start with a secret key.
Xa and Xb
• By exchanging some information based on the two keys they
securely derive a secret session key.
Ks
17
Diffie-Hellman Exponential Key Exchange System
• A Mathematical Implementation:
• Alice and Bob agree on two numbers and q (need not be secret)
• Alice chooses Xa, computes Ya = f(,q,Xa), sends Ya to Bob
• Bob chooses Xb, computes Yb = f(,q,Xb), sends Yb to Alice
• Alice computes Ks = g(Xa,Yb)
• Bob computes Ks = g(Xb,Ya)
18
Diffie-Hellman Exponential Key Exchange System
• A Mathematical Implementation:
• The functions f and g need not be secret
• Its required that g(Xa,Yb) = g(Xb,Ya) for all Xa and Xb so that
keys Ks computed by Alice and Bob should be
identical!
• It should be very difficult to infer Xa (or Xb) from Ya (or Yb),
i.e. f is a one-way function.
19
Diffie-Hellman Exponential Key Exchange System
• Functions f and g:
• Choose f to be the exponential function:
y = f(x) = x mod q, so that
Ya = Xa mod q Yb = Xb mod q
• Choose g to be the exponential function:
k = g(x,y) = yx mod q , so that
Ks = YbXa mod q = [Link] mod q
Ks = YaXb mod q = [Link] mod q
20
Diffie-Hellman Exponential Key Exchange System
How secure?
Intruder can obtain , q, Ya and Yb
Needs to compute either Xa or Xb
Require application of “discrete logarithms” very difficult!
Concept of one way function
21