Transcript public key

IS410: Information Security
Lecture 6: Key Management
Course Information
 Lecturer: Dr. Walid Khedr
 [email protected]

http://groups.yahoo.com/group/CS_Network_Security
 Course Readings:
 Lecture Notes
 The Textbook
2/55
Course Syllabus
 Introduction
 Cryptography







Classical Encryption Techniques
Block Ciphers and the Data Encryption Standard
More on Symmetric Ciphers
Public-Key Cryptography and RSA
Key Management
Hash and MAC Algorithms
Digital Signatures Standard
 Real-World Information Security Protocols
 Authentication Protocols
 Secure Electronic Transaction (SET)
 Access Control
3/55
Course Syllabus
 Cryptography
 Key Management
 Key Management
 Diffie-Hellman Key Exchange
4/55
Last Lecture
 Public-Key Cryptography and RSA
 Principles of Public-Key Cryptosystems
 The RSA Algorithm
5/55
Key Management
 Key management is the set of
techniques and procedures supporting
the establishment and maintenance
of keying relationships between
authorized parties.
 Key management includes techniques
and procedures supporting:
1. Storing Keying materials;
2. establishment, distribution, and
installation of keying material;
3. Update and revocation of keying material
6/55
7/55
Importance of Key Management
8/55
Key Management –two problems
 Distribution of public keys (for public-key
cryptography)
 Distribution of secret keys (for classical
cryptography)
 This has more to do with authentication of the
users
9/55
Distribution of Public Keys
 Several techniques have been
proposed for the distribution of public
keys:
1.
2.
3.
4.
Public announcement
Publicly available directory
Public-key authority
Public-key certificates
10/55
Public Announcement
 If Alice and Bob do not know each other,
how do they get each other’s public key to
communicate with each other?
 Solution 1: append your public key to the
end of your email
 Attack: emails can be forged:
 Eve sends an email to Bob pretending she is
Alice and handing him a public key
 Eve will be able to communicate with Bob
pretending she is Alice
11/55
Public Announcement – Cont.
 Solution 2: post it on your website
 Attack: Eve breaks into the DNS server
and sends Alice a fake webpage
purportedly of Bob’s
 Alice encrypts the message using that
public key and Eve will be able to read it
 Eve may even modify the message and
forwards it to Bob using his public key
12/55
Public Announcement – Cont.
13/55
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 (e.g. in person)
with directory
 participants can replace key at any time
 directory is periodically published
 directory can be accessed electronically
 Still vulnerable to tampering or forgery.
14/55
Publicly Available Directory
15/55
Public-Key Authority
16/55
Public-Key Authority – Cont.
 The scenario is attractive, yet it has
some drawbacks.
 The public-key authority could be
somewhat of a bottleneck in the system.
 As before, the directory of names and
public keys maintained by the authority
is vulnerable to tampering.
17/55
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
18/55
Public-Key Certificates
19/55
Public-Key Certificates
 We can place the following requirements on
this scheme:
1. Any participant can read a certificate to
determine the name and public key of the
certificate's owner.
2. Any participant can verify that the certificate
originated from the certificate authority.
3. Only the certificate authority can create and
update certificates.
4. Any participant can verify the currency of the
certificate.
20/55
A standard for certificates: X.509
 To avoid having different types of
certificates for different users
standard X.509 has been issued for
the format of certificates –widely
used over the Internet.
 At its core, X.509 is a way to describe
certificates.
 X.509 certificates are used in most
network security applications,
including IP security, secure sockets
layer (SSL)
21/55
Distribution of Secret Keys Using Public-Key
Cryptography
 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
22/55
Simple Secret Key Distribution
1. A generates a public/private key pair {PUa, PRa} and
transmits a message to B consisting of PUa and an
identifier of A, IDA.
2. B generates a secret key, Ks, and transmits it to A,
encrypted with A's public key.
3. A computes D(PRa, E(PUa, Ks)) to recover the secret
key. Because only A can decrypt the message, only A
and B will know the identity of Ks.
4. A discards PUa and PRa and B discards PUa.
23/55
Man-in-the-Middle Attack (MITM)
1 A generates a public/private key pair {PUa, PRa} and
transmits a message intended for B consisting of PUa
and an identifier of A, IDA.
2 E intercepts the message, creates its own public/private
key pair {PUe, PRe} and transmits PUe||IDA to B.
3 B generates a secret key, Ks, and transmits E(PUe, Ks).
4 E intercepts the message, and learns Ks by computing
D(PRe, E(PUe, Ks)).
5 E transmits E(PUa, Ks) to A.
24/55
Man-in-the-Middle Attack (MITM)
25/55
Secret Key Distribution with
Confidentiality and authentication
 If have securely exchanged public-keys:
26/55
Discrete Logarithms
 What is a logarithm?
 the logarithm of a number to a given base is the
power or exponent to which the base must be
raised in order to produce that number.
 log10100 = 2 because 102 = 100
 In general if logmb = a then ma = b
 Where m is called the base of the logarithm
 A discrete logarithm can be defined for
integers only
 In fact we can define discrete logarithms
mod p also where p is any prime number
27/55
Discrete Logarithm Problem
 The security of the Diffie-Hellman algorithm
depends on the difficulty of solving the
discrete logarithm problem (DLP) in the
multiplicative group of a finite field
 consider (Z17). To compute 34 in this group, we
compute 34 mod 17 = 13
 Discrete logarithm is just the inverse operation.
For example, take the equation 3k ≡ 13 (mod
17) for k.
 As shown above k=4 is a solution, but it is not
the only solution. Since if n is an integer then
34+16 n ≡ 13 (mod 17).
28/55
Sets, Groups and Fields
 A set is any collection of objects
called the elements of the set
 Examples of sets: R, Z, Q
 If we can define an operation on the
elements of the set and certain rules
are followed then we get other
mathematical structures called groups
and fields
29/55
Groups
 A group is a set G with a custom-defined binary
operation + such that:
 The group is closed under +, i.e., for a, b  G:
 a+bG
 The Associative Law holds i.e., for any a, b, c  G:
 a + (b + c) = (a + b) + c

There exists an identity element 0, such that
 a+0=a
 For each a  G there exists an inverse element –a
such that
 a + (-a) = 0
 If for all a, b  G: a + b = b + a then the group is
called an Abelian or commutative group
 If a group G has a finite number of elements it is
called a finite group
30/55
More About Group Operations
 + does not necessarily mean normal
arithmetic addition
 + just indicates a binary operation
which can be custom defined
 The group operation could be denoted
as •
 The group notation with + is called
the additive notation and the group
notation with • is called the
multiplicative notation
31/55
Fields
 A field is a set F with two custom-defined binary
operations + and • such that:
 The Field is closed under + and •, i.e., for a, b  F:
 a + b  F and a • b  F
 The Associative Law holds i.e., for any a, b, c  F:
 a + (b + c) = (a + b) + c and a • (b • c) = (a • b) • c

There exist identity elements 0 and 1, such that
 a + 0 = a and a • 1 = a
 For each a  F there exist inverse elements –a and a1such that
 a + (-a) = 0 and a • a-1 = 1
 If a field F has a finite number of elements it is called
a finite field
32/55
Examples of Groups
 Groups








Set
Set
Set
Set
Set
Set
Set
Set



Set of real numbers R under + and *
Set of integers Z under + and *
Set of integers modulo a prime number p under + and * ZP
 Fields
of
of
of
of
of
of
of
of
real numbers R under +
real numbers R under *
integers Z under +
integers Z under *?
integers modulo a prime number p under +
integers modulo a prime number p under *
3 X 3 matrices under + meaning matrix addition
3 X 3 matrices under * meaning matrix multiplication?
33/55
Generator of Group
 If for a  G, all members of the group can
be written in terms of a by applying the
group operation * on ‘a’ a number of times
then a is called a generator of the group G
 Examples
 2 is a generator of Z*11
 2 and 3 are generator of Z*19
m
2m mod 11
1
2
3
4
5
6
7
8
9
10
2
4
8
5
10
9
7
3
6
1
m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2m mod 19
2
4
8
16
13
7
14
3
6
17
15
11
3
6
12
5
10
1
3m mod 19
3
9
8
5
15
7
2
6
18
16
10
11
14
4
12
17
13
1
34/55
Primitive Roots
 If xn = a then a is called the n-th root of x
 For any prime number p, if we have a number a such that
powers of a mod p generate all the numbers between 1
to p-1 then a is called a Primitive Root of p.
 In terms of the Group terminology a is the generator
element of the multiplicative group of the finite field
formed by mod p
 Then for any integer b and a primitive root a of prime
number p we can find a unique exponent i such that
b = ai mod p
 The exponent i is referred to as the discrete logarithm
or index, of b for the base a.
35/55
36/55
Diffie-Hellman Key Exchange
 First public-key type scheme
proposed
 By Diffie & Hellman in 1976 along
with the exposition of public key
concepts
 Is a practical method for public
exchange of a secret key
 Used in a number of commercial
products
37/55
Diffie-Hellman Key Exchange
 a public-key distribution scheme
 cannot be used to exchange an arbitrary
message
 rather it can establish a common key
 known only to the two participants
 value of key depends on the participants
(and their private and public key
information)
 based on exponentiation in a finite (Galois)
field (modulo a prime or a polynomial) easy
 security relies on the difficulty of computing
discrete logarithms (similar to factoring) –
hard
38/55
Discrete Logarithms
What is a logarithm?
log10100 = 2 because 102 = 100
In general if logmb = a then ma = b
Where m is called the base of the
logarithm
 A discrete logarithm can be defined
for integers only
 In fact we can define discrete
logarithms mod p also where p is any
prime number




39/55
Discrete Logarithm Problem
 The security of the Diffie-Hellman
algorithm depends on the difficulty of
solving the discrete logarithm
problem (DLP) in the multiplicative
group of a finite field
 Y = aX mod p
 X = logaY mod p
40/55
Diffie-Hellman Key Exchange
41/55
Diffie-Hellman Algorithm
 Five Parts
1.
2.
3.
4.
5.
Global Public Elements
User A Key Generation
User B Key Generation
Generation of Secret Key by User A
Generation of Secret Key by User B
42/55
Global Public Elements
 q:
 :
Prime number
 < q and  is a primitive
root
of q
 The global public elements are also
sometimes called the domain
parameters
43/55
User A Key Generation
 Select private XA
 Calculate public YA
mod q
XA < q
YA =  XA
44/55
User B Key Generation
 Select private XB
 Calculate public YB
mod q
XB < q
YB =  XB
45/55
Generation of Secret Key by User A
 K = (YB)XA mod q
46/55
Generation of Secret Key by User B
 K = (YA)XB mod q
47/55
Diffie-Hellman Key Exchange
48/55
Diffie-Hellman Example
 q = 97
 =5
 XA = 36
 XB = 58
 YA = 536 = 50 mod 97
 YB = 558 = 44 mod 97
 K = (YB)XA mod q = 4436 mod 97 = 75 mod 97
 K = (YA)XB mod q = 5058 mod 97 = 75 mod 97
49/55
Diffie-Hellman Example
50/55
Diffie-Hellman MITM Attack
g X A mod p Y A
Y BX A mod p  K AB
YA
YB
K AB
g X B mod p Y B
Y AX B mod p  K BA
52/55
Diffie-Hellman MITM Attack
g X A mod p Y A
g X B mod p Y B
Y DX1A mod p  K 1  K AD
Y DX2B mod p  K 2  K BD
Y D2
K1 Y D1 Y A
g X D 1 mod p Y D 1
YB K2
g X D 2 mod p Y D 2
Y AX D 1 mod p  K 1  K AD Y BX D 2 mod p  K 2  K BD
54/55
Summary
 Have considered:
 Key Management
 Diffie-Hellman Key Exchange
 Reading: Chapter 6
55/55
Thank You . . .
56/55