a factorization of the identity 1 = g1 g2 ...gt with gi ∈ S and gi gi+1 = 1 for

all i ∈ {1, 2, ...t ’ 1}.

“ Preimage resistance and second preimage resistance follow from similar prob-

lems.

One proposal by Charles, Goren and Lauter [3] is to use the celebrated LPS

graphs of Lubotzky, Philips and Sarnak [7] that we now describe. Let p and l be

primes, l small and p large, both p and l equal to 1 mod 4, and l being a quadratic

residue modulo p. To l and p is associated an LPS graph Xl,p as follows. Let i

be an integer such that i2 ≡ ’1 mod p. The vertices of Xl,p are elements in the

group G = P SL(2, Fp ) (i.e. 2 — 2 matrices of square determinant, modulo the

equivalence relation M1 ∼ »M2 , » ∈ F— ). The set S is S = {gj }j=1...,l+1 , where

p

±j + iβj γj + iδj

gj = , j = 1, ..., l + 1;

’γj + iδj ±j ’ iβj

and (±j , βj , γj , δj ) are all the integer solutions of ±2 + β 2 + γ 2 + δ 2 = l, with

± > 0 and β, γ, δ even. The Cayley graph Xl,p = CG,S is undirected since S is

stable under inversion.

The choice of LPS graphs was very appealing : they are Ramanujan (i.e.,

they have optimal expansion properties asymptotically [7,6]); they have no short

cycles, and computing the resulting hash functions turned out to be quite e¬cient

compared to other provable hashes [11]. Unfortunately, it turns out that LPS

hash function is neither collision nor preimage resistant (see Sections 3 and 4

below).

For e¬ciency reasons, we recently considered the use of Morgenstern graphs to

replace LPS graphs in Charles-Goren-Lauter™s construction [11]. Morgenstern™s

Ramanujan graphs [9] generalize LPS graphs from an odd prime p ≡ 1 mod 4 to

any power of any prime q. More speci¬cally, we suggested the use of Morgenstern

graphs with q = 2k , that we now describe.

266 C. Petit, K. Lauter, and J.-J. Quisquater

Let q be a power of 2 and f (x) = x2 +x+ irreducible in Fq [x]. Let p(x) ∈ Fq [x]

be irreducible of even degree n = 2d and let Fqn be represented by Fq [x]/(p(x)).

The vertices of the Morgenstern graph “q are elements of G = P SL2 (Fqn ) (i.e.

2 — 2 matrices modulo the equivalence relation M1 ∼ »M2 , » ∈ F—n ). Let i ∈ Fqn

q

be a root of f (x). The set S is taken to be S = {gj }j=1...,q+1 , where

1 γj + δj i

gj = , j = 1, ..., q + 1;

(γj + δj i + δj )x 1

where γj , δj ∈ Fq are all the q + 1 solutions in Fq for γj + γj δj + δj = 1. The

2 2

Cayley graphs “q = CG,S are also undirected as each gj has order 2.

An interesting property of Morgenstern hashes compared to LPS hashes is

that arithmetic is done in ¬elds that are extensions of F2 rather than in ¬nite

prime ¬elds, potentially leading to faster hashes for some architectures. The

total break of LPS hashes leads to the question of whether similar attacks can

be found for Morgenstern hashes. This is indeed the case, and as an example we

give a collision-¬nding attack for q = 2 in Section 5.

3 Z´mor and Tillich Algorithm

e

As our new attacks will build upon it, we now brie¬‚y recall Z´mor and Tillich™s

e

algorithm that ¬nds collisions for LPS hashes [17]. The algorithm lifts the graph

generators and the representation problem from P SL(2, Fp ) to an appropriate

subset © of SL(2, Z[i]) (in this section and the next one, i is the complex imagi-

nary number satisfying i2 + 1 = 0 while i is a solution to i2 + 1 ≡ 0 mod p). The

relevant set is

a + bi c + di

|(a, b, c, d) ∈ Ee for some integer e > 0

©=

’c + di a ’ bi

where Ee is the set of 4-tuples (a, b, c, d) ∈ Z4 such that

§2

⎨ a + b2 + c2 + d2 = le

a > 0, a ≡ 1 mod 2

©

b ≡ c ≡ d ≡ 0 mod 2.

We will call the ¬rst of these equations describing Ee the norm equation, as

the left-hand side of this equation is the norm of the quaternion corresponding

to the quadruplet (a, b, c, d) (see [7]). The set © has two important properties:

¬rst, any element of © admits a unique factorization in terms of the lifts of the

graph generators, and second, there exists a multiplicative homomorphism from

© to P SL(2, Fp ) that allows translation of this factorization back to P SL(2, Fp).

In their exposition, Z´mor and Tillich decompose their attack into three steps.

e

The ¬rst step (lifting the decomposition problem to SL(2, Z[i])) amounts to

¬nding integers a, b, c, d and » satisfying the following conditions:

§

⎨ (a, b, c, d) ∈ Ee

(a, b, c, d) not divisible by l

©

(a, b, c, d) ≡ »(1, 0, 0, 0) mod p.

Full Cryptanalysis of LPS and Morgenstern Hash Functions 267

Putting every congruence condition into the norm equation leads to a diophan-

tine equation that was solved by Z´mor and Tillich in their paper. The second

e

step of the attack is to factorize the lifted element I of © into products of lifted

generators gj , j = 1...l+1. We know this factorization is unique and has size e, so

let us write it I = gj1 gj2 ...gje . Multiplying on the right by a lifted generator g

gives a matrix that is divisible by l if and only if g = (gje )’1 , so by trying each

of the graph generators we get the last factor, and we then proceed recursively.

The ¬nal step is to transpose the factorization of I in © into a factorization of

the identity in P SL(2, Fp ), but using the homomorphism from © to P SL(2, Fp),

this last step is trivial. For details on the attack we refer to [17].

4 Finding Preimages for LPS Hashes

M1 M2

∈ P SL(2, Fp ) which has square

Suppose we are given a matrix M =

M3 M4

determinant, and we are asked to ¬nd a preimage, that is a factorization of it

with the graph generators. By solving two linear equations in Fp we can write it

in the form

A + Bi C + Di

M= .

’C + Di A ’ Bi

Our algorithm follows along the lines of Z´mor and Tillich™s. We ¬rst lift the

e

problem from P SL(2, Fp) to the set © de¬ned above, then factorize in © and

¬nally come back to P SL(2, Fp ). The only di¬erence will be in the ¬rst step.

Lifting the representation problem now amounts to ¬nding integers a, b, c, d and

» satisfying the following conditions:

§

⎨ (a, b, c, d) ∈ Ee

(a, b, c, d) not divisible by l

©

(a, b, c, d) ≡ »(A, B, C, D) mod p.

We write a = A» + wp, b = B» + xp, c = C» + yp and d = D» + zp with

w, x, y, z ∈ Z. For convenience we choose e even, that is e = 2k for k an integer.

The norm equation becomes

(A» + wp)2 + (B» + xp)2 + (C» + yp)2 + (D» + zp)2 = l2k . (1)

In the case B = C = D = 0 the norm equation is (A» + wp)2 + (xp)2 + (yp)2 +

(zp)2 = l2k and was solved by Z´mor and Tillich as follows: choose

e

A» + wp = lk + mp2

for small m and appropriate k, hence the equation is already satis¬ed modulo p2 .

Simplifying by p2 we get a quadratic diophantine equation of type x2 + y 2 + z 2 =

m(lk ’ mp2 ) which Z´mor and Tillich show has a solution either for m = 1 or

e

for m = 2. In Equation 1, when B, C, D are non-zero we cannot divide by p2

because of the term 2p(wA + xB + yC + zD)». Since we do not, the coe¬cients

268 C. Petit, K. Lauter, and J.-J. Quisquater

of degree-2 terms are huge (at least p), and the equation is at ¬rst sight very

hard to solve.

We overcome this di¬culty with a new idea. In the remainder of this section,