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₁ ¹ x₂ such that F(x₁) = F(x₂). 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 F₀ which only accepts a limited size input, follows.

We need to define the F₀(x) that is used in the above function F(x). First we define a function f₀(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)

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

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