INTERNET-DRAFT E. Rescorla RTFM, Inc. (March 2000 (Expires September 2001) Preventing the Million Message Attack on CMS Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, 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 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.'' To learn the current status of any Internet-Draft, please check the ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). 1. Introduction When data is encrypted using RSA it must be padded out to the length of the modulus--typically 512 to 2048 bits. he most popular tech- nique for doing this is described in [PKCS-1]. However, in 1998 Ble- ichenbacher described an adaptive chosen ciphertext attack on SSL [MMA]. This attack, called the Million Message Attack, allowed the recovery of a single PKCS-1 encrypted block, provided that the attacker could convince the receiver to act as a particular kind of oracle. The MMA is also possible against [CMS]. The CMS implementa- tions most likely to be targets for the MMA are automated servers such as mailing list agents, which will automatically respond to a large number of messages. This document describes a strategy for resisting such attacks. 2. Overview of PKCS-1 The first stage in RSA encryption is to map the message to be encrypted (in CMS a symmetric Content Encryption Key (CEK)) into an integer of the same order as (but less than) the RSA modulus of the recipient's public key (typically somewhere between 512 and 2048 bits). PKCS-1 describes the most common procedure for this transfor- mation. Rescorla [Page 1] Internet-Draft Security Considerations Guidelines We start with an "encryption block" of the same length as the modu- lus. The rightmost bits of the string are set to the message to 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 used as padding. The padding is constructed by generating a series of non-zero random bytes. The last padding byte is zero, which allows the padding to be distinguished from the message. |--------------------------------------------------------| | 0 | 2 | Nonzero random bytes | 0 | Message | |--------------------------------------------------------| 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- ger in big-endian form. Thus, the resulting number is less than the modulus (because the first byte is zero), but of more or less the same order (because the second byte is 2). In CMS, the message is always a randomly generated symmetric content encryption key (CEK). Depending on the cipher being used it might be anywhere from 64 to 256 bytes. There must be at least 8 bytes of non-random. The padding prevents an attacker from verifying guesses about the encrypted message. Imagine that the attacker wishes to determine whether or not two RSA- encrypted keys are the same. Because there are at least 2^64 differ- ent padding value with high probability two encryptions of the same message will be different. The padding also prevents the attacker from verifying guessed CEKs by trial-encrypting them with the recipi- ent's RSA key since he must try each potential pad for every guess. Note that a lower cost attack would be to exhaustively search the CEK space by trial-decrypting the content and examining the plaintext to see if it appears reasonable. 2.1. The Million Message Attack The purpose of the Million Message Attack (MMA) is to recover a sin- gle plaintext given the ciphertext. The attacker first captures the ciphertext in transit and then uses the recipient as an oracle to recover the plaintext by sending transformed versions of the cipher- text and observing the recipient's response. Call the ciphertext C. The attacker then generates a series of inte- gers S and computes C'=C(S^e) mod n. Upon decryption, C' produces a corresponding plaintext M'. Most M's will appear to be garbage but some M's (about one in 2^16) will have the correct first two bytes 00 02 and thus appear to be correctly PKCS-1 formatted. The attack pro- ceeds by finding a sequence of values S such that the resulting M' is Rescorla [Page 2] Internet-Draft Security Considerations Guidelines correctly PKCS-1 formatted. This information can be used to discover M. Operationally, this attack usually requires about 2^20 messages and responses. Details can be found in [MMA]. 2.2. Applicability 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- tice, no human is willing to read this many messages and so the MMA can only be mounted against an automated victim. 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 case of CMS the attacker will be sending CMS messages with M' replac- ing the wrapped CEK. Thus, there are five possibilities: 1. M' is improperly formatted. 2. M' is properly formatted but the CEK is prima facie bogus (wrong length, etc.) 3. M' is properly formatted and the CEK appears OK. A signature or MAC is present so integrity checking fails. 4. M' is properly formatted and no integrity check is applied. In this case there is some possibility (approximately 1/8) that the CBC padding block will verify correctly. The message will appear OK at the CMS level but will be bogus at the application level. 5. M' is properly formatted and the resulting CEK is correct. This is extremely improbable but not impossible. 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 happen if the victim returned different errors for each case. The attacker might also be able to distinguish these cases based on tim- ing--decrypting the message and verifying the signature takes some time. If the victim responds uniformly to all four errors then no attack is possible. 2.3. Countermeasures 2.3.1. Careful Checking Even without countermeasures, sufficiently careful checking can go quite a long way to mitigating the success of the MMA. If the receiving implementation also checks the length of the CEK and the parity bits (if available) AND responds identically to all such errors, the chances of a given M' being correctly formatted are sub- stantially decreased. This increases the number of probe messages Rescorla [Page 3] Internet-Draft Security Considerations Guidelines required to recover M. However, this sort of checking only increases the workfactor and does not eliminate the attack entirely because some messages will still be correctly formatted up to the point of keylength. However, the combination of all three kinds of checking (padding, length, parity bits) increases the number of messages to the point where the attack is impractical. 2.3.2. Random Filling The simplest countermeasure is to treat misformatted messages as if they were correctly PKCS-1 formatted. When the victim detects an incorrectly formatted message, instead of returning an error he sub- stitutes a randomly generated message. In CMS, since the message is always a wrapped content encryption key (CEK) the victm should simply substitute a randomly generated CEK of appropriate length and con- tinue. Eventually this will result in a decryption or signature veri- fication error but this is exactly what would have happened if M' happened to be correctly formatted. Note that the timing behavior will also identical. 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 not known. In that case the implementation must ensure that bad 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 that are of the wrong length or otherwise improperly formatted. 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 would decrypt correctly, thus allowing the attacker to determine that the PKCS-1 formatting was incorrect. In fact, the randomly generated CEK should be cryptographically random, thus preventing the attacker from guessing the next "random" CEK to be used. 2.3.3. OAEP Optimal Asymmetric Encryption Padding (OAEP) [OAEP, PKCS1v2] is another technique for padding a message into an RSA encryption block. Implementations using OAEP are not susceptible to the MMA. However, OAEP is incompatible with PKCS-1. Implementations of S/MIME and CMS must therefore continue to use PKCS-1 for the foreseable future. 2.4. Security Considerations This entire document describes how to avoid a certain class of attacks when performing PKCS-1 decryption with RSA. Rescorla [Page 4] Internet-Draft Security Considerations Guidelines References [PKCS-1] [MMA] [CMS] Author's Address Eric Rescorla RTFM, Inc. 2439 Alvin Drive Mountain View, CA 94043 Phone: (650) 314-0116 Rescorla [Page 5] Internet-Draft Security Considerations Guidelines Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2. Overview of PKCS-1 . . . . . . . . . . . . . . . . . . . . . . . 1 2.1. The Million Message Attack . . . . . . . . . . . . . . . . . . 2 2.2. Applicability . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3. Countermeasures . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3.1. Careful Checking . . . . . . . . . . . . . . . . . . . . . . 3 2.3.2. Random Filling . . . . . . . . . . . . . . . . . . . . . . . 4 2.3.3. OAEP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.4. Security Considerations . . . . . . . . . . . . . . . . . . . . 4 2.4. References . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . . 5