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  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  (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  in anonymous payment systems! each of the attacks described above in a heuristic
THE TECHNICAL NEWSLETTER OF RSA LABORATORIES -AUTUMN 1995 CRYPTOBYTES
Previous Page Home Next Page
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  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
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-
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,
. . . we have The construction of Bellare and Rogaway , also April 1988.
seen that there known as Optimal Asymmetric Encryption Padding,  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-  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  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  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
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
Previous Page Home Next Page
Ann. of Math., 126:649-673, 1987.
Crypto ‚Ä˜8.5, pages 18-27, Springer-Verlag, 1986.
 G.L. Miller. Reimann‚Ä™s hypothesis and tests for primality.
 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&  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.
 W. Diffie and M.E. Hellman. New directions in cryptog-  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.
 B. Preneel. Analysis and Design of Cryptographic Hash Func-
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-  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,  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,  RSA Laboratories. PKCS #I: RSA Encryption Standard,
Springer-Verlag, 199 1. Version 1.5, November 1993.
1121  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-  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-  H.C. Williams and B. Schmid. Some remarks concerning
Wesley, Reading, MA., 1981. the MIT public-key cryptosystem. BIT 19, pages 525-
 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.
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-
THE TECHNICAL NEWSLETTER OF RSA LABORATORIES - AUTUMN 1995 CRYPTOBYTES
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.
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  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-
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
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