Lucks proposes modified structure called the wide-pipe hash

Building Hash Functions from Block

Ciphers, Their Security and

Abstract

This work deals with methods to construct a hash function containing a compression function that is built from a block cipher. There are many schemes to turn a block cipher into a compression function, here the most known are presented including Merkle-Damg˚ard Construction. Such schemes can produce either single-length-block or double-length-block hash functions according to the underlying block cipher with certain properties. At the end security considerations are outlined to convey what signifies a secure hash function that is built from a block cipher.

The purpose of a cryptographic hash function (and other hash functions) is easy to understand. It takes a string of arbitrary length as input and maps it to a fixed-length output string. Therefore the output string should be suggested as a digest of the input string. That also implies an essential property, an alter-ation of at least one character of the input causes a completely different output, thus every output should be unique for every input. For instance somebody obtains a very long text from somebody else and wants to determine whether a third person has altered it unauthorized, if a hash function is used one just have to compare to short strings.

At first sight the necessary functions for the above-mentioned applications seem to be equal, but they are not. We need different hash functions with special properties to meet the demands of each application.

1Cryptographic Hash Algorithm Competition, http://www.nist.gov/hash-competition

1

2 Hash Functions

This section gives a brief outline about the functional principle, usage and ex-amples of hash functions. In cryptographic understanding the properties of an underlying hash function design are greatly important since they provide infor-mation whether the hash function is useful in a certain application. In this work our focus lies on cryptographic hash functions, hence we exemplary introduce one of the most common hash functions (e.g. in signatures, certificates etc.) by now.

h(x)

2

big enough.

• Ease of computation. Every hash-value (output string s) of hash func-tion h(x) is efficient to compute in software and hardware.

• Preimage resistance. It is computationally infeasible to find an input string x′(preimage) such that h(x′) = s for any given output string s for which corresponding input string x is unknown.

• Partial-preimage resistance. It is computationally infeasible to find any substring of input string x for any given output string s even for any given distinct substring of input string x.

Here, computationally infeasible means solving the underlying problem is not possible within polynomial time or constrained memory. This should outline the practical meaning of some properties.

But we definitely not intend to proclaim MD5 as a secure hash function. Quite the opposite latest practical attacks2reveal security lacks such it is possible to create rogue Certification Authority certificate which are accepted as valid and trusted by all common web browsers. This approach is possible due to new methods for computing MD5 collisions. A scientific paper containing details is not yet released.

3 Hash Function Constructions from Block Ci-

3.1 Merkle-Damg˚ard Construction

The construction was described by R. Merkle in his Ph.D. thesis [4] in 1979. It represents a guidance to build hash functions from compression functions. A block cipher can be considered as a compression function since it transforms two

I. Damg˚ard proved the most important property of the construction [5].

Fact 1. Any compression function f which is collision resistant can be ex-tended to a collision resistant hash function h(x).

append padding bits

append length block
x1x2...xtxt+1

g

h(x)

5

Single-length hash functions output approximately the same number of bits as processed by the underlying block cipher. Considering security concerns the following approaches should be applied if the block cipher already provides a satisfying amount of output bits.

Hi-1

The output Hi is then concatenated with the previous output Hi−1 with aid of the exclusive-or operator.

The final output Ht is defined by the iterated formula

bit-length n of input or output, respectively.

3.3.2 Matyas-Meyer-Oseas

Hi = Eg(Hi−1)(xi) ⊕ xi

7

Figure 4: Matyas-Meyer-Oseas Scheme

for 1 ≤ i ≤ t, H0 = IV .

xi

The final output Ht is defined by the iterated formula

Hi = Eg(Hi−1)(xi) ⊕ xi ⊕ Hi−1

Fact 2. If either h1 or h2 is a collision resistant hash function, then h(x) = h1(x) || h2(x) is a collision resistant hash function.

Note. If h1 and h2 are applied independently then one could hope finding a collision for h(x) requires twice the effort to find a collision for one of them, if both are collision resistant [1]. Consequently, this stresses the main motivation for double-length constructions.

˜g(U) = u101u4u5u6u7u9 . . . u63.

9

˜Hi = ˜CL i|| CR i; ˜Ci= E˜g( ˜Hi−1)(xi) ⊕ xi
for 1 ≤ i ≤ t, H0 = IV and ˜H0 =�The rate of a hash function using MDC-2 compression function is IV .

RMDC2 = 2 · n= 1
since it needs two block cipher operations for one output regardless of the double-length hash-value.

of MDC-2. It employs four separated iterations of Matyas-Meyer-Oseas scheme

xi

respectively two iterations of MDC-2. The two MDC-2 schemes in MDC-4 are

connected in a similar way like the two Matyas-Meyer-Oseas schemes in MDC-2.

The final output Gt ||˜Gt is defined by the iterated formula

Hi = CL i|| ˜CR i; Ci= Eg(Gi−1)(xi)⊕ xi

for 1 ≤ i ≤ t, G0 = IV and ˜G0 =�The rate of a hash function using MDC-4 compression function is IV .

E || E

Hi Gi

Gi = EHi−1||xi(Gi−1) ⊕ Gi−1 ⊕ c

12

The MD5 algorithm exactly follows the approach of Merkle-Damg˚ard Construc-tion (Fig. 2). The input x is divided into t 512-bit bocks. The appending of the padding and the length block is combined in one step. First a single 1-bit is appended and as few 0-bits as necessary resulting in a overall bit-length 64 less than a multiple of 512. These last 64 bits are represented by the right-justified 64 bits of the initial overall bit-length of input x.

The MD5 compression function does not exactly follow one of those note above but utilizes a varied version of Davies-Meyer scheme. Hereby, the exclusive-or operation involving the previous preliminary output Hi is replaced by an addi-tion modulo 232 (preliminary output is divided into 4 32-bit words).

y(j)

second, third and fourth word of Hi. The result is then added to Hi modulo 232. The lookup table z determines which word of input block xi is added in the next step. The lookup table y consists of constant 32-bit words derived from the sine function. One of those constants is added prior a leftshift is applied determined by the lookup table s. Finally, the second word of Hi is added and the words are right shifted by one. Further details are describe in [2].

4 Security Consideration

• Following the approach above it is easy to find any number of collisions once a single collision is found. This succeeds since any extension attached to each of the colliding inputs will result in the same hash-value.

14

is iteratively used in the same manner as in Merkle-Damg˚ard construction but with bit-length w greater than hash-value bit-length n. The second compression

C′′: {0, 1}w→ {0, 1}n

• Complementation property. Ek(x) = Ek(x), whereas x denotes bit-wise complement. This facilitates finding collisions trivially. A slightly modified Matyas-Meyer-Oseas compression function EHi−1⊕xi(xi) ⊕ xi, for instance, produces the same output for x and x.

• Weak keys. Ek(Ek(x)) = x, for any x. For example, a simplified Davies-Meyer compression function Exi(Hi−1) allows creating a two-step fixed point since inserting two blocks xi containing a weak key leads to the relation Hi = Hi−2.

4.4 Black-Box Analysis

The black-box analysis applies the ideal cipher model where an encryption func-tion E : {0, 1}n× {0, 1}k→ {0, 1}nis assumed to be randomly selected from a set Bn,k containing all such block ciphers. The encryption, respectively, the decryption is simulated by two oracles.

FindColHF(A, H) is an experiment to measure the collision resistance. A de-notes a collision-finding algorithm.

FindColHF(A, H)
E ←R Bn,n+|xi|;
(c, c′) ←R Ae,e−1;
if c ̸= c′∧ hH(c) = hH(c′) return 1; else 0;

The methods to construct hash functions from block ciphers presented in this work are well studied and represent a proper way to develop new hash algo-rithms. However, in the real world most of common hash functions are partially built from scratch (e.g. MD5, SHA-1) which means following a dedicated design. As illustrated in section 3.5 these hash functions indeed use the Merkle-Damg˚ard construction as a structural frame but virtually none of them contains a com-pression function based on a well-known block cipher. Whirlpool3for example uses the Merkle-Damg˚ard construction combined with the Miyaguchi-Preneel compression function scheme but uses its own dedicated block cipher.

Utilizing the Merkle-Damg˚ard construction is advantageous since it reduces the problem of finding a secure hash function to finding a secure compression func-tion where secure means any collision-finding attack is at most as efficient as the birthday attack. Section 4 outlined that some compression functions satisfy this meaning of being secure with certain assumptions but it is still an open question whether a secure block cipher leads to a secure hash function or not. There still could be unknown weaknesses in a block cipher that makes the hash function vulnerable to collision-finding attacks. Moreover, in the matter of per-formance block ciphers are handicapped related to dedicated block ciphers since dedicated algorithms are less complex (MD5, section 3.5).

18