Evaluation of Security Level of Cryptography:
RSA Signature Schemes(PKCS#1 v1.5, ANSI X9.31, ISO 9796)
Alfred Menezes
University of Waterloo
Contact: ajmeneze@uwaterloo.ca
July 31, 2002

Contents

Page 1

Contents
1

Executive Summary22Introduction

2

3

Multiplicative Property of RSA

33.1

RSA Key Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

3.2

Basic RSA Signature Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

3.3

Multiplicative Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

4

5

6

RSA Signature Schemes with Appendix

6

4.1

PKCS#1 v1.5 RSA Signature Scheme . . . . . . . . . . . . . . . . . . . . . .

6

4.2

ANSI X9.31 RSA Signature Scheme . . . . . . . . . . . . . . . . . . . . . . .

7

4.3

Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

ISO 9796 RSA Signature Schemes with Message Recovery

10

5.1

ISO 9796-1 RSA Signature Scheme . . . . . . . . . . . . . . . . . . . . . . .

10

5.2

ISO 9796-2 RSA Signature Scheme . . . . . . . . . . . . . . . . . . . . . . .

11

5.2.1

Partial Message Recovery . . . . . . . . . . . . . . . . . . . . . . . .

11

5.2.2

Full Message Recovery . . . . . . . . . . . . . . . . . . . . . . . . . .

14Conclusions

References

16
17

2

Introduction

1

Executive Summary

Page 2In recent years, some attacks on fixed-padding RSA signature schemes have been reported in theliterature. This report evaluates the implications of these attacks on the RSA signature schemes
specified in the PKCS#1 v1.5 [27], ANSI X9.31 [1], ISO 9796-1 [14] and ISO 9796-2 [15]standards.

2

Introduction

The RSA signature scheme was introduced in 1977 [24]. Since then many versions have beenstandardized and used in practice. The different versions can be divided into two categories:
1. RSA signature schemes with appendix first compute the hash value of the message, andthen compute a signature by applying the RSA private-key operation to the (possibly
padded) hash value. Both the message and the signature are then transmitted to the receiver. The receiver applies the RSA public-key operation to the signature, and compares
the result to the hash of the message. The signed message is accepted if and only if thesevalues are the same. The PKCS#1 v1.5 [27] and ANSI X9.31 [1] RSA signature schemes
are examples of signature schemes with appendix.
2. RSA signature schemes with message recovery first add some redundancy to the message,
and then apply the RSA private-key operations to the padded message to obtain the signature. The signature only is transmitted to the receiver, who applies the RSA public-key
operation to recover the padded message and thereafter the message. The signed message
is accepted if and only if the padded message contains the correct form of redundancy.
The RSA signature schemes specified in ISO 9796-1 [14] and ISO 9796-2 [15] are examples of signature schemes with message recovery.
S ECURITY. A signature scheme is said to be secure if it is existentially unforgeable against
chosen-message attacks [11]. Informally, this means that an adversary who is able to obtainentity A’s signatures on any messages of its choice is unable to successfully forge A’s signature
on some other message. This notion of security is a very strong one—the adversary may have nocontrol over the contents of the message in the existential forgery and therefore the forgery may
be of no practical use to her. A potentially more damaging attack is a selective forgery whereby
the adversary is able to forge A’s signature of some particular message of her choosing.
A necessary condition for the security of all RSA signature schemes is that the problem of
inverting the RSA function (i.e., finding eth roots modulo n) be intractable. Another necessary
condition for the security of all RSA signature schemes with appendix is that the hash function
employed be collision resistant.

3

Multiplicative Property of RSA

Page 3In this report, we shall not be concerned with the intractability of the RSA function (nor of theinteger factorization problem), with specific security properties of the hash function, or with theefficiency of the schemes. Instead, we shall focus our attention on attacks that exploit the fixedpadding mechanisms used in the PKCS#1 v1.5, ANSI X9.31, ISO 9796-1 and ISO 9796-2 RSA
signature schemes. We note that unlike RSA-PSS and RSA-FDH1 [3], none of these schemes
have been proven to be secure under reasonable assumptions.
O RGANIZATION. The remainder of this report is structured as follows. The basic RSA signature scheme and the Desmedt-Odlyzko multiplicative attack which exploits its multiplicative
property are reviewed in Section 3. The resistance of the PKCS#1 v1.5 and ANSI X9.31 RSA
signature schemes with appendix to fixed-padding attacks is studied in Section 4. Section 5
considers the resistance of the ISO 9796-1 and ISO 9796-2 signatures schemes to fixed-padding
attacks. Our conclusions are stated in Section 6.

3

Multiplicative Property of RSA

3.1 RSA Key Generation
The RSA key generation procedure is common to all RSA-based signature schemes. To generate
an RSA key pair, each entity A does the following:
1. Randomly select two large distinct primes p and q of the same bit length.
2. Compute npq and φ n p  1 q  1 .


3. Select an arbitrary integer e, 1  e  φ n  , such that gcd e  φ n 






1.

4. Compute d, 1  d  φ n  , such that ed  1 mod φ n  .


5. A’s public key is n  e  ; A’s private key is d.
N OTES.
1. n is called the RSA modulus.
2. e is called the encryption exponent.
3. d is called the decryption exponent.
4. If n is a k-bit integer, then the RSA scheme is referred to as k-bit RSA.
1 Bellare and Rogaway proved that RSA-PSS and RSA-FDH are secure in the so-called random oracle model[2] under the assumptions that the problem of finding eth roots modulo n is intractable and that the hash function
employed is a public random function.

3

Multiplicative Property of RSA

Page 4

5. RSA signature verification involves modular exponentiations by the number e—computations of the form M e mod n. To speed signature verification, a widely-employed strategy
is to select a small encryption exponent e, such as e 3 or e 216 1. With such a
choice, RSA signature verification is much faster than RSA signature generation. Notethat RSA signature generation cannot be sped up by selecting a small decryption exponent
d without incurring a significant security risk [29, 4].

3.2 Basic RSA Signature SchemeLet n  e  be A’s RSA public key, and let d be A’s corresponding private key.
S IGNATURE G ENERATION. To sign a message m, A does the following:
1. Compute M

H m  where H is a cryptographic hash function such as SHA-1.

2. Use the private key d to compute s

M d mod n.

3. Send the signature s and the message m to B.
S IGNATURE V ERIFICATION. The verifier B does the following:

1. Obtain an authentic copy of A’s public key n  e  .


2. Compute M

H m .

3. Compute M 

se mod n.

4. Accept A’s signature provided that M

M .

3.3 Multiplicative Attacks
Multiplicative attacks on RSA signature schemes all exploit the multiplicative property 2 that

m1 m2  d  md1 md2



mod n (1)

If RSA signature generation did not use a hash function, i.e., s m d mod n for m  0  n  1 ,then an active attacker could forge the signature of any message m as follows:
1. Select arbitrary m1  1  n  1 and compute m2

mm1 1 mod n (so m

2. Obtain A’s signatures s1 , s2 on m1 and m2 , respectively.
3. Then it follows from (1) that A’s signature on m is s
2 also known as the homomorphic property.

s1 s2 mod n.

m1 m2 mod n).

3Multiplicative Property of RSA

Page 5To avoid this selective forgery attack,the message is padded (or formatted) prior to applicationof the RSA operation.  We let P m  denote the padded message corresponding to m, so thesignature on m is s P m  d mod n. The padding mechanism is chosen
so thatgiven
a message
P m1  P m2  mod n.
m it is (hopefully) infeasible to find messages m1 and m2 such that P m The most common way to format a message m is P m 
H m  , where H is a cryptographic
hash function. This results in the basic RSA signature scheme presented in Section 3.2. In
1985, Desmedt and Odlyzko [8] discovered the following selective forgery attack on basic RSA
signatures.
D ESMEDT-O DLYZKO S ELECTIVE F ORGERY ATTACK. For concreteness, we describe the attack in the case where n is a 1024-bit integer, e is prime (e.g., e 3 or e 2 16 1), and thehash function H is SHA-1. The adversary’s goal is to forge A’s signature s on a variant m  of amessage m.3
pt , where pi denotes the ith prime number.

1. Select a smoothness bound B

2. Select random messages m1  m2      mt until H mi  are B-smooth:t∏ p ji j 

H mi 

v1

 i tj 1

and the exponent vectors vi

vi1  vi2      vit  are linearly independent over


 .
e

H mi  d mod n.

3. Obtain the signatures si of the mi : si

4. Select variants m of m until H m  is B-smooth:t∏ pj j 

H m 

w

j 1

5. Solve the linear system of equations
c1 v1

c2 v2

 c v

 .

for c1  c2      ct 

w

t t

e

6. Now,
w

c 1 v1c2 v2

 c v

over the integers. Hence

H m 



H m1 

c1



H m2 

c2

eu

t t

 H m




t

ct

t

∏

e
u
pjj



j 1

3 For example, if m is a fragment of plain text then the variants m

between words of m so that the meaning of m is unchanged.

can be obtained by inserting extra spaces

4

RSA Signature Schemes with Appendix

Page 6

Raising both sides to the power d and reducing modulo n gives:s s ∏ p mod n 

sc11 sc22

ct
t

t

uj
j

(2)

j 1

Thus s can be computed according to the formula (2).
Using standard results on the distribution of smooth integers, we find that if B 2 20 then thenumber of chosen messages in the attack is about 216, while the number of steps in the algorithm (hash function evaluations + smoothness testing) is about 2 40. Thus the attack must be
considered as practical.
The attack can be prevented by using a hash function whose range is as large as the modulus
size—this is the idea behind RSA-FDH. In that case, the probability that a random hash value
is smooth is negligible. Indeed, running the attack will be slower than the number field sieve
factoring algorithm which searches for smooth integers of significantly smaller sizes. Anotherapproach to preventing the attack is to pad the hash value so that the resulting padded hash value
has the same bitlength as n—this is the idea behind the padding mechanisms in PKCS#1 v1.5
and ANSI X9.31.

4

RSA Signature Schemes with Appendix

4.1 PKCS#1 v1.5 RSA Signature Scheme
We present the PKCS#1 v1.5 RSA signature scheme as described in [27] 4. This scheme is a refinement of the basic RSA signature scheme (Section 3.2). It specifies a method for padding thehashed message in order to defeat known attacks on basic RSA such as the Desmedt-Odlyzko
multiplicative attack described in Section 3.3.


Let n  e  be A’s RSA public key, and let d be A’s corresponding private key. The integer n is koctets in length. (For example, if n is a 1024-bit modulus, then k 128.) H is a hash function
such as SHA-1 that is identified by some octet string HID. For SHA-1, HID is 15 octets inlength. For SHA-256, SHA-384 and SHA-512, HID is 18 octets in length.
S IGNATURE G ENERATION. To sign a message m, A does the following:
1. Compute hH m .

2. Form the following octet string M of length k octets:










00 01 PS 00 HID h 
where PS denotes a string of ‘FF’ octets. The length of PS must be at least 8 octets.
4 The PKCS#1 v1.5 RSA signature scheme described in PKCS#1 v2.1 [27] is the same as the original description

in the PKCS#1 v1.5 standard [26].

4

RSA Signature Schemes with Appendix

Page 7M d mod n.

3. Use the private key d to compute s

4. Send the signature s and the message m to B.
S IGNATURE V ERIFICATION. The verifier B does the following:

1. Obtain an authentic copy of A’s public key n  e  .
2. Compute M 

se mod n, and convert M  to an octet string of length k octets.

3. Compute h

H m .



4. Form the following octet string M of length k octets:










00 01 PS 00 HID h 
where PS denotes a string of ‘FF’ octets.
5. Compare M and M  . If M

M  then accept the signature; otherwise reject the signature.

4.2 ANSI X9.31 RSA Signature Scheme
We present the ANSI X9.31 RSA signature scheme [1]. This scheme is a refinement of the basic
RSA signature scheme (Section 3.2). It specifies a method for padding the hashed message inorder to defeat known attacks on basic RSA such as the Desmedt-Odlyzko multiplicative attack
described in Section 3.3.


Let n  e  be A’s RSA public key, and let d be A’s corresponding private key. The integer n is koctets in length. (For example, if n is a 1024-bit modulus, then k 128.) H is a hash function
such as SHA-1 that is identified by some string HID of length 2 octets. For SHA-1, HID is thehexadecimal string ‘33CC’.
S IGNATURE G ENERATION. To sign a message m, A does the following:
1. Compute hH m .

2. Form the following octet string M of length k octets:

6 PS h HID 
where PS denotes the hexadecimal string ‘BBBB...BBA’.
3. Use the private key d to compute s

M d mod n.

4. Send the signature s and the message m to B.
S IGNATURE V ERIFICATION. The verifier B does the following:

1. Obtain an authentic copy of A’s public key n  e  .

4

RSA Signature Schemes with Appendix

Page 8

2. Compute M 

se mod n, and convert M  to an octet string of length k octets.

3. Compute h

H m .



4. Form the following octet string M of length k octets:

6 PS h HID 
where PS denotes the hexadecimal string ‘BBBB...BBA’.
5. Compare M and M  . If M

M  then accept the signature; otherwise reject the signature.

S TRONG P RIMES. ANSI X9.31 mandates that the primes p and q satisfy the following strong
prime conditions:
1. p  1, p

1, q  1 and q

1 each have a prime factor of bitlength between 100 and 120.

2. p and q are different in at least one of the first 100 bits.
Condition 1 ensures resistance to the p  1 and p 1 factoring algorithms (due to Pollard [23]and Williams [30]). Condition 2 ensures resistance to a factoring algorithm of Fermat (andextended by Lehman [18]).5
We recall that the p  1 and p 1 factoring algorithms are “special-purpose” in that they are
most effective when p  1 or p 1 have only small factors. After the discovery of the elliptic
curve factoring method (ECM) by Lenstra in 1985 [20], it became clear that the requirementsthat p  1 and p 1 each have a large factor are no longer necessary. This is because it ismore important to guard against the ECM which is effective whenever an elliptic curve definedover p can be found whose order is smooth—this includes the cases where the elliptic curve
has order p  1 or p 1. Moreover, Rivest and Silverman [25] (see also Silverman [28]) haveshown that the p  1 and p 1 factoring algorithms are almost certainly to fail if the primes
p and q are sufficiently large and chosen at random. Clearly, condition 2 is also satisfied withoverwhelming probability if the primes p and q are randomly generated.
We conclude that while there is no security weakness if p and q are chosen to be strong primes,
there is also no reason to require that p and q be strong primes.

4.3 Security
BCCN ATTACK. Brier, Clavier, Coron and Naccache (BCCN) [5] presented the following
existential forgery attack on fixed padding RSA signature schemes. The attack improves earlier
attack of Girault and Misarsky [9] and Misarsky [21]. The survey article by Misarsky [22]5Another condition sometimes imposed on p (and q) is that the large factor r of p 1 must be so that r 1 also
has a large prime factor. This condition maximizes resistance to a cyclic attack on the RSA encryption scheme.
Since this attack is not relevant to signature schemes, the condition on r is not required.




4

RSA Signature Schemes with Appendix

Page 9provides a comprehensive overview on attacks known on fixed padding RSA signature schemes
prior to 1998.
Let the padding of an RSA message m be


P m

a

wm



(3)



For example, if the padded message is R m L where L is s bits in length and m is l bits inlength, then we can write P m 
wm a where w 2s and a L 2s l R.

Suppose now that messages are at most l bits in length, where l is an integer whose bitlength isat most 1 3 that of n. The idea of the BCCN attack is to find messages m 1 , m2 , m3, m4 such that










P m1  P m2   P m3  P m4 

mod n (4)

Then, after obtaining the signatures of m1 , m2 and m4 , the adversary can compute the signatureof m3 as follows:
P m1  d P m2  ddP m3 
mod n p m4  d
Finding m1 , m2 , m3, m4 satisfying (4) is equivalent to solving

for t  x  y z where RRz  xy  tz

mod n (5)

a w mod n, and where
m1
m2
m3
m4

x
y
t
x

t
t
y

z

t

are each at most l bits in length. The algorithm for finding t  x  y z is the following:





 
2. Let z  Q  and u  RQ nP  .

1. Run the Euclidean algorithm with inputs R and n to find the continued fraction convergent
Pj Q j to R n satisfying Q j  n1 3 Q j 1 .
j

j

j

  y  2n  and gcd y z

3. Select an arbitrary integer y with n1 3





1.





5. Let x

tz  y.

uuz 1 mod y.

4. Compute t

1 3Now, in the PKCS#1 v1.5 and ANSI X9.31 signature schemes, the padding function is of theformwH m  a
(6)
P m

5

ISO 9796 RSA Signature Schemes with Message Recovery

Page 10for some w and a. Note here that (6) differs from (3) in that the hash value of m is used instead ofm itself. In the BCCN attack, the adversary does not have any control over the value of z (which
is determined from R and n). Moreover, after the adversary has chosen y, the values of t and x
are determined. Thus, the BCCN attack is doomed to fail for the PKCS#1 v1.5 and ANSI X9.31
signature schemes since the attacker would need to determine messages whose hash values are
determined from t  x  y z (since the adversary has to present the actual messages to the signingoracle, and not their hash values). Finding messages from hash values is infeasible assumingthat the hash function is one-way.
We could not see how to modify the BCCN attack to be effective on the PKCS#1 v1.5 and
ANSI X9.31 signature schemes.
L ENSTRA -S HPARLINSKI ATTACK. Lenstra and Shparlinski [19] presented the following improvement to a selective forgery attack of Brier, Clavier, Coron and Naccache [5]. For a selective
forgery of m3 , congruence (5) is rewritten asR

m3  z  xy

mod n  

(7)

Given m3 , the adversary’s task is to find x  y z satisfying (7) so that the corresponding m 1  m2  m4
are at most l bits long. Lenstra and Shparlinski describe a method for finding such x  y z. In thismethod, the adversary has some freedom in the selection of x, y and z. However, there is notenough freedom to allow solutions x, y and z to be chosen so that messages corresponding tohash values m1 , m2 , m4 are known. Thus, as with the BCCN attack, the adversary is still facedwith the insurmountable task of finding the messages corresponding to the derived hash values.
We could not see how to modify the Lenstra-Shparlinski attack to be effective on the PKCS#1 v1.5
and ANSI X9.31 signature schemes.

5

ISO 9796 RSA Signature Schemes with Message Recovery

The ISO 9796 standard covers signature schemes with message recovery. It has three parts:
1. ISO 9796-1 [14]: RSA and Rabin schemes without a hash function.
2. ISO 9796-2 [15]: RSA and Rabin schemes using a hash function.
3. ISO 9796-3 [16]: Discrete logarithm based mechanisms.
This section studies the RSA signature schemes in ISO 9796-1 and ISO 9706-2.

5.1 ISO 9796-1 RSA Signature Scheme
ISO 9796-1 [14] was first published in 1991. It is an RSA signature scheme with message
recovery. Plaintext messages can be at most half the bitlength of the modulus. Rationale for5

ISO 9796 RSA Signature Schemes with Message Recovery

Page 11

the redundancy function in ISO 9796-1 was provided in [13]. We will not present the details of
the redundancy function because, as described below, the ISO 9796-1 signature scheme is now
considered to be completely broken.
Coron, Naccache and Stern [7] in 1999 presented an attack on a slight modification of theISO 9796-1 signature scheme. The attack is a refinement of the Desmedt-Odlyzko chosenmessage attack that exploits the special structure of padded messages. Shortly after, Coppersmith, Halevi and Jutla [6] modified the attack to work on the (unmodified) ISO 9796-1 scheme.
In 2000, Grieu [12] introduced a simpler attack that can efficiently find 4 messages m 1 , m2 , m3 ,m4 such that





P m1  P m2   P m3  P m4 
mod n (8)and can therefore construct the signature for any one of these messages given the signatures forthe other three messages. Girault and Misarsky [10] also showed that several countermeasures
proposed by Coppersmith, Halevi and Jutla [6] were not adequate for repairing the signaturescheme.
We conclude from this recent work that the ISO 9796-1 signature scheme should be considered
to be insecure and should not be used in practice.
We note that the attacks of Coron, Naccache and Stern [7], Coppersmith, Halevi and Jutla [6],and Grieu [12] do not appear to apply to the PKCS#1 v1.5 and ANSI X9.31 RSA signatureschemes.6

5.2 ISO 9796-2 RSA Signature Scheme
ISO 9796-2 specifies an RSA signature scheme with partial message recovery and one with fullmessage recovery.
We note that ISO 9796-2 is in the process of being revised (see [17]). The revision, currently
under development, is expected to contain three signature schemes, one of which will be thesame as the scheme specified the current edition [15]. All three schemes will be RSA-based,
but will be distinguished by the use of three different formatting mechanisms.
5.2.1

Partial Message RecoveryLet n  e  be A’s RSA public key, and let d be A’s corresponding private key. H is an l-bit hashfunction such as SHA-1. We assume that l and the bitlength k of n are multiples of 8, as is thebitlength of the message m.

6 Coron, Naccache and Stern [7] observe that their attack does apply to the PKCS#1 v1.5 and ANSI X9.31

signature schemes if the RSA modulus is of the special form n 2k c where c is small. However since such RSA
moduli are not used in practice, the attack is not effective in practice.
5

ISO 9796 RSA Signature Schemes with Message Recovery

Page 12

S IGNATURE G ENERATION. To sign a message m, A does the following:

1. Write mmL mR where mL has bitlength k  l  16.

2. Compute hH m .

3. Form the following octet string M of length k bits:

6A mL h BC 
M d mod n.

4. Use the private key d to compute s
5. Send the signature s and mR to B.

S IGNATURE V ERIFICATION. The verifier B does the following:

1. Obtain an authentic copy of A’s public key n  e  .
se mod n and parse M  as follows:

2. Compute M M

X X mL h YY 

where ‘X X ’ and ‘YY ’ are hexadecimal strings of length 2.
3. Verify that X X
4. Compute h

6A and YY

BC. If not, then reject the signature.



H m L mR  .

5. If h h then reject the signature.
Else, accept m mL mR as the message signed by A.
S ECURITY. Coron, Naccache and Stern (CNS) [7] observed that the Desmedt-Odlyzko multiplicative attack can be adapted to attack the ISO 9796-2 signature scheme with partial message
recovery. In the following, we use bit strings and hexadecimal strings to represent integers.


Denote the padded message m by µ m  ; that is,




µ m








BC 

6A mL H m 

1  2k by n yields a quotient q and a remainder r satisfying

Dividing the integer 6A6A

Now, letn
where n has bitlength k
mL nL , we see thatqn

1  2kr where r  n  2k 

qn

6A  2k

2k  r 

6A nL nR 

7, nL has bitlength k  l  16, and nR has bitlength l


T m



qn  µ m  28

nR 





H m

16. Letting

BC00 

(9)has bitlength at most l 16. The adversary, whose goal is to forge A’s signature s on a variantm of a message m nL mR (for any mR of the adversary’s choice), does the following:5

ISO 9796 RSA Signature Schemes with Message Recovery

Page 13

pt , where pi denotes the ith prime number. Let pt 1

1. Select a smoothness bound B1.

2. Select arbitrary mR 1  mR 2      mR t 1 until the corresponding T values are B-smooth:t∏ p ji j  1

qn  µ mi  28

T mi z i t 1j 1



where minL mRi , and the tviµ mi  

vi1  vi2      vit  vi t 1 

zi1  8  zi2      zit  1 

 . Note that by (9) we haveare linearly independent over

1 exponent vectorse

T mi  2

8

t 1



∏ pjj



v

mod n  for 1

 i  t 1j 1

µ mi  d mod n.

3. Obtain the signatures si of the mi : si

4. Select variants mR of mR until T m  is B-smooth:t∏ p jj 

qn  µ m  28

T m 

z

j 1

where mnL mR . Set w

z1  8  z2      zt  1  .

5. Solve the linear system of equations
c1 v1
for c1  c2      ct 1 

c2 v2 c v .
e c v

6. Now,
w

c 1 v1c2 v2

 µ m

t 1 t 1over the integers. Hencew

t 1 t 1

µ m    µ m1 c1

µ m2 

c2



t 1



t 1

∏

ct 1


eu

e
u
pjj



mod n  

j 1

Raising both sides to the power d and reducing modulo n givess

sc11 sc22 s

ct 1
t 1


t 1

∏ pjj
u

j 1

Thus s can be computed according to formula (10).



mod n  

(10)

5

ISO 9796 RSA Signature Schemes with Message Recovery

Page 14A NALYSIS . The running time of this attack depends on the choice of the smoothness boundB pt . The optimum choicefor B depends on the distribution of smooth integers of bitlengthl 16 (recall that the T mi  have bitlength l 16), and not on the parameter k (the bitlength ofthe modulus n). If l 160 (the bitlength of SHA-1 outputs), then the optimum choice of t isapproximately 220. In this case, the adversary needs to query the signing oracle approximately
220 times, and the expected running time (hash function evaluations + smoothness testing) isabout 261—it is important to note that this running time is independent of the bitlength of the
RSA modulus. The running time of 261 is less than the expected running time of the number
field sieve to factor 1024-bit RSA moduli (about 280 steps). Thus the CNS attack is effectivein that it is faster than the best known factoring algorithm. On the other hand, the attack stillrequires the signatures of 220 chosen-messages, so it can be argued that the attack is not practicalin many scenarios.
We conclude that the CNS attack is a concern for the ISO 9796-2 signature scheme with partial
message recovery in environments where the attacker is capable of obtaining the signatures of asignificant number (e.g., one million) of chosen messages. In environments where the attacker
is not capable of obtaining these signatures, the CNS attack is not a concern.
5.2.2

Full Message RecoveryLet n  e  be A’s RSA public key, and let d be A’s corresponding private key. H is an l-bit hashfunction. ISO 9796-2 recommends that l  64  80 . We assume that l and the bitlength k of nare multiples of 8, and that the message m has bitlength k  l  16.
S IGNATURE G ENERATION. To sign a message m, A does the following:
1. Compute hH m .

2. Form the following octet string M of length k bits:

4A m h BC 
3. Use the private key d to compute s

M d mod n.

4. Send the signature s to B.
S IGNATURE V ERIFICATION. The verifier B does the following:

1. Obtain an authentic copy of A’s public key n  e  .
2. Compute M 

se mod n and parse M  as follows:M

X X m h YY 

where ‘X X ’ and ‘YY ’ are hexadecimal strings of length 2.

5

ISO 9796 RSA Signature Schemes with Message Recovery

3. Verify that X X
4. Compute h

4A and YY

Page 15

BC. If not, then reject the signature.

H m .

5. If h h then reject the signature.
Else, accept m as the message signed by A.
S ECURITY. Coron, Naccache and Stern (CNS) [7] observed that the Desmedt-Odlyzko multiplicative attack can also be adapted to the ISO 9796-2 RSA signature with full message recovery. The attack is similar to the one described in Section 5.2.1. Here again, we use bitstringsand hexadecimal strings to represent integers.


We write a plaintext message m as m mL mR where mhas bitlength x. Here, x is a parameter R
to be chosen later. Denote the padded message m by µ m  ; that is,




µ m








BC 

4A m H m 

1  2k by n yields a quotient and a remainder r satisfying

Dividing the integer 4A4A

Now, letnqn

1  2kr where r  n  2k 

qn

4A  2k

2k  r 

where n has bitlength k 7, nR has bitlength l
Letting mL nL , we see that

x





T m



qn  µ m  28nR 

4A nL nR 16, and nL has bitlength k  l  x  9.
mR H m BC00 

(11)

has bitlength at most l x 16. The adversary can now modify mR until T m  is smooth. The
attack then proceeds as in the CNS attack described in Section 5.2.1.
A NALYSIS . The running time of this attack depends on the choice of x and the smoothness
bound B pt . The optimum choice for B depends on the distribution of smooth integers ofbitlength l x 16 (recall that the T mi  have bitlength l x 16), and not on the parameter k(the bitlength of the modulus n). For example, if l 64, then x 32 and t 2 15. In this case, theadversary needs to query the signing oracle approximately 2 15 times, and the expected running
time (hash function evaluations + smoothness testing) is about 247 —it is important to note that
this running time is independent of the bitlength of the RSA modulus. Similarly, if l 80, thenx 34 and t 217. In this case, the adversary needs to query the signing oracle approximately
217 times, and the expected running time (hash function evaluations + smoothness testing) isabout 251. These running times are significantly less than the expected running time of thenumber field sieve to factor 1024-bit RSA moduli (about 280 steps). Thus the CNS attack iseffective in that it is faster than the best known factoring algorithm. On the other hand, theattack still requires the signatures of about 215 chosen-messages, so it can be argued that theattack is not practical in many scenarios.

6

Conclusions

Page 16

We conclude that the CNS attack is a concern for the ISO 9796-2 signature scheme with fullmessage recovery in environments where the attacker is capable of obtaining the signatures of asignificant number (e.g., 50 thousand) of chosen messages. In environments where the attacker
is not capable of obtaining these signatures, the CNS attack is not a concern.

6

Conclusions

The recently published attacks on fixed-padding RSA signature schemes completely break the
ISO 9796-1 RSA signature scheme with message recovery. They also seriously threaten the
security of the ISO 9796-2 RSA signature schemes in environments where an adversary is able
to obtain the signatures of a significant number (e.g., one million) of chosen messages. For
these reasons, we recommend that the ISO 9796-1 and ISO 9796-2 standards not be adopted by
CRYPTREC.
The attacks are not a threat to the practical security of schemes described in the ANSI X9.31
and PKCS#1 v1.5 standards. Nevertheless, the possibility of an effective attack being discovered in the future still remains. It is strongly recommended that RSA signature schemes withpseudorandom padding be used instead. The best candidate is the RSA PSS signature scheme[3] which has been proven secure in the random oracle model.

References

Page 17

References[1] ANSI X9.31, Digital Signatures Using Reversible Public Key Cryptography for the Financial Services Industry (rDSA), 1998.
[2] M. Bellare and P. Rogaway, “Random oracles are practical: a paradigm for designingefficient protocols”, 1st ACM Conference on Computer and Communications Security,
1993, 62-73. Full version available at http://www.cs.ucdavis.edu/ rogaway/papers/index.
html.
[3] M. Bellare and P. Rogaway, “The exact security of digital signatures—How to sign with
RSA and Rabin”, Advances in Cryptology—Eurocrypt ’96, Lecture Notes in Computer
Science, 1070 (1996), Springer-Verlag, 399-416. Full version available at http://www.cs.
ucdavis.edu/ rogaway/papers/index.html[4] D. Boneh and G. Durfee, “Cryptanalysis of RSA with private key d less than N 0 292”,
IEEE Transactions on Information Theory, 46 (2000), 1339-1349.
[5] E. Brier, C. Clavier, J. Coron and D. Naccache, “Cryptanalysis of RSA signatures with
fixed-pattern padding”, Advances in Cryptology—Crypto 2001, Lecture Notes in Computer Science, 2139 (2001), Springer-Verlag, 433-439.
[6] D. Coppersmith, S. Halevi and C. Jutla, “ISO 9796-1 and the new forgery strategy”, working draft, 1999. Available at http://grouper.ieee.org/groups/1363/Research/Cryptanalysis.
html.
[7] J. Coron, D. Naccache and J. Stern, “On the security of RSA padding”, Advanced in
Cryptology—Crypto ’99, Lecture Notes in Computer Science, 1666 (1999), SpringerVerlag, 1-18.
[8] Y. Desmedt and A. Odlyzko, “A chosen text attack on RSA cryptosystem and some discrete logarithm schemes”, Advanced in Cryptology—Crypto ’85, Lecture Notes in Computer Science, 218 (1986), Springer-Verlag, 516-522.
[9] M. Girault and J. Misarsky, “Selective forgery of RSA signatures using redundancy”, Advances in Cryptology—Eurocrypt ’97, Lecture Notes in Computer Science, 1233 (1997),
Springer-Verlag, 495-507.
[10] M. Girault and J. Misarsky, “Cryptanalysis of countermeasures proposed for repairing
ISO 9796-1”, Advances in Cryptology—Eurocrypt 2000, Lecture Notes in Computer Science, 1807 (2000), Springer-Verlag, 81-90.
[11] S. Goldwasser, S. Micali and R. Rivest, “A digital signature scheme secure against adaptive chosen-message attacks”, SIAM J. Computing, 17 (1988), 281-308.

References

Page 18[12] F. Grieu, “A chosen message attack on ISO/IEC 9796-1 signature scheme”, Advances in
Cryptology—Eurocrypt 2000, Lecture Notes in Computer Science, 1807 (2000), SpringerVerlag, 70-80.
[13] L. Guillou and J. Quisquater, “Precautions taken against various potential attacks in
ISO/IEC DIS 9796”, Advances in Cryptology—Eurocrypt ’90, Lecture Notes in Computer
Science, 473 (1991), Springer-Verlag, 465-473.
[14] ISO/IEC 9796-1, Information Technology–Security Techniques-Digital Signature Scheme
Giving Message Recovery, Part 1: Mechanisms Using Redundancy, 1999.
[15] ISO/IEC 9796-2, Information Technology–Security Techniques-Digital Signature Scheme
Giving Message Recovery, Part 1: Mechanisms Using a Hash Function, 1997.
[16] ISO/IEC 9796-3, Information Technology–Security Techniques-Digital Signature Scheme
Giving Message Recovery, Part 3: Discrete Logarithm Based Mechanisms, 2000.
[17] ISO/IEC FDIS 9796-2 (2002), Digital signature schemes giving message recovery - Part
2: Integer factorization based mechanisms, 2002. Available at http://www.din.de/ni/sc27/
doc7.html.
[18] R. Lehman, “Factoring large integers”, Mathematics of Computation, 28 (1974), 637-646.
[19] A. Lenstra and I. Shparlinski, “Selective forgery of RSA signatures with fixed-patternpadding”, Proceedings of PKC 2002, Lecture Notes in Computer Science, 2274 (2002),
Springer-Verlag, 228-236.
[20] H. Lenstra, “Factoring integers with elliptic curves”, Annals of Mathematics, 126 (1987),
649-673.
[21] J. Misarsky, “A multiplicative attack using LLL algorithm on RSA signatures with redundancy”, Advances in Cryptology—Crypto ’97, Lecture Notes in Computer Science, 1294
(1997), Springer-Verlag, 221-234.
[22] J. Misarsky, “How (not) to design RSA signature schemes”, Proceedings of PKC ’98,
Lecture Notes in Computer Science, 1431 (1998), Springer-Verlag, 14-28.
[23] J. Pollard, “Theorems on factorization and primality testing”, Proceedings of the Cambridge Philosophical Society, 76 (1974), 521-528.
[24] R. Rivest, A. Shamir and L. Adleman, “A method for obtaining digital signatures andpublic-key cryptosystems”, Communications of the ACM, 21 (1978), 120-126.
[25] R. Rivest and R. Silverman, “Are ‘strong’ primes needed for RSA?”, Report 2001/007,
Cryptology ePrint Archive, 2001. Available at http://http://eprint.iacr.org/

References

Page 19[26] RSA Laboratories, PKCS#1 v1.5: RSA Encryption Standard, November 1993. Available
at http://www.rsasecurity.com/rsalabs/pkcs/pkcs-1/[27] RSA Laboratories, PKCS#1 v2.1: RSA Cryptography Standard), June 14 2002. Available
at http://www.rsasecurity.com/rsalabs/pkcs/pkcs-1/[28] R. Silverman, “Fast generation of random, strong RSA primes”, CryptoBytes, 1, Springer
1997, 9-13. Available at http://www.rsasecurity.com/rsalabs/cryptobytes/index.html[29] M. Wiener, “Cryptanalysis of short RSA secret exponents”, IEEE Transactions on Information Theory, 36 (1990), 553-558.
[30] H. Williams, “A p225-234.

1 method of factoring”, Mathematics of Computation, 39 (1982),