Parallel FFT–Hashing

C.P. Schnorr

Fachbereich Mathematik/Informatik Universität Frankfurt Postfach 111932 60054 Frankfurt a.M. e-mail: schnorr@informatik.uni-frankfurt.de

S. Vaudenay

Dép. Math. Inf. ENS Paris 45 Rue d’Ulm 75230-05 Paris e-mail: vaudenay@dmi.ens.fr

Abstract We propose two families of scalable hash functions for collision–resistant hashing that are highly parallel and based on the generalized fast Fourier transform (FFT). FFT–hashing is based on multipermutations. This is a basic cryptographic primitive for perfect generation of diffusion and confusion which generalizes the boxes of the classic FFT. The slower FFT–hash functions iterate a compression function. For the faster FFT–hash functions all rounds are alike with the same number of message words entering each round.

1 Introduction and surview

We propose two families of hash functions for collision–resistant hashing. These hash functions are scalable, highly parallel and based on the generalized fast Fourier transform (FFT). In comparison to FFT–Hash II we discard the polynomial iteration over a finite field. This yields an extremely simple and highly parallel design which is entirely defined by the FFT–graph. The only free parameters are the order 2^{k} of the FFT, the number of rounds and the boxes which we require to be multipermutations.

Our first and slower family of hash functions iterates a compression function. For this hashing we have determined, by black box cryptanalysis, the minimal number of rounds that is necessary for collision– resistant hashing. Black box cryptanalysis shows that iterating a compression function is not the best method for FFT–hashing. Our second and faster family of hash functions uses multiple fan–in of message words. A message word enters four times within the same round. The same number of message words enters each round so that all rounds are alike.

Multipermutations are a new cryptographic primitive for perfect generation of diffusion and confusion. For an arbitrary set E we call a permutation B : E^{2} → E^{2} , B(a, b) = (B_{1}(a, b), B_{2}(a, b)) a multipermutation if for every a, b ∈ E the mappings B_{i}(a, ∗), B_{i}(∗, b) for i = 1, 2 are permutations on E. Our hashing uses a vector space E = IF^{m} over the Galois field IF = {0, 1}, e.g. IF^{8}, IF^{16}, IF^{32}. There is a large variety of multipermutations for these E, both linear and non–linear over IF. Non–linear multipermutations can be generated by composing linear ones with non–linear permutations on E. We can use for this composition the multiplication modulo 2^{m} + 1.

We present in section 2 a family of compression functions based on FFT–networks. In section 3 we report on black box attacks on these compression functions. In section 4 we propose fast FFT hash algorithms that do not iterate a compression function. In section 5 we present multipermutations for the case that E is a linear space over the field IF. An example hash algorithm is proposed in section 6.

2 A family of compression functions.

Notation 1. We let IF denote the Galois field of order 2 and let E = IF^{m} be the linear space over the field IF with dimension m, e.g. m = 8, 16, 32, 64. We call the elements of E words.

2. Let k be a fixed integer, k > 0 and let i ∈ {0, …, 2^{k} − 1}. Let i_{j} ∈ {0, 1} for j = 0, …, k − 1 denote the j–th bit of i = i_{0} + 2i_{1} + … + 2^{k−1}i_{k−1}. Let the integer i(j) be obtained from i by negating the bit i_{j}. For our purposes it is convenient to define for j ≥ k that i_{j} = i_{j(modk)} , i(j) = i(j mod k) .

The compression function g_{k,s} : E^{2k} → E^{2k−1} INPUT e_{i} ∈ E for i = 0, …, 2^{k} − 1

(We call H = [e_{i} | i_{0} = 0] the hash input and M = [e_{i} | i_{0} = 1] the message input)

FOR j = 0, …, s DO
(e_{i}, e_{i(j)}) := B_{i,j}(e_{i}, e_{i(j)}) for all i, 0 ≤ i < 2^{k} with i_{j} = 0, in parallel

OUTPUT g_{k,s}(H, M) = [e_{i} | i_{s} = 0] ∈ E^{2^{k−1}}.

The choice of the boxes B_{i,j} : We require that the boxes B_{i,j} perform multipermutations on E^{2}. We call a permutation B : E^{2} → E^{2}, B(a, b) = (B_{1}(a, b), B_{2}(a, b)), a multipermutation if for every fixed a, b ∈ E the mappings B_{i}(a, ∗), B_{i}(∗, b) for i = 1, 2 are permutations on E. We call the component mappings B_{i} : E^{2} → E i = 1, 2 a bipermutation because they act as a permutation on both inputs. A permutation B : E^{2} → E^{2} is a multipermutation iff both component mappings B_{1}, B_{2} are bipermutations.

It is important that the message inputs e_{2i+1} and hash inputs e_{2i} are mixed by the boxes B_{i,0} of the first round j = 0. The hash outputs are from distinct boxes B_{i,s} of the last round j = s.

It may be of interest that g_{k,s} transforms the uniform distribution on E^{2^{k}} into the uniform distribution on E^{2^{k−1}}. This is because the boxes B_{i,j} perform permutations on E^{2}.

We can represent the algorithm g_{k,s} by a network. It consists of s+1 layers j = 0, …, s. Layer j has 2^{k−1} vertices B_{i,j} for i = 0, …, 2^{k}−1 with i_{j} = 0. The edges of the g_{k,s}–network correspond to the inputs/outputs e_{i}, e_{i(j)} of B_{i,j}. More precisely we let e_{i,j}, e_{i(j),j} denote the inputs of B_{i,j} and e_{i,j+1}, e_{i(j),j+1} the outputs of B_{i,j}. The hash input is H = [e_{i,0} | i_{0} = 0], the hash output is g_{k,s}(H, M) = [e_{i,s+1} | i_{s} = 0] and we have for j = 0, …, s :

(e_{i,j+1}, e_{i(j),j+1}) = B_{i,j}(e_{i,j}, e_{i(j),j}) for 0 ≤ i < 2^{k} with i_{j} = 0.

By iterating the compression function g_{k,s} we can transform arbitrary binary messages into a hash value in E^{2^{k−1}} that is m2^{k−1} bits long. We require that a given message, consisting of t bits, is padded so that its bit length becomes a multiple of m2^{k−1}. We recommend to append to the message a single “1” followed by a suitable number of “0” bits followed by the binary representation of t. So the padded message M = M_{1}M_{2} ⋯ M_{n} consists of n blocks M_{1}, …, M_{n} ∈ E^{2^{k−1}}, n = ⌈(t + 1 + ⌈log_{2}(t + 1)⌉)/m2^{k−1}⌉.

The hash function h_{k,s} INPUT M = M_{1} ⋯ M_{n} ∈ E^{n·2^{k−1}} (the padded message)

Fix an initial value H_{0} ∈ E^{2^{k−1}}

H_{i} := g_{k,s}(H_{i−1}, M_{i}) for i = 1, …, n

OUTPUT h_{k,s}(M) := H_{n} (the hash value of M)

The goal of the design is to make it infeasible to construct a collision for h_{k,s}, i.e. to produce distinct messages with the same hash value. To be infeasible for current technology the production of collisions should at least require about 2^{64} steps. We call h_{k,s} collision–resistant if producing a collision is infeasible.

3 Black box attacks on the compression function.

We consider the following problems: inverting g_{k,s} : Given random H, H′ ∈ E^{2^{k−1}} find M ∈ E^{2^{k−1}} satisfying g_{k,s}(H, M) = H′. g_{k,s} collisions : Given random H, H′ ∈ E^{2^{k−1}} find M, M′ ∈ E^{2^{k−1}} satisfying g_{k,s}(H, M) = g_{k,s}(H′, M′)

Black box cryptanalysis has been introduced in [SV 93]. It assumes that the B_{i,j} are black box multipermutations given by oracles. For B_{i,j}(a, b) = (u, v) any two words out of a, b, u, v determine the other two. The box B_{i,j} has degree of freedom 2, i.e. any two input/output edges of B_{i,j} determine all edges of B_{i,j}.

A black box attack is a sequence of two type of steps

• Guess an unknown edge e_{i,j}, i.e. try all possible values in E.

• Evaluate a vertex (box) B_{i,j}, i.e. determine all its edges from two known ones.

The complexity of a step is the number of edge assignments to be tried for this step. Initially the step complexity is 1; it increases by a factor 2^{m} when guessing a new edge in IF^{m}; it decreases by a factor 2^{m} when evaluating a vertex with three known edges. The complexity of the attack is the maximal step complexity over all steps. This complexity depends in a crucial way on the choice of guessed edges and the order in which the boxes are evaluated. The time bound for the attack is the product of the complexity and the time for evaluating all vertices of the g_{k,s}–network. We take the second factor to be 1.

In some attacks we pick random values for certain edges and we hold these values fixed. E.g. when H, H′ are given the edges corresponding to H, H′ are fixed. We assume that all fixed edges are uniformly at random. Then the complexity of the attack is the average complexity with respect to the fixed random edges.

To invert g_{k,s} we have to evaluate for the given random H, H′ all boxes of the g_{k,s}–network. To produce a collision for g_{k,s} we fix some output words of g_{k,s} at random, we evaluate with these random values all boxes of the network and we apply the birthday paradox to the output words of g_{k,s} that have not been fixed. Here are the complexities of the best known black box attacks according to [SV 93]:

g_{3,2} g_{3,3} g_{3,4}
inversion 2^{2m} 2^{3m} 2^{4m}
collision  2^{m} 2^{2m} 2^{2m}

\begin{matrix}g_{4,3} & g_{4,4} & g_{4,5} & g_{4,6} \\ 2^{4m} & 2^{5m} & 2^{6m} & 2^{8m} \\ 2^{2m} & 2^{3m} & 2^{4m} & 2^{4m} \end{matrix} \begin{matrix}g_{5,4} & g_{5,5} & g_{5,6} & g_{5,7} & g_{5,8} \\ 2^{8m} & 2^{9m} & 2^{10m} & 2^{12m} & 2^{16m} \\ 2^{4m} & 2^{5m} & 2^{6m} & 2^{8m} & 2^{8m} \end{matrix}

We let I(k, s) and C(k, s) denote the minimal complexity for the inversion of g_{k,s} and for producing g_{k,s}– collisions where the minimum is taken over all black box attacks. The best known black box attacks are based on the following inequalities reflecting a simple divide and conquer argument:

I(1, 0) = 1, I(k, k − 1) ≤ 2^{m2^{k−2}}  for k ≥ 2
I(k, k − 1 + t) ≤ I(k, k − 1) · I(t + 1, t)  for 0 ≤ t ≤ k − 1 and k ≥ 2 .
C(k, k − 1 + t) ≤ 2^{m2^{k−3}} · I(t + 1, t)  for 0 ≤ t ≤ k − 2 and k ≥ 3 .

We conjecture that these inequalities are actually equalities. If this holds true they determine the minimal complexities I(k, s) and C(k, s) for all k ≥ 2, s ≥ k − 1 and the above tables give the minimal complexities for arbitrary black box attacks. The restriction t ≤ k − 1 (resp. t ≤ k − 2) is due to the inequalities I(k, s) ≤ 2^{m2^{k−1}} , C(k, s) ≤ 2^{m2^{k−2}} since the length of the hash input/output is 2^{m2^{k−1}}. Under our conjecture the inversion and the collision production have maximal complexity for s = 2k −2 and s = 2k −3, i.e. I(k, 2k − 2) = 2^{m2^{k−1}} and C(k, 2k − 3) = 2^{m2^{k−2}} .

4 Fast parallel FFT–hashing

In view of the known attacks we are going to improve the hashing h_{k,s}. Here are our main points:

• Instead of discarding for every iteration of g_{k,s} half of the hash words e_{i} we combine them with the next message words. Only after processing the entire message we apply the compression function g_{k,s} discarding half the hash words.

• Each message word enters repeatedly in the same round. The same number of message words enters each round.

Using the circular rotation R on {0, 1, …, 2^{k} − 1} defined as R(i_{0} + 2i_{1} + … + 2^{k−1}i_{k−1}) = (i_{k−1} + 2i_{0} + … + 2^{k−1}i_{k−2}) we can simplify the recursion for g_{k,s} to FOR j = 0, …, s DO

FOR i = 0, 1, …, 2^{k−1} − 1 DO in parallel (e_{R^{j}(2i)}, e_{R^{j}(2i+1)}) := B_{i,j}^{∗}(e_{R^{j}(2i)}, e_{R^{j}(2i+1)}) The boxes B_{i,j}^{∗}, 0 ≤ i < 2^{k−1}, are a corresponding permutation of the boxes B_{i,j} , 0 ≤ i < 2^{k} with i_{j} = 0. R^{j} is the circular rotation by j positions. We can further rewrite this to

1. FOR i = 0, …, 2^{k} − 1 DO in parallel e_{R(i)} := e_{i}

2. FOR j = 0, …, s DO FOR i = 0, …, 2^{k−1} − 1 DO in parallel (e_{2i}, e_{2i+1}) := B_{i,j}^{∗}(e_{R(2i)}, e_{R(2i+1)})

3. FOR i = 0, …, 2^{k} − 1 DO in parallel e_{R^{s}(i)} := e_{i}

We use this recursion for the fast parallel FFT hashing. We again write B_{i,j} for B_{i,j}^{∗}. Let the padded message M consist of n words m_{i} ∈ E for i = 0, …, n − 1 and let m_{i} = 0 for i ≥ n.

Fast parallel FFT hashing h_{k} INPUT M = m_{0}m_{1} … m_{n−1} ∈ E^{n} (the padded message)

Fix initial values e_{i} ∈ E for i = 0, …, 2^{k} − 1

FOR j = 0, …, ⌈n/ℓ⌉ + s − 1 DO
e_{R(i)} := e_{R(i)} op_{i} m_{ℓj+(imodℓ)} for i = 0, …, 4ℓ − 1
FOR i = 0, …, 2^{k−1} − 1 DO in parallel (e_{2i}, e_{2i+1}) := B_{i,j}(e_{R(2i)}, e_{R(2i+1)})

OUTPUT h_{k}(M) = [e_{2i} | i = 0, …, 2^{k−1} − 1] Specific proposals for the binary operations op_{i} : E^{2} → E and the multipermutations B_{i,j} : E^{2} → E^{2} are given in section 6. We let each rounds j = 0, …, ⌈n/ℓ⌉ − 1 process ℓ ≤ 2^{k−2} consecutive message words m_{ℓj+i} for i = 0, …, ℓ − 1 . Each message word enters four times. After the last message word m_{n−1} is entered there follow s + 1 layers of multipermutations B_{i,j} for j = ⌈n/ℓ⌉ − 1, …, ⌈n/ℓ⌉ + s − 1 corresponding to the compression function g_{k,s}. The number s + 1 of the final layers can well be smaller than 2k and even 2k − 2, the number of layers which maximize the complexities I(k, s) and C(k, s). This is because the multiple duplication of the message words seriously complicates the attacks.

Figure of the network for h_{4} with n = 6, ℓ = 3, s = 3. The values k = 4, ℓ = 3 are as in the example algorithm in section 6.

[figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

[figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure]

■ ■ ■ ■

◇ ♣ ♠ ◇ ♣ ♠ ◇ ♣ ♠ ◇ ♣ ♠

j = 4

j = 3

j = 2

j = 1

j = 0

message words [figure] ■ ◇ ♣ ♠ marking the edges to which they are mixed via op_{i}

PARALLEL COSTS (depth) of h_{k}: Processing ℓ message words with m · ℓ bits requires a single operation op_{i} and a single box B_{i,j} plus s boxes on termination.

5 Examples of multipermutations

We introduce multipermutations on E^{2} that are based on the operations ⊕ (bitwise XOR), ∧ (bitwise AND), + (addition modulo 2^{m}), · (multiplication modulo 2^{m}), ∗ (multiplication in ZZ_{2^{m}+1}^{∗}) and R the circular rotation to the right on E.

Notation Let ⊕ denote the bitwise XOR on E = IF^{m}, i.e. ⊕ is the vector addition on the linear space E over the field IF. For b, c ∈ E let b ∧ c denote the bitwise AND . Let R^{ℓ} : E → E denote the circular rotation by ℓ positions to the right.

Theorem 1 [SV 93] For c ∈ E, ℓ ∈ ZZ the mapping L_{c} : E^{2} → E^{2} , L_{c}(a, b) = (a⊕b, a⊕(b∧c)⊕R^{ℓ}(b)), is a multipermutation if and only if the iterates of R^{ℓ} on c take for each bit position both values 0, 1.

Remarks. 1. We see that if L_{c} is a multipermutation then c ∉ {0^{m}, 1^{m}} since otherwise the bits of c are constant and so are the bits of R^{ℓ·n}(c) for all n.

2. If gcd(ℓ, m) = 1 , i.e. if ℓ is odd, then L_{c} is a multipermutation if and only if c ∉ {0^{m}, 1^{m}}. This is because, for odd ℓ, the iterates of R^{ℓ} carry every bit of c to all positions.

Proof. L_{c} is a multipermutation if and only if both mappings

b ↦ (b ∧ c) ⊕ R^{ℓ}(b) , b ↦ b ⊕ (b ∧ c) ⊕ R^{ℓ}(b)

are permutations of E. Now the claim follows from Lemma 2 with d = c and d = c̄, the bitwise negation of c. For the second mapping we use that b ⊕ (b ∧ c) = b ∧ c̄ . □

Lemma 2 [SV 93] For d ∈ E the linear mapping f_{d} : E → E , f_{d}(b) = (b∧d)⊕R^{ℓ}(b) , is a permutation of E if and only if the iterates R^{ℓ·n}(d) take for each bit position the 0–bit for some n.

Let d = (d_{0}, …, d_{m−1}) ∈ E = {0, 1}^{m} and for i ∉ {0, …, m − 1} let d_{i} = d_{i(modm)}. The claim means that f_{d} is a permutation if and only if for every i there is some n with d_{i+ℓn} = 0.

Further multipermutations can be constructed by composition. The composition of a multipermutation P : E^{2} → E^{2} with arbitrary permutations σ_{1}, σ_{2} : E → E yields new multipermutations

P (σ_{1}(a), σ_{2}(b)), (σ_{1}P_{1}(a, b), σ_{2}P_{2}(a, b)) .

Also the inverse of a multipermutation is again a multipermutation.

We finally point to several useful permutations on E. We identify an integer b ∈ {0, …, 2^{m} − 1}, b = Σ_{i}b_{i}2^{i} with its binary representation (b_{0}, b_{1}, …, b_{m−1}) ∈ E.

Lemma 3 Let c ∈ {0, …, 2^{m} − 1} be odd. Then σ_{c}(a) = a · c mod 2^{m} defines a permutation σ_{c} on E.

Further permutations on E can be derived from the binary operation ∗ on E = {0, …, 2^{m} − 1}:

a ∗ b = (a′b′ mod 2^{m} + 1) mod 2^{m} ,

where a′ = 2^{m} if a = 0 and a′ = a otherwise. Lai and Massey (1990) use the operation ∗ in the case m = 16. If 2^{m} + 1 is prime e.g. for m = 8, 16 the operation ∗ is invertible. Then (E, ∗) is a cyclic group of order 2^{m} with neutral element 1. The group (E, ∗) is isomorphic to ZZ_{2^{m}+1}^{∗}, the multiplicative group of residues modulo 2^{m} + 1. We have an isomorphism φ : (E, ∗) → ZZ_{2^{m}+1}^{∗} , φ(a) = a′.

Lemma 4 If 2^{m} + 1 is prime then every c ∈ E defines a permutation a ↦ a ∗ c on E.

6 An example hash algorithm h_{4}

We propose particular boxes B_{i,j} and operations op_{i} for the hash function h_{4} of section 4. These propositions are preliminary and subject to further studies. Let E = IF^{16}, m = 16, k = 4, ℓ = 3, s = 5. The choice s = 5 maximizes the collision complexity C(4, s). This may be an overkill due to the multiple duplication of message words. One of the final 6 FFT–layers comes with the output.

INPUT M = m_{0}m_{1} ⋯ m_{n−1} ∈ E^{n} (the padded message)

FOR i = 0, …, 15 DO e_{i} := c_{i} (c_{i} is defined below)

FOR j = 0, …, ⌈n/3⌉ + 3 DO
FOR i = 0, …, 11 DO

e_{R(i)} := \{ \begin{matrix}e_{R(i)} + m_{3j+(imod3)} & for even i \\ e_{R(i)} ∗ m_{3j+(imod3)} & for odd i \end{matrix}

FOR i = 0, …, 7 DO in parallel

e_{2i} := e_{R(2i)} ⊕ e_{R(2i+1)} , e_{2i+1} := e_{R(2i)} ⊕(e_{R(2i+1)} ∧ c) ⊕ R^{2i+1}(e_{R(2i+1)}) FOR i = 0, …, 15 DO e_{i} := e_{i} ∗ c_{i}

OUTPUT h_{4}(M) := [e_{R(2i)} ∗ e_{R(2i+1)} | i = 0, …, 7]

Here + is the addition modulo 2^{16} on E ≅ {0, …, 2^{16} −1}, ∗ is the multiplication in E ≅ ZZ_{2^{16}+1}^{∗} defined in section 5, ⊕ is the bitwise XOR, ∧ is the bitwise logical AND, R is the circular right shift on E, R is the circular shift on {0, 1, …, 15} ≅ {0, 1}^{4} so that R(i) = 2i for i ≤ 7 and R(i) = 1 + 2(i − 8) for i > 7.

The constants. Let c = 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 . We define c_{0}, …, c_{15} in hexadecimal notation (c_{0}, c_{1}, c_{2}, c_{3}) := (ef01, 2345, 6789, abcd) , (c_{4}, c_{5}, c_{6}, c_{7}) := (dcba, 9876, 5432, 10fe) , c_{8+i} := c̄_{i} for i = 0, …, 7 where c̄_{i} is the bitwise logical negation of c_{i}.

The example algorithm uses multipermutations B_{i,j} that are non–linear both in E = IF^{16} , in E ≅ ZZ/2^{16}ZZ and in E ≅ ZZ_{2^{16}+1}^{∗}. We have B_{i,j}(a, b) = ( (a ⊕ b) ∗ c_{2i}, (a ⊕ (b ∧ c) ⊕ R^{2i+1}(b)) ∗ c_{2i+1} ) for j ≤ ⌈n/3⌉ + 3. The final round j = ⌈n/3⌉ + 4 is special B_{i,j}(a, b) = (a ∗ b, undef).

The sequential costs The algorithm processes 48 message bits (three words) per round performing the following operations 22 ∗, 24 ⊕, 8 ∧, 6 +, 8 R^{2i+1} . In total there are 68 operations on E per round. There are 4 additional rounds per message and 8 additional ∗ operations in the output. The number of operations on E per message bit 68/48 is smaller than for FFT–Hash II which requires 192 operations per 128 message bits.

Parallelization The degree of parallelization is 16, i.e. 16 parallel processors yield a speed up factor 16. The potential of possible speed–up’s in this design is twofold:

• If we operate on 32 words, i.e. k = 5, instead on 16 words the degree of parallelization is 32.

• If we choose for E the set of bit strings of length 32 with a suitable operation ∗ we obtain a speed–up factor 2.

It is important to analyse carefully the number of message words that can safely enter per round as we increase k . It is open whether the processing rate of three message words per round is the maximal rate for which the example algorithm is secure.

Acknowledgement We thank H. Hörner for producing the figure for the h_{k}–network. J. Massey proposed the term bipermutation.

References

[LM 91] Lai, X. and Massey, J.L.: A proposal of a new block encryption standard. Advances in Cryptology. Eurocrypt’90. Proceedings LNCS 473, pp. 389–404, Springer Verlag, Berlin, 1991.

[S 92] Schnorr, C.P.: FFT–Hash II, efficient cryptographic hashing. Proceedings EUROCRYPT’92. Springer LNCS 658 (1992), pp. 45–54.

[V 93] Vaudenay, S.: FFT–Hash II is not yet Collision–free. Advances in Cryptology, Proceedings of Crypto’92, Springer LNCS 740, (1993) pp. 587–593.

[SV 93] Schnorr, C.P. and Vaudenay, S.: Black Box Cryptanalysis of Hash Networks based on Multipermutations. Technical Report, Universität Frankfurt – ENS Paris, December 1993. Submitted to Eurocrypt’94.