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 x1 ¹ x2 such that F(x1) = F(x2). So we can "authenticate" a value x by using a one-way hash function to produce some fixed size output. This output can then be reliably known to come from this certain value x, because an impersonator cannot efficiently find some other input value that produces the same output.

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.

1. F can be applied to any argument of any size.
2. F produces a fixed size output.
3. Given F and x, it is easy to compute F(x).
4. 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.

1. F can be applied to any argument of any size.
2. F produces a fixed size output.
3. Given F and x, it is easy to compute F(x).
4. 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 F0 which only accepts a limited size input, follows.

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

1. int x[0..n-1] // conveniently sized chunks (y-bit)
2. int result // y-bit, note: y > z
3. begin
4. result = 0; // F0 accepts 2y bits and returns z bits
5. for i = 1 to n do
6. result = F0(concatenate(result, x[i]))
7. return result
8. end

We need to define the F0(x) that is used in the above function F(x). First we define a function f0(x) as follows. DES_ENCRYPT takes a 56-bit key and a 64-bit-plaintext as input, and produces a 64-bit-ciphertext output. (total of 120 input bits)

f0(key, plaintext) = DES_ENCRYPT(key, plaintext) xor plaintext

For some 119 bit value x,
F0(x) = first 112 bits of (f0("0", x), f0("1", x))

This definition of F0(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.

F0’(x) = f0("00", f0("10", x1), x2), f0("01", f0("11", x1), x2)

F0’’(x) = f0("00", first59bits(f0("100", x1)), first59bits(f0("101", x2))),

f0("01", first59bits(f0("110", x1)), first59bits(f0("111", x2)))

These new functions give better efficiency: 11 bits per DES application for F0’(x) and 18 bits per DES application for F0’’(x). In a similar way, one could develop more efficient ways to compute strong one-way hash functions from the DES algorithm.