doc: Add RFC documents

1 files changed, 395 insertions, 0 deletions

diff --git a/doc/rfc/rfc3218.txt b/doc/rfc/rfc3218.txt
new file mode 100644
index 0000000..0b64b70
--- /dev/null
+++ b/doc/rfc/rfc3218.txt
@@ -0,0 +1,395 @@
+
+
+
+
+
+
+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]
+
+RFC 3218      Preventing the Million Message Attack on CMS  January 2002
+
+
+   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
+   single plaintext (formatted block) given the ciphertext (encrypted
+   block).  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 ciphertext and observing the
+   recipient's response.
+
+   Call the ciphertext C. The attacker then generates a series of
+   integers S and computes C'=C*(S^e) mod n.  Upon decryption, C'
+   produces a corresponding plaintext M'.  Most values of M' will appear
+   to be garbage but some values of M' (about one in 2^16) will have the
+   correct first two bytes 00 02 and thus appear to be properly PKCS-1
+   formatted.  The attack proceeds by finding a sequence of values S
+   such that the resulting M' is properly 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
+   practice, 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 C'
+   replacing 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/32) that the
+      CBC padding block will verify properly.  (The actual probability
+      depends highly on the receiving implementation.  See "Note on
+      Block Cipher Padding" below).  The message will appear OK at the
+      CMS level but will be bogus at the application level.
+
+
+
+
+Rescorla                     Informational                      [Page 3]
+
+RFC 3218      Preventing the Million Message Attack on CMS  January 2002
+
+
+   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
+   timing -- 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.2.1.  Note on Block Cipher Padding
+
+   [CMS] specifies a particular kind of block cipher padding in which
+   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
+   bytes of value 03, as in:
+
+     XX XX XX XX XX 03 03 03
+
+   [CMS] does not specify how this padding is to be removed but merely
+   observes that it is unambiguous.  An implementation might simply get
+   the value of the final byte and truncate appropriately or might
+   verify that all the padding bytes are correct.  If the receiver
+   simply truncates then the probability that a random block will appear
+   to be properly padded is roughly 1/32.  If the receiver checks all
+   the padding bytes, then the probability is 1/256 + (1/256^2) + ...
+   (roughly 1/255).
+
+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 properly formatted are
+   substantially decreased.  This increases the number of probe messages
+   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 properly 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.
+
+
+
+
+
+
+Rescorla                     Informational                      [Page 4]
+
+RFC 3218      Preventing the Million Message Attack on CMS  January 2002
+
+
+2.3.2.  Random Filling
+
+   The simplest countermeasure is to treat misformatted messages as if
+   they were properly PKCS-1 formatted.  When the victim detects an
+   improperly formatted message, instead of returning an error he
+   substitutes a randomly generated message.  In CMS, since the message
+   is always a wrapped content-encryption key (CEK) the victim should
+   simply substitute a randomly generated CEK of appropriate length and
+   continue.  Eventually this will result in a decryption or signature
+   verification error but this is exactly what would have happened if M'
+   happened to be properly formatted but contained an incorrect CEK.
+   Note that this approach also prevents the attacker from
+   distinguishing various failure cases via timing since all failures
+   return roughly the same timing behavior.  (The time required to
+   generate the random-padding is negligible in almost all cases.  If an
+   implementation has a very slow PRNG it can generate random padding
+   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
+   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
+   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
+   then produce a CMS message encrypted with that CEK.  This message
+   would decrypt properly (i.e. appear to be a completely valid CMS
+   application to the receiver), thus allowing the attacker to determine
+   that the PKCS-1 formatting was incorrect.  In fact, the new 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, PKCS-1-v2] 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 foreseeable future if
+   they wish to communicate with current widely deployed
+   implementations.  OAEP is being specified for use with AES keys in
+   CMS so this provides an upgrade path to OAEP.
+
+
+
+
+
+
+Rescorla                     Informational                      [Page 5]
+
+RFC 3218      Preventing the Million Message Attack on CMS  January 2002
+
+
+2.4.  Security Considerations
+
+   This entire document describes how to avoid a certain class of
+   attacks when performing PKCS-1 decryption with RSA.
+
+3.  Acknowledgments
+
+   Thanks to Burt Kaliski and Russ Housley for their extensive and
+   helpful comments.
+
+4.  References
+
+   [CMS]         Housley, R., "Cryptographic Message Syntax", RFC 2630,
+                 June 1999.
+
+   [MMA]         Bleichenbacher, D., "Chosen Ciphertext Attacks against
+                 Protocols based on RSA Encryption Standard PKCS #1",
+                 Advances in Cryptology -- CRYPTO 98.
+
+   [MMAUPDATE]   D. Bleichenbacher, B. Kaliski, and J. Staddon, "Recent
+                 Results on PKCS #1: RSA Encryption Standard", RSA
+                 Laboratories' Bulletin #7, June 26, 1998.
+
+   [OAEP]        Bellare, M., Rogaway, P., "Optimal Asymmetric
+                 Encryption Padding", Advances in Cryptology --
+                 Eurocrypt 94.
+
+   [PKCS-1-v1.5] Kaliski, B., "PKCS #1: RSA Encryption, Version 1.5.",
+                 RFC 2313, March 1998.
+
+   [PKCS-1-v2]   Kaliski, B., "PKCS #1: RSA Encryption, Version 2.0",
+                 RFC 2347, October 1998.
+
+5.  Author's Address
+
+   Eric Rescorla
+   RTFM, Inc.
+   2064 Edgewood Drive
+   Palo Alto, CA 94303
+
+   Phone: (650) 320-8549
+   EMail: ekr@rtfm.com
+
+
+
+
+
+
+
+
+
+Rescorla                     Informational                      [Page 6]
+
+RFC 3218      Preventing the Million Message Attack on CMS  January 2002
+
+
+6.  Full Copyright Statement
+
+   Copyright (C) The Internet Society (2002).  All Rights Reserved.
+
+   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.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Rescorla                     Informational                      [Page 7]
+