Transcript CSCI6268L07

Foundations of Network and
Computer Security
John Black
Lecture #7
Sep 13th 2005
CSCI 6268/TLEN 5831, Fall 2005
CBC MAC (again)
• Review:
– A common method is the CBC MAC:
• CBC MAC is stateless (no nonce N is used)
• Proven security in the ACMA model provided messages are
all of once fixed length
• Resistance to forgery quadratic in the aggregate length of
adversarial queries plus any insecurity of AES
• Widely used: ANSI X9.19, FIPS 113, ISO 9797-1
M1
M2
Mm
AESK
AESK
AESK
tag
Varying Message Lengths: XCBC
• There are several well-known ways to overcome this
limitation of CBC MAC
• XCBC, is the most efficient one known, and is provablysecure (when the underlying block cipher is
computationally indistinguishable from random)
– Uses blockcipher key K1 and needs two additional n-bit keys K2
and K3 which are XORed in just before the last encipherment
• A proposed NIST standard (as “CMAC”)
M1
AESK1
M2
AESK1
Mm
AESK1
tag
K2
if n divides |M|
K3
otherwise
UMAC: MACing Faster
• In many contexts, cryptography needs to be as
fast as possible
– High-end routers process > 1Gbps
– High-end web servers process > 1000 requests/sec
• But AES (a very fast block cipher) is already
more than 15 cycles-per-byte on a PPro
– Block ciphers are relatively expensive; it’s possible
to build faster MACs
• UMAC is roughly ten times as fast as current
practice
UMAC follows the Wegman-Carter
Paradigm
• Since AES is (relatively) slow, let’s avoid using it
unless we have to
– Wegman-Carter MACs provide a way to process M
first with a non-cryptographic hash function to reduce
its size, and then encrypt the result
Message M
hash key
hash function
hash(M)
encryption key
encrypt
tag
The Ubiquitous HMAC
• The most widely-used MAC (IPSec, SSL, many
VPNs)
• Doesn’t use a blockcipher or any universal hash
family
– Instead uses something called a “collision resistant
hash function” H
•
•
•
•
•
Sometimes called “cryptographic hash functions”
Keyless object – more in a moment
HMACK(M) = H(K © opad || H(K © ipad || M))
opad is 0x36 repeated as needed
ipad is 0x5C repeated as needed
Notes on HMAC
• Fast
– Faster than CBC MAC or XCBC
• Because these crypto hash functions are fast
• Slow
– Slower than UMAC and other universal-hash-family
MACs
• Proven security
– But these crypto hash functions have recently been
attacked and may show further weaknesses soon
What are cryptographic hash
functions?
• A cryptographic hash function takes a message from
{0,1}* and produces a fixed size output
• Output is called “hash” or “digest” or “fingerprint”
• There is no key
• The most well-known are MD5 and SHA-1 but there
are other options
• MD5 outputs 128 bits
• SHA-1 outputs 160 bits
Message
% md5
Hello There
Hash Function
^D
A82fadb196cba39eb884736dcca303a6
%
Output
e.g., MD5,SHA-1
512 bits
M1
SHA-1
...
M2
Mm
for i = 1 to m do
Wt =
t-th word of Mi
( Wt-3 © Wt-8 © Wt-14 © Wt-16 ) << 1
{
A H0i-1;
B  H1i-1;
C H2i-1;
0  t  15
16  t  79
D  H3i-1;
E  H4i-1
for t = 1 to 80 do
T  A << 5 + gt (B, C, D) + E + Kt + Wt
E D;
D C;
C B >> 2; B  A; A T
end
H0i A +H0i-1;
H3i  D + H3i-1;
H1i  B + H1i-1;
H4i  E + H4i-1
end
return H0m H1m H2m H3m H4m
H2i C+ H2i-1;
160 bits
Real-world applications
Hash functions are pervasive
• Message authentication codes (HMAC)
• Digital signatures (hash-and-sign)
• File comparison (compare-by-hash, eg, RSYNC)
• Micropayment schemes
• Commitment protocols
• Timestamping
• Key exchange
• ...
A cryptographic property
(quite informal)
1. Collision resistance
given a hash function
it is hard to find two colliding inputs
BAD: H(M) = M mod 701
M
H
H
M’
Strings
{0,1}n
More cryptographic properties
P1. Collision resistance
given a hash function
it is hard to find two colliding inputs
2. Second-preimage
resistance
given a hash function and
given a first input,
it is hard to find a second input
that collides with the first
3. Preimage resistance
given a hash function and
given an hash output
it is hard to invert that output
Merkle-Damgard construction
Compression function
M1
M3
M2
n
f
IV
h1
f
h2
f
k
k
Fixed initial value
Chaining value
MD Theorem: if f is CR, then so is H
h3 = H (M)
Mi1
...
M2
Mm
512 bits
for i = 1 to m do
Wt =
t-th word of Mi
( Wt-3 Wt-8 Wt-14  Wt-16 ) << 1
0  t  15
16  t  79
A H0i-1;
E  H4i-1
{
B  H1i-1;
C H2i-1;
D  H3i-1;
for t = 1 to 80 do
T  A << 5 + gt (B, C, D) + E + Kt + Wt
160 bits
E D; D C; C B >> 2; B  A; A T
end
H0..4i1
H0i A +H0i-1; H1i  B + H1i-1; H2i C+ H2i-1;
H3i  D + H3i-1; H4i  E + H4i-1
end
return H0m H1m H2m H3m H4m
160 bits
160 bits
Hash Function Security
• Consider best-case scenario (random
outputs)
• If a hash function output only 1 bit, how
long would we expect to avoid collisions?
– Expectation: 1£ 0 + 2 £ ½ + 3 £ ½ = 2.5
• What about 2 bits?
– Expectation: 1 £ 0 + 2 £ ¼ + 3 £ ¾ ½ + 4 £ ¾
½ ¾ + 5 £ ¾ ½ ¼ ¼ 3.22
• This is too hard…
Birthday Paradox
• Need another method
– Birthday paradox: if we have 23 people in a
room, the probability is > 50% that two will
share the same birthday
• Assumes uniformity of birthdays
– Untrue, but this only increases chance of birthday match
• Ignores leap years (probably doesn’t matter much)
– Try an experiment with the class…
Birthday Paradox (cont)
• Let’s do the math
– Let n equal number of people in the class
– Start with n = 1 and count upward
•
•
•
•
•
•
•
Let NBM be the event that there are No-Birthday-Matches
For n=1, Pr[NBM] = 1
For n=2, Pr[NBM] = 1 £ 364/365 ¼ .997
For n=3, Pr[NBM] = 1 £ 364/365 £ 363/365 ¼ .991
…
For n=22, Pr[NBM] = 1 £ … £ 344/365 ¼ .524
For n=23, Pr[NBM] = 1 £ … £ 343/365 ¼ .493
– Since the probability of a match is 1 – Pr[NBM] we
see that n=23 is the smallest number where the
probability exceeds 50%
Occupancy Problems
• What does this have to do with hashing?
– Suppose each hash output is uniform and random on
{0,1}n
– Then it’s as if we’re throwing a ball into one of 2n bins
at random and asking when a bin contains at least 2
balls
• This is a well-studied area in probability theory called
“occupancy problems”
– It’s well-known that the probability of a collision occurs
around the square-root of the number of bins
• If we have 2n bins, the square-root is 2n/2
Birthday Bounds
• This means that even a perfect n-bit hash
function will start to exhibit collisions when
the number of inputs nears 2n/2
– This is known as the “birthday bound”
– It’s impossible to do better, but quite easy to
do worse
• It is therefore hoped that it takes (264)
work to find collisions in MD5 and (280)
work to find collisions in SHA-1
The Birthday Bound
Probability
1.0
0.5
0.0
2n/2
2n
Number of Hash Inputs
Latest News
• At CRYPTO 2004 (August)
– Collisions found in HAVAL, RIPEMD, MD4, MD5, and
SHA-0 (240 operations)
• Wang, Feng, Lai, Yu
• Only Lai is well-known
– HAVAL was known to be bad
– Dobbertin found collisions in MD4 years ago
– MD5 news is big!
• CU team has lowered time-to-collision to 3 mins (July 2005)
– SHA-0 isn’t used anymore (but see next slide)
Collisions in SHA-0
M1, M1’
not in SHA-0
Wt =
{
t-th word of Mi
( Wt-3 Wt-8 Wt-14  Wt-16 ) << 1
A H0i-1;
B  H1i-1;
65
C H2i-1;
0  t  15
16  t  79
D  H3i-1;
E  H4i-1
for t = 1 to 80 do
T  A << 5 + gt (B, C, D) + E + Kt + Wt
E D;
D C;
C B >> 2; B  A; A T
end
H0..4i1
H0i A +H0i-1;
H3i  D + H3i-1;
H1i  A + H1i-1;
H4i  E + H4i-1
H2i C+ H2i-1;
Collision!
What Does this Mean?
• Who knows
– Methods are not yet understood
– Will undoubtedly be extended to more attacks
– Maybe nothing much more will happen
– But maybe everything will come tumbling
down?!
• But we have OTHER ways to build hash
functions
A Provably-Secure Blockcipher-Based
Compression Function
Mi
n bits
hi-1
n bits
hi
E
n bits
The Big (Partial) Picture
Second-Level
Protocols
(Can do proofs)
First-Level
Protocols
(Can do proofs)
SSH, SSL/TLS, IPSec
Electronic Cash, Electronic Voting
Symmetric
Encryption
Block
Ciphers
Stream
Ciphers
MAC
Schemes
Hash
Functions
Asymmetric
Encryption
Hard
Problems
Digital
Signatures
Primitives
(No one knows how to prove security; make assumptions)
Symmetric vs. Asymmetric
• Thus far we have been in the symmetric key
model
– We have assumed that Alice and Bob share some
random secret string
– In practice, this is a big limitation
• Bootstrap problem
• Forces Alice and Bob to meet in person or use some
mechanism outside our protocol
• Not practical when you want to buy books at Amazon
• We need the Asymmetric Key model!
Asymmetric Cryptography
• In this model, we no longer require an
initial shared key
– First envisioned by Diffie in the late 70’s
– Some thought it was impossible
– MI6 purportedly already knew a method
– Diffie-Hellman key exchange was first public
system
• Later turned into El Gamal public-key system
– RSA system announced shortly thereafter
But first, a little math…
• A group is a nonempty set G along with an
operation # : G £ G ! G such that for all a, b, c
2G
– (a # b) # c = a # (b # c)
– 9 e 2 G such that e # a = a # e = a
– 9 a-1 2 G such that a # a-1 = e
(associativity)
(identity)
(inverses)
• If 8 a,b 2 G, a # b = b # a we say the group is
“commutative” or “abelian”
– All groups in this course will be abelian
Notation
• We’ll get tired of writing the # sign and just use
juxtaposition instead
– In other words, a # b will be written ab
– If some other symbol is conventional, we’ll use it instead
(examples to follow)
• We’ll use power-notation in the usual way
– ab means aaaaa repeated b times
– a-b means a-1a-1a-1a-1 repeated b times
– Here a 2 G, b 2 Z
• Instead of e we’ll use a more conventional identity name
like 0 or 1
• Often we write G to mean the group (along with its
operation) and the associated set of elements
interchangeably
Examples of Groups
•
•
•
•
•
•
•
Z (the integers) under + ?
Q, R, C, under + ?
N under + ?
Q under £ ?
Z under £ ?
2 £ 2 matrices with real entries under £ ?
Invertible 2 £ 2 matrices with real entries under £ ?
• Note all these groups are infinite
– Meaning there are an infinite number of elements in them
• Can we have finite groups?
Finite Groups
• Simplest example is G = {0} under +
– Called the “trivial group”
• Almost as simple is G = {0, 1} under addition
mod 2
• Let’s generalize
–
–
–
–
–
–
Zm is the group of integers modulo m
Zm = {0, 1, …, m-1}
Operation is addition modulo m
Identity is 0
Inverse of any a 2 Zm is m-a
Also abelian
The Group Zm
• An example
–
–
–
–
–
Let m = 6
Z6 = {0,1,2,3,4,5}
2+5 = 1
3+5+1 = 3 + 0 = 3
Inverse of 2 is 4
• 2+4 = 0
• We can always pair an element with its inverse
a :
a -1 :
0
0
1
5
2
4
3
3
4
2
• Inverses are always unique
• An element can be its own inverse
– Above, 0 and 0, 3 and 3
5
1
Another Finite Group
• Let G = {0,1}n and operation is ©
– A group?
– What is the identity?
– What is the inverse of a 2 G?
• We can put some familiar concepts into
group-theoretic notation:
– Caesar cipher was just P + K = C in Z26
– One-time pad was just P © K = C in the group
just mentioned above
Multiplicative Groups
• Is {0, 1, …, m-1} a group under
multiplication mod m?
– No, 0 has no inverse
• Ok, toss out 0; is {1, …, m-1} a group
under multiplication mod m?
– Hmm, try some examples…
•
•
•
•
m = 2, so G = {1}
X
m = 3, so G = {1,2}
X
m = 4, so G = {1,2,3} oops!
m = 5, so G = {1,2,3,4} X
Multiplicative Groups (cont)
• What was the problem?
– 2,3,5 all prime
– 4 is composite (meaning “not prime”)
• Theorem: G = {1, 2, …, m-1} is a group under
multiplication mod m iff m is prime
Proof:
Ã: suppose m is composite, then m = ab where a,b 2
G and a, b  1. Then ab = m = 0 and G is not closed
!: follows from a more general theorem we state in a
moment
The Group Zm*
• a,b 2 N are relatively prime iff gcd(a,b) = 1
– Often we’ll write (a,b) instead of gcd(a,b)
• Theorem: G = {a : 1 · a · m-1, (a,m) = 1}
and operation is multiplication mod m
yields a group
– We name this group Zm*
– We won’t prove this (though not too hard)
– If m is prime, we recover our first theorem
Examples of Zm*
• Let m = 15
– What elements are in Z15*?
• {1,2,4,7,8,11,13,14}
– What is 2-1 in Z15*?
• First you should check that 2 2 Z15*
• It is since (2,15) = 1
– Trial and error:
• 1, 2, 4, 7, 8 X
– There is a more efficient way to do this called
“Euclid’s Extended Algorithm”
• Trust me
Euler’s Phi Function
• Definition: The number of elements of a group G
is called the order of G and is written |G|
– For infinite groups we say |G| = 1
– All groups we deal with in cryptography are finite
• Definition: The number of integers i < m such
that (i,m) = 1 is denoted (m) and is called the
“Euler Phi Function”
– Note that |Zm*| = (m)
– This follows immediately from the definition of ()
Evaluating the Phi Function
• What is (p) if p is prime?
– p-1
• What is (pq) if p and q are distinct
primes?
– If p, q distinct primes, (pq) = (p)(q)
– Not true if p=q
– We won’t prove this, though it’s not hard
Examples
• What is (3)?
– |Z3*| = |{1,2}| = 2
• What is (5)?
• What is (15)?
– (15) = (3)(5) = 2 £ 4 = 8
– Recall, Z15* = {1,2,4,7,8,11,13,14}