One Way Hash Functions and DES

Ralph C. Merkle – Xerox PARC

Crypto ’89 - A Conference on the Theory and Applications of Cryptology

The idea of this paper is to build a secure one-way hash function using DES. The motivation behind using one-way hash functions in cryptography is authentication. One of the properties of a one-way hash is that given the hash function it is computationally infeasible to find two values that hash to the same place. If our hash function is *F(x)*, it is computationally infeasible to find some pair *x _{1} ¹
x_{2}* such that

The author first gives definitions of the two general types of one-way hash functions: weak and strong.

Properties of a weak one-way hash function *F*.

*F*can be applied to any argument of any size.*F*produces a fixed size output.- Given
*F*and*x*, it is easy to compute*F(x)*. - Given
*F*and a "suitably chosen" (e.g. random)*x*, it is computationally infeasible to find an*x’ ¹ x*such that*F(x) = F(x’)*.

Properties of a strong one-way hash function *F*.

*F*can be applied to any argument of any size.*F*produces a fixed size output.- Given
*F*and*x*, it is easy to compute*F(x)*. - Given
*F*, it is computationally infeasible to find any pair*x, x’*such that*x ¹ x’*and*F(x) = F(x’)*.

Weak one-way hash functions suffer from a number of problems, including a weakening of their security on repeated use. For example, computing 1000 different random values of *x* could make the chances of finding an *x’* such that *one* of the thousand values of *x* satisfies *F(x) = F(x’)* 1000 times higher. Strong one-way hash functions can be used repeatedly without security compromise.

The main advantage of using strong one-way hash functions in authentication is that they can quickly and securely reduce the size of the cleartext. Say I have a 1-megabyte cleartext message that I want to digitally sign (using my RSA private key). Instead of directly encrypting this message using the private key, I can first run it through a strong one-way hash function to reduce it to some fixed size (say 56 bits). It is computationally infeasible to find any other cleartext message that will hash to this same value, even though those messages obviously exist. Therefore, instead of signing the whole message I can just sign this hash output. Anyone can now verify that the cleartext is authentic (that it came from my RSA private key) by checking the signature (using my RSA public key), and then computing the hash value of the cleartext message. Any slight change in the cleartext message will produce a huge change in the output from the hash function. This gives us an easy way of knowing if a document has been altered.

The algorithm for a strong one-way hash function *F* , in terms of a simpler *F _{0}* which only accepts a limited size input, follows.

function F(x) returns fixed size (z-bit) output string

- int x[0..n-1] // conveniently sized chunks (y-bit)
- int result // y-bit, note: y > z
- begin
result = 0; // F _{0}accepts 2y bits and returns z bitsfor i = 1 to n do result = F _{0}(concatenate(result, x[i]))return result - end

We need to define the *F _{0}(x)* that is used in the above function

f_{0}(key, plaintext) = DES_ENCRYPT(key, plaintext) xor plaintext

F

This definition of *F _{0}(x)* accepts 119-112 = 7 bits per iteration, requiring one application of DES_ENCRYPT for every 3.5 bits to be hashed. This is very inefficient, so the author gives some more efficient approaches.

F_{0}’(x) = f_{0}("00", f_{0}("10", x_{1}), x_{2}), f_{0}("01", f_{0}("11", x_{1}), x_{2})

F_{0}’’(x) = f_{0}("00", first59bits(f_{0}("100", x_{1})), first59bits(f_{0}("101", x_{2}))),

f_{0}("01", first59bits(f_{0}("110", x_{1})), first59bits(f_{0}("111", x_{2})))

These new functions give better efficiency: 11 bits per DES application for *F _{0}’(x)* and 18 bits per DES application for