draft-ietf-smime-pkcs1-01.txt   rfc3218.txt 
INTERNET-DRAFT E. Rescorla Network Working Group E. Rescorla
<draft-ietf-smime-pkcs1-01.txt> RTFM, Inc. Request for Comments: 3218 RTFM, Inc.
(September 2001 (Expires March 2002) Category: Informational January 2002
Preventing the Million Message Attack on CMS Preventing the Million Message Attack on
Cryptographic Message Syntax
Status of this Memo Status of this Memo
This document is an Internet-Draft and is in full conformance with This memo provides information for the Internet community. It does
all provisions of Section 10 of RFC2026. Internet-Drafts are working not specify an Internet standard of any kind. Distribution of this
documents of the Internet Engineering Task Force (IETF), its areas, memo is unlimited.
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Copyright Notice
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference mate-
rial or to cite them other than as ``work in progress.''
The list of current Internet-Drafts can be accessed at Copyright (C) The Internet Society (2002). All Rights Reserved.
http://www.ietf.org/1id-abstracts.html
The list of Internet-Draft Shadow Directories can be accessed at Abstract
http://www.ietf.org/shadow.html.
To learn the current status of any Internet-Draft, please check the This memo describes a strategy for resisting the Million Message
``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow Attack.
Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or Table of Contents
ftp.isi.edu (US West Coast).
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 1
2. Overview of PKCS-1 . . . . . . . . . . . . . . . . . . . . . 2
2.1. The Million Message Attack . . . . . . . . . . . . . . . . 3
2.2. Applicability . . . . . . . . . . . . . . . . . . . . . . . 3
2.2.1. Note on Block Cipher Padding . . . . . . . . . . . . . . 4
2.3. Countermeasures . . . . . . . . . . . . . . . . . . . . . . 4
2.3.1. Careful Checking . . . . . . . . . . . . . . . . . . . . 4
2.3.2. Random Filling . . . . . . . . . . . . . . . . . . . . . 5
2.3.3. OAEP . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4. Security Considerations . . . . . . . . . . . . . . . . . . 6
3. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 6
4. References . . . . . . . . . . . . . . . . . . . . . . . . . 6
5. Author's Address. . . . . . . . . . . . . . . . . . . . . . . 6
6. Full Copyright Statement . . . . . . . . . . . . . . . . . . 7
1. Introduction 1. Introduction
When data is encrypted using RSA it must be padded out to the length When data is encrypted using RSA it must be padded out to the length
of the modulus--typically 512 to 2048 bits. The most popular tech- of the modulus -- typically 512 to 2048 bits. The most popular
nique for doing this is described in [PKCS-1-v1.5]. However, in 1998 technique for doing this is described in [PKCS-1-v1.5]. However, in
Bleichenbacher described an adaptive chosen ciphertext attack on SSL 1998 Bleichenbacher described an adaptive chosen ciphertext attack on
[MMA]. This attack, called the Million Message Attack, allowed the SSL [MMA]. This attack, called the Million Message Attack, allowed
recovery of a single PKCS-1 encrypted block, provided that the the recovery of a single PKCS-1 encrypted block, provided that the
attacker could convince the receiver to act as a particular kind of attacker could convince the receiver to act as a particular kind of
oracle. (An oracle is a program which answers queries based on infor- oracle. (An oracle is a program which answers queries based on
mation unavailable to the requester (in this case the private key)). information unavailable to the requester (in this case the private
The MMA is also possible against [CMS]. Mail list agents are the key)). The MMA is also possible against [CMS]. Mail list agents are
most likely CMS implementations to be targets for the MMA, since mail the most likely CMS implementations to be targets for the MMA, since
list agents are automated servers that automatically respond to a mail list agents are automated servers that automatically respond to
large number of messages. This document describes a strategy for a large number of messages. This document describes a strategy for
resisting such attacks. resisting such attacks.
2. Overview of PKCS-1 2. Overview of PKCS-1
The first stage in RSA encryption is to map the message to be The first stage in RSA encryption is to map the message to be
encrypted (in CMS a symmetric Content-Encryption Key (CEK)) into an encrypted (in CMS a symmetric content-encryption key (CEK)) into an
integer the same length as (but numerically less than) the RSA modu- integer the same length as (but numerically less than) the RSA
lus of the recipient's public key (typically somewhere between 512 modulus of the recipient's public key (typically somewhere between
and 2048 bits). PKCS-1 describes the most common procedure for this 512 and 2048 bits). PKCS-1 describes the most common procedure for
transformation. this transformation.
We start with an "encryption block" of the same length as the modu- We start with an "encryption block" of the same length as the
lus. The rightmost bytes of the block are set to the message to be modulus. The rightmost bytes of the block are set to the message to
encrypted. The first two bytes are a zero byte and a "block type" be encrypted. The first two bytes are a zero byte and a "block type"
byte. For encryption the block type is 2. The remaining bytes are byte. For encryption the block type is 2. The remaining bytes are
used as padding. The padding is constructed by generating a series of used as padding. The padding is constructed by generating a series
non-zero random bytes. The last padding byte is zero, which allows of non-zero random bytes. The last padding byte is zero, which
the padding to be distinguished from the message. allows the padding to be distinguished from the message.
|--------------------------------------------------------| +---+---+----------------------+---+---------------------+
| 0 | 2 | Nonzero random bytes | 0 | Message | | 0 | 2 | Nonzero random bytes | 0 | Message |
|--------------------------------------------------------| +---+---+----------------------+---+---------------------+
Once the block has been formatted, the sender must then convert the Once the block has been formatted, the sender must then convert the
block into an integer. This is done by treating the block as an inte- block into an integer. This is done by treating the block as an
ger in big-endian form. Thus, the resulting number is less than the integer in big-endian form. Thus, the resulting number is less than
modulus (because the first byte is zero), but within a factor of 2^16 the modulus (because the first byte is zero), but within a factor of
(because the second byte is 2). 2^16 (because the second byte is 2).
In CMS, the message is always a randomly generated symmetric content- In CMS, the message is always a randomly generated symmetric
encryption key (CEK). Depending on the cipher being used it might be content-encryption key (CEK). Depending on the cipher being used it
anywhere from 8 to 32 bytes. might be anywhere from 8 to 32 bytes.
There must be at least 8 bytes of non-zero padding. The padding pre- There must be at least 8 bytes of non-zero padding. The padding
vents an attacker from verifying guesses about the encrypted message. prevents an attacker from verifying guesses about the encrypted
Imagine that the attacker wishes to determine whether or not two RSA- message. Imagine that the attacker wishes to determine whether or
encrypted keys are the same. Because there are at least 255^8 (about not two RSA-encrypted keys are the same. Because there are at least
2^64) different padding values with high probability two encryptions 255^8 (about 2^64) different padding values with high probability two
of the same message will be different. The padding also prevents the encryptions of the same CEK will be different. The padding also
attacker from verifying guessed CEKs by trial-encrypting them with prevents the attacker from verifying guessed CEKs by trial-encrypting
the recipient's RSA key since he must try each potential pad for them with the recipient's RSA key since he must try each potential
every guess. Note that a lower cost attack would be to exhaustively pad for every guess. Note that a lower cost attack would be to
search the CEK space by trial-decrypting the content and examining exhaustively search the CEK space by trial-decrypting the content and
the plaintext to see if it appears reasonable. examining the plaintext to see if it appears reasonable.
2.1. The Million Message Attack 2.1. The Million Message Attack
The purpose of the Million Message Attack (MMA) is to recover a sin- The purpose of the Million Message Attack (MMA) is to recover a
gle plaintext (formatted block) given the ciphertext (encrypted single plaintext (formatted block) given the ciphertext (encrypted
block). The attacker first captures the ciphertext in transit and block). The attacker first captures the ciphertext in transit and
then uses the recipient as an oracle to recover the plaintext by then uses the recipient as an oracle to recover the plaintext by
sending transformed versions of the ciphertext and observing the sending transformed versions of the ciphertext and observing the
recipient's response. recipient's response.
Call the ciphertext C. The attacker then generates a series of inte- Call the ciphertext C. The attacker then generates a series of
gers S and computes C'=C(S^e) mod n. Upon decryption, C' produces a integers S and computes C'=C*(S^e) mod n. Upon decryption, C'
corresponding plaintext M'. Most values of M' will appear to be produces a corresponding plaintext M'. Most values of M' will appear
garbage but some values of M' (about one in 2^16) will have the cor- to be garbage but some values of M' (about one in 2^16) will have the
rect first two bytes 00 02 and thus appear to be properly PKCS-1 for- correct first two bytes 00 02 and thus appear to be properly PKCS-1
matted. The attack proceeds by finding a sequence of values S such formatted. The attack proceeds by finding a sequence of values S
that the resulting M' is properly PKCS-1 formatted. This information such that the resulting M' is properly PKCS-1 formatted. This
can be used to discover M. Operationally, this attack usually information can be used to discover M. Operationally, this attack
requires about 2^20 messages and responses. Details can be found in usually requires about 2^20 messages and responses. Details can be
[MMA]. found in [MMA].
2.2. Applicability 2.2. Applicability
Since the MMA requires so many messages, it must be mounted against a Since the MMA requires so many messages, it must be mounted against a
victim who is willing to process a large number of messages. In prac- victim who is willing to process a large number of messages. In
tice, no human is willing to read this many messages and so the MMA practice, no human is willing to read this many messages and so the
can only be mounted against an automated victim. MMA can only be mounted against an automated victim.
The MMA also requires that the attacker be able to distinguish cases The MMA also requires that the attacker be able to distinguish cases
where M' was PKCS-1 formatted from cases where it was not. In the where M' was PKCS-1 formatted from cases where it was not. In the
case of CMS the attacker will be sending CMS messages with C' replac- case of CMS the attacker will be sending CMS messages with C'
ing the wrapped CEK. Thus, there are five possibilities: replacing the wrapped CEK. Thus, there are five possibilities:
1. M' is improperly formatted. 1. M' is improperly formatted.
2. M' is properly formatted but the CEK is prima facie bogus 2. M' is properly formatted but the CEK is prima facie bogus (wrong
(wrong length, etc.) length, etc.)
3. M' is properly formatted and the CEK appears OK. A signature 3. M' is properly formatted and the CEK appears OK. A signature or
or MAC is present so integrity checking fails. MAC is present so integrity checking fails.
4. M' is properly formatted and no integrity check is applied. 4. M' is properly formatted and no integrity check is applied. In
In this case there is some possibility (approximately 1/32) that this case there is some possibility (approximately 1/32) that the
the CBC padding block will verify properly. (The actual probability CBC padding block will verify properly. (The actual probability
depends highly on the receiving implementation. See "Note on depends highly on the receiving implementation. See "Note on
Block Cipher Padding" below). The message will Block Cipher Padding" below). The message will appear OK at the
appear OK at the CMS level but will be bogus at the application CMS level but will be bogus at the application level.
level.
5. M' is properly formatted and the resulting CEK is correct. 5. M' is properly formatted and the resulting CEK is correct. This
This is extremely improbable but not impossible. is extremely improbable but not impossible.
The MMA requires the attacker to be able to distinguish case 1 from The MMA requires the attacker to be able to distinguish case 1 from
cases 2-4. (He can always distinguish case 5, of course). This might cases 2-4. (He can always distinguish case 5, of course). This
happen if the victim returned different errors for each case. The might happen if the victim returned different errors for each case.
attacker might also be able to distinguish these cases based on tim- The attacker might also be able to distinguish these cases based on
ing--decrypting the message and verifying the signature takes some timing -- decrypting the message and verifying the signature takes
time. If the victim responds uniformly to all four errors then no some time. If the victim responds uniformly to all four errors then
attack is possible. no attack is possible.
2.2.1. Note on Block Cipher Padding 2.2.1. Note on Block Cipher Padding
[CMS] specifies a particular kind of block cipher padding in which [CMS] specifies a particular kind of block cipher padding in which
the final cipher block is padded with bytes containing the length of the final cipher block is padded with bytes containing the length of
the padding. For instance, a 5-byte block would be padded with three the padding. For instance, a 5-byte block would be padded with three
bytes of value 03, as in: bytes of value 03, as in:
XX XX XX XX XX 03 03 03 XX XX XX XX XX 03 03 03
[CMS] does not specify how this padding is to be removed but merely [CMS] does not specify how this padding is to be removed but merely
observes that it is unambiguous. An implementation might simply get observes that it is unambiguous. An implementation might simply get
the value of the final byte and truncate appropriately or might ver- the value of the final byte and truncate appropriately or might
ify that all the padding bytes are correct. If the receiver simply verify that all the padding bytes are correct. If the receiver
truncates then the probability that a random block will appear to be simply truncates then the probability that a random block will appear
properly padded is roughly 1/8. If the receiver checks all the to be properly padded is roughly 1/32. If the receiver checks all
padding bytes, then the probability is 1/256 + (1/256^2) + ... the padding bytes, then the probability is 1/256 + (1/256^2) + ...
(roughly 1/255). (roughly 1/255).
2.3. Countermeasures 2.3. Countermeasures
2.3.1. Careful Checking 2.3.1. Careful Checking
Even without countermeasures, sufficiently careful checking can go Even without countermeasures, sufficiently careful checking can go
quite a long way to mitigating the success of the MMA. If the quite a long way to mitigating the success of the MMA. If the
receiving implementation also checks the length of the CEK and the receiving implementation also checks the length of the CEK and the
parity bits (if available) AND responds identically to all such parity bits (if available) AND responds identically to all such
errors, the chances of a given M' being properly formatted are sub- errors, the chances of a given M' being properly formatted are
stantially decreased. This increases the number of probe messages substantially decreased. This increases the number of probe messages
required to recover M. However, this sort of checking only increases required to recover M. However, this sort of checking only increases
the workfactor and does not eliminate the attack entirely because the workfactor and does not eliminate the attack entirely because
some messages will still be properly formatted up to the point of some messages will still be properly formatted up to the point of
keylength. However, the combination of all three kinds of checking keylength. However, the combination of all three kinds of checking
(padding, length, parity bits) increases the number of messages to (padding, length, parity bits) increases the number of messages to
the point where the attack is impractical. the point where the attack is impractical.
2.3.2. Random Filling 2.3.2. Random Filling
The simplest countermeasure is to treat misformatted messages as if The simplest countermeasure is to treat misformatted messages as if
they were properly PKCS-1 formatted. When the victim detects an they were properly PKCS-1 formatted. When the victim detects an
improperly formatted message, instead of returning an error he sub- improperly formatted message, instead of returning an error he
stitutes a randomly generated message. In CMS, since the message is substitutes a randomly generated message. In CMS, since the message
always a wrapped content-encryption key (CEK) the victim should sim- is always a wrapped content-encryption key (CEK) the victim should
ply substitute a randomly generated CEK of appropriate length and simply substitute a randomly generated CEK of appropriate length and
continue. Eventually this will result in a decryption or signature continue. Eventually this will result in a decryption or signature
verification error but this is exactly what would have happened if M' verification error but this is exactly what would have happened if M'
happened to be properly formatted but contained an incorrect CEK. happened to be properly formatted but contained an incorrect CEK.
Note that this approach also prevents the attacker from distinguish- Note that this approach also prevents the attacker from
ing various failure cases via timing since all failures return distinguishing various failure cases via timing since all failures
roughly the same timing behavior. (The time required to generate the return roughly the same timing behavior. (The time required to
random-padding is negligible in almost all cases. If an implementa- generate the random-padding is negligible in almost all cases. If an
tion has a very slow PRNG it can generate random padding for every implementation has a very slow PRNG it can generate random padding
message and simply discard it if the CEK decrypts correctly). for every message and simply discard it if the CEK decrypts
correctly).
In a layered implementation it's quite possible that the PKCS-1 check In a layered implementation it's quite possible that the PKCS-1 check
occurs at a point in the code where the length of the expected CEK is occurs at a point in the code where the length of the expected CEK is
not known. In that case the implementation must ensure that bad not known. In that case the implementation must ensure that bad
PKCS-1 padding and ok-looking PKCS-1 padding with an incorrect length PKCS-1 padding and ok-looking PKCS-1 padding with an incorrect length
CEK behave the same. An easy way to do this is to also randomize CEKs CEK behave the same. An easy way to do this is to also randomize
that are of the wrong length or otherwise improperly formatted when CEKs that are of the wrong length or otherwise improperly formatted
they are processed at the layer that knows the length. when they are processed at the layer that knows the length.
Note: It is a mistake to use a fixed CEK because the attacker could Note: It is a mistake to use a fixed CEK because the attacker could
then produce a CMS message encrypted with that CEK. This message then produce a CMS message encrypted with that CEK. This message
would decrypt properly (i.e. appear to be a completely valid CMS would decrypt properly (i.e. appear to be a completely valid CMS
application to the receiver), thus allowing the attacker to determine application to the receiver), thus allowing the attacker to determine
that the PKCS-1 formatting was incorrect. In fact, the new CEK that the PKCS-1 formatting was incorrect. In fact, the new CEK
should be cryptographically random, thus preventing the attacker from should be cryptographically random, thus preventing the attacker from
guessing the next "random" CEK to be used. guessing the next "random" CEK to be used.
2.3.3. OAEP 2.3.3. OAEP
Optimal Asymmetric Encryption Padding (OAEP) [OAEP, PKCS-1-v2] is Optimal Asymmetric Encryption Padding (OAEP) [OAEP, PKCS-1-v2] is
another technique for padding a message into an RSA encryption block. another technique for padding a message into an RSA encryption block.
Implementations using OAEP are not susceptible to the MMA. However, Implementations using OAEP are not susceptible to the MMA. However,
OAEP is incompatible with PKCS-1. Implementations of S/MIME and CMS OAEP is incompatible with PKCS-1. Implementations of S/MIME and CMS
must therefore continue to use PKCS-1 for the foreseeable future if must therefore continue to use PKCS-1 for the foreseeable future if
they wish to communicate with current widely deployed implementa- they wish to communicate with current widely deployed
tions. OAEP is being specified for use with AES keys in CMS so this implementations. OAEP is being specified for use with AES keys in
provides an upgrade path to OAEP. CMS so this provides an upgrade path to OAEP.
2.4. Security Considerations 2.4. Security Considerations
This entire document describes how to avoid a certain class of This entire document describes how to avoid a certain class of
attacks when performing PKCS-1 decryption with RSA. attacks when performing PKCS-1 decryption with RSA.
Acknowledgments 3. Acknowledgments
Thanks to Burt Kaliski and Russ Housley for their extensive and help- Thanks to Burt Kaliski and Russ Housley for their extensive and
ful comments. helpful comments.
References 4. References
CMS Housley, R., "Cryptographic Message Syntax", RFC 2630,
[CMS] Housley, R., "Cryptographic Message Syntax", RFC 2630,
June 1999. June 1999.
MMA Bleichenbacher, D., "Chosen Ciphertext Attacks against [MMA] Bleichenbacher, D., "Chosen Ciphertext Attacks against
Protocols based on RSA Encryption Standard PKCS #1", Protocols based on RSA Encryption Standard PKCS #1",
Advances in Cryptology -- CRYPTO 98. Advances in Cryptology -- CRYPTO 98.
MMAUPDATE D. Bleichenbacher, B. Kaliski, and J. Staddon, "Recent [MMAUPDATE] D. Bleichenbacher, B. Kaliski, and J. Staddon, "Recent
Results on PKCS #1: RSA Encryption Standard", Results on PKCS #1: RSA Encryption Standard", RSA
RSA Laboratories' Bulletin #7, June 26, 1998. Laboratories' Bulletin #7, June 26, 1998.
OAEP Bellare, M., Rogaway, P., "Optimal Asymmetric Encryption [OAEP] Bellare, M., Rogaway, P., "Optimal Asymmetric
Padding", Advances in Cryptology -- Eurocrypt 94. Encryption Padding", Advances in Cryptology --
Eurocrypt 94.
PKCS-1-v1.5 Kaliski, B., "PKCS #1: RSA Encryption, Version 1.5.", [PKCS-1-v1.5] Kaliski, B., "PKCS #1: RSA Encryption, Version 1.5.",
RFC 2313, March 1998. RFC 2313, March 1998.
PKCS-1-v2 Kaliski, B., "PKCS #1: RSA Encryption, Version 2.0", [PKCS-1-v2] Kaliski, B., "PKCS #1: RSA Encryption, Version 2.0",
RFC 2347, October 1998. RFC 2347, October 1998.
Author's Address 5. Author's Address
Eric Rescorla <ekr@rtfm.com>
RTFM, Inc.
2064 Edgewood Drive
Palo Alto, CA 94303
Phone: (650) 320-8549
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Eric Rescorla
2. Overview of PKCS-1 . . . . . . . . . . . . . . . . . . . . . . . 1 RTFM, Inc.
2.1. The Million Message Attack . . . . . . . . . . . . . . . . . . 2 2064 Edgewood Drive
2.2. Applicability . . . . . . . . . . . . . . . . . . . . . . . . . 3 Palo Alto, CA 94303
2.2.1. Note on Block Cipher Padding . . . . . . . . . . . . . . . . 3
2.3. Countermeasures . . . . . . . . . . . . . . . . . . . . . . . . 4 Phone: (650) 320-8549
2.3.1. Careful Checking . . . . . . . . . . . . . . . . . . . . . . 4 EMail: ekr@rtfm.com
2.3.2. Random Filling . . . . . . . . . . . . . . . . . . . . . . . 4
2.3.3. OAEP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 6. Full Copyright Statement
2.4. Security Considerations . . . . . . . . . . . . . . . . . . . . 5
2.4. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . 5 Copyright (C) The Internet Society (2002). All Rights Reserved.
2.4. References . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . . 6 This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
 End of changes. 42 change blocks. 
156 lines changed or deleted 161 lines changed or added

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/