Method and Apparatus for Generating Secure Hash Functions

This patent application claims the benefit of U.S. Provisional patent application Ser. No. 60/035,222, entitled "New Constructions for Secure Hash Functions" filed on Jan. 8, 1997 for William Aiello and Ramaranthnam Venkatesan. The contents of this provisional application are incorporated herein by reference.

1. Field of the Invention

The present invention is directed to a device and method for providing secure, collision resistant hash functions. These secure, collision resistant hash functions are provided by mapping an input string into a longer string using a secure stretch function and then applying a compression function to the longer string.

2. Description of Related Art

A hash function is a function which takes a variable length input string (often called a pre-image) and converts it into a fixed-length output string (often called a hash value). A one way hash function is a hash function which works in one direction. Briefly, a one-way function is a function that is easy to compute but hard to invert on an overwhelming fraction of its range. In a good one-way hash function, given a hash value, it is computationally infeasible to determine the pre-image that hashed to that value. Another type of hash function is a collision resistant hash function. One important feature of a collision resistant hash function is that it is difficult to generate two pre-images which hash to the same hash value.

Hash functions are typically performed by a computer or special purpose processor. FIG. 1 is a block diagram of a computer or processor 100 which may be used to perform hash functions. The device 100 has a processor including one or more CPUs 102, a main memory 104, a disk memory 106, an input/output device 108, and a network interface 110. The devices 102-110 are connected to a bus 120 which transfers data, i.e., instructions and information between each of these devices 102-110. A hash function algorithm may be stored as data in either main memory 104 or a disk memory 106. A pre-image may be provided at the I/O device 108 or network interface 110. The processor 102 may retrieve the algorithm from memory 104 or 106 and receive the pre-image from the I/O (or network interface 110), both via the bus 120. The processor 102 may perform the hash and provide the hash value to the I/O device 108 (or network interface 110) or store the hash value in memory 104, 106.

Hash functions play a crucial role in practical cryptography and are in ubiquitous use. Applications for hash functions include authentication, digital signatures, and digital time stamping. As a result, the security of a hash function is important. Widely used constructions like the well known SHA (Secure Hash Algorithm), MD4 (Message Digest 4), and MD5 (Message Digest 5) hash functions have been recently attacked, raising questions about their security. MD5, for example, has been widely used, somewhat studied, and is quite efficient. But MD5 has come under attack by cryptanalysts. For example, den Boer and Bosselaers have produced collisions using MD5's compression function. (B. den Boer and A. Bosselaers, "Collisions for the Compression Function of MD5," Advances in Cryptology--EUROCRYPT '93 Proceedings, Spring-Verlag, 1994, pp. 293-304). On the other hand, constructions based on block ciphers like DES, while they have been less successfully attacked (and thus more secure), are usually slow, and need a large number of encryptions per block of data compressed. As a result, block ciphers are less efficient; that is they are computationally intensive and therefore use a great deal of processing power and time.

Therefore, it is an object of the present invention to provide a secure hash function which is simple in design and which yields a faster hash primitive.

These and other objects of the present invention are achieved by a secure hash function according to the present invention. The present invention uses a stretch function and a compression function to provide a secure hash value.

As used herein, a stretch function is a function which increases an input string (pre-image) of information elements, such as bits. In a preferred embodiment, a stretch function .function. maps l-bit inputs into 2m bits, where 2m>l. Preferably, the stretch function .function. is one-way. Preferably, the stretch function randomizes the input string, and is one-to-one along almost all points in the range of the function. The output of the stretch function is fed into a compression function c, which compresses the stretch function output from 2m bits to 2n bits, where m>n and which may have an initial value IV of S bits. The compression function is preferably a cryptographic compression function such as MD4, MD5, SHA-1, or suitably modified block cypher such as DES (see R. C. Merkle. Advances in Cryptoloty--Crypto '89, Lecture Notes in Computer Science, Vol. 435 Springer-Verlag, 1988). In an embodiment using a suitably modified block cypher, preferably, the output of the stretch function is used for an extended key of the cipher in place of the extended key produced by the standard key scheduling algorithm of the cipher. The inventors find that using a stretch function output as the compression function key improves the security of the compression function. Moreover, because the stretch function output randomizes the input string, the security constraints on the compression function are less stringent.

As a result, an efficient, simple, and secure hash function is provided.

These and other features of the present invention will be made apparent with reference to the following drawings:

FIG. 1 is a block diagram illustrating a conventional computer or special purpose processor;

FIG. 2 illustrates a method of performing a secure hash according to a preferred embodiment of the present invention;

FIG. 3 is a block diagram of a hashing device according to a preferred embodiment of the present invention;

FIG. 4 is a flowchart of a preferred method of performing a stretch function according to the present invention; and

FIG. 5 is a flowchart illustrating a preferred method of performing a compression function according to the present invention.

For clarity of presentation, the invention is described in the following sections:

I. Overview

An overview of the operation and structure of the present invention is provided with reference to FIGS. 2 and 3.

II. The Stretch Function and Stretch Processor

The stretch function and the stretch processor are described with reference to FIGS. 3 and 4.

III. The Compression Function and the Compression Module

The compression function and the compression module are described with reference to FIGS. 3 and 5.

VI. Conclusion

A conclusion is provided.

FIG. 2 illustrates the operation of the invention. In a preferred embodiment, a stretch function .function. (202) maps l bit inputs from input string t into 2m bit outputs, where 2m>l. In a preferred embodiment, a stretch function is a function which mildly increases an input string. Preferably, the stretch function .function. is (1) one-way: given any y=.function.(x), it is hard to find any x' such that .function.(x')=y, (2) randomizing, and (3) one-to-one on almost all points in the range of outputs.

The output of the stretch function 202 is fed into a compression function c (204), which compresses the stretch function output from 2m bits to 2n bits. The compression function c is preferably a cryptographic compression function. As seen in FIG. 2, the compression function 204 may comprise a plurality of primitives, such as the two primitives h, h, from s+m bits to n bits. s bits of the input of h may be randomly chosen and fixed. Call this value x. It is the initial value of h. One can write h(x,K)=g.sub.x (K) where g is randomly chosen from a family of 2.sup.s functions, indexed by a key x. n bits of the input h of are randomly chosen and fixed. Call this value x. One can write h(x,K)=g.sub.x (K) where g is randomly chosen from a family of 2.sup.s functions, indexed by a key x. H is the initial value of h. Thus, the compression function c (204) may be defined as:

Where X and X constitute the initial value IV for c. In a preferred embodiment in which h and/or h are a suitably modified block cipher, the output of the stretch function K, K may be used as the extended key of the cipher in place of the extended key produced by the standard key scheduling algorithm of the cipher. The inventors find that using a stretch function output as the compression function key improves the security of the compression function.

The overall inventive hash function H may be defined as:

(where t is the input string and x, x are the initial value IV of H).

FIG. 3 is a block diagram of a secure hashing device 300 according to the present invention. The device 300 may include a stretch processor 302 and a compression module 304. The stretch processor 302 and compression module 304 may be located in a computer or special purpose processor 100 as seen in FIG. 1. For example, the stretch processor 302 and compression module 304 may be a combination of algorithms stored in memory 104, 106 and processed by the processor 102. Alternatively, an application specific integrated circuit (ASIC) may be developed which contains a processor and the algorithms.

The stretch processor 302 may receive an input string t having l bits from an I/O 108 or network interface 110. The stretch processor 302 performs a stretch function 202 on the l bits of t and outputs a longer string having 2m bits, where 2m>l. Preferably, 2m is selected to be sufficiently larger than l so that the outputs of the stretch processor 302 are one-to-one on almost all elements in the range of outputs. The 2m bits are then sent to the compression module 304. The compression module performs a compression function 204 on the 2m bits and outputs 2n bits, where l>2n. The compression module 304 may also receive an initial value IV, which may be s bits long.

In a preferred embodiment, 2m-l may be on the order of a 10% increase over l or higher and preferably in a range between 30%-60% higher. As an example, suitable values for the variables discussed above are:

l=1024,

m=16*48=768; and

2n=128.

A person skilled in the art readily recognizes that preferred values of l, m, and n vary according to the specific application of the invention.

Given a fixed-length collision-resistant hash function H mapping l bit inputs to N bit outputs (N<l), one can build a collision-resistant hash function g defined on arbitrary-length inputs following the construction of Merkle (R. C. Merkle, "A fast software one-way hash function", Journal of Cryptology, Vol. 3, pp. 43-58 (1990)) and Damgard (I. Damgard, "A design principle for hash functions", Advances in Cryptology--Crypto '89, Lecture Notes in Computer Science, Vol. 435, pp. 416-427, Springer-Verlag (1988)). As seen in FIG. 3, assign a fixed bit string, IV, and let the value of g(x) on an input x=x.sub.1, x.sub.2, . . . x.sub.t (formatted with "Merkle-Damgard strengthening," i.e., with appropriate padding to encode the length of the text, as t blocks of length l-N) be defined as follows: g.sub.o =IV; g.sub.i =g(G.sub.i-l, x.sub.i), l.ltoreq.i.ltoreq.t; G(x)=G.sub.t.

The stretch processor 302 receives an input string and performs a stretch function 202 which randomizes the input string. In a preferred embodiment, the stretch function uses existing "secure" hash primitives like hash functions SHA, MD4, and MD5, and block cipher DES or other suitable hash functions or block ciphers. As discussed above, some of these primitives have been attacked and as a result, their security may be compromised. The present invention, however, relies only on the one-wayness and randomness properties of the chosen functions.

FIG. 4 is a flowchart 400 illustrating a preferred method of performing the stretch function 202. As seen in FIG. 4, the method is implemented as follows:

1. The stretch processor 302 fixes a string .alpha.=.alpha..sub.1, . . . , .alpha..sub.d (step 402).

2. The stretch processor 302 receives an input string (step 404) and stretches the input string t using an algorithm stored, for example, in a memory 104, 106 as follows:

a. The stretch processor 302 selects a secure hash function or cipher sh, such as one of the functions listed above (different functions may be used in different invocations of sh(.)) (step 406).

b. Break the input t into d blocks t.sub.1, . . . , t.sub.d (step 408).

c. Perform .function. as follows (step 410):

In a second preferred embodiment, a chaining variation may be used as the stretch function .function.. In the above function, using an algorithm stored, for example, in memory 104, 106, the stretch processor 302 selects some .alpha..sub.1 of length .lambda., where .lambda. is a fixed value. Then, function .function. performed by the processor may be modified by chaining the values for .alpha..sub.i, for i=2, . . . , d in the following manner:

Here MSB.lambda. stands for the .lambda. most significant bits of the argument.

Choosing 2m-l to be large enough (as discussed above) and if the stretching function is sufficiently random, .function. is one-to-one on almost all points in the range of outputs.

The stretching function described above thoroughly randomizes the input string. This prevents any targeted selection of input pairs for the compression function c, in an arguable way. In this respect, the stretch function is secure. The inability to target the outputs to a set of the attacker's choice pays off: in fact, it considerably simplifies the construction of the compression function.

The compression module 304 receives the 2m bits output by the stretch processor 302 and compresses these bits into 2n bits using compression function 204. The compression function c performed by the compression module 304 is preferably a cryptographic compression function, such as MD4, MD5, SHA or, as described below, DES. As seen in FIG. 2, the compression function 204 may comprise a plurality of primitives, such as primitives h, h, from s+m bits to n bits where s bits constitute an initial value, IV. Of course, three or more primitives may be used, i.e., h, h', h", etc. Using two primitives, the compression function c (204) may be defined as:

where x and x are the initial values of h and h respectively. As described below, the inventors find that using a stretch function output as the compression function key improves the security of the compression function. This is described in more detail below.

FIG. 5 is a flowchart 500 illustrating a preferred method of performing the compression function c 204. As seen in FIG. 5, the method is implemented as follows:

1. The compression module receives the 2m bits output by the stretch processor 302 (step 502).

2. The compression module 304 divides the 2m output bits into two sets of bits, K and K (step 504).

3. The compression module 302, using an algorithm stored, for example, in a memory 104, 106, processes x and K as follows (step 506a):

4. The compression module 302, using an algorithm stored, for example, in a memory 104, 106, processes x and K as follows (step 506b):

Here the "+" sign indicates any simple arithmetic or field operation, such as addition, subtraction, bit-wise exclusive-or, etc. Also, r(x,K) (and r(x,K)) is preferably a fixed, easy to compute function. The function r(x,K) may be r(x,K)=x. In a preferred embodiment, r(x, K) is a hash function. Preferred hash functions include r(x,K)=ax+b mod 2.sup.n and r(x,K)=aK+b mod 2.sup.n, where the pair (a,b) is randomly chosen with a odd.

K and K may be standard DES keys by choosing m=56. That is, the 56 bits are supplied to the standard DES key scheduling algorithm. In a preferred embodiment, however, the stretch function output may be used by the compression module 304 as the key scheduling algorithm in place of the standard DES keys. This may be done in the following manner:

1. Let EK DES denote DES without the key scheduling algorithm performed by the compression module 304 and which expects an expanded key of length m (e.g., 16*48) to be supplied directly from the stretch processor 302.

2. Denote the encryption of x with an expanded key K as y=EK.sub.DES (x).

3. h(x,K) may now be defined as:

Evidence supports that this is a secure use of the function. Replacing the standard key scheduling algorithm has two advantages. First, this speeds up the overall hash process because the DES key scheduling algorithm is slow. Second, previously, block ciphers have not been efficient enough for compression because of the number of input bits which may be accepted by DES. For example, using a conventional DES key scheduling algorithm, only 56 bits may be input into the DES cipher. Here, however, because the key scheduling algorithm has been replaced with the output of the stretch processor 302, a greater number of bits may be accepted by the DES block cipher than previously permitted. For example, if the stretch processor 302 receives a 100 bit input string and increases that string by 50%, a 150 bits are output. These 150 bits are used as K, K. As a result, DES, which was previously thought to be too inefficient for use as a hash function, may now be used as a suitable compression function when used in accordance with the present invention.

Alternatively, the compression function c may be performed wherein each primitive operates on all of the outputs. This may be defined as:

Another alternative may be where the simple function "r" operates on all of the outputs. This may be defined as follows:

where r is a simple, potentially randomly chosen and fixed hash function similar to those already mentioned. Again, the "+" sign may represent any simple arithmetic or field operation.

For example:

h(K,x)=EK-DES(K,x),

h(K,x)=EK-DES(K,x)

r(K,K,x,x)=x

r(K,K,x,x)=x.

Performing the compression function in this manner helps to thwart an adversary attempting to find a collision.

Also, as defined above, the compression function may be adapted to receive an input string of arbitrary length. Given a fixed-length collision-resistant hash function H mapping l bit inputs to N bit outputs (N<l), one can build a collision-resistant hash function g defined on arbitrary-length inputs following the construction of Merkle (R. C. Merkle, "A fast software one-way hash function", Journal of Cryptology, Vol. 3, pp. 43-58 (1990)) and Damgard (I. Damgard, "A design principle for hash functions", Advances in Cryptology--Crypto '89, Lecture Notes in Computer Science, Vol. 435, pp. 416-427, Springer-Verlag (1988)). As seen in FIG. 3, assign a fixed bit string IV, and let the value of g(x) on an input x=x.sub.1, x.sub.2, . . . x.sub.t (formatted with "Merkle-Damgard strengthening," i.e., with appropriate padding to encode the length of the text, as t blocks of length l-N) be defined as follows: g.sub.o =IV; g.sub.i =g(G.sub.i-l, x.sub.i), l.ltoreq.i.ltoreq.t; G(x)=G.sub.t.

In the hash function, the keys are known to an attacker. This allows the attacker to mount a well known meet-in-the-middle attack, which may be performed on algorithms using double encryption. Here, however, the meet-in-the-middle attack is thwarted for two reasons: First, to be able to mount a meet-in-the-middle attack on the keys, the attacker must be able to choose at least some portion of the keys. It is easy to check that the one-wayness and the randomizing properties of the stretch function prevent the attacker from doing so. Second, the present invention uses DES in a non-invertible way. DES is used as a one-way function mapping (K, x) y. That is, given any y it is considered infeasible to find a key K and input x to DES that generate this output so that y=DES.sub.K (x)+(x,K).

Disclosed is a device and method for providing secure, collision resistant hash functions. The inventors find that the inventive method and device provide a simpler primitive to design and analyze and which yields a faster secure hash function than the prior art. These secure, collision resistant hash functions are provided by mapping an input string into a longer string using a secure stretch function and then applying a compression function to the longer string.

The above described embodiments of the invention are intended to be illustrative only. Numerous alternative embodiments may be devised by those skilled in the art without departing from the spirit and scope of the following claims.