Improved rate upper bound of collision resistant compression functions

Abstract

Based on Stanek's results [1] we know that in model with integer rate PGV like compression functions no high speed collision resistant compression functions exist. Thus we try to study more general multiple block ciphers based model of compression functions with rational rate, like 6/5. We show a new upper bound of the rate of collision resistant compression functions in this model.

-

Traditional constructions [ 8 ] of hash functions require one block cipher transformation per input message block (so called rate-1 hash functions) and they require rekeying for every input message block. Black, Cochran and Shrimpton [ 10 ] showed in year 2005 that it is not possible to construct a provably secure rate-1 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 iterated hash function based on block cipher. In other words, we attempt to maximize the number of input message blocks processed by a single block cipher invocation. The cryptographic hash functions are a basic building block of many other cryptographic constructions (such 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 notasome 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 = ample, it is possible to extract 160 bits block cipher f0; 1gm. 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 2 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 In this year Preneel, Govaerts and Vandewalle done block ciphers E : Vk £ Vn ! Vn. Let denote E¡1 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 speedups of iterated hash functions based on block ci- H : Bloc(k; n) £ Vb¤ ! Va defined by HE (m1 : : : ml) = phers is increasing the number of input message blocks hl, where hi = f E (hi¡1; mi) and h0 is fixed element processed by one use of block cipher. Another possibil- from Va (so called initialization vector). Let HE (") = 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 divisible by n. The rate r represents average number of input message blocks processed by a single enciphering transformation E. For example, if b=n = 3 and t = 2 then we get rate- 32 compression function. 2.1

Black-box model

For any q ¸ 0 we write:

Advcfomp(q) = mAaxfAdvcfomp(A)g where the maximum is taken over all adversaries that 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 funccipher model. In this model, an adversary A is given tion [ 9 ]). Let H be hash function based on block ciaccess to oracles E and E¡1, where E is a block ci- pher. Let A be an adversary. Then the advantage of the pher. We write the oracles as superscripts, i.e. AE;E¡1 . 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.

Adversary A tries to find collisions in the com- AdvcHoll(A) = PrhE á$ Bloc(k; n); (M; M 0) à AE;E¡1: pression function. Other cryptographic properties of compression functions are also important, but we fo- M 6= M 0 ^ HE (M ) = HE (M 0)i : 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 necessary to analyze other properties. AdvcHoll(q) = mAaxfAdvcHoll(A)g

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 una black-box. The only modeled structural property of derlying compression function is collision resistant. the block cipher is its invertibility. This model cannot 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 . model is stronger than model in which block cipher Then AdvcHoll(q) · Advcfomp(q) for any q ¸ 1. is assumed to be random function, because adversary can compute E¡1.

We say that inputs (h; m) and (h0; m0) of compression function f collide, if they are distinct and f E (h; m) = f E (h0; m0). We say that (h; m) collides with empty string, if f E (h; m) = h0, where h0 is initialization vector.

We write random draw of element x from finite set S as x á$ S. We will use notation (x; y) à AE;E¡1 for computation of two colliding inputs x and y by adversary A (represented by probabilistic algorithm) with knowledge of oracles E and E¡1.

Birth-day attack is generic way of attacking collision resistance of any compression or hash function.

The advantage of finding collision by applying birthday attack is £(q2=2n), where q is number of evaluation of the function and n is output length.

If q depends on n, then we assume that q(n) = o(2n=2), because greater q(n) does not make sense, as we can still use generic birth-day attack with lower q(n) = 2n=2 with unacceptably high probability (¼ 1=2) of finding collision.

Compression function f (or hash function H) is usually called collision resistant up to birthday attack bound or simply collision resistant if Advcfomp(q) = Definition 1 (Coll. res. of comp. function [ 9 ]).

Let f be block cipher based compression function, f : Bloc(k; n) £ Va £ Vb ! Vc. Fix a constant h0 2 Vc and an adversary A. Then the advantage of adversary A (denoted by Advcfomp(A)) in finding collisions in compression function f is the following probability:

PrhE á$ Bloc(k; n); ¡(h; m); (h0; m0)¢ à AE;E¡1 : ¡(h; m) 6= (h0; m0) ^ f E (h; m) = f E (h0; m0)¢ _ f E (h; m) = h0i:

O(q2=2n) (or AdvcHoll(q) = O(q2=2n)). Since birth-day attack is always possible, we can rewrite these equations into equivalent form Advcfomp(q) = £(q2=2n) (or AdvcHoll(q) = £(q2=2n)). 3

Known results In [ 11 ] we have proposed a model of rate-r compression functions that cover all compression functions that 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 mulgeneralizations 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 Theorem 2 (Stanek [1]). Let E 2 Bloc(k; n). Let used block ciphers t, then we will write t as superscript f X : Va £ Vrn ! Vn, f K : Va £ Vrn ! Vk and f C : of compression function, i.e. f t. Iterated hash function Va £ Vrn £ Vn ! Va be arbitrary functions. Let f : based on compression function f : Bloc(k; n)t £ Va £ fVa(h£;mV)rn= !f CV¡ha; mbe; EcofmKp(hr;emss)(iofnX (fhu;nmct)io)¢n. dLeefitnqed¸b1y fiVnbe!dbVya His((fEun1;c:ti:o:n; EHt);:mB1lo::c:(mk;ln))=t£hlV,b¤wh!ereVahide=denote maximum number of queries on E and E¡1. f ((E1; : : : ; Et); hi¡1; mi) and h0 is fixed element from Let r > 1 + k¡log2 q . Then Advcfomp(q) = 1. Va. We define H((E1; : : : ; Et); ") to be equal to h0. If n 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 2 Bloc(n; n). Let f X : Vn £ Vrn ! Vn, f K : Vn £ Vrn ! Vn and f C : Vn£Vrn£Vn ! Vn be arbitrary functions. Let function f : Vn£Vrn ! Vn be a compression function defined by f (h; m) = f C ¡h; m; EfK(h;m)(f X (h; m))¢. Let r > 1.

Then f is not collision resistant in black-box model.

Now our result about nonexistence of rate-2 collision resistant PGV-like compression functions from [ 11 ] follows from corollary 1. But the attack based on theorem 2 has exponential time complexity (and asks n oracle queries, even if it is not necessary).

Therefore our attacks from [ 11 ] constructed specifically for rate-2 PGV-like compression and hash functions are still justified as they use only polynomial time and ask at most two queries.

Until now we have not modeled any compression function which uses more block ciphers per one compression function computation. For example: – Computation of compression function f t asks exactly one query on each oracle Ei for the purpose of evaluation of f t(h; m).

This assumption is without loss of the generality.

We do not assume that in practice all E1; : : : ; Et are distinct, but the model allows it. If for computation of function f t we need to evaluate Ei, e.g. two times, then we can set Et+1 = Ei and use function f t+1 defined analogically as f t but with the only exception, that in place of second evaluation of Ei evaluation of Et+1 will be used. 1 As we will clarify in following paragraph, it is important that t queries on oracles are made during each evaluation of compression function f . It does not matter, if the same block cipher is invoked t times, or if t different block ciphers are invoked exactly once. Hence some of t block ciphers can be equal. Analogically, it does not make sense to specify function f C processes both inputs h and m with all inblock 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 funcacles 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 compression function does not have to be divisible by block cipher E plain text block length n.

The compression function f t (and its iterated hash function H) have rate r = (b=n)=t.

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).

Let for all i 2 f1; 2; : : : ; tg fiX : Va£Vb£V i¡1 ! Vn

n and fiK : Va £ Vb £ V i¡1 ! Vk be arbitrary functions.

n Let f C : Va£Vb£V t

n ! Va be arbitrary function. Computation of compression function f t : Bloc(k; n)t £ Va £ Vb ! Va in generalized model is defined by the following algorithm 1.

Algorithm 1 The gen. model of compression function 1: function f ((E1; : : : ; Et); h; m) 2: Y 0 = () 3: for i = 1 to t do 4: Xi à fiX (h; m; Y i¡1) 5: Ki à fiK (h; m; Y i¡1) 6: Yi à Ei(Ki; Xi) 7: Y i à Y i¡1 ¢ Yi 8: end for 9: return f C (h; m; Y t) 10: end function Remark 1. Function fiX , respective function fiK prepares the plain text, respective the key for the block cipher Ei. Both inputs h and m are arguments of these functions together with all already computed cipher texts Y1; Y2; : : : ; Yi¡1. At the end of the algorithm, 2 Requirement of fixed evaluation order of block ciphers is not so restrictive as it can seem. We can simulate compression function with variable evaluation order of t block ciphers by compression function with fixed evaluation order of t2 block ciphers. See e.g. discussion at the end of section 2 in [ 13 ].

Before proof of the upper bound we first define some auxiliary notions and prove some lemmas.

Definition 4. Let i 2 f0; 1; : : : ; tg and (h; m) 2 Va £ Vb. If i = 0 then Y i;(h;m) = (). If i > 0 then we define Y i;(h;m) recursively as follows:

Y i¡1;(h;m) ¢ Ei³fiK ¡h; m; Y i¡1;(h;m)¢;

´ fiX ¡h; m; Y i¡1;(h;m)¢ : Sequence Y i;(h;m) represents individual Yi calculated during individual rounds of f t(h; m) evaluation. It can easily be seen that Y i¡1;(h;m) is prefix of Y i;(h;m) and that Y t;(h;m) is equal to Y t, which is created during evaluation of compression function f t(h; m).

Definition 5. Let i 2 f1; 2; : : : ; tg, X 2 Vn, K 2 Vk and let 2n+k > ® > 0 be an integer. Let S µ Va, where jSj = s > 0. Then D®0 = S £ Vb and D®i is union of ® largest sets DXi;K taken through all X and K (let denote them DXi1i;K1i ; : : : ; DXi®i;K®i ), where DXi;K is defined as follows: DXi;K = n(h; m) 2 D®i¡1 ¯¯¯ fiX ¡h; m; Y i¡1;(h;m)¢ = X^

^ fiK ¡h; m; Y i¡1;(h;m)¢ = Ko :

Set DXi;K is subset of D®i¡1. It consists of those elements, which in next (i-th) round will lead to the same query Ei(X; K) on oracle Ei. That means that to compute next round for all elements from DXi;K one oracle query is sufficient. Construction of sets DXi;K have of course exponential complexity, but does not require any oracle queries. Since we use black-box model, adversary have computationally unlimited power and is limited only by number of oracle queries.

Set D®1 is the largest set of tuples (h; m) 2 S £ Vb, for which we can made first round of compression function f t with spending exactly ® queries on oraD1 cle E1. By definition D®1 is union of ® largest sets

X11;K11 ; : : : ; DX1®1;K®1 . For the calculation of the first round for elements from every set DX1j1;Kj1 we need one query E1(Xj1; Kj1) on oracle E1. Since all tuples (Xj1; Kj1) are distinct, we need exactly ® queries for selected ® sets. set D®i in following way.

We do not know how to estimate cardinality of set, which is the largest set of tuples (h; m) 2 S £ Vb, for which we can do first two rounds of compression function f with at most 2® queries on oracles E1 and E2. However we know how to estimate cardinality of set D®2, which is such largest set of tuples (h; m) 2 D®1.

Therefore we have constructed set D®i as subset of D®i¡1. Then we are able to lower bound cardinality of integers. Then jD®ij ¸ ®i2b¡i(n+k)s.

Lemma 1. Let 1 · ® · 2n+k and let 0 · i · t be Proof. (Using mathematical induction over i.) Ind. basis: jD®0j = jS £ Vbj = s2b

¸ ®02b¡0(n+k)s.

Ind. hypothesis: Let jD®ij ¸ ®i2b¡i(n+k)s.

Ind. step: Then jD®i+1

j ¸ ®i+12b¡(i+1)(n+k)s.

Set jD®i+1

j is by definition 5 union of ® < 2n+k largest sets DXi+;K1 . Nonempty sets DXi+;K1 are all distinct and their union is equal to D®i. In other words, elements of the set D®i are divided into 2n+k shelves.

Then using pigeonhole principle we can estimate cardinality of ® largest of them in the following way: jD®i+1j ¸ ® 2jDn+®ikj ¸ ¸ ® ®i2b¡i(n+k)s 2n+k = ®i+12b¡(i+1)(n+k)s :

tu Lemma 2. At most t® queries on oracles E1; : : : ; Et are sufficient for computation of set D®t among with values of compression function f t(h; m) for all tuples (h; m) from the set D®t. matrix M have totally t® elements.

Proof. We construct matrix M , which has on i-th row Di tuples (X1i ; K1i ) : : : (X®i; K®i) used during the construction of set D®i by taking the union of ® largest sets

X1i;K1i ; : : : ; DXi®i;K®i . M has t rows and ® columns, so B B B B . . cles are necessary as it is S £Vb by definition. Similarly during the construction of set D®1 no queries on oracles are necessary as Y 0;(h;m) is by definition empty.

During the construction of D®i for i 2 f2; 3; : : : ; tg all queries will be on oracles E1; : : : ; Ei¡1. Queries on oracle E1 will be only from the first row of matrix M , queries on oracle E2 will be only from the second row, and so on, ending with queries on oracle Ei¡1, which are only from (i ¡ 1)-th row of matrix M . Last row of matrix M (together with all others) is used during the computation of values f t(h; m) = f C (h; m; Y t;(h;m)) for all (h; m) 2 D®t.

During the computation of D®i a new i-th row is created in the matrix M . Tuples (Xji¡1; Ki¡1) from

j (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 from already evaluated row l of matrix M . That follows from the fact that D®i µ D®i¡1. Therefore we will need at most t® queries on oracles E1; : : : ; Et during the computation of D®t together with values of compression function f t(h; m) for all (h; m) 2 D®t if we remember already asked queries together with corresponding answer.

tu Theorem 3. Let f : Bloc(k; n)t £ Va £ Vb ! Va be arbitrary rate-r compression function defined by algorithm 1, while r = b=tn . Let q ¸ 1 be maximum allowed number of queries on oracles Ei and Ei¡1. Let q be an integer of the form q = t®, where ® ¸ 1 is also an integer3. Let r > 1 + nk ¡ log2 ® . Then Advcfomp(q) = 1.

n Proof. By asking at most q queries we are according to lemma 2 able to compute values of f t(h; m) 2 Va for all (h; m) 2 D®t. Let S = Va, thus s = jSj = 2a. According to lemma 1 we know that jD®tj ¸ ®t2b¡t(n+k)s = ®t2a+b¡t(n+k). We can guarantee that between computed values there are at least two identical values if: ®t2a+b¡t(n+k) > 2

a t log2 ® + a + b ¡ t(n + k) > a

b > t(n + k) ¡ t log2 ® : 3 This requirement is natural. For computation of f t we need t oracle queries. Hence if we set q = t®, then as if we allow ® complete computations of f t. Now we rewrite this inequality into required form by using following equality r = b=tn :

b > t(n + k) ¡ t log2 ® b=n t > n + k

n r > 1 +

¡ k n ¡ log2 ® log2 ® n n

: Advcfomp(q) = 1 holds.

This means that with probability 1 we can find (and so the adversary) collision in the compression function f , while asking at most q queries on oracles. Hence

tu

Computation of the particular D®i has exponential complexity. Also finding the collision between values f t(h; m) for all (h; m) 2 D®t has exponential complexity. But computationally unlimited adversary of blackbox model can do all this unless he does not ask more than q queries on oracles.

Theorem 3 gives upper bound depending on number of oracle queries. The following corollary adapts number of queries q, the number of output bits a of compression function is used in the inequality for r. resistant.

Corollary 2. Let f t : Bloc(k; n)t £ Va £ Vb ! Va be arbitrary rate-r compression function defined by algorithm 1, where r = b=tn . Let 0 · " < 12 be arbitrary constant. Let r > 1 + nk ¡ " na . Then f t is not collision Proof. Let 0 · ¸ < 1 be arbitrary constant. Then we set q = t2¸ a2 , i.e. ® = 2¸ a2 . Then by substituting into theorem 3 we get that Advcfomp(q) = 1 (that means according to size of q that f t is not collision resistant) if: r > 1 + r > 1 + r > 1 + k n ¡ n ¡ k k log2 ®

n log2 2¸ a2

n n ¡ (¸=2) a n

: Now we make a substitution " = ¸=2 and required inequality follows: r > 1 + k

a n ¡ " n , where 0 · " < 1 2

:

As we have already mentioned, constructions of compression function based on block cipher, often have the same size of the key and the plain-text input of block cipher, i.e. k = n. Similarly, the output of compression function have usually the same size, i.e. a = n.

For this typical situation we can simplify corollary 2. the previous theorem in such a way, that instead of In our effort to find high speed collision resistant comsion function f t is not collision resistant.

Corollary 3. Let f t : Bloc(n; n)t £ Vn £ Vb ! Vn be arbitrary rate-r compression function defined by algorithm 1, where r = b=tn . Let r > 3=2. Then compresconstant 0 · " < 12 we get that compression function f t is not collision resistant if r > 1 + nn ¡ " nn = 2 ¡ " for an arbitrary

That implies that compression function f t is not collision resistant if r > 2 ¡ 21 = 3=2.

tu

In generalized model rate r of compression function can be rational number and not only integer as in [ 11 ]. Therefore based on our results we cannot conclude that no high rate compression function exists in the generalized model. Still it is possible that e.g. rate- 56 collision resistant compression function exists. 6

Conclusion pression function we have introduced and studied new generalized model of compression function since in all previous models it was proved that no such functions exists. This model introduces rational rates, so we can study more precisely the rate upper bound of collision resistant compression functions. Based on previous results, it seems to be less than or equal to 2. We have improved this bound to be less than or equal to 32 . 1. M. Stanek:

Analysis of fast blockcipher-based hash functions. In: Computational Science and Its Applications – ICCSA 2006, Springer, 2006, 426–435. 2. D.R. Stinson:

Cryptography: Theory and Practice, Third Edition. Chapman & Hall/CRC, Boston, MA,

USA, 2005.

Menezes, P.C. van Oorschot, S.A. Vanstone: Handbook of Applied Cryptography. CRC-Press, Boca

Raton, FL, USA, 1996. 4. R.C. Merkle:

One way hash functions and DES.

Volume 435 of Lecture Notes in Computer Science,

Springer Berlin, Heidelberg, 1990, 428–446. 5. I.B. Damgård: A design principle for hash functions.

Volume 435 of Lecture Notes in Computer Science,

Springer Berlin, Heidelberg, 1990, 416–427. tu 6. H. Handschuh, L.R. Knudsen, M.J. Robshaw: Analysis of SHA-1 in encryption mode. Volume 2020 of Lecture Notes in Computer Science, Springer Berlin, Heidelberg, 2001, 70–83. 7. M.O. Rabin:

Digitalized signatures. In Millo R.D., Dobkin D., Jones A., Lipton R., eds.: Foundations of Secure Computations, New York, Academic Press,

References

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 analysis of the block-cipher-based hash-function constructions 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 impossibility of highly-efficient blockcipher-based hash functions . Volume 3494 of Lecture Notes in Computer Science , 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 functions are not collision resistant . In: ITAT: Information Technologies - Applications and Theory , Seòa: PONT, 2006 , 139 - 143 .

13. P. Rogaway , J. Steinberger: Security/efficiency tradeoffs for permutation-based hashing . Volume 4965 of Lecture Notes in Computer Science , Springer Berlin, Heidelberg, 2008 , 220 - 236 .