I 248 H2001

8. forelesning 21.9.2001

Authentication: Hash functions

• Practical requirements:
• H(M) is a fixed-length m value calculated based on a message M of any length
• It is simple to execute H(M) for any message M, in software as well as in hardware
• Security considerations
• One-way: given a hash value h, it is computationally infeasible to find an M such that

h=H(M).
• If this is not satisfied, it is trivial to find collisions, as defined below. Moreover,
  if the hash function is used only with a secret value (Fig. 8.5e), then an attacker 
  with access to M and H(M) can easily find the secret value S.

A collision is defined as the event that two messages M, M'  have identical  hash values
h = H(M) = H(M'). Note that there will be infinitely many collisions for a given hash value h.
The point is that it should be computationally infeasible to find one.

• Weak collision resistance: For a given message M, it is computationally infeasible to find

another message M' such that  H(M) = H(M').
• If this is not satisfied, and if the hash value is encrypted (Fig. 8.5b and c), then an attacker
  with access to (and ability to change) M and E_K (H(M)) can easily
• regenerate the unencrypted hash value (since the message is available in plaintext)
• generate a fake message M' with the same hash value H(M)=H(M')
• "authenticate" M' with the observed encrypted hash value E_K(H(M))
• Note that "computationally infeasible" in this case is on the order of O(2^m) operations, for an m-bit hash value,
  since a brute force attack (involving trying different messages until a collision with the target message is found) takes an
  average of 2^m-1 tries.
• Strong collision resistance: It is computationally infeasible to find two messages M and M' such that  H(M) = H(M').
• If this is not satisfied, an attacker can launch the following attack.
• Suppose that the legitimate sender  is willing to sign (by adding the encrypted m-bit hash value) a message M prepared
  by the attacker.
• The attacker generates a set M_OK of some variations of M (with the same semantic content),
• by sneaky techniques (see, for example, Fig. 8.9?), and also a set M_FAKE of some  variations.
  of a fake message M' (that, presumably,  the legitimate sender would  not have signed.)
• If the sizes (some) of the sets  M_OK    and  M_FAKE  are large enough, then 
  there is a high probability that the attacker will find a collision between 
  the sets M_OK   and  M_FAKE , that is a M in M_OK   and a M' in  M_FAKE  such that  H(M) = H(M') .
• Then, of course, the attacker will let the sender sign M with E_K(H(M)) , and later replace 
  the message M with M', while keeping the "signature" E_K (H(M))  with the fake message.
• By the birthday paradox, if  the number some is approximately  0.83*2^m/2,  then the probability of collision is 0.5.
• Thus, modern hash functions have 160 bits
  

• Consider a random variable H, with a uniform probability distribution on {1,...,n}. Let X be a set of k random values drawn 
  with the same probability distribution. Then the probability that one of the values in X is equal to the value of H is approximately k/n.
• But what is the probability P(n,k) that some value occurs at least twice in X?
• P(n,k) = 1 - probability that all elements in X are distinct
  =  1  -  the number of ways to choose k distinct elements)/(the number of ways to choose k elements)
  =  1  -  n*(n-1)*(n-2)*...*(n-k +1) / n^k
            (see plot for n = 365)
  =  1 - ( 1 * (n-1)/n * (n-2)/n  * ...*( n-k+1)/n  )
  =  1 - ( (1-1/n) * (1-2/n ) * ... * (1-(k-1)/ n)  )
             using the fact that (1-x ) <= e^-x (with equality only for x=1) we get further
  >  1 - ( e^-1/n  * e^-2/n  * ...  * e^-(k-1)/n )
  =  1 -     e^{-(1+ 2+3+...+(k-1))/n}
  =  1 -     e^{-k(k-1) /2n}
  
  
• P(n,k) = 0.5  =>       e^{-k (k-1)/2n}  = 0.5  =>  k   ~  sqrt ( 2*ln(2)*n)  ~ 1.18 sqrt (n )
• n = 2^m ?  if k > 1.18 * 2 ^m/2  , then P(2^m,k) > 0.5
• But this is not the variant used in the birthday attack
• Let X and Y be two sets each of  k random values drawn from {1,...,n} with uniform probability.
  What is the probability P_XY(n,k) that some value occurs in both  X and Y?
  • Ignore the fact that there may be duplicates in X.  Then
    the probability that all values in Y are distinct from all of those in X is
    1 -  P_XY(n,k) =( (1-1/n)^k )^k   =  (1-1/n)^{k* k} , and
    P_XY(n,k)  >  1 -     e ^-k*k/n .
    
  • P_XY(n,k) = 0.5  =>       k² = n*ln(2) = 0.5  =>  k   ~  sqrt ( ln(2)*n)  ~ 0.83 sqrt (n)
  • n = 2^m ?  if k > 0.83 * 2^m/2  , then P_XY(2^m ,k) > 0.5
  • This is the variant used in the birthday attack
  
  

• Bitwise XOR...Fig 8.7 ...as we saw last time: not a good idea
• Bitwise XOR...Fig 8.8...rotate after processing each block
• Still unsafe; there are many ways to create collisions
• Block chaining: Message M₁,...,M_N
• H₀: Initial value
• For i=1...N do
      H_i = E_Mi (H_{i -1})
  
• The final H_N is the hash value
  

• Meet-in-the middle attack:
• Given public hash function and original message, calculate unencrypted hash value H
• Construct any message  Q₁,..., Q_N-2, and  H_i = E _Qi (H_i-1) for i = 1,...,N-2
  
• Generate a set X of 2^m/2  blocks as candidates for being  Q_N-1, for each x in X compute E_x (H_N-2)
  and another set Y of  2^m/2  blocks as candidates for being Q_{N ,} for each y in Y compute D _y (H)
• By the birthday paradox there is a high probability of finding a collision
• Enforcements:
• H_i = E_Mi (H_i-1 )+ H_i-1
• H_i = E_Hi-1 (M_i )+ M_i
• Both have weaknesses
  

• Depend on the actual functions:
• Fig. 8.10
• L fixed size input blocks Y
• length appended to last blocks. Padding if necessary

• use a compression function
• Can prove: if compression function is collision resistant, so is the overall hash function
• CV₀: Initial value, chaining variable
• For i=1...L do   
  CV_i = f (CV_i-1, Y _i-1)
  
• final CV_L is the hash value
• cryptanalytic attacks: Attack the compression functions