On existence of robust combiners for cryptographic hash functions? Michal Rjaško Department of Computer Science, Faculty of Mathematics, Physics and Informatics, Comenius University, Bratislava rjasko@dcs.fmph.uniba.sk Abstract. A (k, l)-robust combiner for collision resistant combination remains secure. For collision resistance hash functions is a construction, which takes l hash func- we can achieve this by concatenation. Let H1 , H2 : tions and combines them so that if at least k of the compo- {0, 1}∗ → {0, 1}v be some hash functions. We can con- nents are collision resistant, then so is the resulting com- struct a hash function H, where bination. A black-box (k, l)-robust combiner is robust com- biner, which takes its components as black-boxes. A trivial H(M ) = H1 (M )||H2 (M ). black-box combiner is concatenation of any (l−k +1) of the hash functions. Boneh and Boyen [1] followed by Pietrzak Note, that if (M, M 0 ) is a pair of colliding messages [3] proved, that for collision resistance we cannot do much for H, then this pair collides also for H1 and H2 . better that concatenation, i.e. there does not exist black box Therefore if at least one of the H1 and H2 is collision (k, l)-robust combiner for collision resistance, whose output resistant, then H is collision resistant too. However is significantly shorter that the output of the trivial com- this approach has one important disadvantage – the biner. In this paper we analyze whether robust combiners output length of H is twice as large as the output of for other hash function properties (e.g. preimage resistance underlying hash functions H1 and H2 , what can lead and second preimage resistance) exist. to problems with practical implementation, mainly on Key words: Cryptographic hash function, robust com- biner, preimage resistance, second preimage resistance 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 con- 1 Introduction catenation. Boneh and Boyen in [1] proved the first negative result in this direction, in particular that Cryptographic hash functions play important role in there does not exist secure combiner for collision resis- the current cryptography. In the last few years, many tant hash functions with output shorter than concate- attacks on popular hash functions believed to be se- nation, with an assumption, that the combiner queries cure (e.g. SHA1, MD5) have been proposed. Within each hash function exactly once. This result was gen- these attacks arises a question, whether we are able eralized by Pietrzak [3], where the author proved that to construct a secure hash function. A hash function the secure combiners for collision resistance with sig- is a function H : {0, 1}∗ → {0, 1}v , which maps mes- nificantly shorter output than concatenation do not sages (strings of 0 and 1) of arbitrary length to strings exist. The later work consider a (k, l)-robust combin- of fixed length – called images. Practically useful hash ers for collision resistant, which are secure if at least k functions must guarantee several security properties: of the l components are secure. they should be collision resistant, what means that it In this paper we follow the work of Pietrzak [3] and is hard to find two different messages which map to prove the similar results for other important proper- the same image. Other important properties of hash ties of hash functions – second preimage resistance and functions are preimage resistance (for given image, it is preimage resistance. We define a (k, l) combiner for hard to find its preimage, i.e. a message which maps to preimage resistance and second preimage resistance that image) and second-preimage resistance (for given and for these definitions we prove the impossibility message, it is hard to find another message, which results similar to one from [3]. maps to the same image). For formal definitions of the Organization In the section 2 we start by some properties mentioned above or other notions of hash useful notation and continue with the formal defini- function security we refer to the works [4], [5]. tions of (k, l) combiners for collision resistance, preim- Natural way how to construct secure hash func- age resistance and second-preimage resistance. In the tion is to combine several known (regarded to be se- section 3 we prove the negative results, namely in the cure) hash functions in such a way, that if one of Theorem 1 we prove that secure combiner for preim- the combined functions appears to be insecure, the age resistance with output significantly shorter than ? This paper was supported by VEGA grant number concatenation does not exists and in the Theorem 2 1/0266/09 and by Comenius University grant number we prove the similar result for second-preimage resis- UK/365/2009. tance. 72 Michal Rjaško 2 Preliminaries The security of combiner (with respect to some se- curity notion) is determined by the number how many In this section we formally define a combiner of l hash of the candidate hash functions need to be secure in functions for three notions of hash function security order to guarantee that the resulting combiner is se- – collision resistance, preimage resistance and second cure. By (k, l)-combiner (C, P ) we denote the com- preimage resistance. The definition of the combiner biner (C, P ), which is secure, if at least k of the l for collision resistance is from [1], the other definitions candidate hash functions are secure. (i.e. for preimage and second-preimage resistance) are We expect from all candidate hash functions Hi to slight modification of the former one. have the same output length v. We assume this just $ for simplicity, our results can be easily extended for We start with some basic notation. We write M ←S for the experiment of choosing random element from variable output length of these candidate hash func- the distribution S. If S is a finite set, then M is chosen tions. uniformly from S. Concatenation of finite strings M1 In this paper we deal only with black box combin- and M2 we denote by M1 ||M2 or simply M1 M2 . ers, what means that the combination algorithm (C) An oracle turing machine T with oracle access to has only black box (i.e. oracle) access to the candi- turing machines T1 , . . . , Tl is a turing machine, which date hash functions. It does not know the structure of accepts inputs via input tape, performs some compu- underlying primitives H1 , . . . , Hl . tation and replies via output tape. During the com- We start by formal definition of the combiner for putation it can write on some additional “oracle” in- collision resistance from [3]. put tapes t1 , . . . , tl and recieves responses via oracle output tapes t01 , . . . , t0l – connections to the turing ma- 2.1 Combiner for collision resistance chines T1 , . . . , Tl . Whenever T writes some input on tape ti , the turing machine Ti is run on that input and A collision resistant (k, l)-combiner for l hash func- T recieves the output on tape t0i . We call such a opera- tions H1 , . . . , Hl is a pair (C, P ) of oracle turing ma- tion a query to oracle Ti . All queries are performed in chines C and P , where unit time (i.e. computation of Ti is not counted into the running time of T ). By T T1 ,...,Tl we denote that – C : {0, 1}m → {0, 1}n has oracle access to hash the oracle turing machine T has oracle access to the functions H1 , . . . , Hi and performs the “combina- turing machines T1 , . . . , Tl . tion” of hash functions. On input it takes a mes- Let λ be some parameter. In this section, and later, sage of fixed length m and outputs an image of by Hi we denote a function mapping from {0, 1}∗ to fixed length n. The output of C on an input M {0, 1}v , where i = 1 . . . l and v = p(λ) for some polyno- and with oracle access to H1 , . . . , Hl is denoted as mial p. In general, a combiner of l hash functions Hi , C H1 ,...,Hl (M ). i = 1, . . . , l for some notion of hash function security – P is an oracle machine, which provides a “proof” is a pair (C, P ), where of security for C. It takes as input a pair of mes- sages (M, M 0 ) and outputs two vectors – C : {0, 1}m → {0, 1}n does the “combination” (m = pm (λ) and n = pn (λ) for some polynomi- W = (w1 , . . . , wl ) and W0 = (w10 , . . . , wl0 ). als pm , pn ), i.e. it is an oracle turing machine with oracle access to H1 , . . . , Hl . It behaves as a stan- The role of the algorithm P is to transform the dard hash function (i.e. it takes some message on collision in C to collisions in at least l − k + 1 of the input and outputs a hash of the message – string underlying hash functions H1 , . . . , Hl . If such a P ex- of fixed length), but during the computation it can ists, which transforms collisions in C to collisions in Hi query any of its oracles. for all compatible H1 , . . . , Hl , then we consider C as – P provides a proof of the security for C. It is an al- a collision resistant (k, l) combiner. Now, we formally gorithm, which transforms the “ability” of break- define what was discussed above. ing the C (with respect to the particular security We say that P k succeeds on H1 , . . . , Hl , M and property) to the ability of breaking the candidates. M 0 if: ∃J ⊆ {1, . . . , l}, |J| ≥ l − k + 1 : We note that both C and P should be efficient – they run in a time that is polynomial in the security (∀j ∈ J) : (wj , wj0 ) is a collision for Hj parameter λ (and thus it is polynomial also in m, n (i.e. Hj (wj ) = Hj (wj0 )) or v). The oracle turing machine C is the same for combiners of all security notions. On the other hand, Let Coll[k] AdvP [(H1 , . . . , Hl ), M, M 0 ] P needs to be modified when going from one security notion to another. denote the probability that P k-succeeds. Combiners for cryptographic hash functions 73 We say that (C, P ) is ε-secure (k, l)-Coll-combiner, 3. A message M = f (Y ), is given to P (note if for all H1 , . . . , Hl and all collisions (M, M 0 ) in C we that C H1 ,...,Hl (M ) = Y ), if f (Y ) = ⊥, then have: the game ends and P fails. Coll[k] 4. P continues (still can query H1 , . . . , Hl ) and AdvP [(H1 , . . . , Hl ), M, M 0 ] ≥ 1 − ε outputs a vector W = (w10 , . . . , wl0 ). We consider (C, P ) to be secure (k, l)-Coll-combiner, We note, that the function f , which parametrizes if ε is negligible in the security parameter λ. the Pre-Comb game can be understood as a deter- For example, a secure (1, 2)-combiner for collision ministic “device”, which finds preimages in C (it need resistance can look like follows: not to be efficient). An algorithm P from a secure – C H1 ,H2 (M ) = H1 (M )||H2 (M ) preimage resistant combiner should win the Pre-Comb – P H1 ,H2 0 (M, M ) = (M, M ), (M, M )0 game for all possible functions f (or at least for non- negligible part of such functions, however in this paper The turing machine C just passes its input to the can- we consider combiners to be secure if they win for all didates and returns the concatenation of their output. possible f s). Note that collision in C implies collision in both H1 We say that P k succeeds on H1 , . . . , Hl , y1 , . . . , yl and H2 . In more detail, if (M, M 0 ) is a collision for and f if: such a C, then (M, M 0 ) is also a collision in both H1 and H2 . Thus P has easy work – it copies its input to ∃J ⊆ {1, . . . , l}, |J| ≥ l − k + 1 : the output. It is easy to see, that for all H1 , H2 and 0 all collisions (M, M ) in C is (∀j ∈ J) : wj0 is preimage of yj on Hj Coll[1] AdvP [(H1 , H2 ), M, M 0 ] = 1. (i.e. Hj (wj0 ) = yj ) Therefore (C, P ) is 0-secure (1, 2)-Coll-combiner. Let 2.2 Combiner for preimage resistance Pre[k] AdvP [(H1 , . . . , Hl ), (y1 , . . . , yl ), f ] The combiner for preimage resistance is similar to one denote the probability that P k-succeeds. for collision resistance. Only difference is in the al- Finally, (C, P ) is ε-secure (k, l)-Pre-combiner, if for gorithm P , which provides “a proof of the security“. all H1 , . . . , Hl , all images y1 , . . . , yl and all possible f Algorithm P is given on its input challenge images we have: y1 , . . . , yl of H1 , . . . , Hl , for which it has to find preim- ages. It plays a game, in which it chooses an image of C Pre[k] for which it gets a preimage. AdvP [(H1 , . . . , Hl ), (y1 , . . . , yl ), f ] ≥ 1 − ε A preimage resistant combiner for l hash functions We say (C, P ) is secure (k, l)-Coll-combiner, if ε is neg- H1 , . . . , Hl is a pair (C, P ) of oracle turing machines C and P , where ligible in the security parameter λ. For example consider the following (1, 2)-combiner – C : {0, 1}m → {0, 1}n is the same as in the colli- for preimage resistance: sion resistant combiner. – P is an oracle turing machine, which provides – C H1 ,H2 (M1 ||M2 ) = H1 (M1 ) || H2 (M2 ) – C gets a “proof” of security for C. It plays the following a message on its input, divides it into two parts game. Let f : {0, 1}n → {0, 1}m ∪ {⊥} be a func- of roughly equal length and passes these two parts tion, such that for all Y ∈ {0, 1}n is f (Y ) = M , to H1 and H2 . for which C H1 ,...,Hl (M ) = Y . If such a M does not – P – given images y1 , y2 on input, P computes the exists, then f (Y ) = ⊥. image Y = y1 ||y2 and returns it in the second step of the Pre-Comb game. In turn P receives a mes- Pre-Combf game: sage M , where C H1 ,H2 (M ) = Y . Finally P divides m 1. Messages w1 , . . . , wl ∈ {0, 1} are chosen at the message M into two parts w1 and w2 (exactly random, then images y1 = H1 (w1 ), . . . , yl = as C divides its input) and returns (w1 , w2 ). Hl (wl ) are computed and given to P on its input. Since C H1 ,H2 (w1 ||w2 ) = H1 (w1 )||H2 (w2 ), we can see 2. P with oracle access to H1 , . . . , Hl outputs that H1 (w1 ) = y1 and H2 (w2 ) = y2 . Thus (C, P ) is some image Y ∈ {0, 1}n . 0-secure (1, 2)-Pre-combiner. 74 Michal Rjaško 2.3 Combiner for second-preimage resistance It is easy to see, Here we define a combiner for second-preimage re- C H1 ,H2 (M 0 ) = H1 (M 0 )||H2 (M 0 ) sistance. Again, only difference from combiners for = H1 (M )||H2 (M ) preimage or collision resistance is in the algorithm P . = C H1 ,H2 (M ), A second-preimage resistant combiner for l hash functions H1 , . . . , Hl is a pair (C, P ) of oracle turing thus H (M 0 ) = H (M ), H (M 0 ) = H (M ). 1 1 2 2 machines C and P , where – C : {0, 1}m → {0, 1}n is the same as in the case of 3 Impossibility proofs preimage resistant or collision resistant combiner. – P is an oracle turing machine, which provides Boneh and Boyen [1] followed by Pietrzak [3] showed, a “proof” of security for C. It plays the following that there does not exist a collision resistant (k, l) game. Let f : {0, 1}m → {0, 1}m ∪ {⊥} be a func- combiner with short output. In this section we prove tion, such that for all M ∈ {0, 1}m is f (M ) = M 0 , the similar results for preimage resistance and second- for M 0 6= M and C H1 ,...,Hl (M ) = C H1 ,...,Hl (M 0 ). preimage resistance. If such a M 0 does not exist, then f (M ) = ⊥. The impossibility result for preimage resis- tant combiners is given in the Theorem 1, and in the Sec-Combf game: Theorem 2 is given the impossibility result for second- 1. Message w ∈ {0, 1}m is chosen at random and preimage resistance. given to P on its input. We start by notation used in the rest of this paper. 2. P with oracle access to H1 , . . . , Hl outputs Let (C, P ) be some combiner and let: some message M ∈ {0, 1}m . 3. P is given a message M 0 = f (M ) (M 0 6= M – Wi (M ) be the set of oracle queries to Hi made and C H1 ,...,Hl (M ) = C H1 ,...,Hl 0 (M )). while evaluating C H1 ,...,Hl on the message M 4. P continues (still can query H1 , . . . , Hl ) and – Vi (M ) = {Hi (M ); M ∈ Wi (M )} be the set of 0 0 outputs a vector (w1 , . . . , wl ). corresponding answers. – wi,j (M ) be the j-th query to Hi made while eval- We say that P k succeeds on H1 , . . . , Hl , w and f uating C H1 ,...,Hl (M ) and vi,j (M ) be the corre- if: sponding answer. ∃J ⊆ {1, . . . , l}, |J| ≥ l − k + 1 : To simplify the presentation we will assume that (∀j ∈ J) : wj0 is second-preimage of w on Hj P can output only messages that it has queried during the game. Note that we can assume this without loss (i.e. Hj (wj0 ) = Hj (w) and wj0 6= wj ) of generality. Now, let Theorem 1. Let (C, P ) be a (k, l)-combiner for pre- image resistance, where C can make at most qC oracle Sec[k] AdvP [(H1 , . . . , Hl ), w, f ] queries. Suppose, that denote the probability that P k-succeeds. n < (v − lg(qC ))(l − k + 1) − l Finally, (C, P ) is ε-secure (k, l)-Sec-combiner, if for all H1 , . . . , Hl , all messages w and all possible f we Then there exist y1 , . . . , yl , H1 , . . . , Hl and f , such that have: Pre[k] AdvP [(H1 , . . . , Hl ), (y1 , . . . , yl ), f ] is negl. in λ Sec[k] AdvP [(H1 , . . . , Hl ), w, f ] ≥ 1 − ε Proof. Let H1 , . . . , Hl : {0, 1}∗ → {0, 1}v be all uni- And we say (C, P ) is secure (k, l)-Coll-combiner, if ε is formly random hash functions. Let qP be the total negligible in the security parameter λ. number of queries that P makes in the Pre-Comb game Consider the following example of secure (1, 2) and let y1 , . . . , yl be the challenge images that P gets combiner for second-preimage resistance: in the first step of the game. From the fact, that P runs in a polynomial time we have that qP = p(λ) for some – C H1 ,H2 (M ) = H1 (M )||H2 (M ) polynomial p. Therefore the probability that P queries – P – on input w in the second step of the Sec-Comb any Hi with some message w, such that Hi (w) = yi , game P returns a message M = w. In turn P is negligible in λ. To see this only a simple idea is receives a message M 0 6= M , where C H1 ,H2 (M 0 ) = needed. All of the Hi s are random thus the probabil- C H1 ,H2 (M ). Finally P returns a vector (M 0 , M 0 ). ity that P gets output yi for some i = 1, . . . , l in one Combiners for cryptographic hash functions 75 query is l/2v . The probability that P queries yi for query each Hi with qi distinct inputs. Now we follow some i in qP queries is therefore the same steps as Pietrzak [3] did in the proof of the similar theorem for collision resistant combiner. l l qP v = p(λ) p0 (λ) , 2 2 Pr[E2 ] ≤ Pr[AH1 ,...,Hl finds l − k + 1 preimages] X what is negligible in λ. ≤ Pr[∀i ∈ J : A finds preimage for yi ] Thus P ’s only chance to win is in the message M J⊆{1,...,l} |J|=l−k+1 it gets as a preimage for the image Y chosen in the X Y qi second step of the Pre-Comb game. We show, that if ≤ n < (v − lg(qC ))(l − k + 1) − l, then there exist images 2v J⊆{1,...,l} i∈J y1 , . . . , yl , and a function f such that for all images Y |J|=l−k+1 which P can output in the second step, evaluating of X l−k+1 qC C(f (Y )) does not present a preimage for at least k of < 2v(l−k+1) the y1 , . . . , yl . This means, that for such H1 , . . . , Hl , J⊆{1,...,l} |J|=l−k+1 y1 , . . . , yl and f is µ ¶ l−k+1 l−k+1 l − k + 1 qC 2l qC Pre[k] ≤ v(l−k+1) < v(l−k+1) AdvP [(H1 , . . . , Hl ), (y1 , . . . , yl ), f ] l 2 2 negligible in λ, what we want to prove. When we put everything together: Let H1 , . . . , Hl be as defined above (independent random hash functions) and let Y ∈ {0, 1}n be some lg(Pr[E1 ]) ≥ lg(2−n ) = −n image of C H1 ,...,Hl . Consider the following random ex- periment. First, images y1 , . . . , yl ∈ {0, 1}v are chosen and at random and then a message M ∈ {0, 1}m is ran- µ l l−k+1 ¶ 2 qC domly chosen. Now consider the following events: lg(Pr[E2 ]) < lg v(l−k+1) 2 E1 ⇐⇒ C H1 ,...,Hl (M ) = Y = (−(v − lg(qC ))(l − k + 1) + l). E2 ⇐⇒ ∃J ⊆ {1, . . . , l}, |J| > l − k : Thus if n < (v − lg(qC ))(l − k + 1) − l we have Pr[E1 ] > ∀j ∈ J : yj ∈ Vj (M ) Pr[E2 ], what we wanted to prove. Note that if Pr[E1 ] > Pr[E2 ]. then Pr[E1 ∧¬E2 ] > 0, ¤ what means, that there exist images y1 , . . . , yl ∈ {0, 1}v such that for each Y ∈ {0, 1}n there exists a message The condition n < (v−lg(qC ))(l−k+1)−l gives the M ∈ {0, 1}m for which C H1 ,...,Hl (M ) = Y and the lower bound how short can be the output of a secure evaluation of C H1 ,...,Hl (M ) does not present preim- (k, l)-Pre-combiner. It looks rather unnatural, how- ages for y1 , . . . , yl . In other words, it means that there ever if C is allowed to query each Hi exactly once exist images y1 , . . . , yl and a function f 1 for which the and we consider only (1, l)-combiners (what means, theorem holds. that a combiner is secure if at least one of the candi- We know that for particular Y and randomly cho- dates is secure) then the condition can be rewritten to sen M is n < (v − 1)l. We note, that this lower bound need not to be Pr[C H1 ,...,Hl (M ) = Y ] ≥ 2−n . optimal – maybe there exists a higher lower bound. We leave such an analysis for future work. Similar analysis Thus for collision resistant combiners can be found in the Pr[E1 ] ≥ 2−n . work [2]. To find Pr[E2 ], let qi be the number of queries to Hi Pl Theorem 2. Let (C, P ) be a (k, l)-combiner for made by C (note that i=1 qi = qC ). The Pr[E2 ] can 2nd-preimage resistance, where C makes at most be upper bounded by the probability that the best or- qC oracle queries. Suppose, that acle algorithm AH1 ,...,Hl , which is allowed to query Hi at most qi times finds a preimage for at least l − k + 1 n < (v − lg(qC ))(l − k + 1) − l + 1 of yi (A can evaluate C H1 ,...,Hl and then A’s success probability is equal to Pr[E2 ]). Since Hi are all inde- Then there exist w, H1 , . . . , Hl and f , for which pendent random functions, the best A can do is to Sec[k] 1 for each Y we set f (Y ) to the corresponding message M AdvP [(H1 , . . . , Hl ), w, f ] is negligible in λ 76 Michal Rjaško Proof. The proof is very similar to one in the Theo- rem 1, therefore we provide just a sketch of the proof. µl−k+1 ¶ Let H1 , . . . , Hl be all independent random hash func- 2l qC lg(Pr[E2 ]) < lg tions. We claim, that the probability where P queries 2v(l−k+1) a second-preimage of w for at least one of the Hi is = −(v − lg(qC ))(l − k + 1) + l. negligible. This is due the fact, that P runs in a poly- nomial time and therefore it can make at most polyno- Thus if n < (v − lg(qC ))(l − k + 1) − l + 1 we have mial number of queries, what is not enough for winning Pr[E1 ] > Pr[E2 ], what we wanted to prove. 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(qC ))(l − k + 1) − l + 1, then there exist a message w 4 Conclusion and a function f , where for all messages M that P can output in the second step of the Sec-Comb game eval- We proved that combiners for preimage resistance and uation of C(f (M )) does not present a second preimage second-preimage resistance with output (significantly) of w for at least k of the H1 , . . . , Hl . shorter than concatenation do not exist. Our results Thus let H1 , . . . , Hl be as defined above and let are similar to ones for collision resistance from [1] M ∈ {0, 1}m be some message. Consider the random and [3]. In particular, we showed that one can not cre- experiment, where w ∈ {0, 1}m and M 0 ∈ {0, 1}m are ate a secure (k, l)-combiner (for some mentioned secu- chosen uniformly at random. We define the following rity notion) of l arbitrary hash functions, with output events E1 and E2 : shorter than concatenation of l − k + 1 candidates. These results are, however, too strict in a point, E1 ⇐⇒ M 0 6= M ∧ C H1 ,...,Hl (M ) = C H1 ,...,Hl (M 0 ) that we want from a combiner to work for all l-tuples E2 ⇐⇒ ∃J ⊆ {1, . . . , l}, |J| > l − k : (∀j ∈ J)(∃i) : of (compatible) hash functions and that the al- vj,i (M 0 ) = Hj (w) ∧ wj,i (M 0 ) 6= w gorithm P providing the proof of combiner’s security must succeed with non-negligible probability on all In other words, E1 is the event when M 0 is the possible inputs. Such a condition is not very practi- second-preimage of M in the sense of C H1 ,...,Hl and cally relevant – one can think of creating a combiner, E2 means that the evaluation of C H1 ,...,Hl (M 0 ) does which combines only hash functions from some subset presents at least l − k + 1 second-preimages for w. of all hash functions (e.g. set of functions computable Again, if we prove that Pr[E1 ] > Pr[E2 ], then Pr[E1 ∧ in polynomial time). Another way how to weaken the ¬E2 ] > 0, what means that for each M the above restrictions on combiners is to allow the algorithm P w1 , . . . , wl and M 0 exist and therefore there exists to fail on negligible part of inputs. We leave the analy- a function f (we set f (M ) := M 0 ) for which the the- sis of such “weaker” combiners for a future work. orem holds (together with w1 , . . . , wl ). Now, since m > n References Pr[E1 ] = 2−n − 2−m ≥ 2−n−1 1. D. Boneh and X. Boyen: On the impossibility of ef- Now, let qi be the maximum number of queries ficiently combining collision resistant hash functions. to Hi made by C. We can upper bound Pr[E2 ] by the LNCS, 4117, 2006. probability that the best oracle algorithm A which can 2. R. Canetti, R. Rivest, M. Sudan, L. Trevisan, S. Vad- query each Hi at most qi times finds second-preimage han and H. Wee: Amplifying collision resistance: of w for at least l−k+1 of the Hi s. However H1 , . . . , Hl a complexity-theoretic treatment. LNCS, 4622, 2007. 3. K. Pietrzak: Non-trivial black-box combiners for are all independent random functions, thus the best A collision-resistant hash-functions don’t exist. LNCS, can do is to query each Hi on qi distinct inputs dif- 4515, 2007. ferent from w. If we follow the steps as in the corre- 4. P. Rogaway and T. Shrimpton: Cryptographic hash- sponding part of the proof of the Theorem 1 we get function basics: definitions, implications, and separa- l−k+1 tions for preimage resistance, second-preimage resis- 2l qC tance, and collision resistance. In Fast Software Encryp- Pr[E2 ] < v(l−k+1) 2 tion, LNCS, Springer, 3017, 2004, 371–388. 5. M. Rjaško: Properties of cryptographic hash functions. When we put everything together: Mikulášska Kryptobesı́dka, 2008. lg(Pr[E1 ]) ≥ lg(2−n−1 ) = −n − 1 and