Hash Functions Based on
Three Permutations: A Generic Security Analysis
Bart Mennink (KU
Bart Preneel (KU
Abstract:
We consider the family of 2n-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 pi_1, pi_2, pi_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^{2n/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 XOR pi_1(x_1) XOR pi_2(x_2) XOR pi_3(x_1 XOR x_2 XOR pi_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^{2n/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.