Transcript Message Authentication and Hash Function

Message Authentication and Hash Functions
1
Message Authentication and
Hash Functions
•
•
•
•
•
Authentication Requirements
Authentication Functions
Message Authentication Codes
Hash Functions
Security of Hash Functions and MACs
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
2
Authentication Requirements
•
Kind of attacks (threats) in the context of
communications across a network
1.
2.
3.
4.
5.
6.
7.
•
Disclosure
Traffic analysis
Masquerade
Content modification
Sequence modification
Timing modification
Repudiation
Measures to deal with first two attacks:
– In the realm of message confidentiality, and are addressed with
encryption
•
Measures to deal with items 3 thru 6
– Message authentication
•
Measures to deal with items 7
– Digital signature
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
3
Authentication Requirements
• Message authentication
– A procedure to verify that messages come from the alleged
source and have not been altered
– Message authentication may also verify sequencing and
timeliness
• Digital signature
– An authentication technique that also includes measures to
counter repudiation by either source or destination
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
4
Authentication Functions
Authentication Functions
• Message authentication or digital signature
mechanism can be viewed as having two levels
– At lower level: there must be some sort of functions producing an
authenticator – a value to be used to authenticate a message
– This lower level functions is used as primitive in a higher level
authentication protocol
• Three classes of functions that may be used to
produce an authenticator
– Message encryption
» Ciphertext itself serves as authenticator
– Message authentication code (MAC)
» A public function of the message and a secret key that
produces a fixed-length value that serves as the
authenticator
– Hash function
» A public function that maps a message of any length into a
fixed-length hash value, which serves as the authenticator
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
5
Authentication Functions
Message Encryption
• Conventional encryption can serve as authenticator
– Conventional encryption provides authentication as well as
confidentiality
– Requires recognizable plaintext or other structure to distinguish
between well-formed legitimate plaintext and meaningless
random bits
» e.g., ASCII text, an appended checksum, or use of layered
protocols
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
6
Authentication Functions
Basic Uses of Message Encryption
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
7
Authentication Functions
Ways of Providing Structure
• Append an error-detecting code (frame check
sequence (FCS)) to each message
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
8
Authentication Functions
Ways of Providing Structure - 2
• Suppose all the datagrams except the IP header is
encrypted.
• If an opponent substituted some arbitrary bit pattern for
the encrypted TCP segment, the resulting plaintext
would not include a meaningful header
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
9
Authentication Functions
Confidentiality and Authentication
Implications of Message Encryption
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
10
Authentication Functions
Message Authentication Code
• Uses a shared secret key to generate a fixed-size
block of data (known as a cryptographic checksum
or MAC) that is appended to the message
• MAC = CK(M)
• Assurances:
– Message has not been altered
– Message is from alleged sender
– Message sequence is unaltered (requires internal sequencing)
• Similar to encryption but MAC algorithm needs not
be reversible
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
11
Authentication Functions
Basic Uses of MAC
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
12
Authentication Functions
Basic Uses of MAC
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
13
Authentication Functions
Why Use MACs?
– i.e., why not just use encryption?
•
•
•
•
•
•
Cleartext stays clear
MAC might be cheaper
Broadcast
Authentication of executable codes
Architectural flexibility
Separation of authentication check from message
use
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
14
Authentication Functions
Hash Function
• Converts a variable size message M into fixed size
hash code H(M) (Sometimes called a message
digest)
• Can be used with encryption for authentication
–
–
–
–
–
–
E(M || H)
M || E(H)
M || signed H
E( M || signed H ) gives confidentiality
M || H( M || K )
E( M || H( M || K ) )
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
15
Authentication Functions
Basic Uses of Hash Function
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
16
Authentication Functions
Basic Uses of Hash Function
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
17
Authentication Functions
Basic Uses of Hash Function
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
18
MACs
Message Authentication Codes
• MAC= CK(M)
• Key length requirements
– Sufficient key length to thwart brute force attack
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
MACs
19
Brute-force Attacks on MACs
• Let k = key length, n = MAC length
• Suppose confidentiality is not employed; i.e., the
opponent has access to plaintext messages and their
associated MACs
• If k > n
– Brute force gives 2(k-n) candidate keys
» Given known M1 and MAC1, with MAC1=CK1(M1), the
cryptanalyst can perform MACi = CKi(M1) for all possible key
values Ki.
» Al least one key is guaranteed to produce a match
» On average, a total of 2k/2n = 2(k-n) keys will produce a match
– Second round (new M and MAC) reduces this to 2(k-2n) candidate
keys
– On average, this requires k/n rounds
• If k  n, one round should suffice
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
MACs
20
Attacks on MACs
• Other attacks are possible, depending on the MAC
algorithm
• E.g., consider the following MAC algorithm
– Let M = (X1 || X2 || … || Xm) be a message that is treated as a
concatenation of 64-bit blocks Xi
– Define (M) = X1  X2  ...  Xm; Ck(M) = DESK[(M)]
• The opponent can attack the system as follows
– Replace Xi by Yi for i = 1 to m-1
– Calculate Ym to produce the right checksum, and replace Xm by Ym
» Ym = Y1  Y2  ...  Ym-1  (M)
– The new message, Y1 thru Ym, with the original MAC will be
accepted as authentic by the receiver
– With this tactic, any message of length 64  (m-1) bits can be
fraudulently inserted
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
MACs
21
Requirements for MAC Functions
•
Assume that an opponent knows the MAC function
C but does not know K. Then the MAC function
should have the following properties
1. Given M and Ck(M), it must be computationally
infeasible to construct M’ s.t. Ck(M’) = Ck(M)
2. CK(M) should be uniformly distributed in the sense
that for any M and M’, Pr[Ck(M) = Ck(M’)] should be
2-n, where n is the length of the MAC
3. Let M’ be equal to some known transformation on
M. That is, M’ = f(M). In that case, Pr[Ck(M) = Ck(M’)]
= 2-n,
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
22
MACs
MAC Based on DES
• Last block of DES CBC, with IV = 0
• Referred to as Data Authentication Algorithm (FIPS PUB
113 and ANSI standard (X9.17))
• Data Authentication Code (DAC) consists of 16 to 64
leftmost bits of ON
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
23
Hash Functions
Hash Functions
• h = H(M)
• M is a variable-length message, h is a fixed-length
hash value, H is a hash function
• The hash value is appended at the source
• The receiver authenticates the message by
recomputing the hash value
• Because the hash function itself is not considered
to be secret, some means is required to protect the
hash value
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
24
Hash Functions
Hash Function Requirements
1.
2.
3.
4.
H can be applied to any size data block
H produces fixed-length output
H(x) is relatively easy to compute for any given x
H is one-way, i.e., given h, it is computationally
infeasible to find any x s.t. h = H(x)
5. H is weakly collision resistant: given x, it is
computationally infeasible to find any y  x s.t.
H(x) = H(y)
6. H is strongly collision resistant: it is
computationally infeasible to find any x and y
s.t. H(x) = H(y)
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
25
Hash Functions
Hash Function Requirements
• One-way property is essential for authentication
• Weak collision resistance is necessary to prevent
forgery
• Strong collision resistance is important for
resistance to birthday attack
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
26
Hash Functions
Simple Hash Functions
• Operation of hash functions
– The input is viewed as a sequence of n-bit blocks
– The input is processed one block at a time in an iterative fashion to
produce an n-bit hash function
• Simplest hash function: Bitwise XOR of every block
– Ci = bi1  bi2  …  bim
» Ci = i-th bit of the hash code, 1  i  n
» m = number of n-bit blocks in the input
» bij = i-th bit in j-th block
– Known as longitudinal redundancy check
– Not useful as a one-way function
– Less effective in some cases
» E.g., if only 7-bit out of 8-bit characters is used in text files, the
128-bit hash value is effectively 112-bit
• We will encounter strong hash functions in Chapter 9
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
27
Hash Functions
Simple Hash Functions
• Improvement over the simple
bitwise XOR
– Initially set the n-bit hash value to zero
– Process each successive n-bit block of data as
follows
» Rotate the current hash value to the left by
one bit
» XOR the block into the hash value
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
28
Birthday Attack
Birthday Paradox for Birthday Attack
• Given a hash function H with n possible outputs and a
specific value h, how many random inputs must we
test before our chance of finding some x s.t. h = H(x) is
greater than ½ ?
• Obviously it is n/2
– For any single value y, Pr[h = H(y)] = 1/n
– Equivalently, Pr[h  H(y)] = 1-1/n
– If we generate k random values, the probability that none of them
matches h is [1-1/n]k
– The binomial theorem states that
(1-a)k = 1 - ka - (k(k-1)/2!)a2 + (k(k-1)(k-2)/3!)a3 …
– For small a, this is approximately 1 - ka
– So the probability that one of the k random values matches is 1-(11/n)k  k/n
– For probability ½, k  n/2
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
29
Birthday Attack
Birthday Paradox
• Given k random inputs, what is the chance that any
two of them produce the same output?
– Let Pr[n, k] be the probability that among k independently selected
random values taken from n possible values, there is at least one
duplicate value
– Let Q(n, k) denote the probability of no duplicates
– Let N(k) be the number of different ways we can have k values with
no duplicates
– N(1) = n
– N(2) = n  n-1
– N(3) = n  n-1  n-2
– N(k) = n  n-1  n-2  n-k+1 = n!/(n-k)!
– Q(n, k) = n!/((n-k)!  nk)
– If we allow duplicates, the number of selections is nk
– Pr[n, k] = 1 - Q(n, k)
– Example: Pr[365, k] is approximately ½ when k is 23.
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
30
Birthday Attack
Birthday Paradox
23
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
31
Birthday Attack
Birthday Paradox - Generalization
– Rewriting, Pr[n, k] = 1 - (n  (n-1)  …  (n-k+1))/nk
= 1 - (n-1)/n  (n-2)/n  …  (n-k+1)/n
= 1 - (1 - 1/n)  (1 - 2/n)  …  (1 - (k-1)/n)
– Because (1-x)  e-x for all x  0, we can write
Pr[n, k]  1 - (e-1/n  e-2/n  …  e-(k-1)/n)
 1 - e-(1/n + 2/n + … (k-1)/n)
 1 - e-(k  (k-1))/2n
– Solving for Pr[n, k]  0.5,
1/2 = 1 - e-(k  (k-1))/2n, so
1/2 = e-(k  (k-1))/2n, so
2 = e(k  (k-1))/2n, so
ln(2) = (k  (k-1))/2n
– For large k, k  k-1, giving ln(2)  k2/2n
– ln(2)  1.18, so we have 1.18  k2/2n, so k  1.18 n
– In rough terms, k  n
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
32
Birthday Attack
Birthday Paradox - Generalization
• Let a hash function H have m-bit output (i.e., 2m
possible outputs). What is the value of k s.t. if H
is applied to k random inputs, a duplicate is
likely? (i.e., H(x)=H(y) for some inputs x and y)
• Approximately k = 2m/2
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
33
Birthday Attack
Birthday Paradox – Overlap bet. Two Sets
• Given a random variable that is an integer with
uniform distribution between 1 and n and two sets of
k instances (k  n) of the random variable, let R(n, k)
be the probability that two sets are not disjoint; i.e.,
the probability that there is at least one value found
in both.
• What value of k is required s.t. R(n,k) > 0.5 ?
– Approximately k  n
• Suppose we have a hash function H, with 2m possible
outputs (i.e., an m-bit output). Apply H to k random
inputs to produce the set X and again to k additional
random inputs to produce the set Y. What must be
the value of k so that there is the probability of at
least one match between the two sets [i.e., H(x) = H(y)
for some inputs x  X, y  Y] ?
– K = 2m/2
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
34
Birthday Attack
Birthday Attack
• If the adversary can generate 2m/2 variants of a
valid message and an equal number of fraudulent
messages
• The two sets are compared to find one message
from each set with a common hash value
• The valid message is offered for signature
• The fraudulent message with the same hash value
is inserted in its place
• If a 64-bit hash code is used, the level of effort is
only on the order of 232
• Conclusion: the length of the hash code must be
substantial
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
35
Birthday Attack
Generating 2m/2 Variants of Valid Messages
• Insert a number of
“space-backspace-space”
character pairs between
words throughout the
document.
Variations could then be
generated by substituting
“space-backspace-space”
in selected instances
• Alternatively, simply
reword the message but
retain the meaning
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
36
Hash Function
Block Chaining Technique Hash Function
• A number of proposals for hash functions based on
using a cipher block chaining technique, but without
the secret key
• Ravin’s proposal:
– Divide a message M into fixed-size blocks M1, M2, …, MN and use a
conventional encryption system such as DES to compute the
hash code G as follows
» H0 = initial value
» Hi = EMi[Hi-1]
» G = HN
– Similar to CBC technique, but no secret key
– As with any hash code, subject to the birthday attack
» If DES is used, and only a 64-bit hash code is produced, then
the system is vulnerable
– Another version of birthday attack is possible
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
37
Hash Function
Birthday Attack to Block Chaining Techniques
•
Assume the opponent intercepts a message with a
signature in the form of an encrypted hash code and
the unencrypted hash code is m bits long
Use the algorithm (Ravin’s) to calculate the unencrypted hash code G
Construct any desired message in the form Q1, Q2, …, QN-2
Compute Hi = EQi[Hi-1] for 1  i  (N-2)
Generate 2m/2 random blocks; for each block X, compute EX[HN-2].
Generate an additional 2m/2 random blocks; for each block Y, compute
DY[G].
5. Based on birthday paradox, with high probability there will be an X and
Y s.t. EX[HN-2] = DY[G]
6. Form the message Q1, Q2, …, QN-2, X, Y. This message has the hash
code G and therefore can be used with the intercepted encrypted
signature
1.
2.
3.
4.
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
38
Security of Hash Functions and MACs
Brute-Force Attack of Hash Functions
• Three desirable properties of hash functions
– One-way: For any given code h, it is computationally infeasible to
find x s.t. H(x) = h
– Weak collision resistance: For any given block x, it is
computationally infeasible to find y  x s.t. H(y) = H(x)
– Strong collision resistance: It is computationally infeasible to find
any pair (x, y) s.t. H(y) = H(x)
• Brute-force attack on n-bit hash code
– One-way and weak collision require 2n effort
– Strong collision requires 2n/2 effort
–  If strong collision resistance is required (and this is desirable for
a general-purpose secure hash code), 2n/2 determines the strength
of hash code against brute-force attack
– Currently, two most popular hash codes, SHA-1 and RIPEMD-160,
provide a 160-bit hash code length
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
39
Security of Hash Functions and MACs
Brute-Force Attack of MACs
• Desired security property of a MAC algorithm
– Computation resistance: Given one or more text-MAC pairs
(xi, CK(xi)), it is computationally infeasible to compute any text-MAC
pair (x, CK(x)) for any new input x  xi
• Brute-force attack on key space or MAC space
• Brute-force key space search for k-bit key
– See p.19
– Overall effort is roughly 2k
• Brute-force MAC space search for n-bit MAC value
– Overall effort is roughly 2n
• The level of effort for brute-force attack on a MAC
algorithm is min(2k, 2n)
• It is required min(k, n)  N, where N  128
Cryptography & Network Security
H. Yoon
Message Authentication and Hash Functions
40
Homework
•
•
•
•
Prob. 8.2
Prob. 8.4
Prob. 8.5
Prob. 8.6
Cryptography & Network Security
H. Yoon