©=

x(c + di + d) a + bi + b

where Ee is the set of 4-tuples (a, b, c, d) ∈ F2 [x] such that

§2

⎨ (a + b2 + ab) + (c2 + d2 + cd)x = (1 + x)e

a ≡ 1 mod x

©

b ≡ 0 mod x.

Again call the ¬rst of these equations the norm equation. We point out that

in this section, small letters a, b, c, d, i, p are polynomials in x over F2 , while

capitalized letters will be used for elements of the ¬eld F2n . By [9], corollary 5.4

and 5.7, if we restrict Ee to tuples (a, b, c, d) not divisible by (1+x), the elements

of © have a unique factorization in terms of the lifts of the graph generators:

1 1+i 11 1 i

g0 = , g1 = , g2 = .

ix 1 x1 (1 + i)x 1

Full Cryptanalysis of LPS and Morgenstern Hash Functions 271

Moreover, the “reduction modulo p” (a, b, c, d) ’ (A, B, C, D) = (a, b, c, d) mod

p gives a homomorphism from © to SL(2, F2n ):

a + bi c + di A + Bi C + Di

’ .

x(c + di + d) a + bi + b x(C + Di + D) A + Bi + B

From this it is now clear how the second and third steps of Z´mor and Tillich

e

algorithm will work for Morgenstern hashes, so we now give details for ¬rst step.

This amounts to lifting the representation problem, that is ¬nding a, b, c, d, » ∈

F2n satisfying the following conditions:

§

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

(a, b, c, d) not divisible by x+1

©

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

Write b = xpb , c = pc , d = pd for b , c , d ∈ F2 [x] and arbitrarily choose

e = 2k and a = (1 + x)k + xpm, with k ∈ Z and m ∈ F2 [x] still to be determined.

Note that such an a satis¬es a ≡ 1 mod x. The norm equation becomes

x2 p2 m2 + x2 p2 b 2 + xpb (1 + x)k + mxp + xp2 (c 2 + d 2 + c d ) = 0.

Simplifying by xp we get

xpm2 + xpb 2 + b (1 + x)k + xpm + p(c 2 + d 2 + c d ) = 0.

Reducing this equation modulo p we get b (1 + x)k + xpm ≡ 0 which implies

b = pb for some b ∈ Fp . The norm equation becomes

xpm2 + xp3 b 2

(1 + x)k + xpm + p(c 2 + d 2 + c d ) = 0.

+ pb

Simplifying again by p we get

c 2 + d 2 + c d = n(b , m, k) := xm2 + xp2 b 2

+ b (1 + x)k + b xpm.

Our approach for step 1 will be to generate random m and b (with x + 1 b )

until the equation c 2 + d 2 + c d = n(b , m, k) has solutions, then to solve this

equation for c , d . As will be clear later, the equation has a solution if and only

if all the irreducible factors of n are of even degree. So in particular

“ We will choose b = b(3) x + 1 for some b(3) ∈ F2 [x] to avoid an x factor.

“ As the term xp2 b 2 is of odd degree, we will make another term of higher

even degree, with the following strategy:

• Choose b and m randomly of degree equal to or less than R.

• Choose k = 2 deg(p) + deg(b ) + 2 + (deg(b ) + ) where = 0 if deg(b )

is even and = 1 if deg(b ) is odd.

If R is large enough we get an n with the desired property after su¬ciently many

random trials on b and m. In our implementation, we chose R = 10 which is

more than enough for 1024-bit parameters. It remains to show how to solve the

equation c 2 + d 2 + c d = n and to explain the condition on the degrees of

irreducible factors of n. We begin with the solution of the equation.

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

Solving c2 + d2 + cd = n. It is enough to have an algorithm solving it when

n is irreducible. Indeed, if c2 + d2 + c1 d1 = n1 and c2 + d2 + c2 d2 = n2 then

1 1 2 2

(c3 , d3 ) = (c1 c2 + d1 d2 , c1 d2 + c2 d1 + d1 d2 ) satis¬es c2 + d2 + c3 d3 = n1 n2 . So

3 3

suppose n is irreducible of even degree.

We describe a continued fraction algorithm for polynomials over F2 and then

we use it to solve the equation. For a fraction ξ = P where P and Q are

Q

polynomials, let P = a0 Q + r0 where deg r0 < deg Q. Let Q = a1 r0 + r1 with

deg r1 < deg r0 , then recursively for i = 2, ..., de¬ne ri’2 = ai ri’1 + ri with

deg ri < deg ri’1 . (This is the Euclidean algorithm applied to the ring F2 [x]).

De¬ne p0 = a0 , q0 = 1, p1 = a0 a1 + 1, q1 = a1 , and then recursively pi =

ai pi’1 + pi’2 and qi = ai qi’1 + qi’2 . (The fraction pi /qi is the ith truncated

continued fraction of P/Q.) We see recursively that qi pi’1 + qi’1 pi = 1, so

pi’1

pi 1

qi + qi’1 = qi’1 qi and

n

P 1

= a0 +

Q qq

i=0 i+1 i

where n is the ¬rst i such that pi /qi = P/Q. De¬ne a “norm” v on quotients of

polynomials as follows: v a = deg a ’ deg b if a, b = 0, v a = 0 if b = 0, and

b b

v a = ’∞ if a = 0. Note that v(qi+1 ) ≥ v(qi ), v(pi+1 ) ≥ v(pi ), and that

b

⎛ ⎞

n ’1 n

P 1⎠ 1

v ⎝ + a0 + ¤ ’v(qn +1 ) ’ v(qn )

=v

Q qi+1 qi qi+1 qi

i=0 i=n

As n has even degree, we can compute ± ∈ F2 [x] such that ±2 +±+1 ≡ 0 mod n

(see next paragraph). We apply a continued fraction expansion to ξ = ± and let

n

pi /qi be the successive approximations. Let j be such that

v(n)

v(qj ) ¤ ¤ v(qj+1 ).

2

We have

qj + (qj ± + pj n)2 + qj (qj ± + pj n) ≡ qj + qj ±2 + qj ± ≡ 0 mod n.

2 2 2 2

On the other hand, as

pj

¤ v(n) + v(qj ) ’ v(qj ) ’ v(qj+1 )

deg(qj ± + pj n) = v(n) + v(qj ) + v ξ +

qj

¤ v(n)/2 = deg(n)/2

we have

¡

v qj + (qj ± + pi n)2 + qi (qj ± + pj n) ¤ 2 max (deg(qj ), deg(qj ± + pj n)) ¤ deg n.

2

Consequently,

qj + (qj ± + pj n)2 + qj (qj ± + pj n) = n

2

and (c, d) = (qj , qj ± + pj n) is a solution to c2 + d2 + cd = n.

Full Cryptanalysis of LPS and Morgenstern Hash Functions 273

Solutions to ±2 + ± + 1 ≡ 0 mod n. As the map x ’ x2 + x is linear in F2 ,

solutions to this equation, if there are any, are found easily by writing down

then solving a linear system of equations. We conclude the exposition of our

algorithm by showing the following lemma.

Lemma 2. For n irreducible, ±2 + ± + 1 ≡ 0 mod n has solutions if and only if

d := deg(n) is even.

(’) Suppose ± satis¬es ±2 + ± + 1 ≡ 0 mod n. Then 1 = ± + ±2 . Squaring each

2 2 3

side we get 1 = ±2 + ±2 , then squaring again and again we get 1 = ±2 + ±2 ,...