ON THE SECURITY OF RSA PADDING

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

1. E cole Normale Superieure 2. Gemplus Card International
45 rue d'Ulm 34 rue Guynemer
F-75005, Paris, France Issy-les-Moulineaux, F-92447, France
coron@[Link] fcoron,naccacheg@[Link]
3. UCL Cryptography Group 4. Universite de Paris-Sud
B^atiment Maxwell, place du Levant 3 Laboratoire de Recherche en Informatique
Louvain-la-Neuve, B-1348, Belgium B^atiment 490, F-91405, Orsay, France
stern@[Link] stern@[Link]

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 ecient 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
ecient than factoring; therefore, the attack does not endanger any of
these standards.

1 Introduction
At a recent count ([Link] 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 diculty 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
>
>
<
1 if 0  t  1
(t) = > Z t
(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=Flog
(L) kL log2 (pk ) kL log2 (k ln k)
(p )) ) = O( (L= log (p )) ) = O( (L= log (k ln k)) )
2 k 2 k 2

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(pppi ) to pull-out pi using Pollard-Brent's method we can further
bound F (L) by L pk to obtain :
p
CL;k = O( (L=Llogk (lnk kln 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
q = 7 mod 8 d = (n ? p ? q + 5)=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 >
>
<
if w = 6 mod 8
(m) = > 2nw? w
? if
if
w = 3 mod 8
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 :
Y k
(mi ) = vi;j
p
j mod n for 1  i  
j =1

Let us associate to each (mi ) a k-dimensional vector V~i with coordinates

vi;j taken modulo the public exponent e :
(mi ) 7?! V~i = 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  ?1
V~ = ~i mod e; with
iV i 2 e
Z
Z (1)
i=1
From equation (1) we get :
?1
X
v;j = v ? j  e for all 1  j  k
i i;j
i=1
.
k
p?j j :
Q
and denoting x =
j =1
?1
Y
(m ) = xe  (mi ) i mod n
i=1
For RSA, the forger will submit the  ? 1 rst messages to S and forge the
signature of m by :
 ?1 ?
Y

(m )d = x  (mi )d i
mod n
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 = x mod n = ?xx ifif xnot.
2d is a square modulo n
?1 ?
Y

(m )d = x  (mi )d i
mod n (2)
i=1
If J(x) = ?1, then u2 = x2 mod n and (u ? x)(u + x) = 0 mod n. Since
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

sucient 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 sucient
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' coecients 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 sucient to
guarantee that (at least) one vector is a linear combination of the others; modulo
each of the pri i , 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 :
p
C0 Lk log e k ln k
L;k = O(CL;k ) = O( (L= log (k ln k )) )
2
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
a5
a4
a3
a2
a1
6616

:::
a6
a5
a4
a3
a2
a1
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  x0 , x3  x2  x1
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 :
 
k + 1  223   log (64 (3)
2 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

k # 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
f

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

ter ). Note, as a mere curiosity, a slight (
f = 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
the powers of 2 and ?23 are identical, one can use k chosen messages instead of
k + 1, packing p1 = 2 and pk+1 = ?23 into the updated unknown p1 = 2?23 .
Non-impact on iso 9796-1 : The authors could not extend the attack to
iso 9796-1 and it would be wrong to state that iso 9796-1 is broken.
Note : When we rst looked into the standard, we did not notice s~ and we
are grateful to Peter Landrock and Jrgen Brandt for drawing our attention to
that. It appears from our discussions with iso/jtc1/sc27 that s~ (the alteration
that codes the message-border) has also been introduced to prevent arithmetic
operations on (m); further information on iso 9796-1 and our attack on F will
be soon posted on [Link]
4.2 The security of iso 9796-2 signatures
iso 9796-2 is a generic padding standard allowing total or partial message re-
covery. Hash-functions of di erent sizes are acceptable and parameter L (in the
standard kh ) is consequently a variable. Section 5, note 4 of [22] recommends
64  L  80 for total recovery (typically an iso 10118-2 [23]) and 128  L  160
for partial recovery.

Partial message recovery. For simplicity, assume that N , L and the size of
m are all multiples of eight and that the hash function is known to both parties.
The message m = m[1]
m[2] is separated into two parts where m[1] consists of
the N ? L ? 16 most signi cant bits of m and m[2] of all the remaining bits of
m. The padding function is :
(m) = 6A16
m[1]
HASH(m)
BC16
and m[2] is transmitted in clear.
Dividing (6A16 + 1)  2N by n we obtain :
(6A16 + 1)  2N = i  n + r with r < n < 2N

n0 = i  n = 6A16  2N + (2N ? r) = 6A16
n0 [1]
n0 [0]

where n0 is N + 7 bits long and n0 [1] is N ? L ? 16 bits long.
Setting m[1] = n0 [1] we get :
t = i  n ? (m)  28 = n0 [0] ? HASH(m)
BC0016
where the size of t is less than L + 16 bits.
The forger can thus modify m[2] (and therefore HASH(m)) until he gets a
set of messages which t-values are pk -smooth and express one such (m ) as a
multiplicative combination of the others.
Note that the attack is again independent of the size of n (forging 1024-bit
signatures is not harder than forging 512-bit ones) but, unlike our F -attack,
forged messages are speci c to a given n and can not be recycled when attacking
di erent moduli.
To optimize e orts, A must use the k minimizing CL0 +16;k .
Although the optimal time complexities for L = 160 and L = 128 are lower
than the birthday complexities of SHA and MD5 we consider that L = 160
implementations are still reasonably secure.
L = kh optimal log2 k log2 time log2 space
128 18 54 36
160 20 61 40
Table 2. Attacks on iso 9796-2, small public exponent.
Total message recovery. Assuming again that the hash function is known
to both parties, that N and L are multiples of eight and that the size of m is
N ? L ? 16, function  is :
(m) = 4A16
m
HASH(m)
BC16
Let us separate m = m[1]
m[0] into two parts where m[0] consists of the `
least signi cant bits of m and m[1] of all the remaining bits of m and compute,
as in the previous case, an i such that :
n0 = i  n = 4A16
n0 [1]
n0 [0]
where n0 [0] is (L + ` + 16)-bits long and n0 [1]
n0 [0] is N -bits long.
Setting m[1] = n0 [1] we get :
t = i  n ? (m)  28 = n0 [0] ? m[0]
HASH(m)
BC0016
where the size of t is less than L + ` + 16 bits.
A will thus modify m[0] (and therefore HASH(m)) as needed and conclude
the attack as in the partial recovery case. ` must be tuned to expect just enough
pk -smooth t-values with a reasonably high probability i.e. :
 
L + ` + 16
k    log
2`
2 (k ln k )

The complexities summarized in the following table (a few PC-weeks for

kh = 64) seem to suggest a revision of this standard.
L = kh optimal log2 k log2 time log2 space `
64 15 47 30 32
80 17 51 34 34
Table 2 (continued) Attacks on iso 9796-2, small public exponent.
Note that our attack would have applied as well to :
(m) = 4A16
HASH(m)
m
BC16
In which case take n0 = i  n such that n0 mod 256 = BC16 and use m to
replicate the least signi cant bits of n0 ; subtraction will then yield a moderate
size integer times of a power of two.
An elegant protection against our attack is described in [13] (its security is
basically comparable to that of pkcs #1 v2.0, discussed later on in this paper);
a second ecient solution, suggested by Jean-Jacques Quisquater in the rump
session of crypto'97 is :
(m) = 4A16
(m  HASH(m))
HASH(m)
BC16
4.3 Analyzing pkcs #1 v2.0, ssl-3.02 and ansi x9.31
This section describes theoretical attacks on pkcs #1 v2.0, ssl-3.02 and ansi
x9.31 which are better than the birthday-paradox. Since our observations are
not general (for they apply to moduli of the form n = 2k  c) and more demand-
ing than factorization, they do not endanger current implementations of these
standards. It appears that n = 2k  c o ers regular 1024-bit RSA security as far
as c is not much smaller than 2500 , and square-free c-values as small as 400 bits
may even be used [25]. In general (n > 2512) such moduli appear to o er regular
security as long as log2 (c) 
= log2 (n)=2 and c is square-free [26].
Although particular, n = 2k  c has been advocated by a number of cryp-
tographers for it allows trial and error divisions to be avoided. For instance,
the informative annex of iso 9796-1 recommends \...some forms of the modulus
(n = 2k  c) [that] simplify the modulo reduction and need less table storage.".
Note however, that even in our worst scenario, iso 9796-1's particular form is
still secure : for 1024-bit moduli, iso 9796-1 recommends a 767-bit c whereas
our attack will require a 400-bit c. The reader is referred to section 14.3.4 of [27]
for further references on n = 2k  c.
Assume that we are given a 1024-bit n = 2k ? c, where ` = log2 (c)  = 400
and c is square-free; we start by analyzing ssl-3.02 where :
(m) = 000116
FFFF16 : : : FFFF16
0016
SHA(m)
MD5(m)
n ? 2  (m) is an `-bit number on which we conduct an iso 9796-2-like
15

attack which expected complexity is C 0̀;k .

The characteristics of the attack are summarized in table 3 which should be
compared to the birthday paradox (2144 time, negligible space) and the hardness
of factorization (ftime, spaceg denote the base-two logarithms of the time and
space complexities of the attacks) :
log2 n ` optimal log2 k our attack factorization
606 303 28 f84, 56g f68, 41g
640 320 29 f87, 58g f70, 42g
768 384 33 f97, 66g f75, 45g
1024 400 34 f99, 68g f86, 50g
1024 512 39 f115, 78g f86, 50g
Table 3. Estimates for ssl 3.02, small public exponent.
The phenomenon also scales-down to pkcs #1 v2.0 where :
(m) = 000116
FFFF16 : : : FFFF16
0016
cSHA
SHA(m)
(m) = 000116
FFFF16 : : : FFFF16
0016
cMD5
MD5(m)
cSHA = 3021300906052B0E03021A0500041416
cMD5 = 3020300C06082A864886F70D02050500041016
and :
 log2 n ` optimal log2 k our attack factorization
512 256 23 f77, 46g f64, 39g
548 274 27 f80, 54g f66, 40g
Table 4. Estimates for pkcs #1 v2.0 and ansi x9.31, small public exponent.
These gures appear roughly equivalent to a birthday-attack on SHA, even
for rather small (550-bit) moduli. Note that the attack applies to n = 2k + c by
computing n ? 214  (m).
Note : In a recent correspondence, Burt Kaliski informed us that Ron Rivest
developed in 1991 a forgery strategy which is a simple case of the one described
in this paper; the design of pkcs #1 v1.5 took this into account, but Ron's
observation was never published. Further information on our attack will appear
soon in an RSA bulletin [Link]
A similar analysis where the prescribed moduli begin by 6BBBBB : : :16 is ap-
plicable to ansi x9.31 (yielding exactly the same complexities as for pkcs #1
v2.0) where :
(m) = 6B16
BBBB16 : : : BBBB16
BA16
SHA(m)
33CC16
ansi x9.31 recommends to avoid n = 2k  c. If one strictly follows the
standard n = 6BBBBB : : :16 can not occur (the standard requires a bit length
which is a multiple of eight) but one could in theory work with 2(m) instead
of (m).
Finally, we will consider a theoretical setting in which an authority certi es
moduli generated by users who wish to join a network; naturally, users never re-
veal their secret keys but using storage optimizations as a pretext, the authority
implements an ID-based scheme where di erent random looking bits (registra-
tion ID, account numbers etc) are forced into the most signi cant bits of each n
[26]. Users generate moduli having the prescribed patterns they receive.
If the authority can nd two small constants fu; vg such that :
log2 (u  n ? v  (m))  =  for a moderate  (4)
then our attack would extend to moduli which are not necessarily of the
form 2k  c. To do so, oversimplify the setting to (m) = (2w ? 1)
f (m) and
n = n[1]
n[0] where n[0] has the size of f (m) and substitute these de nitions in
equation (4) :
log2 (u  (n[1]
n[0]) ? v  ((2w ? 1)
f (m))) 
=
since the authority has no control over f (m), the best thing to do would be
to request that u  n[1] = v  (2w ? 1) which results in an   = log2 (f (m)) +
log2 (maxfu; vg).
The authority can thus prescribe moduli which most signi cant bits are vi 
(2w ? 1)=ui where ui are moderate-size factors of 2w ? 1. Such factors look
random and should not raise the user's suspicion.
 We can therefore conclude that although practically safe, the use of authority-
speci ed moduli in xed-pattern padding contexts might be an interesting the-
oretical playground.

5 Conclusion and further research

Although the analysis presented in this paper indicates a weakness in iso 9796-
2 when kh = 64, products using this standard should not be systematically with-
drawn; a few product analyzes reveal that system-level speci cations (message
contents, insucient access to S etc.) frequently make real-life attacks harder
than expected.
It seems reasonable (although we can not base our belief on formal grounds)
that good message recovery padding schemes should be usable for encryption
as well; we motivate this recommendation by the functional similarity between
RSA encryption and message recovery.
Full-domain-hash o ers the best possible protection against our attack and
we advocate its systematic use whenever possible. If impossible, it seems appro-
priate to link L and N since for a xed L there is necessarily a point (birthday)
above which increasing N will slow-down the legitimate parties without improv-
ing security.
We also recommend four research directions :
 An integer is fa; pk g-semismooth [3] if each of its prime factors is smaller
than a and all but one are smaller than pk . A well known-strategy (called the
large prime variant) consists of searching, using the birthday paradox, fa; pk g-
semismooth f(x); (y)g pairs having an identical large prime factor (e.g. 80-bits
long); the ratio (x)=(y) mod n can then be used as one pk -smooth input in
the Gaussian elimination.
 It might be interesting to nd out if our F -attack could handle s~ by using
a di erent ? :

? =

00000000000116
00000000000116


00000000000116

In which case x-values should end by the pattern 226616 , be pk -smooth and
such that x0 = x=
is a valid message header. Note that di erent
-values might
be mixed in the same attack, using a large prime variant where the di erent ? -
values are eliminated by modular division.
 Although we have no speci c instances for the moment, one could also try
to combine our technique with [4] to speed-up forgery in speci c situations.
 Finally, it appears that incomplete ad-hoc analyzes of hash-functions (build-
ing digests with u prescribed bits in less than 2u operations) could be the source
of new problems in badly designed padding schemes.
6 Acknowledgements
We are grateful to Arjen Lenstra, Pascal Paillier and Michael Tunstall for their
helpful comments, the authors also thank Pascal Autissier, Christophe Clavier,
Renato Menicocci and Phong N'guyen for their insights into several mathemat-
ical details. Last but not least, we express our recognition to Burt Kaliski, Bart
Preneel and Jean-Jacques Quisquater for their help.

References
1. L. Adleman, A subexponential algorithm for the discrete logarithm prob-
lem with applications to cryptography, Proceedings of the IEEE 20-th
Annual symposium on the foundations of computer science, pp. 55-60,
1979.
2. ANSI X9.31, Digital signatures using reversible public-key cryptography
for the nancial services industry (rDSA), 1998.
3. E. Bach and R. Peralta, Asymptotic semismoothness probabilities, Math-
ematics of computation, vol. 65, no. 216, pp. 1701{1715, 1996.
4. O. Baudron and J. Stern, To pad or not to pad : does formatting degrade
security ?, 1999 RSA Data Security Conference proceeding book, 1999.
5. M. Bellare and P. Rogaway, Random oracles are practical : a paradigm for
designing ecient protocols, Proceedings of the rst annual conference on
computer and communication security, acm, 1993.
6. M. Bellare and P. Rogaway, The exact security of digital signatures : how
to sign with RSA and Rabin, Advances in cryptology eurocrypt'96,
Springer-Verlag, Lectures notes in computer science 1070, pp. 399{416,
1996.
7. R. Brent, An improved Monte Carlo factorization algorithm, Nordisk Tid-
skrift for Informationsbehandling (bit) vol. 20, pp. 176{184, 1980.
8. N. de Bruijn, On the number of positive integers  x and free of prime
factors  y, Indagationes Mathematicae, vol. 13, pp. 50{60, 1951. (cf. as
well to part II, vol. 28, pp. 236{247, 1966.).
9. G. Davida, Chosen signature cryptanalysis of the RSA (MIT) public-key
cryptosystem, TR-CS-82-2, Department of electrical engineering and com-
puter science, University of Wisconsin, Milwaukee, 1982.
10. D. Denning, Digital signatures with RSA and other public-key cryptosys-
tems, Communications of the ACM, vol. 27-4, pp. 388{392, 1984.
11. Y. Desmedt and A. Odlyzko. A chosen text attack on the RSA cryp-
tosystem and some discrete logarithm schemes, Advances in cryptology
crypto'85, Springer-Verlag, Lectures notes in computer science 218, pp.
516{522, 1986.
12. K. Dickman, On the frequency of numbers containing prime factors of a
certain relative magnitude, Arkiv for matematik, astronomi och fysik, vol.
22A, no. 10, pp. 1{14, 1930.
13. DIN NI-17.4, Speci cation of chipcard interface with digital signature ap-
plication/function according to SigG and SigV, version 1.0, 1998.
14. J. Dixon, Asymptotically fast factorization of integers, Mathematics of
computation, vol. 36, no. 153, pp. 255{260, 1981.
15. J. Evertse and E. van Heyst, Which new RSA-signatures can be computed
from certain given RSA signatures ?, Journal of cryptology vol. 5, no. 1,
41{52, 1992.
16. M. Girault, J.-F. Misarsky, Selective forgery of RSA signatures using re-
dundancy, Advances in cryptology eurocrypt'97, Springer-Verlag, Lec-
tures notes in computer science 1233, pp. 495{507, 1997.
17. J. Gordon, How to forge RSA key certi cates, Electronic Letters, vol. 21,
no. 9, April 25-th, 1985.
18. L. Guillou, J.-J. Quisquater, M. Walker, P. Landrock and C. Shaer, Pre-
cautions taken against various attacks in iso/iec dis 9796, Advances in
cryptology eurocrypt'90, Springer-Verlag, Lectures notes in computer
science 473, pp. 465{473, 1991.
19. H. Halberstam, On integers whose prime factors are small, Proceedings of
the London mathematical society, vol. 3, no. 21, pp. 102{107, 1970.
20. K. Hickman, The SSL Protocol, December 1995. Available electronically
at : [Link]
21. ISO/IEC 9796, Information technology - Security techniques - Digital sig-
nature scheme giving message recovery, Part 1 : Mechanisms using redun-
dancy, 1999.
22. ISO/IEC 9796-2, Information technology - Security techniques - Digital
signature scheme giving message recovery, Part 2 : Mechanisms using a
hash-function, 1997.
23. ISO/IEC 10118-2, Information technology - Security techniques - Hash-
functions; Part 2 : Hash functions using an n-bit block-cipher algorithm,
1994.
24. W. de Jonge and D. Chaum. Attacks on some RSA signatures, Advances
in cryptology crypto'85, Springer-Verlag, Lectures notes in computer sci-
ence 218, pp. 18{27, 1986.
25. A. Lenstra, Generating RSA moduli with a predetermined portion, Ad-
vances in cryptology asiacrypt'98, Springer-Verlag, Lectures notes in
computer science 1514, pp. 1{10, 1998.
26. A. Lenstra, de auditu, January 1999.
27. A. Menezes, P. van Oorschot and S. Vanstone, Handbook of applied cryp-
tography, crc Press.
28. M. Michels, M. Stadler and H.-M. Sun, On the security of some variants
of the RSA signature scheme, Computer security-esorics'98, Springer-
Verlag, Lectures notes in computer science 1485, pp. 85{96, 1998.
29. J.-F. Misarsky, A multiplicative attack using LLL algorithm on RSA sig-
natures with redundancy, Advances in cryptology crypto'97, Springer-
Verlag, Lectures notes in computer science 1294, pp. 221{234, 1997.
 30. J.-F. Misarsky, How (not) to design RSA signature schemes, Public-key
cryptography, Springer-Verlag, Lectures notes in computer science 1431,
pp. 14{28, 1998.
31. National Institute of Standards and Technology, Secure hash standard,
FIPS publication 180-1, April 1994.
32. J. Pollard, Factoring with cubic integers, The development of the number
eld sieve, Springer-Verlag, Lectures notes in computer science 1554, pp.
4{10, 1993.
33. C. Pomerance, The quadratic sieve factoring algorithm, Advances in cryp-
tology eurocrypt'84, Springer-Verlag, Lectures notes in computer science
209, pp. 169{182, 1985.
34. R. Rivest, RFC 1321 : The MD5 message-digest algorithm, Internet activ-
ities board, April 1992.
35. R. Rivest, A. Shamir and L. Adleman, A method for obtaining digital sig-
natures and public-key cryptosystems, Communications of the ACM, vol.
21-2, pp. 120{126, 1978.
36. RSA Laboratories, pkcs #1 : RSA cryptography speci cations, version
2.0, September 1998.
37. H. Williams, A modi cation of the RSA public key encryption procedure,
IEEE TIT, vol. 26, pp. 726{729, 1980.

APPENDIX A
The following (redundant) look-up table lists  for the various smoothness
and digest-size values concerned by this paper; (136=24), the probability that
a 136-bit number has no prime factors larger than 224 is 2?14:2 :
? log2 & 16 20 24 28 32 36 40 44 48 52 56 60 64 68 72
32 1.7 0.9 0.5 0.2 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
48 4.4 2.7 1.7 1.1 0.8 0.5 0.3 0.1 0.0 0.0 0.0 0.0 0.0 0.0 0.0
64 7.7 5.0 3.4 2.4 1.7 1.2 0.9 0.7 0.5 0.3 0.2 0.0 0.0 0.0 0.0
80 11.5 7.7 5.4 3.9 2.9 2.2 1.7 1.3 1.0 0.8 0.6 0.5 0.4 0.3 0.2
96 15.6 10.7 7.7 5.7 4.4 3.4 2.7 2.1 1.7 1.4 1.1 0.9 0.8 0.6 0.5
112 20.1 13.9 10.2 7.7 5.9 4.7 3.8 3.1 2.5 2.1 1.7 1.4 1.2 1.0 0.8
128 24.9 17.4 12.8 9.8 7.7 6.1 5.0 4.1 3.4 2.8 2.4 2.0 1.7 1.4 1.2
136 27.4 19.2 14.2 10.9 8.6 6.9 5.6 4.6 3.9 3.2 2.8 2.3 2.0 1.7 1.5
144 29.9 21.1 15.6 12.0 9.5 7.7 6.3 5.2 4.4 3.7 3.1 2.7 2.3 2.0 1.7
152 32.4 22.9 17.1 13.2 10.5 8.5 7.0 5.8 4.9 4.1 3.5 3.0 2.6 2.3 2.0
160 35.1 24.9 18.6 14.4 11.5 9.3 7.7 6.4 5.4 4.6 3.9 3.4 2.9 2.6 2.2
168 37.9 26.9 20.1 15.6 12.5 10.2 8.4 7.0 5.9 5.1 4.4 3.8 3.3 2.9 2.5
176 40.6 28.9 21.7 16.9 13.5 11.0 9.1 7.7 6.5 5.6 4.8 4.2 3.6 3.2 2.8
400 129. 95.2 73.9 59.2 49.0 41.5 35.1 30.2 26.5 23.1 20.8 18.5 16.7 15.1 13.7
512 179. 133 104 84.0 69.8 59.0 50.8 44.0 38.8 34.1 30.6 27.2 24.9 22.5 20.6

The table uses the exact formula (section 2) for t  10 and de Bruijn's
approximation [8] for t > 10 :
Z 
 (2t)?1=2 exp ? t + es ? 1 ds
 
(t) = s
0
where  is the positive solution of e ? 1 = t and is Euler's constant.
 APPENDIX B
The attack's time-consuming part is the exhaustive-search of k appropriate x-
strings; therefore, when one wants the x-strings to be 256-bits long, the increase
in k makes the attack impractical.
To overcome this problem, we suggest the following : as a rst step, col-
lect the signatures corresponding to moderate-size pk -smooth x-strings (which
are relatively easy to nd) and extract from their appropriate multiplicative
combinations the e-th roots of the k rst primes. Then, exhaustive-search two
plain-English 128-bit messages fm; m0 g ending by the letter such that (m)=?
f

and (m0 )=? are both pk -smooth, with :

? = 2256(c?1) + : : : + 2256 + 1
for a (256  c + 1)-bit modulus. Since we only need two such numbers, the
overall workload is very tolerable. Next, submit m to S and divide its signature
by the e-th roots of its small prime factors to recover ? d mod n. Using ? d mod n
and the e-th roots of the k rst primes we can now forge, by multiplication, the
signature of m0 .
APPENDIX C
This appendix contains an F forgery that works with any 1025-bit modulus;
to t into the appendix, the example was computed for e = 3 but forgeries for
other public exponents are as easy to obtain.
step 1 : Select any 1025-bit RSA modulus, generate d = 3?1 mod (n), let
 = F and form the 180 messages :
11
X
mi = (256  message[i]16 + 102)  232j
j =0
where message[i] denotes the elements of the following table :
00014E 008C87 00D1E8 01364B 0194D8 01C764 021864 03442F 0399FB 048D9E 073284 0863DE 09CCE8
0A132E 0A2143 0BD886 0C364A 0C368C 0C6BCF 0D3AC1 0D5C02 0EA131 0F3D68 0F9931 31826A 31BE81
31ED6B 31FCD0 320B25 32B659 332D04 3334D8 33EAFC 33EB1D 343B49 353D02 35454C 35A1A9 36189E
362C79 365174 3743AB 3765F6 37C1E2 3924AC 3998A8 3AF8A7 3B6900 3B9EEB 3BC1FF 3DE2DE 3E51BE
3E8191 3F49F3 3F69AC 4099D9 40BF29 41C36C 41D8C0 424EE8 435DB7 446DC1 4499CC 44AA20 44EE53
4510E8 459041 45A464 45AA03 460B80 4771E7 486B6A 499D40 4A5CF8 4AC449 4ADA0A 4B87A8 4C06A1
4C5C17 4D4685 4E39EA 4EB6B6 4F8464 716729 71C7D3 71FA22 722209 72DBF1 7619AB 765082 767C39
76885C 78F5F3 79E412 79FAD6 7CD0ED 7D0ABA 7DBA1D 7DE6A5 7E06A2 7EA5F2 7EC1ED 7EEC78 90BB4B
90DE38 9139D7 934C2C 9366C5 941809 941BFB 947EB4 94DB29 952D45 9745BD 978897 97A589 9827AF
984FAC 9A193D 9A83E2 9B74E3 9BEAE9 9C704F 9DBA98 9F9337 A00D15 A02E3D A10370 A429A6 A4DADD
A4F689 A5485D A6D728 A76B0F A7B249 A87DF3 A95438 A96AA4 AB1A82 AD06A8 AEA0D0 AEB113 D076C5
D13F0E D18262 D1B0A7 D35504 D3D9D4 D3DEE4 D4F71B D91C0B D96865 DA3F44 DB76A8 DE2528 DE31DD
DE46B8 DE687D DEB8C8 DF24C3 DFDFCF DFF19A E12FAA E1DD15 E27EC1 E39C56 E40007 E58CC8 E63CE0
E6596C E7831E E796FB E7E80C E85927 E89243 E912B4 E9BFFF EA0DFC EACF65 EB29FA
 step 2 : construct the message m0 = EE7E8E6616  Pj 2 j and obtain 11
=0
32

from the signer the 180 signatures si = (mi )d mod n.

step 3 : the signature of m0 is :
(m0 )d = p?gamma[i] sbeta[i] mod n
Y Y 345 180

i i
i=0 i=1
where pi denotes the i-th prime (with p0 = ?23 ) and beta[i] denotes the
elements of the following table :
1 2 1 2 2 2 2 1 2 2 2 1 1 2 2 2 1 1 2 1 2 2 2 2 2 1 1 2 1 1 2 1 1 2 1 1
1 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 2 1 1 2 1 2 1 1 2 2 1 1 1 1 2 1 1 2 1
1 1 1 1 2 2 1 2 1 2 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 2
1 1 1 2 2 2 2 1 2 2 1 1 2 2 2 2 1 1 2 1 2 2 2 2 1 1 1 2 1 1 2 1 1 1 1 2
2 1 1 1 1 2 2 1 2 2 1 1 2 2 2 1 2 1 2 2 2 1 2 1 2 2 1 2 1 2 2 1 1 2 1 1

gamma[ ] i represents the hexadecimal values :

57 57 68 33 27 18 16 13 10 0F 0E 0B 09 09 0D 05 0B 07 04 08 07 07 07 09 0A 03 07
04 05 05 03 04 03 01 02 03 04 03 01 03 03 03 02 06 03 03 04 06 02 04 04 02 02 03
02 04 04 03 04 01 04 03 02 03 02 01 02 02 01 03 01 01 01 01 03 03 01 03 02 02 01
04 02 04 02 02 01 02 01 01 01 03 03 01 02 01 01 00 03 02 03 01 01 02 01 02 02 03
03 04 03 03 02 03 01 02 03 02 01 03 02 02 01 01 00 02 01 01 03 01 01 01 01 01 02
00 02 00 00 01 02 01 01 01 00 01 01 00 01 01 02 02 01 01 01 00 01 00 01 01 04 02
02 02 01 02 02 01 02 01 02 00 01 00 02 01 02 02 00 01 02 01 01 01 02 01 01 01 02
01 00 01 01 00 00 01 02 00 01 00 01 01 00 01 00 01 02 02 01 01 02 00 00 02 01 02
02 01 00 00 01 00 01 00 01 00 02 00 00 00 01 01 00 00 01 01 00 00 00 01 00 00 00
00 00 00 01 01 00 00 01 02 01 01 01 00 01 02 01 01 01 02 00 00 00 01 01 00 01 00
00 00 02 02 01 00 01 02 00 01 00 01 02 00 01 00 00 01 00 01 01 01 00 01 01 00 01
01 01 01 00 00 01 01 00 00 01 01 00 01 01 00 00 01 00 00 00 01 01 02 02 01 01 00
00 01 02 01 02 00 01 01 00 01 00 00 00 00 00 00 01 00 00 01 02 01