( 3)

. . >>

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

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

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 (, 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
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
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 :
if 0 t 1
(t) = > Zt
(v ? 1) dv if n t n + 1
(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)

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-
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
bound F(L) by L pk to obtain :
L k ln k
CL;k = O( (L= log (k ln k)) )

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 :
w w = 6 mod 8
w = 3 mod 8
(m) = > 2w w if

>n ? w = 7 mod 8
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 :
p mod n for 1 i
(mi ) = i;j
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 :
˜ X i Vi mod e; with
˜ 2
V= (1)
i e

From equation (1) we get :
v ;j = e for all 1 j k
i i;j j
p? j :
and denoting x = j
(m ) = x (mi ) i mod n
For RSA, the forger will submit the ? 1 rst messages to S and forge the
signature of m by :
=x mod n
(m )d (mi )d i

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
=x mod n
(m )d (mi )d (2)

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

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 :
e= pri
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
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 :
CL;k = O( CL;k ) = O( (L=log e (kkln k)) )
Lk ln k
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 :
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 :
?23 = 264i
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 :
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).

# of pk -smooth x-values (amongst 223 ) forgeries
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

technical approach sketched in appendix B (6616 represents the ASCII charac-
ter Note, as a mere curiosity, a slight (= 11%) experimental deviation from

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

( 3)

. . >>

Copyright Design by: Sunlight webdesign