Report 10, NTRU CryptoLab (January 1999)

29. Weimerskirch, A., Stebila, D., Shantz, S.C.: Generic GF(2) arithmetic in software

and its application to ECC. In: Safavi-Naini, R., Seberry, J. (eds.) ACISP 2003.

LNCS, vol. 2727, pp. 79“92. Springer, Heidelberg (2003)

Matrix Inversion in GF (2)[x]/(xp + 1)

A

For whatever choice of p, we work on the polynomial ring R = GF (2)[x]/(xp +1).

In any case xp + 1 is divisible by x + 1, because we are working in characteristic

2, so that the ring is not a ¬eld: it has zero divisors and non invertible elements.

If the chosen p is a power of two (p = 2a ), then x + 1 is the only prime factor

of xp + 1 ≡ (x + 1)p and, in such a case, it is very easy to check if an element in

R is not invertible. In fact, it su¬ces checking if 1 is a root, or, equivalently, if

the number of non-zero (1) coe¬cients is even.

If p is not a power of two, the invertibility check becomes more involved.

Obviously general theorems are still valid, so that we can say that a generic

element f ∈ R is invertible if and only if it is coprime with xp + 1, and a matrix

is invertible if and only if its determinant is invertible. But invertible matrices

can exist that only contain non invertible entries.

So one needs a clever algorithm to compute the inverses of the matrices, either

by computing the inverse on any sub-ring GF (2)[x]/d± where d± |xp + 1, then

combining the results with the Chinese Remainder Theorem, or by a modi¬ed

version of Gaussian inversion, exploiting Bezout™s identity to obtain a pivot on

columns without invertible elements.

Full Cryptanalysis of LPS

and Morgenstern Hash Functions

Christophe Petit1, , Kristin Lauter2 , and Jean-Jacques Quisquater1,

1

UCL Crypto Group

2

Microsoft Research

christophe.petit@uclouvain.be, klauter@microsoft.com, jjq@uclouvain.be

Abstract. Collisions in the LPS cryptographic hash function of Charles,

Goren and Lauter have been found by Z´mor and Tillich [17], but it was

e

not clear whether computing preimages was also easy for this hash func-

tion. We present a probabilistic polynomial time algorithm solving this

problem. Subsequently, we study the Morgenstern hash, an interesting

variant of LPS hash, and break this function as well. Our attacks build

upon the ideas of Z´mor and Tillich but are not straightforward exten-

e

sions of it. Finally, we discuss ¬xes for the Morgenstern hash function

and other applications of our results.

1 Introduction

Hash functions are widely used in cryptographic applications such as com-

mitment schemes, digital signatures schemes, message authentication codes or

password encryption. Typically, a hash function is required to be preimage and

collision resistant and to have nearly uniform output distribution. Due to the

importance of cryptographic hash functions, the SHA family was designed as

a NIST standard [2]. However, recently discovered vulnerabilities in SHA-1

[15] prompted NIST to launch a competition for a New Cryptographic Hash

Algorithm [1].

The NIST competition is stimulating research on hash functions in the cryp-

tographic community and a lot of new schemes have been recently designed and

put forward. Particularly appealing from a theoretical point of view, some of

these schemes are provably secure, in the sense that their security relates to

the hardness of some mathematical problem [8,4,3,13]. A good reduction to a

simply formulated mathematical challenge facilitates the evaluation process and

increases the con¬dence once the function has resisted ¬rst cryptanalytic at-

tempts. However, it also gives the cryptanalyst a clue to break the scheme, and

is especially problematic if the mathematical challenge turns out to be easy.

Research Fellow of the Belgian Fund for Scienti¬c Research (F.R.S.-FNRS). Part

of this work was done while visiting the Security and Cryptography group of the

Computer Science Department, UCSD.

Part of this work was done while visiting MIT (CSAIL-Theory of Computation).

A member of BCRYPT and ECRYPT networks.

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 263“277, 2008.

c Springer-Verlag Berlin Heidelberg 2008

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

The LPS hash function proposed by Charles, Goren and Lauter is one of these

constructions [3]. It has a particularly elegant design, as the hash computation

can be interpreted as a random walk in the optimal expander graphs of Lubotzky,

Philips and Sarnak [7]. Finding collisions for this function is ¬nding cycles in the

graphs, which also amounts to ¬nding a non-trivial factorization of the identity in

terms of some particular elements of a projective group of matrices (a problem

we will call the decomposition problem). Charles, Goren and Lauter proposed

this problem as potentially hard. A major step in the breaking of the LPS hash

function has recently been performed by Z´mor and Tillich [17] who produced

e

collisions by actually solving this problem.

One of the main contributions of this paper is an e¬cient algorithm that

¬nds preimages for the LPS hash function. As Z´mor and Tillich did, we actu-

e

ally solve the underlying problem which was presumed hard. Both for e¬ciency

considerations and because of these new attacks, it also seemed worth studying

the Morgenstern hash function, an interesting variant of the LPS hash relying

on di¬erent graphs. A second main contribution of this paper is to adapt the

Z´mor and Tillich attack to Morgenstern hashes, and as an example we give an

e

e¬cient collision ¬nding algorithm. Combining the ideas of our two algorithms

also gives a preimage ¬nding algorithm for Morgenstern hashes that we do not

present here due to space limitations.

The paper is organized as follows: in Section 2 we describe the LPS and Mor-

genstern hash functions; in Section 3 we recall the Z´mor and Tillich algorithm;

e

Section 4 presents our preimage algorithm for LPS hashes; in Section 5 we adapt

Z´mor and Tillich™s algorithm to Morgenstern hashes and in Section 6 we dis-

e

cuss ¬xes for LPS and Morgenstern hashes, as well as potential applications of

our results. In the appendix we give toy examples of our algorithms (1024’bit

examples are given in the full version of this paper [10]).

2 LPS and Morgenstern Hash Functions

A Cayley graph CG,S = (V, E) is a graph constructed from a group G and a

subset S of G as follows: V contains a vertex vg associated to each element

g ∈ G, and E contains the directed edge (vg1 , vg2 ) i¬ there is some s ∈ S such

that g2 = g1 s. The elements of S are called the graph generators. The graph

CG,S is |S|-regular; it is connected i¬ S generates G; it is undirected i¬ S = S ’1 .

A general construction for a cryptographic hash function from a Cayley graph

was introduced by Z´mor and Tillich [16,13,14] in the directed case and by

e

Charles, Goren and Lauter [3] in the undirected case. In this paper, we focus on

two instances of the undirected graph construction, which we now recall following

mainly the description given in [17].

Let a := |S| ’ 1. We will de¬ne a function π which orders the set of generators

(minus one generator to avoid back-tracking). Fix a function π : {0, 1...a ’ 1} —

S ’ S such that for any g ∈ S the set π({0, 1...a’1}—{g}) is equal to S \{g ’1}.

Let g0 and gIV be arbitrary ¬xed elements of S and G respectively. The input

message is converted to a base a number x1 ...xk and the elements gi = π(xi , gi’1 )

Full Cryptanalysis of LPS and Morgenstern Hash Functions 265

are computed recursively. The hashcode of the input message is the product of

group elements H(x) = gIV g1 ...gk .

We will call hash functions constructed following this design strategy Cayley

hashes. These hash functions have some very interesting properties:

“ The girth of the Cayley graph is the length of the smallest cycle, and no two

distinct messages of the same length can collide if their length is less than

half the girth.

“ If the chosen graphs are good expanders (see [6] for precise de¬nitions and

applications), the outputs tend to be uniformly distributed, and the conver-

gence to the uniform distribution is fast.

“ Di¬erential cryptanalysis (DC), which has been the most successful approach

against SHA-1, does not seem to apply to Cayley hashes. Indeed, DC typi-

cally activates various portions of the message simultaneously, while in Cay-

ley hashes the bits (or k-its) are processed one at the time.

“ Collision resistance is equivalent to the hardness of a simply-stated represen-