LINEBURG

 << Ïðåä. ñòð. ñòðàíèöà 2(âñåãî 3)ÎÃËÀÂËÅÍÈÅ Ñëåä. ñòð. >>
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 J rgen 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 http://www.iso.ch/jtc1/sc27.
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.
0
To optimize e orts, A must use the k minimizing CL+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.
optimal log2 k log2 time log2 space
L = kh
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 2` log2 (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.
optimal log2 k log2 time log2 space `
L = kh
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 e cient 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 ? 215 (m) is an `-bit number on which we conduct an iso 9796-2-like
0
attack which expected complexity is C`;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) :
optimal log2 k our attack factorization
log2 n `
f84, 56g f68, 41g
606 303 28
f87, 58g f70, 42g
640 320 29
f97, 66g f75, 45g
768 384 33
f99, 68g f86, 50g
1024 400 34
f115, 78g f86, 50g
1024 512 39
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 :
` optimal log2 k our attack factorization
log2 n
f77, 46g f64, 39g
512 256 23
f80, 54g f66, 40g
548 274 27
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 http://www.rsa.com/rsalabs/.
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
w ? 1)=u where u are moderate-size factors of 2w ? 1. Such factors look
(2 i i
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, insu cient 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
6 Acknowledgements
We are grateful to Arjen Lenstra, Pascal Paillier and Michael Tunstall for their
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.
security ?, 1999 RSA Data Security Conference proceeding book, 1999.
5. M. Bellare and P. Rogaway, Random oracles are practical : a paradigm for
designing e cient 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 : http://www.netscape.com/newsref/std/ssl.html
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.
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
s?
? t + e s 1 ds
(t) = (2 t)?1=2 exp
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 i] + 102) 232j
message 16
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
P11 32j
step 2 : construct the message m0 = EE7E8E6616 j=0 2 and obtain
from the signer the 180 signatures si = (mi )d mod n.
step 3 : the signature of m0 is :
(m0 )d = pi?gamma i] sbeta i] mod n
 << Ïðåä. ñòð. ñòðàíèöà 2(âñåãî 3)ÎÃËÀÂËÅÍÈÅ Ñëåä. ñòð. >>