zero, and then we will write any matrix as a product of four diagonal matrices

and up to four graph generators. Altogether this leads to an e¬cient probabilistic

algorithm that ¬nds preimages of the LPS hash function.

Preimages for diagonal matrices. Now we show how to ¬nd a factorization of a

matrix

A + Bi

M=

A ’ Bi

such that A2 + B 2 is a square modulo p. Write y = 2y and z = 2z where y , z

are integers. We need to ¬nd integer solutions to

§

⎨ (A» + wp)2 + (B» + xp)2 + 4p2 (y 2 + z 2 ) = l2k

A» + wp ≡ 1 mod 2

©

B» + xp ≡ 0 mod 2

Fix k = logl (8p2 ) . As A2 + B 2 is a square, there are exactly two values for

» in {0, 1, ...p ’ 1} satisfying the norm equation modulo p:

(A2 + B 2 )»2 = l2k mod p.

Choose either of them, and let m := (l2k ’ (A2 + B 2 )»2 )/p. Our strategy will be

to pick random solutions to

§ 2k

⎨ l ’ (A» + wp)2 ’ (B» + xp)2 ≡ 0 mod p2

A» + wp ≡ 1 mod 2

©

B» + xp ≡ 0 mod 2

until the equation

4(y 2 + z 2 ) = n

has solutions, where

n := l2k ’ (A» + wp)2 ’ (B» + xp)2 /p2 .

A random solution to the congruence system is computed as follows: until you

get x with the correct parity, pick a random w ∈ {0, 1, ...p ’ 1} with the right

parity and compute x = 2»B ’ B w mod p. By the way k, x and w are chosen we

m A

are guaranteed that n > 0 so the equation 4(y 2 + z 2 ) = n has solution if and

only if 4 divides n and all prime factors of n congruent to 3 modulo 4 appear an

even number of times in the factorization of n. To avoid the factorization of n

in the algorithm, we will actually strengthen this condition to n being equal to

4 times a prime congruent to 1 modulo 4. When it has solutions, the equation

4(y 2 + z 2 ) = n is easily solved with the Euclidean algorithm, as recalled in

[17]. After lifting the problem to SL(2, Z[i]) the second and third steps of the

algorithm are the same as in Z´mor-Tillich algorithm. So we are done with the

e

factorization of diagonal matrices.

Full Cryptanalysis of LPS and Morgenstern Hash Functions 269

Reduction to the diagonal case. Now we show how to decompose any matrix

M ∈ P SL(2, Fp ) into a product of diagonal matrices and graph generators. We

may additionally assume that all the entries of M are nonzero: if they are not,

just multiply M by gg ’1 for some adequate g in S, and consider the factorization

of g ’1 M . We will show how to ¬nd (», ±, ω, β1 , β2 ) with the last four being

squares, such that

M1 M2 10 f1 f2 10 f1 ωf2

=» =» (2)

M3 M4 0± f3 f4 0ω ±f3 ±ωf4

and

f1 f2 12 10 12 10 12

=

’2 1 ’2 1 ’2 1

f3 f4 0 β1 0 β2

1 ’ 4β1 ’ 4β2 ’ 4β1 β2 2 ’ 8β1 + 2β2 + 2β1 β2

= .

’2 ’ 2β1 + 8β2 ’ 2β1 β2 ’4 ’ 4β1 ’ 4β2 + β1 β2

Lemma 1. Matrix equation (2) is equivalent to the following system:

§

⎪ M 2 M 3 f1 f4 ’ M 1 M 4 f2 f3 = 0

⎪

⎨

±M1 f3 ’ M3 f1 =0

(3)

⎪ ωM3 f4 ’ M4 f3 =0

⎪

©

»f1 ’ M1 =0

Proof : (’) Fourth equation is entry (1,1) of the matrix equation. Third equation

is entry (2,1) times M1 minus entry (1,1) times M3 . Second equation is entry

(1,2) times M1 minus entry (1,1) times M2 . First equation is entry (1,1) times

entry (2,2) times M2 M3 minus entry (1,2) times entry (2,1) times M1 M4 .

(⇐) Last equation is M1 = »f1 that is entry (1,1). We have M2 = MMMf1ff4f3 by

1 42

3

¬rst equation so M2 = f2 M4 f3 M11 = f2 ω» by third and fourth equation, that is

M3 f4 f

±M1 f3

entry (1,2). We have M3 = = ±»f3 by second then fourth equation, that

f1

is entry (2,1). We have M4 = ωM3 f4 by third equation, so using the already

f3

proved entry (2,1) we have M4 = ω±»f3 f4 = ωf4 ±» that is entry (2,2).

f3

In the system of equations (3), the ¬rst equation only involves β1 and β2 while

the other equations are linear once β1 and β2 are ¬xed. So we can concentrate

on solving the ¬rst equation, which is quadratic in both β1 and β2 :

M2 M3 f1 f4 ’ M1 M4 f2 f3 = 4(M2 M3 ’ M1 M4 )(’β1 + 3β1 + 4)β2

2 2

+ M2 M3 (12β1 + 49β1 + 12) + M1 M4 (’12β1 + 76β1 ’ 12) β2

2 2

+4(M2 M3 ’ M1 M4 ) 4β1 + 3β1 ’ 1 .

2

Our algorithm then proceeds as follows:

1. Pick a random β1 which is a square.

2. Compute the discriminant of the quadratic equation in β2 , β1 . If it is not a

square, go back to 1.

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

3. Solve the quadratic equation. If none of the roots is a square, go back to 1.

Else, assign a quadratic root to β2 .

4. Compute f1 , f2 , f3 , f4 .

5. Solve ±M1 f3 ’ M3 f1 = 0 to get ±. If ± is not a square, go back to 1.

6. Solve ωM3 f4 ’ M4 f3 = 0 to get ω. If ω is not a square, go back to 1.

This concludes the exposition of our algorithm.

Runtime analysis. First consider the algorithm for diagonal matrices. Assuming

n behaves “as a random number” then according to the prime number theorem

we will need O(log n) = O(log p) trials before getting one n of the correct form.

For each trial, the most expensive computation is a primality test, which can

be done in polynomial time (in our implementation, we actually use the proba-

bilistic function mpz probab prime p of GNU MP). So the algorithm for diagonal

matrices is probabilistic polynomial time. In the reduction algorithm, the proba-

bility for a random number to be a square modulo p being one half, we estimate

that a solution (», ±, ω, β1 , β2 ) with the last four being squares can be found in

about 24 trials. Consequently, the whole algorithm is probabilistic polynomial

time. Our implementation using GNU MP ¬nds preimages in less than 2 minutes

for 1024-bit parameters on an Intel Pentium M processor 1.73GHz.

5 Collisions for the Morgenstern Hash Function

Now we show how to adapt Z´mor and Tillich™s algorithm for ¬nding collisions in

e

Morgenstern hashes when q = 2. Our algorithm lifts the representation problem

from SL(2, F2n ) to a subset © of SL(2, A) where A = F2 [x, y]/(y 2 + y + 1) (in

this section, i will denote a root of i2 + i + 1 = 0 in A while i is a root of the

same equation in F2n ). The relevant set is

a + bi c + di