Improved rate upper bound of collision resistant compression functions Richard Ostertág? Department of Computer Science, Faculty of Mathematics, Physics and Informatics, Comenius University, Mlynská dolina, 842 48 Bratislava, Slovak Republic ostertag@dcs.fmph.uniba.sk http://www.dcs.fmph.uniba.sk Abstract. Based on Stanek’s results [1] we know that in Traditional constructions [8] of hash functions re- model with integer rate PGV like compression functions no quire one block cipher transformation per input mes- high speed collision resistant compression functions exist.sage block (so called rate-1 hash functions) and they Thus we try to study more general multiple block ciphers require rekeying for every input message block. Black, based model of compression functions with rational rate, Cochran and Shrimpton [10] showed in year 2005 that like 6/5. We show a new upper bound of the rate of collision it is not possible to construct a provably secure rate-1 resistant compression functions in this model. iterated hash function based on block cipher, which uses only small fixed set of keys. For these reasons our goal is to maximize rate of 1 Motivation and goals iterated hash function based on block cipher. In other words, we attempt to maximize the number of input The cryptographic hash functions are a basic building message blocks processed by a single block cipher in- block of many other cryptographic constructions (such vocation. as digital signature schemes, message authentication code, . . .). For more complete overview see e.g. [2, 3]. Majority of modern hash functions is based on 2 Notation Merkle-Damgård paradigm [4, 5]. Many compression functions are explicitly based on block cipher. Even We now briefly introduce basic definitions and nota- some of “dedicated” hash functions (which were not tions, following closely [10, 9]. constructed in this way) have this structure. For ex- Let Vm be set of all m-ary binary vectors, i.e. Vm = m ample, it is possible to extract 160 bits block cipher {0, 1} . Let Vm∗ = (Vm )∗ be set of all binary strings with 512 bits key (called SHACAL-1) from compres- that we get by concatenation of zero or more elements sion function implemented in SHA-1 hash function [6]. from Vm . Let k and n be positive integers. A block The idea of hash function construction by iterating cipher is a function E : Vk × Vn → Vn , where for block cipher is at least 30 years old [7]. Nevertheless no each key K ∈ Vk , the function EK (·) = E(K, ·) is systematic analysis of this idea was done until 1994. a permutation on Vn . Let Bloc(k, n) be the set of all −1 In this year Preneel, Govaerts and Vandewalle done block ciphers E : Vk × Vn → Vn . Let denote E the the first systematic study of 64 hash functions based inverse of block cipher E. on block cipher [8]. Thereafter Black, Rogaway and A block cipher based compression function is Shrimpton [9] analyzed these constructions in black- a function f : Bloc(k, n)×Va ×Vb → Vc , where a, b and box model and showed that 20 of them are collision c are positive integers such that a+b ≥ c. We will write resistant up to birthday-attack bound. the first argument (the block cipher) as superscript of At least from the usability point of view, speed the compression function, i.e. f E (·, ·) = f (E, ·, ·). An is important property of hash function. So it is only iterated hash function based on compression function natural to attempt to speedups it. One of possible f : Bloc(k, n) × Va × Vb → Va is the hash function ∗ E speedups of iterated hash functions based on block ci- H : Bloc(k, n) × Vb → Va defined by H (m1 . . . ml ) = E phers is increasing the number of input message blocks hl , where hi = f (hi−1 , mi ) and h0 is fixed element E processed by one use of block cipher. Another possibil- from Va (so called initialization vector). Let H (ε) = ity of speedup is a restriction of keys used in all block h0 for empty string ε. We often omit superscript E ciphers to a small fixed set of keys. Then it is possible of functions f and H when it is apparent from the to pre-schedule subkeys for each round of used block context which block cipher is used. ciphers, whereby saving a big amount of work. If the computation of f E (h, m) uses t queries on E, then compression function f (and its iterated hash ? Supported by VEGA grant No. 1/0266/09. function H) is rate-r, where r = (b/n)/t. Often b is 54 Richard Ostertág divisible by n. The rate r represents average number For any q ≥ 0 we write: of input message blocks processed by a single enci- phering transformation E. For example, if b/n = 3 Advcomp f (q) = max{Advcompf (A)} A and t = 2 then we get rate- 32 compression function. where the maximum is taken over all adversaries that 2.1 Black-box model ask oracles (E or E −1 ) at most q queries. Black-box model (see e.g. [9]) is also known as ideal- Definition 2 (Collision resistance of hash func- cipher model. In this model, an adversary A is given tion [9]). Let H be hash function based on block ci- access to oracles E and E −1 , where E is a block ci- pher. Let A be an adversary. Then the advantage of the −1 pher. We write the oracles as superscripts, i.e. AE,E . adversary A in finding collisions in hash function H Where used oracles are clear from the context, the su- is the following probability: perscript of A will be omitted. h Adversary A tries to find collisions in the com- $ −1 Advcoll H (A) = Pr E ← − Bloc(k, n); (M, M 0 ) ← AE,E : pression function. Other cryptographic properties of i compression functions are also important, but we fo- M 6= M 0 ∧ H E (M ) = H E (M 0 ) . cus exclusively on collision resistance, as on the most “problematic” property of compression functions. We For any q ≥ 0 we write: will see that our results are negative, so it is not nec- essary to analyze other properties. Advcoll coll H (q) = max{AdvH (A)} A In the black-box model the adversary’s collision finding effort is measured by the number of queries where the maximum is taken over all adversaries that made to oracles E and E −1 . Computational power of ask oracles (E or E −1 ) at most q queries. the adversary is not limited in any way — i.e. we as- The Merkle-Damgård construction of iterated hash sume information-theoretic adversary. functions is based on the following theorem. It states Attacks in this model treat the block cipher as that iterated hash function is collision resistant if un- a black-box. The only modeled structural property of derlying compression function is collision resistant. the block cipher is its invertibility. This model can- not guarantee security of compression functions based Theorem 1 (Merkle-Damgård [4, 5]). on weak block ciphers with inappropriate properties Let f : Bloc(k, n) × Vn × Vn → Vn be a compression (such as weak keys). On the other hand, black-box function and let H be an iterated hash function of f . comp model is stronger than model in which block cipher Then Advcoll H (q) ≤ Advf (q) for any q ≥ 1. is assumed to be random function, because adversary can compute E −1 . Birth-day attack is generic way of attacking colli- We say that inputs (h, m) and (h0 , m0 ) of com- sion resistance of any compression or hash function. pression function f collide, if they are distinct and The advantage of finding collision by applying birth- f E (h, m) = f E (h0 , m0 ). We say that (h, m) collides day attack is Θ(q 2 /2n ), where q is number of evalua- with empty string, if f E (h, m) = h0 , where h0 is ini- tion of the function and n is output length. tialization vector. If q depends on n, then we assume that q(n) = We write random draw of element x from finite o(2n/2 ), because greater q(n) does not make sense, as set S as x ← $ − S. We will use notation (x, y) ← AE,E −1 we can still use generic birth-day attack with lower for computation of two colliding inputs x and y by q(n) = 2n/2 with unacceptably high probability (≈ 1/2) adversary A (represented by probabilistic algorithm) of finding collision. with knowledge of oracles E and E −1 . Compression function f (or hash function H) is usually called collision resistant up to birthday attack Definition 1 (Coll. res. of comp. function [9]). bound or simply collision resistant if Advcomp (q) = f Let f be block cipher based compression function, f : O(q 2 /2n ) (or Advcoll H (q) = O(q 2 n /2 )). Since birth-day Bloc(k, n) × Va × Vb → Vc . Fix a constant h0 ∈ Vc and attack is always possible, we can rewrite these equa- an adversary A. Then the advantage of adversary A tions into equivalent form Advcomp (q) = Θ(q 2 /2n ) (or (denoted by Advcompf (A)) in finding collisions in com- f pression function f is the following probability: Advcoll 2 n H (q) = Θ(q /2 )). h ¡ ¢ $ −1 Pr E ← − Bloc(k, n); (h, m), (h0 , m0 ) ← AE,E : ¡ ¢ 3 Known results (h, m) 6= (h0 , m0 ) ∧ f E (h, m) = f E (h0 , m0 ) i In [11] we have proposed a model of rate-r compression ∨ f E (h, m) = h0 . functions that cover all compression functions that Improved rate upper bound of collision . . . 55 process r input message blocks of length n per block cipher invocation with a key of length k. In that paper ³ ¡ ¢ we have showed that 1 + k/n is the upper bound of f (h, m) = f C h, m, E1 f1K (h, m), f1X (h, m) , rate of any collision resistant compression function in ¡ ¢´ such a model. E2 f2K (h, m), f2X (h, m) . For typical constructions, when k = n, we get that if any high-rate collision resistant function in our If m is created from four input message blocks, model exists, then it is rate-2 compression function. then this will be rate-2 compression function but is Consequently we have analyzed in [11] all rate-2 not covered by model from [11]. Also using of mul- generalizations of compression functions from [8] (all tiple block ciphers allows compression functions with of them are covered by our model). We have proved rational rate. For example, if m is created from three that none of them is collision resistant in the black- input message blocks, then we get rate- 32 compression box model. Staneková and Stanek showed in [12] that function. Therefore we have concentrated on creation either hash functions constructed from them are not of new more general model. collision resistant. But these functions does not cover whole set of rate-2 compression functions from our model. Hence 4 The generalized model of the question, if there exist any rate-2 collision resistant compression function compression function still remains open. This question is answered by Stanek in [1], where A compression function f based on t block ciphers1 he improves our upper bound by utilizing the possi- is function defined by f : Bloc(k, n)t × Va × Vb → bility of asking q queries during the attack (before the Vc , where a, b and c are positive integers such that adversary ask only one query). a + b ≥ c. When we will need to emphasize number of used block ciphers t, then we will write t as superscript Theorem 2 (Stanek [1]). Let E ∈ Bloc(k, n). Let of compression function, i.e. f t . Iterated hash function f X : Va × Vrn → Vn , f K : Va × Vrn → Vk and f C : based on compression function f : Bloc(k, n)t × Va × Va × Vrn × Vn → Va be arbitrary functions. Let f : Vb → Va is function H : Bloc(k, n)t × Vb∗ → Va de- Va × Vrn → V ¡ a be compression function ¢ defined by fined by H((E1 , . . . , Et ), m1 . . . ml ) = hl , where hi = f (h, m) = f C h, m, Ef K (h,m) (f X (h, m)) . Let q ≥ 1 f ((E1 , . . . , Et ), hi−1 , mi ) and h0 is fixed element from denote maximum number of queries on E and E −1 . Va . We define H((E1 , . . . , Et ), ε) to be equal to h0 . If Let r > 1 + k−log n 2q . Then Advcompf (q) = 1. block ciphers used in functions f and H are clear from By substituting q = n, a = n and k = n into theo- the context, then we will omit them as arguments of rem 2 we get upper bound for rate r in the following these functions. form r > 2 − logn2 n . If we take into account that in our Now we will start to define the general model of model rate r is always an integer, then we get following compression function f t : Bloc(k, n)t × Va × Vb → Va corollary of previous theorem. based on t block ciphers. Model is based on following assumptions: Corollary 1 (Stanek [1]). Let E ∈ Bloc(n, n). Let f X : Vn × Vrn → Vn , f K : Vn × Vrn → Vn and f C : – Computation of compression function f t asks ex- Vn ×Vrn ×Vn → Vn be arbitrary functions. Let function actly one query on each oracle Ei for the purpose f : Vn ×Vrn →¡Vn be a compression function ¢ defined by of evaluation of f t (h, m). f (h, m) = f C h, m, Ef K (h,m) (f X (h, m)) . Let r > 1. This assumption is without loss of the generality. Then f is not collision resistant in black-box model. We do not assume that in practice all E1 , . . . , Et Now our result about nonexistence of rate-2 col- are distinct, but the model allows it. If for com- lision resistant PGV-like compression functions putation of function f t we need to evaluate Ei , from [11] follows from corollary 1. But the attack based e.g. two times, then we can set Et+1 = Ei and on theorem 2 has exponential time complexity (and use function f t+1 defined analogically as f t but asks n oracle queries, even if it is not necessary). with the only exception, that in place of second Therefore our attacks from [11] constructed specifi- evaluation of Ei evaluation of Et+1 will be used. cally for rate-2 PGV-like compression and hash func- 1 As we will clarify in following paragraph, it is important tions are still justified as they use only polynomial that t queries on oracles are made during each evaluation time and ask at most two queries. of compression function f . It does not matter, if the Until now we have not modeled any compression same block cipher is invoked t times, or if t different function which uses more block ciphers per one com- block ciphers are invoked exactly once. Hence some of pression function computation. For example: t block ciphers can be equal. 56 Richard Ostertág Analogically, it does not make sense to specify function f C processes both inputs h and m with all in- block cipher Ei if it is not used during any cal- termediate results Y1 , Y2 , . . . , Yt into final result. The culation of compression function f . algorithm uses t functions fiX and t functions fiK . This assumption about f t guarantees that every But function f C is just one. Introduction of analogous computation of f t always asks exactly t queries “postprocessing” for every block cipher (i.e. for each on oracles. round) is needless. Calculation of local postprocessing – Computation of compression function f t asks or- at the end of i-th round can be incorporated into func- acles Ei in order of their indexes2 . Thus we can tions fjX and fjK of following rounds ( i.e. for all j > i ) assume that evaluation of block cipher Ei had to and into function f C . occur before evaluation of Ei+1 . – The length of input message block mi of compres- The compression function f t (and its iterated hash sion function does not have to be divisible by block function H) have rate r = (b/n)/t. cipher E plain text block length n. This generalized model of compression functions covers all compression functions, which takes messages In following text we will often work with sequences, of length a and b and process them using exactly therefore we now clarify some necessary notation. t block ciphers E1 , E2 , . . . , Et from Bloc(k, n) in this specified order, into message of length a. All rate-1 Definition 3. Empty sequence will be denoted by (). schemes from [8] and their rate-2 generalizations fall We will write (a1 , a2 , . . . , an ) for a sequence with n el- into this model. ements a1 , a2 , . . ., an . Sequences will be denoted by upper case letters with a overscore, for example Y . For addition of element an+1 at the end of a sequence 5 Upper bound of rate of collision (a1 , a2 , . . . , an ) we will use operation “ ·” in the follow- resistant compression functions ing way: (a1 , a2 , . . . , an )·an+1 = (a1 , a2 , . . . , an , an+1 ). Before proof of the upper bound we first define some Let for all i ∈ {1, 2, . . . , t} fiX : Va ×Vb ×Vni−1 → Vn auxiliary notions and prove some lemmas. and fiK : Va × Vb × Vni−1 → Vk be arbitrary functions. Let f C : Va ×Vb ×Vnt → Va be arbitrary function. Com- Definition 4. Let i ∈ {0, 1, . . . , t} and (h, m) ∈ Va × putation of compression function f t : Bloc(k, n)t × Vb . If i = 0 then Y i,(h,m) = (). If i > 0 then we define Va × Vb → Va in generalized model is defined by the Y i,(h,m) recursively as follows: following algorithm 1. ³ ¡ ¢ Y i−1,(h,m) · Ei fiK h, m, Y i−1,(h,m) , ¡ ¢´ Algorithm 1 The gen. model of compression function fiX h, m, Y i−1,(h,m) . 1: function f ((E1 , . . . , Et ); h; m) 2: Y 0 = () Sequence Y i,(h,m) represents individual Yi calculated 3: for i = 1 to t do during individual rounds of f t (h, m) evaluation. It can 4: Xi ← fiX (h, m, Y i−1 ) easily be seen that Y i−1,(h,m) is prefix of Y i,(h,m) and 5: Ki ← fiK (h, m, Y i−1 ) 6: Yi ← Ei (Ki , Xi ) that Y t,(h,m) is equal to Y t , which is created during 7: Y i ← Y i−1 · Yi evaluation of compression function f t (h, m). 8: end for Definition 5. Let i ∈ {1, 2, . . . , t}, X ∈ Vn , K ∈ Vk 9: return f C (h, m, Y t ) 10: end function and let 2n+k > α > 0 be an integer. Let S ⊆ Va , where |S| = s > 0. Then Dα0 = S × Vb and Dαi is union i of α largest sets DX,K taken through all X and K Remark 1. Function fiX , respective function fiK pre- i i (let denote them DX i ,K i , . . . , DX i i i ), where DX,K α ,Kα pares the plain text, respective the key for the block is defined as follows: 1 1 cipher Ei . Both inputs h and m are arguments of these n ¯ ¡ functions together with all already computed cipher i ¯ ¢ DX,K = (h, m) ∈ Dαi−1 ¯ fiX h, m, Y i−1,(h,m) = X∧ texts Y1 , Y2 , . . . , Yi−1 . At the end of the algorithm, o ¡ ¢ 2 ∧ fiK h, m, Y i−1,(h,m) = K . Requirement of fixed evaluation order of block ciphers is not so restrictive as it can seem. We can simulate i compression function with variable evaluation order of Set DX,K is subset of Dαi−1 . It consists of those ele- t block ciphers by compression function with fixed eval- ments, which in next (i-th) round will lead to the same uation order of t2 block ciphers. See e.g. discussion at query Ei (X, K) on oracle Ei . That means that to com- i the end of section 2 in [13]. pute next round for all elements from DX,K one oracle Improved rate upper bound of collision . . . 57 i query is sufficient. Construction of sets DX,K have of course exponential complexity, but does not require  1 1  (X1 , K1 ) . . . (Xj1 , Kj1 ) . . . (Xα1 , Kα1 ) any oracle queries. Since we use black-box model, ad-  .. .. ..  versary have computationally unlimited power and is    i. i . .  limited only by number of oracle queries.  i i M =  (X1 , K1 ) . . . (Xj , Kj ) . . . (Xα , Kα ) i i  Set Dα1 is the largest set of tuples (h, m) ∈ S × Vb ,  .. .. ..   . . .  for which we can made first round of compression t t t t t t function f t with spending exactly α queries on ora- (X 1 , K 1 ) . . . (X j , K j ) . . . (X α , K α ) 1 cle E1 . By definition Dα is union of α largest sets The only place where queries are made during the com- 1 1 DX 1 1 , . . . , DX 1 ,K 1 . For the calculation of the first putation of sets Dαi is the computation of Y i,(h,m) . 1 ,K1 α α 1 round for elements from every set DX 1 j ,Kj 1 we need During the construction of set Dα0 no queries on ora- one query E1 (Xj , Kj ) on oracle E1 . Since all tuples cles are necessary as it is S ×Vb by definition. Similarly 1 1 1 (Xj1 , Kj1 ) are distinct, we need exactly α queries for during the construction of set Dα no queries on oracles selected α sets. are necessary as Y 0,(h,m) is by definition empty. i We do not know how to estimate cardinality of During the construction of D α for i ∈ {2, 3, . . . , t} set, which is the largest set of tuples (h, m) ∈ S × Vb , all queries will be on oracles E 1 , . . . , E i−1 Queries on . for which we can do first two rounds of compression oracle E 1 will be only from the first row of matrix M , function f with at most 2α queries on oracles E1 and queries on oracle E 2 will be only from the second row, E2 . However we know how to estimate cardinality of and so on, ending with queries on oracle E i−1 , which set Dα2 , which is such largest set of tuples (h, m) ∈ Dα1 . are only from (i − 1)-th row of matrix M . Last row of Therefore we have constructed set Dαi as subset of matrix M (together with all others) is used during the t C Dαi−1 . Then we are able to lower bound cardinality of computation of values f (h, m) = f (h, m, Y t,(h,m) ) t set Dαi in following way. for all (h, m) ∈ D α . During the computation of Dαi a new i-th row is i−1 i−1 Lemma 1. Let 1 ≤ α ≤ 2n+k and let 0 ≤ i ≤ t be created in the matrix M . Tuples (Xj , Kj ) from integers. Then |Dαi | ≥ αi 2b−i(n+k) s. (i − 1)-th row are for the first time evaluated by oracle Ei−1 . Queries on oracle El for l < i − 1 will be only Proof. (Using mathematical induction over i.) from already evaluated row l of matrix M . That fol- 0 Ind. basis: |Dα | = |S × Vb | = s2 ≥ α 2 b 0 b−0(n+k) s. lows from the fact that Dαi ⊆ Dαi−1 . Therefore we will Ind. hypothesis: Let |Dαi | ≥ αi 2b−i(n+k) s. need at most tα queries on oracles E1 , . . . , Et during Ind. step: Then |Dα | ≥ α 2 i+1 i+1 b−(i+1)(n+k) s. the computation of Dαt together with values of com- t t Set |Dαi+1 | is by definition 5 union of α < 2n+k pression function f (h, m) for all (h, m) ∈ Dα if we largest sets DX,K i+1 . Nonempty sets DX,K i+1 are all dis- remember already asked queries together with corre- sponding answer. u t tinct and their union is equal to Dαi . In other words, elements of the set Dαi are divided into 2n+k shelves. Theorem 3. Let f : Bloc(k, n)t × Va × Vb → Va be Then using pigeonhole principle we can estimate car- arbitrary rate-r compression function defined by algo- dinality of α largest of them in the following way: rithm 1, while r = b/n t . Let q ≥ 1 be maximum allowed number of queries on oracles Ei and Ei−1 . Let q be an i+1 |Dαi | |Dα | ≥ α n+k ≥ integer of the form q = tα, where α ≥ 1 is also an in- 2 teger3 . Let r > 1 + nk − logn2 α . Then Advcomp (q) = 1. i b−i(n+k) f α2 s i+1 b−(i+1)(n+k) ≥α = α 2 s . Proof. By asking at most q queries we are according to 2n+k lemma 2 able to compute values of f t (h, m) ∈ Va for all u t (h, m) ∈ Dt . Let S = V , thus s = |S| = 2a . Accord- α a ing to lemma 1 we know that |Dαt | ≥ αt 2b−t(n+k) s = Lemma 2. At most tα queries on oracles E1 , . . . , Et αt 2a+b−t(n+k) . We can guarantee that between com- are sufficient for computation of set Dαt among with puted values there are at least two identical values if: values of compression function f t (h, m) for all tuples (h, m) from the set Dαt . αt 2a+b−t(n+k) > 2a t log2 α + a + b − t(n + k) > a Proof. We construct matrix M , which has on i-th row tuples (X1i , K1i ) . . . (Xαi , Kαi ) used during the construc- b > t(n + k) − t log2 α . i tion of set Dα by taking the union of α largest sets 3 This requirement is natural. For computation of f t we i i DX i i , . . . , DX i ,K i . M has t rows and α columns, so need t oracle queries. Hence if we set q = tα, then as if 1 ,K1 α α matrix M have totally tα elements. we allow α complete computations of f t . 58 Richard Ostertág Now we rewrite this inequality into required form by Corollary 3. Let f t : Bloc(n, n)t × Vn × Vb → Vn be using following equality r = b/n t : arbitrary rate-r compression function defined by algo- rithm 1, where r = b/n t . Let r > 3/2. Then compres- b > t(n + k) − t log2 α sion function f t is not collision resistant. b/n n + k log2 α > − Proof. After substituting n for a and k into corollary 2 t n n k log2 α we get that compression function f t is not collision r >1+ − . resistant if r > 1 + nn − ε nn = 2 − ε for an arbitrary n n constant 0 ≤ ε < 12 . This means that with probability 1 we can find (and That implies that compression function f t is not so the adversary) collision in the compression func- collision resistant if r > 2 − 1 = 3/2. u t 2 tion f , while asking at most q queries on oracles. Hence Advcompf (q) = 1 holds. u t In generalized model rate r of compression func- tion can be rational number and not only integer as Computation of the particular Dαi has exponential in [11]. Therefore based on our results we cannot con- complexity. Also finding the collision between values clude that no high rate compression function exists f t (h, m) for all (h, m) ∈ Dαt has exponential complex- in the generalized model. Still it is possible that e.g. ity. But computationally unlimited adversary of black- rate- 6 collision resistant compression function exists. 5 box model can do all this unless he does not ask more than q queries on oracles. Theorem 3 gives upper bound depending on num- 6 Conclusion ber of oracle queries. The following corollary adapts the previous theorem in such a way, that instead of In our effort to find high speed collision resistant com- number of queries q, the number of output bits a of pression function we have introduced and studied new compression function is used in the inequality for r. generalized model of compression function since in all Corollary 2. Let f : Bloc(k, n) × Va × Vb → Va be previous models it was proved that no such functions t t arbitrary rate-r compression function defined by algo- exists. This model introduces rational rates, so we can study more precisely the rate upper bound of collision rithm 1, where r = b/n 1 t . Let 0 ≤ ε < 2 be arbitrary resistant compression functions. Based on previous re- k a constant. Let r > 1 + n − ε n . Then f t is not collision sults, it seems to be less than or equal to 2. We have resistant. improved this bound to be less than or equal to 32 . Proof. Let 0 ≤ λ < 1 be arbitrary constant. Then we a a set q = t2λ 2 , i.e. α = 2λ 2 . Then by substituting into theorem 3 we get that Advcomp (q) = 1 (that means References f according to size of q that f t is not collision resistant) 1. M. Stanek: Analysis of fast blockcipher-based hash if: functions. In: Computational Science and Its Applica- k log2 α tions – ICCSA 2006, Springer, 2006, 426–435. r >1+ − 2. D.R. Stinson: Cryptography: Theory and Practice, n n a Third Edition. Chapman & Hall/CRC, Boston, MA, k log2 2λ 2 r >1+ − USA, 2005. n n 3. A.J. Menezes, P.C. van Oorschot, S.A. Vanstone: k a Handbook of Applied Cryptography. CRC-Press, Boca r > 1 + − (λ/2) . n n Raton, FL, USA, 1996. 4. R.C. Merkle: One way hash functions and DES. Now we make a substitution ε = λ/2 and required Volume 435 of Lecture Notes in Computer Science, inequality follows: Springer Berlin, Heidelberg, 1990, 428–446. k a 1 5. I.B. Damgård: A design principle for hash functions. r >1+ − ε , where 0 ≤ ε < . Volume 435 of Lecture Notes in Computer Science, n n 2 Springer Berlin, Heidelberg, 1990, 416–427. u t 6. H. Handschuh, L.R. Knudsen, M.J. Robshaw: Analysis of SHA-1 in encryption mode. Volume 2020 of Lecture As we have already mentioned, constructions of Notes in Computer Science, Springer Berlin, Heidel- compression function based on block cipher, often have berg, 2001, 70–83. the same size of the key and the plain-text input of 7. M.O. Rabin: Digitalized signatures. In Millo R.D., block cipher, i.e. k = n. Similarly, the output of com- Dobkin D., Jones A., Lipton R., eds.: Foundations pression function have usually the same size, i.e. a = n. of Secure Computations, New York, Academic Press, For this typical situation we can simplify corollary 2. 1978, 155–166. Improved rate upper bound of collision . . . 59 8. B. Preneel, R. Govaerts, J. Vandewalle: Hash functions based on block ciphers: A synthetic approach. Volume 773 of Lecture Notes in Computer Science, Springer Berlin, Heidelberg, 1994, 368–378. 9. J. Black, P. Rogaway, T. Shrimpton: Black-box analy- sis of the block-cipher-based hash-function construc- tions from PGV. Volume 2442 of Lecture Notes in Computer Science, Springer Berlin, Heidelberg, 2002, 103–118. 10. J. Black, M. Cochran, T. Shrimpton: On the impos- sibility of highly-efficient blockcipher-based hash func- tions. Volume 3494 of Lecture Notes in Computer Sci- ence, Springer Berlin, Heidelberg, 2005, 526–541. 11. R. Ostertág, M. Stanek: On high-rate cryptographic compression functions. Computing and Informatics 26, 2007, 77–87. 12. L. Staneková, M. Stanek: Generalized PGV hash func- tions are not collision resistant. In: ITAT: Information Technologies – Applications and Theory, Seòa: PONT, 2006, 139–143. 13. P. Rogaway, J. Steinberger: Security/efficiency trade- offs for permutation-based hashing. Volume 4965 of Lecture Notes in Computer Science, Springer Berlin, Heidelberg, 2008, 220–236.