Hash Functions Based on Three Permutations: A Generic Security Analysis

We consider the family of 2

n

-to-

n

-bit compression functions that are solely based on at most three permutation executions and on XOR-operators, and analyze its collision and preimage security. Despite their elegance and simplicity, these designs are not covered by the results of Rogaway and Steinberger (CRYPTO 2008). By defining a carefully chosen equivalence relation on this family of compression functions, we obtain the following results. In the setting where the three permutations

π

1

,

π

2

,

π

3

are selected independently and uniformly at random, there exist at most four equivalence classes that achieve optimal 2

n

/2

collision resistance. Under a certain extremal graph theory based conjecture, these classes are then proven optimally collision secure. Three of these classes allow for finding preimages in 2

n

/2

queries, and only one achieves optimal 2

2

n

/3

preimage resistance (with respect to the bounds of Rogaway and Steinberger, EUROCRYPT 2008). Consequently, a compression function is optimally collision and preimage secure if and only if it is equivalent to

F

(

x

1

,

x

2

) = 

x

1

 ⊕ 

π

1

(

x

1

) ⊕ 

π

2

(

x

2

) ⊕ 

π

3

(

x

1

 ⊕ 

x

2

 ⊕ 

π

1

(

x

1

)). For compression functions that make three calls to the same permutation we obtain a surprising negative result, namely the impossibility of optimal 2

n

/2

collision security: for any scheme, collisions can be found with 2

2

n

/5

queries. This result casts some doubt over the existence of any (larger) secure permutation-based compression function built only on XOR-operators and (multiple invocations of) a single permutation.