Introduction

Cryptographic hash functions play important role in the current cryptography. In the last few years, many attacks on popular hash functions believed to be secure (e.g. SHA1, MD5) have been proposed. Within these attacks arises a question, whether we are able to construct a secure hash function. A hash function is a function H : {0, 1} * → {0, 1} v , which maps messages (strings of 0 and 1) of arbitrary length to strings of fixed length -called images. Practically useful hash functions must guarantee several security properties: they should be collision resistant, what means that it is hard to find two different messages which map to the same image. Other important properties of hash functions are preimage resistance (for given image, it is hard to find its preimage, i.e. a message which maps to that image) and second-preimage resistance (for given message, it is hard to find another message, which maps to the same image). For formal definitions of the properties mentioned above or other notions of hash function security we refer to the works [4], [5].

Natural way how to construct secure hash function is to combine several known (regarded to be secure) hash functions in such a way, that if one of the combined functions appears to be insecure, the This paper was supported by VEGA grant number 1/0266/09 and by Comenius University grant number UK/365/2009. combination remains secure. For collision resistance we can achieve this by concatenation. Let H 1 , H 2 : {0, 1} * → {0, 1} v be some hash functions. We can construct a hash function H, where

H(M ) = H 1 (M )||H 2 (M ).

Note, that if (M, M ) is a pair of colliding messages for H, then this pair collides also for H 1 and H 2 . Therefore if at least one of the H 1 and H 2 is collision resistant, then H is collision resistant too. However this approach has one important disadvantage -the output length of H is twice as large as the output of underlying hash functions H 1 and H 2 , what can lead to problems with practical implementation, mainly on devices with small amount of memory as smart-cards.

Thus the question is, whether one can construct a secure combiner with output shorter than the concatenation. Boneh and Boyen in [1] proved the first negative result in this direction, in particular that there does not exist secure combiner for collision resistant hash functions with output shorter than concatenation, with an assumption, that the combiner queries each hash function exactly once. This result was generalized by Pietrzak [3], where the author proved that the secure combiners for collision resistance with significantly shorter output than concatenation do not exist. The later work consider a (k, l)-robust combiners for collision resistant, which are secure if at least k of the l components are secure.

In this paper we follow the work of Pietrzak [3] and prove the similar results for other important properties of hash functions -second preimage resistance and preimage resistance. We define a (k, l) combiner for preimage resistance and second preimage resistance and for these definitions we prove the impossibility results similar to one from [3].

Organization In the section 2 we start by some useful notation and continue with the formal definitions of (k, l) combiners for collision resistance, preimage resistance and second-preimage resistance. In the section 3 we prove the negative results, namely in the Theorem 1 we prove that secure combiner for preimage resistance with output significantly shorter than concatenation does not exists and in the Theorem 2 we prove the similar result for second-preimage resistance.

Preliminaries

In this section we formally define a combiner of l hash functions for three notions of hash function security -collision resistance, preimage resistance and second preimage resistance. The definition of the combiner for collision resistance is from [1], the other definitions (i.e. for preimage and second-preimage resistance) are slight modification of the former one.

We start with some basic notation. We write M $ ←S for the experiment of choosing random element from the distribution S. If S is a finite set, then M is chosen uniformly from S. Concatenation of finite strings M 1 and M 2 we denote by

M 1 ||M 2 or simply M 1 M 2 .

An oracle turing machine T with oracle access to turing machines T 1 , . . . , T l is a turing machine, which accepts inputs via input tape, performs some computation and replies via output tape. During the computation it can write on some additional "oracle" input tapes t 1 , . . . , t l and recieves responses via oracle output tapes t 1 , . . . , t l -connections to the turing machines T 1 , . . . , T l . Whenever T writes some input on tape t i , the turing machine T i is run on that input and T recieves the output on tape t i . We call such a operation a query to oracle T i . All queries are performed in unit time (i.e. computation of T i is not counted into the running time of T ). By T T1,...,T l we denote that the oracle turing machine T has oracle access to the turing machines T 1 , . . . , T l .

Let λ be some parameter. In this section, and later, by H i we denote a function mapping from {0, 1} * to {0, 1} v , where i = 1 . . . l and v = p(λ) for some polynomial p. In general, a combiner of l hash functions H i , i = 1, . . . , l for some notion of hash function security is a pair (C, P ), where -C : {0, 1} m → {0, 1} n does the "combination" (m = p m (λ) and n = p n (λ) for some polynomials p m , p n ), i.e. it is an oracle turing machine with oracle access to H 1 , . . . , H l . It behaves as a standard hash function (i.e. it takes some message on input and outputs a hash of the message -string of fixed length), but during the computation it can query any of its oracles.

-P provides a proof of the security for C. It is an algorithm, which transforms the "ability" of breaking the C (with respect to the particular security property) to the ability of breaking the candidates.

We note that both C and P should be efficientthey run in a time that is polynomial in the security parameter λ (and thus it is polynomial also in m, n or v). The oracle turing machine C is the same for combiners of all security notions. On the other hand, P needs to be modified when going from one security notion to another.

The security of combiner (with respect to some security notion) is determined by the number how many of the candidate hash functions need to be secure in order to guarantee that the resulting combiner is secure. By (k, l)-combiner (C, P ) we denote the combiner (C, P ), which is secure, if at least k of the l candidate hash functions are secure.

We expect from all candidate hash functions H i to have the same output length v. We assume this just for simplicity, our results can be easily extended for variable output length of these candidate hash functions.

In this paper we deal only with black box combiners, what means that the combination algorithm (C) has only black box (i.e. oracle) access to the candidate hash functions. It does not know the structure of underlying primitives H 1 , . . . , H l .

We start by formal definition of the combiner for collision resistance from [3].

Combiner for collision resistance

A collision resistant (k, l)-combiner for l hash functions H 1 , . . . , H l is a pair (C, P ) of oracle turing machines C and P , where -C : {0, 1} m → {0, 1} n has oracle access to hash functions H 1 , . . . , H i and performs the "combination" of hash functions. On input it takes a message of fixed length m and outputs an image of fixed length n. The output of C on an input M and with oracle access to H 1 , . . . , H l is denoted as C H1,...,H l (M ). -P is an oracle machine, which provides a "proof" of security for C. It takes as input a pair of messages (M, M ) and outputs two vectors W = (w 1 , . . . , w l ) and W = (w 1 , . . . , w l ).

The role of the algorithm P is to transform the collision in C to collisions in at least l − k + 1 of the underlying hash functions H 1 , . . . , H l . If such a P exists, which transforms collisions in C to collisions in H i for all compatible H 1 , . . . , H l , then we consider C as a collision resistant (k, l) combiner. Now, we formally define what was discussed above.

We say that P k succeeds on H 1 , . . . , H l , M and

M if: ∃J ⊆ {1, . . . , l}, |J| ≥ l − k + 1 : (∀j ∈ J) : (w j , w j ) is a collision for H j (i.e. H j (w j ) = H j (w j )) Let Adv Coll[k] P [(H 1 , . . . , H l ), M, M ]

denote the probability that P k-succeeds.

We say that (C, P ) is ε-secure (k, l)-Coll-combiner, if for all H 1 , . . . , H l and all collisions (M, M ) in C we have:

Adv Coll[k] P [(H 1 , . . . , H l ), M, M ] ≥ 1 − ε We consider (C, P ) to be secure (k, l)-Coll-combiner, if ε is negligible in the security parameter λ.

For example, a secure (1, 2)-combiner for collision resistance can look like follows:

-C H1,H2 (M ) = H 1 (M )||H 2 (M ) -P H1,H2 (M, M ) = (M, M ), (M, M )

The turing machine C just passes its input to the candidates and returns the concatenation of their output. Note that collision in C implies collision in both H 1 and H 2 . In more detail, if (M, M ) is a collision for such a C, then (M, M ) is also a collision in both H 1 and H 2 . Thus P has easy work -it copies its input to the output. It is easy to see, that for all

H 1 , H 2 and all collisions (M, M ) in C is Adv Coll[1] P [(H 1 , H 2 ), M, M ] = 1. Therefore (C, P ) is 0-secure (1, 2)-Coll-combiner.

Combiner for preimage resistance

The combiner for preimage resistance is similar to one for collision resistance. Only difference is in the algorithm P , which provides "a proof of the security". Algorithm P is given on its input challenge images y 1 , . . . , y l of H 1 , . . . , H l , for which it has to find preimages. It plays a game, in which it chooses an image of C for which it gets a preimage.

A preimage resistant combiner for l hash functions H 1 , . . . , H l is a pair (C, P ) of oracle turing machines C and P , where We note, that the function f , which parametrizes the Pre-Comb game can be understood as a deterministic "device", which finds preimages in C (it need not to be efficient). An algorithm P from a secure preimage resistant combiner should win the Pre-Comb game for all possible functions f (or at least for nonnegligible part of such functions, however in this paper we consider combiners to be secure if they win for all possible f s).

-C : {0, 1} m → {0,

We say that P k succeeds on H 1 , . . . , H l , y 1 , . . . , y l and f if:

∃J ⊆ {1, . . . , l}, |J| ≥ l − k + 1 : (∀j ∈ J) : w j is preimage of y j on H j (i.e. H j (w j ) = y j ) Let Adv Pre[k] P [(H 1 , . . . , H l ), (y 1 , . . . , y l ), f ]

denote the probability that P k-succeeds.

Finally, (C, P ) is ε-secure (k, l)-Pre-combiner, if for all H 1 , . . . , H l , all images y 1 , . . . , y l and all possible f we have:

Adv Pre[k] P [(H 1 , . . . , H l ), (y 1 , . . . , y l ), f ] ≥ 1 − ε We say (C, P ) is secure (k, l)-Coll-combiner, if ε is neg- ligible in the security parameter λ.

For example consider the following (1, 2)-combiner for preimage resistance:

-C H1,H2 (M 1 ||M 2 ) = H 1 (M 1 ) || H 2 (M 2 ) -C

Combiner for second-preimage resistance

Here we define a combiner for second-preimage resistance. Again, only difference from combiners for preimage or collision resistance is in the algorithm P .

A second-preimage resistant combiner for l hash functions H 1 , . . . , H l is a pair (C, P ) of oracle turing machines C and P , where

-C : {0, 1} m → {0,M = f (M ) (M = M and C H 1 ,...,H l (M ) = C H 1 ,.

..,H l (M )). 4. P continues (still can query H 1 , . . . , H l ) and outputs a vector (w 1 , . . . , w l ).

We say that P k succeeds on H 1 , . . . , H l , w and f if:

∃J ⊆ {1, . . . , l}, |J| ≥ l − k + 1 :

(∀j ∈ J) : w j is second-preimage of w on H j (i.e. H j (w j ) = H j (w) and w j = w j )

Now, let

Adv

Sec[k] P [(H 1 , . . . , H l ), w, f ]

denote the probability that P k-succeeds. Finally, (C, P ) is ε-secure (k, l)-Sec-combiner, if for all H 1 , . . . , H l , all messages w and all possible f we have:

Adv Sec[k] P [(H 1 , . . . , H l ), w, f ] ≥ 1 − ε

And we say (C, P ) is secure (k, l)-Coll-combiner, if ε is negligible in the security parameter λ.

Consider the following example of secure (1, 2) combiner for second-preimage resistance:

-C H1,H2 (M ) = H 1 (M )||H 2 (M ) -P -on input w in the second step of the Sec-Comb game P returns a message M = w. In turn P receives a message M = M , where

C H 1 ,H 2 (M ) = C H 1 ,H 2 (M )

. Finally P returns a vector (M , M ).

It is easy to see,

C H1,H2 (M ) = H 1 (M )||H 2 (M ) = H 1 (M )||H 2 (M ) = C H1,H2 (M ), thus H 1 (M ) = H 1 (M ), H 2 (M ) = H 2 (M ).

Impossibility proofs

Boneh and Boyen [1] followed by Pietrzak [3] showed, that there does not exist a collision resistant (k, l) combiner with short output. In this section we prove the similar results for preimage resistance and secondpreimage resistance.

The impossibility result for preimage resistant combiners is given in the Theorem 1, and in the Theorem 2 is given the impossibility result for secondpreimage resistance.

We start by notation used in the rest of this paper. Let (C, P ) be some combiner and let:

-W i (M ) be the set of oracle queries to H i made while evaluating C H1,...,H l on the message M -V i (M ) = {H i (M ); M ∈ W i (M )} be the set of corresponding answers. -w i,j (M ) be the j-th query to H i made while evaluating C H 1 ,...,H l (M ) and v i,j (M ) be the corresponding answer.

To simplify the presentation we will assume that P can output only messages that it has queried during the game. Note that we can assume this without loss of generality.

Theorem 1. Let (C, P ) be a (k, l)-combiner for preimage resistance, where C can make at most q C oracle queries. Suppose, that

n < (v − lg(q C ))(l − k + 1) − l

Then there exist y 1 , . . . , y l , H 1 , . . . , H l and f , such that

Adv Pre[k] P [(H 1 , . . . , H l ), (y 1 , . . . , y l ), f ] is negl. in λ Proof. Let H 1 , . . . , H l : {0, 1} * → {0, 1} v

be all uniformly random hash functions. Let q P be the total number of queries that P makes in the Pre-Comb game and let y 1 , . . . , y l be the challenge images that P gets in the first step of the game. From the fact, that P runs in a polynomial time we have that q P = p(λ) for some polynomial p. Therefore the probability that P queries any H i with some message w, such that H i (w) = y i , is negligible in λ. To see this only a simple idea is needed. All of the H i s are random thus the probability that P gets output y i for some i = 1, . . . , l in one query is l/2 v . The probability that P queries y i for some i in q P queries is therefore

q P l 2 v = p(λ) l 2 p (λ) ,

what is negligible in λ.

Thus P 's only chance to win is in the message M it gets as a preimage for the image Y chosen in the second step of the Pre-Comb game. We show, that if n < (v − lg(q C ))(l − k + 1) − l, then there exist images y 1 , . . . , y l , and a function f such that for all images Y which P can output in the second step, evaluating of C(f (Y )) does not present a preimage for at least k of the y 1 , . . . , y l . This means, that for such H 1 , . . . , H l , y 1 , . . . , y l and f is Adv

Pre[k] P [(H 1 , . . . , H l ), (y 1 , . . . , y l ), f ] negligible in λ, what we want to prove.

Let H 1 , . . . , H l be as defined above (independent random hash functions) and let Y ∈ {0, 1} n be some image of C H 1 ,...,H l . Consider the following random experiment. First, images y 1 , . . . , y l ∈ {0, 1} v are chosen at random and then a message M ∈ {0, 1} m is randomly chosen. Now consider the following events:

E 1 ⇐⇒ C H 1 ,...,H l (M ) = Y E 2 ⇐⇒ ∃J ⊆ {1, . . . , l}, |J| > l − k : ∀j ∈ J : y j ∈ V j (M ) Note that if Pr[E 1 ] > Pr[E 2 ]. then Pr[E 1 ∧¬E 2 ] > 0,

what means, that there exist images y 1 , . . . , y l ∈ {0, 1} v such that for each Y ∈ {0, 1} n there exists a message M ∈ {0, 1} m for which C H 1 ,...,H l (M ) = Y and the evaluation of C H 1 ,...,H l (M ) does not present preimages for y 1 , . . . , y l . In other words, it means that there exist images y 1 , . . . , y l and a function f 1 for which the theorem holds.

We know that for particular Y and randomly chosen M is

Pr[C H 1 ,...,H l (M ) = Y ] ≥ 2 −n . Thus Pr[E 1 ] ≥ 2 −n .

To find Pr[E 2 ], let q i be the number of queries to H i made by C (note that l i=1 q i = q C ). The Pr[E 2 ] can be upper bounded by the probability that the best oracle algorithm A H1,...,H l , which is allowed to query H i at most q i times finds a preimage for at least l − k + 1 of y i (A can evaluate C H 1 ,...,H l and then A's success probability is equal to Pr[E 2 ]). Since H i are all independent random functions, the best A can do is to 1 for each Y we set f (Y ) to the corresponding message M query each H i with q i distinct inputs. Now we follow the same steps as Pietrzak [3] did in the proof of the similar theorem for collision resistant combiner.

q i 2 v < J⊆{1,...,l} |J|=l−k+1 q l−k+1 C 2 v(l−k+1) ≤ l − k + 1 l q l−k+1 C 2 v(l−k+1) < 2 l q l−k+1 C 2 v(l−k+1)

When we put everything together:

lg(Pr[E 1 ]) ≥ lg(2 −n ) = −n and lg(Pr[E 2 ]) < lg 2 l q l−k+1 C 2 v(l−k+1) = (−(v − lg(q C ))(l − k + 1) + l). Thus if n < (v − lg(q C ))(l − k + 1) − l we have Pr[E 1 ] > Pr[E 2 ]

, what we wanted to prove. The condition n < (v−lg(q C ))(l−k+1)−l gives the lower bound how short can be the output of a secure (k, l)-Pre-combiner. It looks rather unnatural, however if C is allowed to query each H i exactly once and we consider only (1, l)-combiners (what means, that a combiner is secure if at least one of the candidates is secure) then the condition can be rewritten to n < (v − 1)l.

We note, that this lower bound need not to be optimal -maybe there exists a higher lower bound. We leave such an analysis for future work. Similar analysis for collision resistant combiners can be found in the work [2]. Theorem 2. Let (C, P ) be a (k, l)-combiner for 2nd-preimage resistance, where C makes at most q C oracle queries. Suppose, that

n < (v − lg(q C ))(l − k + 1) − l + 1

Then there exist w, H 1 , . . . , H l and f , for which

Adv Sec[k] P [(H 1 , . . . , H l ), w, f ] is negligible in λ Proof.

The proof is very similar to one in the Theorem 1, therefore we provide just a sketch of the proof. Let H 1 , . . . , H l be all independent random hash functions. We claim, that the probability where P queries a second-preimage of w for at least one of the H i is negligible. This is due the fact, that P runs in a polynomial time and therefore it can make at most polynomial number of queries, what is not enough for winning against random functions (for more formal discussion see the similar part in the proof of the Theorem 1).

Therefore we only need to prove that if n < (v − lg(q C ))(l − k + 1) − l + 1, then there exist a message w and a function f , where for all messages M that P can output in the second step of the Sec-Comb game evaluation of C(f (M )) does not present a second preimage of w for at least k of the H 1 , . . . , H l .

Thus let H 1 , . . . , H l be as defined above and let M ∈ {0, 1} m be some message. Consider the random experiment, where w ∈ {0, 1} m and M ∈ {0, 1} m are chosen uniformly at random. We define the following events E 1 and E 2 :

E 1 ⇐⇒ M = M ∧ C H1,...,H l (M ) = C H1,...,H l (M ) E 2 ⇐⇒ ∃J ⊆ {1, . . . , l}, |J| > l − k : (∀j ∈ J)(∃i) : v j,i (M ) = H j (w) ∧ w j,i (M ) = w

In other words, E 1 is the event when M is the second-preimage of M in the sense of C H 1 ,...,H l and E 2 means that the evaluation of C H1,...,H l (M ) does presents at least l − k + 1 second-preimages for w. Again, if we prove that Pr

[E 1 ] > Pr[E 2 ], then Pr[E 1 ∧ ¬E 2 ] > 0,

what means that for each M the above w 1 , . . . , w l and M exist and therefore there exists a function f (we set f (M ) := M ) for which the theorem holds (together with w 1 , . . . , w l ). Now, since m > n

Pr[E 1 ] = 2 −n − 2 −m ≥ 2 −n−1

Now, let q i be the maximum number of queries to H i made by C. We can upper bound Pr[E 2 ] by the probability that the best oracle algorithm A which can query each H i at most q i times finds second-preimage of w for at least l−k+1 of the H i s. However H 1 , . . . , H l are all independent random functions, thus the best A can do is to query each H i on q i distinct inputs different from w. If we follow the steps as in the corresponding part of the proof of the Theorem 1 we get

Pr[E 2 ] < 2 l q l−k+1 C 2 v(l−k+1)

When we put everything together:

Conclusion

We proved that combiners for preimage resistance and second-preimage resistance with output (significantly) shorter than concatenation do not exist. Our results are similar to ones for collision resistance from [1] and [3]. In particular, we showed that one can not create a secure (k, l)-combiner (for some mentioned security notion) of l arbitrary hash functions, with output shorter than concatenation of l − k + 1 candidates.

These results are, however, too strict in a point, that we want from a combiner to work for all l-tuples of (compatible) hash functions and that the algorithm P providing the proof of combiner's security must succeed with non-negligible probability on all possible inputs. Such a condition is not very practically relevant -one can think of creating a combiner, which combines only hash functions from some subset of all hash functions (e.g. set of functions computable in polynomial time). Another way how to weaken the restrictions on combiners is to allow the algorithm P to fail on negligible part of inputs. We leave the analysis of such "weaker" combiners for a future work.