Preventing the Million Message Attack on Cryptographic Message Syntax
RFC 3218

Document Type RFC - Informational (January 2002; Errata)
Last updated 2017-07-26
Stream IETF
Formats plain text html pdf htmlized with errata bibtex
Stream WG state (None)
Document shepherd No shepherd assigned
IESG IESG state RFC 3218 (Informational)
Consensus Boilerplate Unknown
Telechat date
Responsible AD (None)
Send notices to (None)
Network Working Group                                        E. Rescorla
Request for Comments: 3218                                    RTFM, Inc.
Category: Informational                                     January 2002

                Preventing the Million Message Attack on
                      Cryptographic Message Syntax

Status of this Memo

   This memo provides information for the Internet community.  It does
   not specify an Internet standard of any kind.  Distribution of this
   memo is unlimited.

Copyright Notice

   Copyright (C) The Internet Society (2002).  All Rights Reserved.

Abstract

   This memo describes a strategy for resisting the Million Message
   Attack.

Table of Contents

   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

   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
   technique for doing this is described in [PKCS-1-v1.5].  However, in
   1998 Bleichenbacher 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

Rescorla                     Informational                      [Page 1]
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                      [Page 2]
Show full document text