Cryptography and Network
Key Management and generation
Cryptography and Network Security
Key Exchange
Public key systems are much slower than
private key system
Public key system is then often for short data
Signature, key distribution
Key distribution
One party chooses the key and transmits it to other user
Key agreement
Protocol such two parties jointly establish secret key over
public communication channel
Key is the function of inputs of two users
Cryptography and Network Security
Distribution of Public Keys
can be considered as using one of:
Public
announcement
Publicly available directory
Public-key authority
Public-key certificates
Cryptography and Network Security
Public Key Management
Simple one: publish the public key
Such
as newsgroups, yellow-book, etc.
But it is not secure, although it is convenient
Anyone can forge such a announcement
Ex: user B pretends to be A, and publish a key for A
Then all messages sent to A, readable by B!
Let trusted authority maintain the keys
Need to verify the identity, when register keys
User can replace old keys, or void old keys
Cryptography and Network Security
Possible Attacks
Observe all messages over the channel
So
assume that all plaintext messages are available to
all
Save messages for reuse later
So have to avoid replay attack
Masquerade various users in the network
So have to be able to verify the source of the message
Cryptography and Network Security
Public Announcement
users distribute public keys to recipients
or broadcast to community at large
eg. append PGP (pretty good privacy) keys to email
messages or post to news groups or email list
major weakness is forgery
anyone can create a key claiming to be someone else
and broadcast it
until forgery is discovered can masquerade as claimed
user
Cryptography and Network Security
Publicly Available Directory
can obtain greater security by registering
keys with a public directory
directory must be trusted with properties:
contains {name,public-key} entries
participants register securely with directory
participants can replace key at any time
directory is periodically published
directory can be accessed electronically
still vulnerable to tampering or forgery
Cryptography and Network Security
Public-Key Authority
improve security by tightening control over
distribution of keys from directory
has properties of directory
and requires users to know public key for
the directory
then users interact with directory to
obtain any desired public key securely
does
require real-time access to directory when keys are
needed
Cryptography and Network Security
Public-Key Authority
Cryptography and Network Security
Cont.
More advanced distribution
A
sends request-for-key(B) to authority with timestamp, that is, Ida|Idb|Time
Authority replies with key(B) (encrypted by its private
key), that is EKTta(KUb| Ida|Idb|Time)
A initiates a message to B, including a random number
Na, its IDA
B then ask authority to get key(A)
B sends A (encrypted by As public key) Na and Nb
A then replies B Nb encrypted by Bs public key
Cryptography and Network Security
10
Cont.
In above scheme, the authority is
bottleneck
New approach: certificate
Any user can read certificate, determine name and
public key of the certificates owner
Any user can verify the authority of certificate
Only the authority can create and update certificate
Any user can verify the time-stamp of certificate
The certificate is
CA=EKRauth[T,IDA, KUA], where the EKRauth is the private key
used by the authority.
Time-stamp is to avoid reuse of voided key
Cryptography and Network Security
11
Public-Key Certificates
Cryptography and Network Security
12
Public-Key Certificates
certificates allow key exchange without real-time access to
public-key authority
a certificate binds identity to public key
usually with other info such as period of validity, rights of use etc
with all contents signed by a trusted Public-Key or
Certificate Authority (CA)
can be verified by anyone who knows the public-key
authorities public-key
To validate the certificate, we need another certificate, one
that matches the Issuer (of CA) in the first certificate.
Then we take the RSA public key from the second (CA)
certificate, use it to decode the signature on the first
certificate to obtain an MD5 hash, which must match an
actual MD5 hash computed over the rest of the certificate.
Cryptography and Network Security
13
X.509
The structure of a X.509 v3 digital certificate is as follows:
Certificate
Version
Serial Number
Algorithm ID
Issuer
Validity
Not Before
Not After
Subject
Subject Public Key Info
Public Key Algorithm
Subject Public Key
Issuer Unique Identifier (Optional)
Subject Unique Identifier (Optional)
Extensions (Optional)
...
Certificate Signature Algorithm
Certificate Signature
Cryptography and Network Security
14
Sample Certificate
Certificate:
Data: Version: 1 (0x0)
Serial Number: 7829 (0x1e95)
Signature Algorithm: md5WithRSAEncryption
Issuer: C=ZA, ST=Western Cape, L=Cape Town, O=Thawte Consulting cc, OU=Certification Services
Division, CN=Thawte Server CA/emailAddress=server-certs@[Link]
Validity
Not Before: Jul 9 16:04:02 1998 GMT
Not After : Jul 9 16:04:02 1999 GMT
Subject: C=US, ST=Maryland, L=Pasadena, O=Brent Baccala, OU=FreeSoft,
CN=[Link]/emailAddress=baccala@[Link]
Subject Public Key Info: Public Key Algorithm: rsaEncryption
RSA Public Key: (1024 bit)
Modulus (1024 bit): 00:b4:31:98:0a:c4:bc:62:c1:88:aa:dc:b0:c8:bb:
33:35:19:d5:0c:64:b9:3d:41:b2:96:fc:f3:31:e1: 66:36:d0:8e:56:12:44:ba:75:eb:e8:1c:9c:5b:66:
70:33:52:14:c9:ec:4f:91:51:70:39:de:53:85:17: 16:94:6e:ee:f4:d5:6f:d5:ca:b3:47:5e:1b:0c:7b:
c5:cc:2b:6b:c1:90:c3:16:31:0d:bf:7a:c7:47:77: 8f:a0:21:c7:4c:d0:16:65:00:c1:0f:d7:b8:80:e3:
d2:75:6b:c1:ea:9e:5c:5c:ea:7d:c1:a1:10:bc:b8: e8:35:1c:9e:27:52:7e:41:8f
Exponent: 65537 (0x10001)
Signature Algorithm: md5WithRSAEncryption
93:5f:8f:5f:c5:af:bf:0a:ab:a5:6d:fb:24:5f:b6:59:5d:9d:
92:2e:4a:1b:8b:ac:7d:99:17:5d:cd:19:f6:ad:ef:63:2f:92:
ab:2f:4b:cf:0a:13:90:ee:2c:0e:43:03:be:f6:ea:8e:9c:67:
d0:a2:40:03:f7:ef:6a:15:09:79:a9:46:ed:b7:16:1b:41:72:
0d:19:aa:ad:dd:9a:df:ab:97:50:65:f5:5e:85:a6:ef:19:d1:
5a:de:9d:ea:63:cd:cb:cc:6d:5d:01:85:b5:6d:c8:f3:d9:f7:
8f:0e:fc:ba:1f:34:e9:96:6e:6c:cf:f2:ef:9b:bf:de:b5:22: 68:9f
Cryptography and Network Security
15
Public-Key Distribution of Secret
Keys
use previous methods to obtain public-key
can use for secrecy or authentication
but public-key algorithms are slow
so usually want to use private-key
encryption to protect message contents
hence need a session key
have several alternatives for negotiating a
suitable session
Cryptography and Network Security
16
Simple Secret Key Distribution
proposed by Merkle in 1979
A
generates a new temporary public key pair
A sends B the public key and their identity
B generates a session key K sends it to A encrypted
using the supplied public key
A decrypts the session key and both use
problem is that an opponent can intercept
and impersonate both halves of protocol
Cryptography and Network Security
17
Secret key Distribution
Simple secret key distribution
A
generates KUA and KRA, sends KUA to B
B generates a secret key ks
B sends ks to A using As public key KUA
A decrypts the message to get the secret key ks
To get more security, the public/private
keys can be regenerated when needed
But vulnerable to the active attack!
Attacker E can compromise the communication
between A and B as follows
Cryptography and Network Security
18
Cont.
Attacking
A
generates KUA and KRA, sends IDA, KUA to B
E intercepts the message, transmits IDA, KUE to B
B generates a secret key ks
B sends ks to A using As public key KUE
E intercepts the message, decrypt it and get ks
E sends A the message Ks, encrypted by KUA
A decrypts the message to get the secret key ks
Now E knows Ks, but A, B are unaware of it
Cryptography and Network Security
19
Secret Key Distribution
So need confidentiality and authentication
A
and B need to use a secure method to exchange their
public keys
Schemes
A initiates a message to B, EKUB(Na,IDa)
B replies it with EKUA(Na,Nb)
A then replies it with EKUB(Nb)
A sends B the message EKUB (EKRA(Ks))
Security
The first 3 steps are used to assure that A is A, B is B
Cryptography and Network Security
20
Public-Key Distribution of Secret
Keys
if have securely exchanged public-keys:
Cryptography and Network Security
21
Diffie-Hellman Key Predist.
Note:Please check your book and your class notes for this
algorithm.
Computationally secure
if discrete logarithm is intractable
Scheme
Assume prime number p public and an integer c public
Each user u has secret component au
User u computes bu=c au mod p
TA certifies it by computing
(ID(u), bu, sigTA(ID(u), bu))
The
common key of two users u and v is
K=c au av mod p
Cryptography and Network Security
22
Diffie-Hellman Key Exchange
Computationally secure
if
discrete logarithm is intractable
Scheme
Assume prime number p public and an integer c public
Each user u chooses a secret component au (new!)
User u computes bu=c au mod p
User v computes bv=c av mod p
The common key of two users u and v is
K=c au av mod p
Cryptography and Network Security
23
Diffie-Hellman Problem
Diffie-Hellman problem definition
Given bu=gau
mod p, bv=gav mod p, how to compute
gavau mod p? Here g is a primitive element of mod p
The problem is not harder than the discrete logarithmetic problem, because the later one can always be
used to solve it
It can be proved that it has the same difficulty as the
ElGamal encryption system
Cryptography and Network Security
24
