LINEBURG

ñòðàíèöà 2 |

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

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 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.

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

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 |

Copyright © Design by: Sunlight webdesign