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- f0; 1g¤ ! f0; 1gv be some hash functions. We can connents 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 combiner, which takes its components as black-boxes. A trivial H(M ) = H1(M )jjH2(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 signi¯cantly 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 bKineeyr,wporredi ms:agCerryepstiosgtaranpceh,icsehcoanshd pfruenicmtiaogne, rersoibsutasntcecom- 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 con1 Introduction catenation. Boneh and Boyen in [1] proved the ¯rst negative result in this direction, in particular that Cryptographic hash functions play important role in there does not exist secure combiner for collision resisthe current cryptography. In the last few years, many tant hash functions with output shorter than concateattacks 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 genthese 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 sigis a function H : f0; 1g¤ ! f0; 1gv, which maps mes- ni¯cantly 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 combinof ¯xed 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 ¯nd two di®erent messages which map to prove the similar results for other important properthe 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 de¯ne a (k; l) combiner for hard to ¯nd 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 de¯nitions we prove the impossibility message, it is hard to ¯nd another message, which results similar to one from [3]. maps to the same image). For formal de¯nitions 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 de¯nifunction security we refer to the works [4], [5]. tions of (k; l) combiners for collision resistance, preimNatural 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 preimthe combined functions appears to be insecure, the age resistance with output signi¯cantly 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 resisUK/365/2009. tance.
2 Preliminaries The security of combiner (with respect to some
security notion) is determined by the number how many
In this section we formally de¯ne 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
compreimage resistance. The de¯nition of the combiner biner (C; P ), which is secure, if at least k of the l
for collision resistance is from [
We start with some basic notation. We write M Ã$S for simplicity, our results can be easily extended for for the experiment of choosing random element from variable output length of these candidate hash functhe distribution S. If S is a ¯nite set, then M is chosen tions. uniformly from S. Concatenation of ¯nite strings M1 In this paper we deal only with black box combinand M2 we denote by M1jjM2 or simply M1M2. 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
candituring 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 de¯nition of the combiner for
putation it can write on some additional \oracle" in- collision resistance from [
Let ¸ be some parameter. In this section, and later, sage of ¯xed length m and outputs an image of by Hi we denote a function mapping from f0; 1g¤ to ¯xed length n. The output of C on an input M f0; 1gv, 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, CH1;:::;Hl (M ). i = 1; : : : ; l for some notion of hash function security is a pair (C; P ), where { P is an oracle machine, which provides a \proof" of security for C. It takes as input a pair of messages (M; M 0) and outputs two vectors { C : f0; 1gm ! f0; 1gn does the \combination" (m = pm(¸) and n = pn(¸) for some polynomials pm; pn), i.e. it is an oracle turing machine with oracle access to H1; : : : ; Hl. It behaves as a standard hash function (i.e. it takes some message on input and outputs a hash of the message { string of ¯xed 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.
they 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 modi¯ed when going from one security notion to another.
W = (w1; : : : ; wl) and W0 = (w10; : : : ; wl0):
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 H1; : : : ; Hl. If such a P exists, which transforms collisions in C to collisions in Hi for all compatible H1; : : : ; Hl, then we consider C as a collision resistant (k; l) combiner. Now, we formally de¯ne what was discussed above.
We say that P k succeeds on H1; : : : ; Hl, M and M 0 if:
Let
9J µ f1; : : : ; lg; jJ j ¸ l ¡ k + 1 : (8j 2 J ) : (wj ; wj0 ) is a collision for Hj
(i.e. Hj (wj ) = Hj (wj0 ))
AdvPColl[k][(H1; : : : ; Hl); M; M 0] denote the probability that P k-succeeds.
if for all H1; : : : ; Hl and all collisions (M; M 0) in C we have:
AdvPColl[k][(H1; : : : ; Hl); M; M 0] ¸ 1 ¡ " 3. A message M = f (Y ), is given to P (note that CH1;:::;Hl (M ) = Y ), if f (Y ) = ?, then the game ends and P fails. 4. P continues (still can query H1; : : : ; Hl) and outputs a vector W = (w10; : : : ; wl0).
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:
We note, that the function f , which parametrizes the Pre-Comb game can be understood as a deterministic \device", which ¯nds preimages in C (it need not to be e±cient). An algorithm P from a secure { CH1;H2 (M ) = H1(M )jjH2(M ) preimage resistant combiner should win the Pre-Comb { P H1;H2 (M; M 0) = (M; M ); (M; M 0) game for all possible functions f (or at least for nonnegligible 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 the output. It is easy to see, that for all H1, H2 and 9J µ f1; : : : ; lg; jJ j ¸ l ¡ k + 1 : all collisions (M; M 0) in C is (8j 2 J ) : wj0 is preimage of yj on Hj
(i.e. Hj (wj0 ) = yj ) Let denote the probability that P k-succeeds.
Finally, (C; P ) is "-secure (k; l)-Pre-combiner, if for all H1; : : : ; Hl, all images y1; : : : ; yl and all possible f we have:
AdvPPre[k][(H1; : : : ; Hl); (y1; : : : ; yl); f ] ¸ 1 ¡ "
AdvPColl[
2.2
The combiner for preimage resistance is similar to one for collision resistance. Only di®erence is in the algorithm P , which provides \a proof of the security\.
Algorithm P is given on its input challenge images y1; : : : ; yl of H1; : : : ; Hl, for which it has to ¯nd 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 H1; : : : ; Hl is a pair (C; P ) of oracle turing machines C and P , where We say (C; P ) is secure (k; l)-Coll-combiner, if " is negligible in the security parameter ¸.
For example consider the following (1; 2)-combiner { C : f0; 1gm ! f0; 1gn is the same as in the colli- for preimage resistance:
sion resistant combiner. { P is an oracle turing machine, which provides a \proof" of security for C. It plays the following game. Let f : f0; 1gn ! f0; 1gm [ f?g be a function, such that for all Y 2 f0; 1gn is f (Y ) = M , for which CH1;:::;Hl (M ) = Y . If such a M does not exists, then f (Y ) = ?. { CH1;H2 (M1jjM2) = H1(M1) jj H2(M2) { C gets a message on its input, divides it into two parts of roughly equal length and passes these two parts to H1 and H2. { P { given images y1; y2 on input, P computes the image Y = y1jjy2 and returns it in the second step of the Pre-Comb game. In turn P receives a message M , where CH1;H2 (M ) = Y . Finally P divides the message M into two parts w1 and w2 (exactly as C divides its input) and returns (w1; w2).
Pre-Combf game: 1. Messages w1; : : : ; wl 2 f0; 1gm are chosen at random, then images y1 = H1(w1); : : : ; yl = Hl(wl) are computed and given to P on its input. Since CH1;H2 (w1jjw2) = H1(w1)jjH2(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 2 f0; 1gn. 0-secure (1; 2)-Pre-combiner.
Here we de¯ne a combiner for second-preimage resistance. Again, only di®erence from combiners for preimage or collision resistance is in the algorithm P .
A second-preimage resistant combiner for l hash functions H1; : : : ; Hl is a pair (C; P ) of oracle turing machines C and P , where { C : f0; 1gm ! f0; 1gn is the same as in the case of 3
preimage resistant or collision resistant combiner. { P is an oracle turing machine, which provides a \proof" of security for C. It plays the following game. Let f : f0; 1gm ! f0; 1gm [ f?g be a function, such that for all M 2 f0; 1gm is f (M ) = M 0, for M 0 6= M and CH1;:::;Hl (M ) = CH1;:::;Hl (M 0).
If such a M 0 does not exist, then f (M ) = ?. if:
Sec-Combf game: 1. Message w 2 f0; 1gm is chosen at random and
given to P on its input. 2. P with oracle access to H1; : : : ; Hl outputs
some message M 2 f0; 1gm. 3. P is given a message M 0 = f (M ) (M 0 6= M
and CH1;:::;Hl (M ) = CH1;:::;Hl (M 0)).
outputs a vector (w10; : : : ; wl0).
9J µ f1; : : : ; lg; jJ j ¸ l ¡ k + 1 : (8j 2 J ) : wj0 is second-preimage of w on Hj (i.e. Hj (wj0 ) = Hj (w) and wj0 6= wj ) Now, let
AdvSPec[k][(H1; : : : ; Hl); w; f ] denote the probability that P k-succeeds.
Finally, (C; P ) is "-secure (k; l)-Sec-combiner, if for all H1; : : : ; Hl, all messages w and all possible f we have:
AdvSPec[k][(H1; : : : ; Hl); w; f ] ¸ 1 ¡ " 2.3
Proof. Let H1; : : : ; Hl : f0; 1g¤ ! f0; 1gv be all uniAnd 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 ¯rst step of the game. From the fact, that P runs in a polynomial time we have that qP = p(¸) for some { CH1;H2 (M ) = H1(M )jjH2(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 CH1;H2 (M 0) = needed. All of the His are random thus the probabilCH1;H2 (M ). Finally P returns a vector (M 0; M 0). ity that P gets output yi for some i = 1; : : : ; l in one CH1;H2 (M 0) = H1(M 0)jjH2(M 0) = H1(M )jjH2(M ) = CH1;H2 (M ); thus H1(M 0) = H1(M ), H2(M 0) = H2(M ).
Impossibility proofs
Boneh and Boyen [
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: { Wi(M ) be the set of oracle queries to Hi made
while evaluating CH1;:::;Hl on the message M { Vi(M ) = fHi(M ); M 2 Wi(M )g be the set of
corresponding answers. { wi;j (M ) be the j-th query to Hi made while evaluating CH1;:::;Hl (M ) and vi;j (M ) be the corresponding answer.
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 qC oracle queries. Suppose, that
n < (v ¡ lg(qC ))(l ¡ k + 1) ¡ l Then there exist y1; : : : ; yl, H1; : : : ; Hl and f , such that
AdvPPre[k][(H1; : : : ; Hl); (y1; : : : ; yl); f ] is negl. in ¸
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 [
l l qP 2v = p(¸) 2p0(¸) ; 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(qC ))(l ¡ k + 1) ¡ l, then there exist images y1; : : : ; yl, 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 y1; : : : ; yl. This means, that for such H1; : : : ; Hl, y1; : : : ; yl and f is negligible in ¸, what we want to prove.
Let H1; : : : ; Hl be as de¯ned above (independent random hash functions) and let Y 2 f0; 1gn be some image of CH1;:::;Hl . Consider the following random experiment. First, images y1; : : : ; yl 2 f0; 1gv are chosen at random and then a message M 2 f0; 1gm is randomly chosen. Now consider the following events:
E1 () CH1;:::;Hl (M ) = Y E2 () 9J µ f1; : : : ; lg; jJ j > l ¡ k : 8j 2 J : yj 2 Vj(M )
When we put everything together: µl ¡ k + 1¶ qCl¡k+1 2lqCl¡k+1 l 2v(l¡k+1) < 2v(l¡k+1) lg(Pr[E1]) ¸ lg(2¡n) = ¡n and lg(Pr[E2]) < lg µ 2lql¡k+1 ¶
C 2v(l¡k+1) = (¡(v ¡ lg(qC ))(l ¡ k + 1) + l): Thus if n < (v ¡ lg(qC ))(l ¡ k + 1) ¡ l we have Pr[E1] > Pr[E2], what we wanted to prove. Pr[E2] · Pr[AH1;:::;Hl ¯nds l ¡ k + 1 preimages]
X
Pr[8i 2 J : A ¯nds preimage for yi] · · < ·
Jµf1;:::;lg jJj=l¡k+1
X Jµf1;:::;lg i2J jJj=l¡k+1
Y qi
2v
X Jµf1;:::;lg jJj=l¡k+1 ql¡k+1
C 2v(l¡k+1)
Note that if Pr[E1] > Pr[E2]. then Pr[E1 ^:E2] > 0, ¤ what means, that there exist images y1; : : : ; yl 2 f0; 1gv such that for each Y 2 f0; 1gn there exists a message The condition n < (v¡lg(qC ))(l¡k+1)¡l gives the M 2 f0; 1gm for which CH1;:::;Hl (M ) = Y and the lower bound how short can be the output of a secure evaluation of CH1;:::;Hl (M ) does not present preim- (k; l)-Pre-combiner. It looks rather unnatural, howages 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[CH1;:::;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 [
To ¯nd Pr[E2], let qi be the number of queries to Hi bmeaudpepbeyr Cbo(unnodteedtbhyatthPe lip=r1oqbia=bilqitCy).thTahtethPer[bEe2s]tcoarn- 2Tnhde-porreeimma2ge. rLeestist(aCn;cPe,) wbheerae (Ck; lm)-caokmesbinaetrmofosrt acle algorithm AH1;:::;Hl , which is allowed to query Hi qC oracle queries. Suppose, that at most qi times ¯nds a preimage for at least l ¡ k + 1 of yi (A can evaluate CH1;:::;Hl and then A's success n < (v ¡ lg(qC ))(l ¡ k + 1) ¡ l + 1 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 1 for each Y we set f (Y ) to the corresponding message M AdvSPec[k][(H1; : : : ; Hl); 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. tLieotnsH. 1W;:e: :c;laHi ml,bethaaltl itnhdeeppreonbdaebnitlitryanwdhoemrehPashqufeurniecs- lg(Pr[E2]) < lgµ 22vl(qlCl¡¡kk++11) ¶ 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 polynomial 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 (signi¯cantly) of w for at least k of the H1; : : : ; Hl. shorter than concatenation do not exist. Our results
Thus let H1; : : : ; Hl be as de¯ned above and let are similar to ones for collision resistance from [
In other words, E1 is the event when M 0 is the possible inputs. Such a condition is not very practisecond-preimage of M in the sense of CH1;:::;Hl and cally relevant { one can think of creating a combiner, E2 means that the evaluation of CH1;:::;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 analya 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
Now, let qi be the maximum number of queries to Hi made by C. We can upper bound Pr[E2] by the probability that the best oracle algorithm A which can query each Hi at most qi times ¯nds second-preimage of w for at least l¡k+1 of the His. However H1; : : : ; Hl are all independent random functions, thus the best A can do is to query each Hi on qi 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[E2] < 2v(l¡k+1)