RFC 3218 (rfc3218) - Page 2 of 7
Preventing the Million Message Attack on Cryptographic Message Syntax
Alternative Format: Original Text Document
RFC 3218 Preventing the Million Message Attack on CMS January 2002 attacker could convince the receiver to act as a particular kind of oracle. (An oracle is a program which answers queries based on information unavailable to the requester (in this case the private key)). The MMA is also possible against [CMS]. Mail list agents are the most likely CMS implementations to be targets for the MMA, since mail list agents are automated servers that 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 the same length as (but numerically 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 transformation. We start with an "encryption block" of the same length as the modulus. The rightmost bytes of the block 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 integer in big-endian form. Thus, the resulting number is less than the modulus (because the first byte is zero), but within a factor of 2^16 (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 8 to 32 bytes. There must be at least 8 bytes of non-zero padding. 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 255^8 (about 2^64) different padding values with high probability two encryptions of the same CEK will be different. The padding also prevents the attacker from verifying guessed CEKs by trial-encrypting them with the recipient's RSA key since he must try each potential Rescorla Informational
