until 1 = ±2 + ±2 = ± + ±2 . Summing up these equations we get d = 0,

so d must be even.

2d ’1

(⇐) Now suppose d is even. Let β be a generator of F—d and let ± = β 3 .

2

Then ±3 = 1 and ± = 1 so ±2 + ± + 1 = 0.

Runtime analysis. We give some estimates for the complexity of our algorithm.

Assuming the polynomial n generated from random (b , m) behaves like random

polynomials of degree k, the number of its irreducible factors is asymptotically

K = O(log deg n) [5]. For n of degree even, we can reasonably approximate

K

the probability that all its factors are of even degree by (1/2) , hence we will

need 2K = O(log n) = O(deg p) random trials. The factorization of n can be

done in O(log2+ n) [12] and the continued fraction algorithm is of complexity

O(deg n), so the global complexity of our algorithm is probabilistic polynomial

time in deg p. Our implementation of the algorithm ¬nds collisions for 1024-bit

parameters in a few seconds on a Pentium Intel M processor 1.73GHz.

6 Discussion and Further Work

In this paper, we presented e¬cient algorithms ¬nding preimages for the LPS

hash function and collisions for the Morgenstern hash function with q = 2.

Similar algorithms with the same complexity can be derived for ¬nding preimages

for the Morgenstern hash function and for di¬erent q values. Our algorithms

build upon the Z´mor and Tillich algorithm [17] although they are not trivial

e

extensions of it.

The modi¬ed version of LPS hashes proposed by Z´mor and Tillich remains

e

unbroken so far regarding both the collision and the preimage properties, as well

as their original scheme [13] (with carefully chosen parameters) that used as

x1 x x+1

graph generators A0 = and A1 = . To avoid our new attack,

10 11

we suggest modifying the Morgenstern hash function as follows: multiply by

g0 g1 if the bit is 0 and by g0 g2 if the bit is 1. However, it is not clear what

would be the advantages of such a scheme compared to Z´mor and Tillich™s, as

e

it would not necessarily have better expansion properties, and comparing the

graph generators, it will certainly be slower.

In further work, we would like to study the applicability of our algorithm to

the Z´mor-Tillich (ZT) hash function. The Cayley graphs used in ZT hashes

e

can be naturally embedded into Morgenstern graphs, so our cryptanalysis of

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

Morgenstern hashes might actually open new perspectives on breaking the ZT

scheme. Our results may also have applications outside the cryptographic com-

munity. The preimage ¬nding algorithm actually solves the diophantine equation

(1) which at ¬rst sight seems to be a very hard problem. Our path-¬nding and

Z´mor and Tillich cycle-¬nding may improve understanding of LPS graphs when

e

considering their Ihara Zeta-function. Finally, expander graphs have numerous

applications in computer science [6], some of which could bene¬t from our new

path-¬nding algorithm.

Because of all these actual and potential applications, we stress that our

algorithms and their running time estimates still may and should be improved

in many ways. The algorithm of Section 4 gives paths of length about 8 log p

while the diameter of LPS graphs is known to be 2 log p. Choosing a smaller

k value in the algorithm will decrease this length and may also improve the

running time. Finding other decompositions with less than 4 diagonal matrices

is another interesting approach. Finally, adapting our algorithms to make them

deterministic is a particularly interesting open problem.

References

1. http://csrc.nist.gov/groups/ST/hash/documents/SHA-3 FR Notice Nov02

2007%20-%20more%20readable%20version.pdf

2. FIPS 180-2 secure hash standard

3. Charles, D.X., Goren, E.Z., Lauter, K.E.: Cryptographic hash functions from ex-

pander graphs. Journal of Cryptology (to appear)

4. Contini, S., Lenstra, A.K., Steinfeld, R.: VSH, an e¬cient and provable collision-

resistant hash function. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS,

vol. 4004, pp. 165“182. Springer, Heidelberg (2006)

5. Flajolet, P., Soria, M.: Gaussian limiting distributions for the number of compo-

nents in combinatorial structures. J. Comb. Theory Ser. A 53(2), 165“182 (1990)

6. Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull.

Amer. Math. Soc. 43, 439“561 (2006)

7. Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8, 261“

277 (1988)

8. Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: Provably secure FFT

hashing. In: NIST 2nd Cryptogaphic Hash Workshop (2006)

9. Morgenstern, M.: Existence and explicit construction of q + 1 regular Ramanujan

graphs for every prime power q. Journal of Combinatorial Theory B 62, 44“62 (1994)

10. Petit, C., Lauter, K.E., Quisquater, J.-J.: Full cryptanalysis of LPS and Morgen-

stern hash functions. Cryptology ePrint Archive, Report 2008/173 (2008),

http://eprint.iacr.org/

11. Petit, C., Lauter, K.E., Quisquater, J.-J.: Cayley hashes: A class of e¬cient graph-

based hash functions (preprint, 2007)

12. Shoup, V.: On the deterministic complexity of factoring polynomials over ¬nite

¬elds. Inf. Process. Lett. 33(5), 261“267 (1990)

13. Tillich, J.-P., Z´mor, G.: Hashing with SL2 . In: Desmedt, Y.G. (ed.) CRYPTO

e

1994. LNCS, vol. 839, pp. 40“49. Springer, Heidelberg (1994)

14. Tillich, J.-P., Z´mor, G.: Group-theoretic hash functions. In: Cohen, G., Lobstein,

e

A., Z´mor, G., Litsyn, S.N. (eds.) Algebraic Coding 1993. LNCS, vol. 781, pp.

e

90“110. Springer, Heidelberg (1994)

Full Cryptanalysis of LPS and Morgenstern Hash Functions 275

15. Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA-1. In: Shoup, V.

(ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 17“36. Springer, Heidelberg (2005)

16. Z´mor, G.: Hash functions and Cayley graphs. Des. Codes Cryptography 4(4),

e

381“394 (1994)

17. Z´mor, G., Tillich, J.-P.: Collisions for the LPS expander graph hash function. In:

e

Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965. Springer, Heidelberg (2008)

A Toy Example of the Preimage-Finding (Path-Finding)

Algorithm in the LPS Graph

As an example of our preimage algorithm, we now give a second preimage

for the message m =“This is not for NIST”, when the parameters are p =

1125899906842769 and l = 5. The ASCII code for m is 01010100 01101000

01101001 01110011 00100000 01101001 01110011 00100000 01101110 01101111

01110100 00100000 01100110 01101111 01110010 00100000 01001110 01001001

01010011 01010100 which in base 5 gives 3023231443000032312104001244030134

21040324420122212133431310442432021. We start at the identity, with gIV the

identity and g0 = M1 . We identify the six graph generators

1 ± 2i 0 1 ±2 1 2i

M±1 = , M±2 = M±3 =

0 1 “ 2i “2 1 2i 1

with their indices. The function π we choose is given in ¬gure A. The hash value

obtained is

1113908155375639 815055784352014

M= .

485525153198538 30164330826615

-3 -2 -1 1 2 3

0 -3 3 2 1 -1 -2

1 2 -3 3 2 1 -1

2 -1 -2 -3 3 2 1

3 1 -1 -2 -3 3 2

4 2 1 -1 -2 -3 3

Fig. 1. Table for the function π: the table gives the index of the next matrix for a given

current matrix and a given base 5 digit

We apply our path-¬nding algorithm on M . First, we get a matrix decom-

position as in Section 4. After 11 trials, the resulting », ±, ω, β1 and β2 values

are

» = 1051846637406052

± = 698130975272599

ω = 846326642296745

β1 = 150389273084944

β2 = 480539407839455.

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