LINEBURG

ñòðàíèöà 1 |

Jean-Sebastien Coron1+2 David Naccache2 Julien P. Stern3+4

1. Ecole Normale Superieure 2. Gemplus Card International

45 rue d'Ulm 34 rue Guynemer

F-75005, Paris, France Issy-les-Moulineaux, F-92447, France

fcoron,naccacheg@gemplus.com

coron@clipper.ens.fr

3. UCL Cryptography Group 4. Universite de Paris-Sud

B^timent Maxwell, place du Levant 3

a Laboratoire de Recherche en Informatique

Louvain-la-Neuve, B-1348, Belgium B^timent 490, F-91405, Orsay, France

a

stern@dice.ucl.ac.be stern@lri.fr

Abstract. This paper presents a new signature forgery strategy.

The attack is a sophisticated variant of Desmedt-Odlyzko's method 11]

where the attacker obtains the signatures of m1 ; : : : ; m ?1 and exhibits

the signature of an m which was never submitted to the signer; we

assume that all messages are padded by a redundancy function before

being signed.

Before interacting with the signer, the attacker selects smooth1 (mi )-

values and expresses (m ) as a multiplicative combination of the padded

strings (m1 ); : : : ; (m ?1 ). The signature of m is then forged using the

homomorphic property of RSA.

A padding format that di ers from iso 9796-1 by one single bit was bro-

ken experimentally (we emphasize that we could not extend our attack

to iso 9796-1); for iso 9796-2 the attack is more demanding but still

much more e cient than collision-search or factoring.

For din ni-17.4, pkcs #1 v2.0 and ssl-3.02, the attack is only theo-

retical since it only applies to speci c moduli and happens to be less

e cient than factoring; therefore, the attack does not endanger any of

these standards.

1 Introduction

At a recent count (http://www.rsa.com), over 300 million RSA-enabled prod-

ucts had been shipped worldwide. This popularity, and the ongoing standard-

izations of signature and encryption formats 2, 13, 20, 21, 22, 36] highlight

the need to challenge claims that such standards eradicate RSA's multiplicative

properties.

1 an integer is `-smooth if it has no bigger factors than `.

Exponentiation is homomorphic and RSA-based protocols are traditionally

protected against chosen-plaintext forgeries 9, 11, 35] by using a padding (or

redundancy) function to make sure that :

RSA( (x)) RSA( (y)) 6= RSA( (x y)) mod n

In general, (x) hashes x and concatenates its digest to pre-de ned strings;

in some cases, substitution and permutation are used as well.

While most padding schemes gain progressive recognition as time goes by,

several speci c results exist : a few functions were broken by ad-hoc analysis

( 16, 24] showed, for instance, that homomorphic dependencies can still appear

in (m) = a m + b) while at the other extreme, assuming that the underlying

building-blocks are ideal, some functions 5, 6] are provably secure in the random

oracle model.

The contribution of this paper is that the complexity of forging chosen

message-signature pairs is sometimes much lower than that of breaking RSA

by frontal attacks (factoring and collision-search). The strategy introduced in

this article does not challenge RSA's traditional security assumptions; instead,

it seeks for multiplicative relations using the expected smoothness of moderate-

size integers (the technique is similar in this respect to the quadratic sieve 33],

the number eld sieve 32] and the index-calculus method for computing discrete

logarithm 1]).

As usual, our playground will be a setting in which the attacker A and the

signer S interact as follows :

A asks S to provide the signatures of ? 1 chosen messages ( being

polylogarithmically-bounded in n). S will, of course, correctly pad all the plain-

texts before raising them to his secret power d.

After the query phase and some post-processing, A must exhibit the sig-

nature of at least one message (m ) which has never been submitted to S.

Previous work : Misarsky's PKC'98 invited survey 30] is probably the best

documented reference on multiplicative RSA forgeries. Davida's observation 9]

is the basis of most RSA forgery techniques. 16, 24] forge signatures that are

similar to pkcs #1 v2.0 but do not produce their necessary SHA/MD5 digests

31, 34]. 15] analyzes the security of RSA signatures in an interactive context.

Michels et al. 28] create relations between the exponents of de Jonge-Chaum

and Boyd's schemes; their technique extends to blind-RSA but does not apply

to any of the padding schemes attacked in this paper. Baudron and Stern 4]

apply lattice reduction to analyze the security of RSA in a security-proof

perspective.

A Desmedt-Odlyzko variant 11] applicable to padded RSA signatures is

sketched in section 3.5 of 30]. It consists in factoring (m ) into small primes

and obtaining the e-th roots of these primes from multiplicative combinations of

signatures of messages which (mi )-values are smooth. The signature of m is

forged by multiplying the e-th roots of the factors of (m ). The complexity of

this attack depends on the size of and not on the size of n; the approach is thus

inapplicable to padding formats having the modulus' size (e.g. iso 9796-2). In

this paper we extend this strategy to padding schemes for which a linear com-

bination of n and the padded value is small; when applied to William's scheme

our attack allows to factor n.

2 A general outline

Let fn; eg be an RSA public key and d be the corresponding secret key. Although

in this paper will alternatively denote iso 9796-2, pkcs #1 v2.0, ansi x9.31,

ssl-3.02 or an iso 9796-1 variant denoted F, we will start by describing our

attack in a simpler scenario where is SHA-1 or MD5 (in other words, messages

will only be hashed before being exponentiated); the attack will be later adapted

to the di erent padding standards mentioned above.

The outline of our idea is the following : since (m) is rather short (128 or 160

bits), the probability that (m) is `-smooth (for a reasonably small `) is small

but non-negligible; consequently, if A can obtain the signatures of chosen smooth

(mi )-values, then he could look for a message m such that (m ) has no bigger

factors than pk (the k-th prime) and construct (m )d mod n as a multiplicative

combination of the signatures of the chosen plaintexts m1 ; : : : ; m ?1.

The di culty of nding `-smooth digests is a function of ` and the size

of (m). De ning (x; y) = #fv < x, suchpthat v is y-smoothg, it is known

12, 14, 19] that, for large x, the ratio (x; t x)=x is equivalent to Dickman's

function de ned by :

8

if 0 t 1

1

>

>

<

(t) = > Zt

(v ? 1) dv if n t n + 1

(n) ?

>

:

v

n

(t) is thus an approximation of the probability that a u-bit number is 2u=t -

smooth; since (t) is somewhat cumbersome to compute, we refer the reader to

appendix A for a lookup table.

Before we proceed, let us illustrate the concerned orders of magnitude. Re-

ferring to appendix A, we see that the probability that SHA/MD5 digests are

224 -smooth is rather high (= 2?19 ; 2?13); this means that nding smooth di-

gests would be practically feasible. This was con rmed by extensive simulations

as illustrated by :

MD5(message =

30854339 successfully forged)

=

955dd317dd4715d26465081e4bfac00016

214 3 53 13 227 1499 1789 2441 4673 4691 9109 8377619

Several heuristics can, of course, accelerate the search : in our experiments, we

factored only digests beginning or ending by a few zeroes; the optimal number

of zeroes being a function of the running times of the attacker's hashing and

factorization algorithms (parallelization is also possible).

In any case, denoting by L the size of the digest and by F(L) the factoring

cost, the complexity of nding pk -smooth digests is :

CL;k = O( (L=F(L)(p )) ) = O( (L=log2 (pk ))) ) = O( (L=log2 (k ln k) )

kL kL

log2 (k ln k))

log2 k log2 (pk

this is justi ed by the fact that pk -smooth L-bit digests are expected only

once per 1= (L= log2 (pk )) and that the most straightforward way to factor L

is k trial divisions by the rst primes (where each division costs L log2 (pi ) bit-

operations).

These formulae should, however, be handled with extreme caution for the

following reasons :

Although in complexity terms L can be analyzed as a variable, one should

constantly keep in mind that L is a xed value because the output size of speci c

hash functions is not extensible.

Trial division is de nitely not the best candidate for F(L). In practice, our

program used the following strategy to detect the small factors of (m) : since

very small divisors are very common, it is worthwhile attempting trial and error

division up to pi = 2048 before applying a primality test to (m) (the candidate

is of course rejected if the test fails). As a next step, trial and error division by

primes smaller than 15; 000 is performed and the resulting number is handed-

over to Pollard-Brent's algorithm 7] which is very good at nding small factors.

Since it costs O(ppi ) to pull-out pi using Pollard-Brent's method we can further

p

bound F(L) by L pk to obtain :

p

L k ln k

CL;k = O( (L= log (k ln k)) )

2

3 The attack

The attack applies to RSA and Williams' scheme 37]; we assume that the reader

is familiar with RSA but brie y recall Williams' scheme, denoting by J(x), the

Jacobi symbol of x with respect to n.

In Williams' scheme (m) = 6 mod 16 and :

p = 3 mod 8 e=2

d = (n ? p ? q + 5)=8

q = 7 mod 8

Before signing, S must check that J( (m)) = 1. If J( (m)) = ?1, (m) is

replaced by (m)=2 to guarantee that J( (m)) = 1 since J(2) = ?1.

A signature s is valid if w = s2 mod n is such that :

8

w w = 6 mod 8

if

>

>

<

w = 3 mod 8

(m) = > 2w w if

?

>n ? w = 7 mod 8

if

2(n ? w) if

:

w = 2 mod 8

3.1 Finding homomorphic dependencies

The attack's details slightly di er between the RSA and Williams' scheme. For

RSA, ? 1 chosen signatures will yield an additional (m )d mod n while in

Williams' case, chosen signatures will factor n. All chosen messages have the

property that there exists a linear combination of (mi ) and n such that :

ai n ? bi (mi ) is pk -smooth

where bi is pk -smooth as well.

It follows that (mi ) is the modular product of small primes :

k

Yv

p mod n for 1 i

(mi ) = i;j

j

j=1

˜

Let us associate to each (mi ) a k-dimensional vector Vi with coordinates

vi;j taken modulo the public exponent e :

˜

(mi ) 7?! Vi = fvi;1 mod e; : : : ; vi;k mod eg

We can now express, by Gaussian elimination, one of these vectors (re-

˜

indexed as V ) as a linear combination of the others :

?1

˜ X i Vi mod e; with

˜ 2

V= (1)

i e

Z

Z

i=1

From equation (1) we get :

?1

X

v?

v ;j = e for all 1 j k

i i;j j

i=1

.

k

p? j :

Q

and denoting x = j

j=1

?1

Y

(m ) = x (mi ) i mod n

e

i=1

For RSA, the forger will submit the ? 1 rst messages to S and forge the

signature of m by :

?1

Y?

=x mod n

(m )d (mi )d i

i=1

In Williams' case, the signature of m will be computed from the other

signatures using equation (2) if J(x) = 1, using the fact that :

u = x2d mod n = ?x if x is a square modulo n

x if

not.

?1

Y?

=x mod n

(m )d (mi )d (2)

i

i=1

If J(x) = ?1, then u = x mod n and (u ? x)(u + x) = 0 mod n. Since

2 2

J(x) = ? J(u) we have x 6= u mod n and GCD(u ? x; n) will factor n. A can

thus submit the messages to S, recover u, factor n and sign any message.

3.2 Expected complexity

It remains, however, to estimate as a function of k :

In the most simple setting e is prime and the set of vectors with k coordi-

nates over e is a k-dimensional linear space; = k +1 vectors are consequently

Z

Z

su cient to guarantee that (at least) one of the vectors can be expressed as a

linear combination (easily found by Gaussian elimination) of the other vectors.

When e is the r-th power of a prime p, = k+1 vectors are again su cient

to ensure that (at least) one vector can be expressed as a linear combination of

the others. Using the p-adic expansion of the vectors' coe cients and Gaus-

sian elimination on k + 1 vectors, we can write one of the vectors as a linear

combination of the others.

Finally, the previous argument can be extended to the most general case :

!

Y

e= pri

i

i=1

where it appears that = 1 + !k = O(k log e) vectors are su cient to

guarantee that (at least) one vector is a linear combination of the others; modulo

each of the pri , the attacker can nd a set Ti of (! ? 1)k + 1 vectors, each of

i

which can be expressed by Gaussian elimination as a linear combination of k

other vectors. Intersecting the Ti and using Chinese remaindering, one gets that

(at least) one vector must be a linear combination of the others modulo e.

The overall complexity of our attack can therefore be bounded by :

p

CL;k = O( CL;k ) = O( (L=log e (kkln k)) )

Lk ln k

0

log2

0

and the attacker can optimize his resources by operating at a k where CL;k

is minimal.

Space complexity (dominated by the Gaussian elimination) is O(k2 log3 e).

4 Analyzing di erent signature formats

4.1 The security of iso/iec-9796-1-like signatures

iso/iec-9796-1 21] was published in 1991 by ISO as the rst international stan-

dard for digital signatures. It speci es padding formats applicable to algorithms

providing message recovery (algorithms are not explicit but map r bits to r bits).

iso 9796-1 is not hashing-based and there are apparently no attacks 16, 18]

other than factoring on this scheme ( 30] : \...iso 9796-1 remains beyond the

reach of all multiplicative attacks known today..."). The scheme is used to sign

messages of limited length and works as follows when n and m are respectively

N = 2 + 1 and -bit numbers and = 4` is a multiple of eight.

De ne by a b the concatenation of a and b, let !i be the i-th nibble of m

and denote by s(x) the hexadecimal substitution table2 :

x=0123456789ABCDEF

s(x) = E 3 5 8 9 4 2 F 0 D B 6 7 A C 1

Letting s(x) force the most signi cant bit in s(x) to 1 and s(x) complement

˜

the least signi cant bit of s(x), iso 9796-1 speci es :

(m) = s(!`?1 ) s(!`?2 ) !`?1 !`?2

˜

s(!`?3 ) s(!`?4 ) !`?3 !`?4

:::

s(!3 ) s(!2 ) !3 !2

s(!1 ) s(!0 ) !0 616

The attack that we are about to describe applies to a slight variant of iso

9796-1 where s(x) is replaced by s(x); this variant (denoted F) di ers from iso

˜

9796-1 by one single bit.

Let aj denote nibbles and consider messages of the form :

mi = a6 a5 a4 a3 a2 a1 6616

a6 a 5 a 4 a 3 a 2 a 1 6616

:::

a6 a 5 a 4 a 3 a 2 a 1 6616

which F-padding is :

(mi ) = s(a6 ) s(a5 ) a6 a5 s(a4 ) s(a3 ) a4 a3

s(a2 ) s(a1 ) a2 a1 216 216 616 616

:::

s(a6 ) s(a5 ) a6 a5 s(a4 ) s(a3 ) a4 a3

s(a2 ) s(a1 ) a2 a1 216 216 616 616

2 actually, the bits of s(x) are respectively x3 x1 x0 , x3 x2 x 0 , x3 x 2 x 1

and x2 x1 x0 but this has no importance in our analysis.

Restricting the choice of a6 to the (eight) nibbles for which s = s, we can

generate 223 numbers of the form (mi ) = x ?23 where x is the 8-byte number

s(a6 ) s(a5 ) a6 a5 s(a4 ) s(a3 ) a4 a3 s(a2 ) s(a1 ) a2 a1 226616 and :

=32?1

X

?23 = 264i

i=0

Section 3 could thus apply (treat ?23 as an extra pi ) as soon as the expecta-

tion of pk -smooth x-values reaches k + 1 :

64

k + 1 223 (3)

log2 (k ln k)

Using k = 3000 we forged thousands of 1024-bit F-signatures in less than

a day on a Pentium-PC (an example is given in appendix C). The attack is

applicable to any (64 c + 1)-bit modulus and its complexity is independent of

c 2 (once computed, the same x-strings work with any such n).

IN

# of pk -smooth x-values (amongst 223 ) forgeries

k

345 346 1

500 799 298

1000 3203 2202

1500 6198 4697

2000 9344 7343

2500 12555 10054

3000 15830 12829

Table 1. Experimental F-forgeries for 64-bit x-values, prime e.

The attack is equally applicable to 32, 48, 80, 96 or 112-bit x-strings (which

yield 7, 15, 31, 39 and 47-bit plaintext spaces); a combined attack, mixing x-

strings of di erent types is also possible (this has the drawback of adding the un-

knowns ?7 ; ?15 ; : : : but improves the probability of nding pk -smooth x-strings).

Long plain-English messages ending by the letter can be forged using a more

f

technical approach sketched in appendix B (6616 represents the ASCII charac-

ter Note, as a mere curiosity, a slight (= 11%) experimental deviation from

f).

formula (3) due to the non-uniform distribution of the x-strings (which most

and least signi cant bits can never be long sequences of zeroes). Finally, since

ñòðàíèöà 1 |

Copyright © Design by: Sunlight webdesign