signature pairs, and r and aI, . . . , a, are arbitrary. the RSA modulus.

Since the resulting message m is not known in ad-

vance, this is an “existential” forgery; the signature Messages to be signed should thus be as large as the

exists but the message may or may not be useful. RSA modulus and, for similar reasons as for encryp-

However by selecting messages mi to be signed, an tion, not a multiple of some known value.

attacker can derive a signature of a given message m

RSA Block Formats

in a chosen message attack. Again, this can be

avoided by padding in a way that destroys the alge- Throughout this article we have considered one po-

braic connections between messages. tential attack after another, in each case highlight-

ing its prevention. Is there a standard way to adopt

While a good padding scheme will destroy the algebraic these safeguards? Is there a way that implementa-

properties which allow these attacks, it is worth point- tions of RSA can communicate with each other and

ing out that de Jonge and Chaum [6] have extended be assured of a basic level of security?

such basic attacks to demonstrate vulnerabilities in

an early proposal for a simple padding scheme. There are a variety of practical methods for address-

ing the different recommendations on encryption

Also note that while the algebraic properties we ex- and signatures. For instance, PKCS #l [22] (see

ploit appear to have a negative impact on the use of accompanying box) is a simple, ad-hoc design for

RSA, we should point out that this “attack” can be protecting RSA encryption and signatures on mes-

used constructively to provide what is called blind- sage digests; it is easy to implement and addresses

ing [4] in anonymous payment systems! each of the attacks described above in a heuristic

THE TECHNICAL NEWSLETTER OF RSA LABORATORIES -AUTUMN 1995 CRYPTOBYTES

Page 37

Previous Page Home Next Page

Conclusions

manner. The amount of padding in each block is at

In this article, we have provided an overview of the

least 11 bytes.

major attacks that have resulted from more than 15

years of cryptanalysis. While many of these attacks

ISO/IEC 9796 [13] provides a mathematical design

would be a serious problem if mounted on a raw form

for protecting signatures and also gives message re-

of RSA, we have seen that there is always a practical

covery: it is intended for signatures on arbitrary data

and efficient countermeasure.

as well as message digests, and the data or message

digest can be recovered from the signature. ISO/IEC

References

While many of 9796 is somewhat more complex than PKCS #l, and

[l] W. Alexi, B. Chor, 0. Goldreich, and C.F™. Schnorr.

about half of each block is padding, but the math-

these attacks

ematical motivation is well justified [ll].

would be a RSA and Rabin functions: certain parts are as hard as the

serious problem whole. SIAM Journal Computing, 17( 2): 194-209,

on

. . . we have The construction of Bellare and Rogaway [3], also April 1988.

seen that there known as Optimal Asymmetric Encryption Padding, [2] D. Atkins, M. Graff, A.K. Lenstra, and PC. Leyland. The

is always a provides a cryptographic design for protecting en- magic words are squeamish ossifrage. In J. Pieprzyk and

pracfical and cryption. It involves hash functions and pseudoran- R. Safavi-Naini, editors, Advances in Cryptology-

efficient counter dom generators and is the most complex of the three A&crypt ˜94, pages 263-277, Springer-Verlag, 1995.

measure. approaches. However, it has the benefit that its se- [3] M. Bellare and E Rogaway. Optimal asymmetric encryp-

curity can be directly related to the quality of the tion. In A. de Santis, editor, Advances in Cryptology-

hash function or pseudorandom generator. The Eurocrypt ˜94, pages 92-111, Springer-Verlag, 1995.

amount of padding is 16 bytes or more, depending [4] D. Chaum. Security without identification: transaction

on the level of security. systems to make big brother obsolete. Comm. ACM

28: JO, October, 1985.

The whole issue of defining block formats is, in itself, 151 D. Coppersmith. Analysis of JSOlCCJTT Document

an interesting and delicate problem, and deserves X.509 Annex D. Internal Memo, IBM T.J. Watson

more attention than we can give in this article. Center, June 11, 1989.

Instead we refer the reader to the relevant references [6] W. de Jonge and D. Chaum. Attacks on some RSA signa-

for additional information. tures. In H.C. Williams, editor, Advances in Cryptology-

PKCS #l Block Formats

i ensures that the block is arithmetically less than the RSA

modulus. The byte 02, and the padding makes the input to

PKCS #l, the RSA signature and encryption standard RSA a large integer, thus preventing short message attacks;

developed by RSA Laboratories and a number of RSA the pseudorandomness in PS prevents low-exponent attacks.

Data Security™s customers in the early 1990™s, defines two The overall structure of the block prevents the various multi-

sets of rules for padding a message block prior to encryp plicative attacks that we observed in the accompanying article.

tion or signature. The padding rules are slightly differ-

ent in the two cases, because of the different style of More specifically, the pseudorandom string increases the diffi-

attacks that they are intended to protect against. culty of a variety of attacks-Hastad™s, Franklin and Reiter™s,

and various chosen ciphertext attacks including Desmedt and

For encryption, the block format is defined as follows. Odlyzko™s-by a factor of at least (255)s = 264, assuming that

The length of the entire block is the same as the length of the pseudorandom string is discarded by the decryption equip-

the RSA modulus which is being used. It has the follow- ment. To complete any of those attacks, the opponent essen-

ing form (from most significant to least significant byte): tially must guess the bits of the pseudorandom string for at

least one, and possibly more messages. (For instance, to com-

00, 02, PS 00, D plete Franklin and Reiter™s attack, the opponent must guess

I

the difference between the encryption blocks for two mes-

The values 00, and 02, are byte values in hexadecimal sages, which involves at least 64 unknown bits.)

notation, PS is a pseudorandom string of nonzero bytes,

and D is the data to be encrypted. The pseudorandom The pseudorandom string also thwarts the “verifiable plain-

string must be at least eight bytes long. The byte 00, text” attack where an opponent re-encrypts guessed plaintext

CRYPTOBYTES AUTUMN 1995 -THE TECHNICAL NEWSLETTER OF RSA LABORATORIES

Page 38

Previous Page Home Next Page

Ann. of Math., 126:649-673, 1987.

Crypto ˜8.5, pages 18-27, Springer-Verlag, 1986.

[16] G.L. Miller. Reimann™s hypothesis and tests for primality.

[7] Y.G. Desmedt and A.M. Odlyzko. A chosen text attack

1. Compur. System Sci., 13:300-317, 1976.

on the RSA cryptosystem and some discrete logarithm

schemes. In H.C. Williams, editor, Advances in Crypt& [17] A.M. Odlyzko. The Future of Integer Factorization. RSA

ogy -Crypto ˜85, pages 516-522, Springer-Verlag, 1986. Laboratories™ CryptoBytes, 1:2, pages 5-12, Summer, 1995.

[8] W. Diffie and M.E. Hellman. New directions in cryptog- [18] J. Pollard. Theorems on factorization and primality test-

raphy. IEEE Transactions on Information Theory, IT-22: ing. Proc. Cambridge Philos. Sot., 76:521-528, 1974.

[19] B. Preneel. Analysis and Design of Cryptographic Hash Func-

644-654, 1976.

191 J.-H. Evertse and E. van Heyst. Which new RSA-signa- tions. Ph.D. Thesis, K.U.Leuven. January, 1993.

tures can be computed from certain given RSA-signa- [20] R. Rivest. Dr. Ron Rivest on the Difficulty of Factoring.

Ciphertext: The RSA Newsletter, vol. 1, no. 1, fall 1993,

tures? Journal ofCryptology, 5( 1):41-52, 1992.

[lo] M. Franklin and M. Reiter. A linear protocol failure for and reprinted, in an updated form, in an appendix on

RSA with exponent three. Presented at the Rump Ses- pages 361-364 in S. Garfinkel, PGP: Pretty Good Privacy,

sion of Crypto ˜95, Santa Barbara, CA. O™Reilly & Associates, 1995.

[ll] L.C. Guillou, J.-J. Quisquater, M. Walker, P. Landrock, [21] R.L. Rivest, A. Shamir, and L. Adleman. A method for

and C. Shaer. Precautions taken against various potential obtaining digital signatures and public-key cryptosystems.

Cutnmunicaticms of &ACM, 21(2):120-126, February 1978.

attacks in ISO/IEC DIS 9796. In LB. Damgird, editor,

Advances in Cryptology-Eurocrypt ˜90, pages 465-473, [22] RSA Laboratories. PKCS #I: RSA Encryption Standard,

Springer-Verlag, 199 1. Version 1.5, November 1993.

1121 [23] G.J. Simmons and M.J. Norris. Preliminary comments on

J. Hastad. Solving simultaneous modular equations of low

degree. SJAh4 Journal on Computing, 17(2):336-341, April 1988. the MIT public-key cryptosystem. Cryptologiu, 1(4):406-

1131 ISO/IEC. International Standard 9796: Infmmation Tech- 414,1977.

nology, Security Techniques: Digital Signature Scheme Giv- [24] M.J. Wiener. Cryptanalysis of short RSA secret expo-

ing Message Recovery, 1991. nents. IEEE Transactions on Infomation Theory, 36:553-

1141 D.E. Knuth. The Art of Computer Programming, Vol.2: 558, 1990.

Seminumerical Algorithms. Second edition, Addison- [25] H.C. Williams and B. Schmid. Some remarks concerning

Wesley, Reading, MA., 1981. the MIT public-key cryptosystem. BIT 19, pages 525-

[15] H.W. Lenstra Jr. Factoring integers with elliptic curves. 538, 1979. b

and compares the result to the ciphertext. Since the opponent sen message forgery is 2@ harder since an opponent can

must guess the pseudorandom string in addition, the difficulty only obtain “raw” RSA signatures on less than one in

increases by at least a factor of 2”. every 264 possible messages. The opponent must repeat-

edly randomize the message to be signed to find one

For protecting RSA signatures, the signature block format is whose block format is correct.

slightly different and has the following form:

The PKCS #l block format for signatures is intended

04 0 1 , ff,... f 00, D only for signatures on the message digests of messages.

I

Some potential attacks arise if the data D is arbitrary,

Again OO,, 01, and ffX are byte values in hexadecimal nota- since an opponent can select the value of D so that the

tion, and D is the data to be signed, which must be a message resulting signature block has small prime factors, or per-

digest. There must be at least eight ff, bytes. haps is even a natural power. However, when the data

D is a message digest, which is effectively a pseudoran-

The byte 00, again ensures that the block is arithmetically dom value, these attacks are not a concern; for applica-

less than the RSA modulus. The byte 01, and the ffX padding tions where a message digest is signed with RSA, the

prevent the variant of Desmedt and Odlyzko™s attack on small format is adequate.

messages and the overall structure of the block prevents vari-

ous multiplicative attacks. In applications where data is signed directly, a format

such as ISO/IEC 9796 designed specifically for signatures

Just as for encryption, there is at least a 264 increase in work with “message recovery” is preferable. m

effort for a variety of attacks. For instance, known and cho-

-Ei

THE TECHNICAL NEWSLETTER OF RSA LABORATORIES - AUTUMN 1995 CRYPTOBYTES

Page 39

Previous Page Home Next Page

FREQUENTLY ASKED QUESTIONS

How Do Digital Time-Stamps make sure it correctly answers (I) who and what? or

Suppolt Digital Signatures? (2) when and what? about the record in question.

Answered by

The “certificate” returned by the certification pro-

Stuart Haber, Burt Kaliski and Scott Stornetta

cedure of a digital signature system is usually called a

signature; it is a signature for a particular signer

Consider two questions that may be asked by a com-

(specifying whom) and for a particular record (speci-

puter user as he or she views a digital document or

fying what). In order to be able to “sign” documents,

on-line record. (1) Who is the author of this record

a user registers with the system by using special soft-

-who wrote it, approved it, or consented to it?

ware to compute a pair of numbers called keys, a

(2) When was this record created or last modified?

public key and a corresponding fivute key. The pri-

vate key should only be available to the user to whom

In both cases, the question is one about exactly this

it belongs, and is used (by the certification or “sign-

record-exactly this sequence of bits-whether it

ing” procedure) in order to sign documents; it is by

was first stored on this computer or was created some-

employing the user™s private key that the signature

where else and then copied and saved here. An an-

and the record are tied to that particular user. The

swer to the first question tells who B what: who

public key may be available to many users of the

approved exactly what is in this record? An answer

system, and is used by the verification procedure.

to the second question tells when B what: when

That is, the verification procedure takes a particular

exactly did the contents of this record first exist?

record, a particular user™s public key, and a putative

signature for that record and that user, and uses this

Both of the above questions have good solutions. A

information to check whether the would-be signa-

system for answering the first question is called a digi-

ture was correctly computed using that record and

tal signature scheme. Such a system was first proposed

the corresponding private key.

in [2] and there is a wide variety of accepted designs

for an implementation of this kind of system [4,5].

Special computational methods are employed for

signing documents and for verifying documents and

A system for answering the second question is called

signatures; when these methods are carefully imple-

a digital time-stamping scheme. Such systems were de-

mented, they have the remarkable property that the

scribed in [1,3], and an implementation is commer-

cially available from Surety Technologies (http:// knowledge of a user™s public key does not enable an

attacker or hacker to figure out the user™s correspond-

www.surety.com/).

ing private key. Of course, if, either through care-

Digital lessness or deliberate intent, someone else-a hacker,

Any system allowing users to answer these questions

time-stamps for example-gains access to the user™s private key,

reliably for all their records must include two differ-

increase the then this person will be able to “forge” the legiti-

ent sorts of procedures. First, there must be a certifi-

mate user™s signatures on documents of the hacker™s

longevity of cation procedure with which (1) the author of a

digitally-signed choice. At that point, even the value of legitimately

record can “sign” the record, or (2) any user can fix

signed records can be called into question.

a record in time. The result of this procedure is a

records.

small certifying file, a certificate if you will, that cap

The “certificate” returned by the certification pro-

tures the result of this procedure. Second, there must

cedure of a digital time-stamping system is a certifi-

be a verification procedure by which any user can

cate for a particular record (specifying what) at a

check a record and its accompanying certificate to

particular time (specifying when). The procedure

works by mathematically linking the bits of the

Stuart Haber is a research scientist in the Security Research Group

record to a “summary number” that is widely wit-

at Bellcore, Burt Kaliski is chiefscientist at RSA Laboratories, and

nessed by and widely available to members of the

W. Scott Stornetta is Chairman of Surety Technologies. Surety

public-including, of course, users of the system.

Technologies was founded by Stornetta and Haber in 1994 as

a spin-offfrom Bellcore, with a mandate to commercialize the digi-

The computational methods employed ensure that

tal time-stamping technology developed by Bellcore. The authors

only the record in question can be linked, according