Course: Cryptography and Network Security
Branch: B.Tech
Lecture – 16 : Key Management
Department of Computer Science and Engineering
Motilal Nehru National Institute of Technology Allahabad,
Prayagraj-211004
SYMMETRIC-KEY DISTRIBUTION
If Alice needs to exchange confidential messages with N people, she needs N
different keys.
What if N people need to communicate with each other? A total of N(N − 1) keys
is needed if we require that Alice and Bob use two keys for bidirectional
communication; only N(N − 1)/2 keys are needed if we allow a key to be used for
both directions.
This means that if one million people need to communicate with each other, each
person has almost one million different keys; in total, almost one trillion keys are
needed.
This is normally referred to as the N2 problem because the number of required
keys for N entities is N2.
SYMMETRIC-KEY DISTRIBUTION
The number of keys is not the only problem; the distribution of keys is
another.
If Alice and Bob want to communicate, they need a way to exchange a
secret key; if Alice wants to communicate with one million people,
how can she exchange one million keys with one million people?
Using the Internet is definitely not a secure method.
It is obvious that we need an efficient way to maintain and distribute
secret keys.
Key-Distribution Center: KDC
A practical solution is the use of a trusted third party, referred to as a
key-distribution center (KDC).
To reduce the number of keys, each person establishes a shared
secret key with the KDC
Key-Distribution Center: KDC
A secret key is established between the KDC and each member. Alice
has a secret key with the KDC, which we refer to as KAlice; Bob has a
secret key with the KDC, which we refer to as KBob; and so on.
Now the question is how Alice can send a confidential message to
Bob. The process is as follows:
Alice sends a request to the KDC stating that she needs a session
(temporary) secret key between herself and Bob.
The KDC informs Bob about Alice’s request.
If Bob agrees, a session key is created between the two.
SYMMETRIC-KEY AGREEMENT
Alice and Bob can create a session key between themselves without
using a KDC.
This method of session-key creation is referred to as the symmetric-
key agreement.
Although there are several ways to accomplish this, only two common
methods, DiffieHellman and station-to-station, are discussed
SYMMETRIC-KEY AGREEMENT
Alice and Bob can create a session key between themselves without
using a KDC.
This method of session-key creation is referred to as the symmetric-
key agreement.
Although there are several ways to accomplish this, only two common
methods, DiffieHellman and station-to-station, are discussed
Diffie-Hellman Key Agreement
In the Diffie-Hellman protocol two parties create a symmetric session
key without the need of a KDC.
Before establishing a symmetric key, the two parties need to choose
two numbers p and g.
The first number, p, is a large prime number on the order of 300
decimal digits (1024 bits).
The second number, g, is a generator of order p − 1 in the group <Zp*,
×>.
These two (group and generator) do not need to be confidential. They
can be sent through the Internet; they can be public.
Diffie-Hellman Key Agreement
The steps are as follows:
1. Alice chooses a large random number x such that 0 ≤ x ≤ p − 1 and
calculates R1 = gx mod p.
2. Bob chooses another large random number y such that 0 ≤ y ≤ p − 1 and
calculates R2 = gy mod p.
3. Alice sends R1 to Bob. Note that Alice does not send the value of x; she
sends only R1.
4. Bob sends R2 to Alice. Again, note that Bob does not send the value of y,
he sends only R2.
5. Alice calculates K = (R2)x mod p.
6. Bob also calculates K = (R1)y mod p
Diffie-Hellman Key Agreement
Diffie-Hellman Key Agreement
Bob has calculated K = (R1)y mod p = (gx mod p)y mod p = gxy mod p.
Alice has calculated K = (R2)x mod p = (gy mod p)x mod = gxy mod p.
Both have reached the same value without Bob knowing the value of x and without
Alice knowing the value of y.
The symmetric (shared) key in the Diffie-Hellman method is K = gxy mod p
Diffie-Hellman Key Agreement
Security of Diffie-Hellman
The Diffie-Hellman key exchange is susceptible to two attacks: the discrete
logarithm attack and the man-in-the-middle attack
Man-in-the-Middle Attack The protocol has another weakness. Eve does
not have to find the value of x and y to attack the protocol.
She can fool Alice and Bob by creating two keys: one between herself and
Alice, and another between herself and Bob.
Security of Diffie-Hellman
The following can happen:
1. Alice chooses x, calculates R1 = gx mod p, and sends R1 to Bob.
2. Eve, the intruder, intercepts R1. She chooses z, calculates R2 = gz mod p, and
sends R2 to both Alice and Bob.
3. Bob chooses y, calculates R3 = gy mod p, and sends R3 to Alice. R3 is intercepted
by Eve and never reaches Alice.
4. Alice and Eve calculate K1 = gxz mod p, which becomes a shared key between
Alice and Eve. Alice, however, thinks that it is a key shared between Bob and
herself.
5. Eve and Bob calculate K2 = gzy mod p, which becomes a shared key between Eve
and Bob. Bob, however, thinks that it is a key shared between Alice and himself.
Security of Diffie-Hellman
Security of Diffie-Hellman
This situation is called a man-in-the-middle attack because Eve comes in
between and intercepts R1, sent by Alice to Bob, and R3, sent by Bob to
Alice.
It is also known as a bucket brigade attack because it resembles a short line
of volunteers passing a bucket of water from person to person.
Station-to-Station Key Agreement
The station-to-station protocol
is a method based on Diffie-
Hellman.
It uses digital signatures with
public-key certificates to
establish a session key between
Alice and Bob
Station-to-Station Key Agreement
The following shows the steps:
After calculating R1, Alice sends R1 to Bob (steps 1 and 2 in Figure).
After calculating R2 and the session key, Bob concatenates Alice’s ID, R1, and
R2. He then signs the result with his private key. Bob now sends R2, the
signature, and his own public-key certificate to Alice. The signature is
encrypted with the session key (steps 3, 4, and 5 in Figure).
After calculating the session key, if Bob’s signature is verified, Alice
concatenates Bob’s ID, R1, and R2. She then signs the result with her own
private key and sends it to Bob. The signature is encrypted with the session
key (steps 6, 7, and 8 in Figure).
If Alice’s signature is verified, Bob keeps the session key (step 9 in Figure)
Security of Station-to-Station Protocol
The station-to-station protocol prevents man-in-the-middle attacks.
After intercepting R1, Eve cannot send her own R2 to Alice and pretend it is
coming from Bob because Eve cannot forge the private key of Bob to create
the signature the signature cannot be verified with Bob’s public key
defined in the certificate.
In the same way, Eve cannot forge Alice’s private key to sign the third
message sent by Alice.
The certificates, are trusted because they are issued by trusted authorities.
Public-Key Infrastructures (PKI)
