Network Working Group E. Rescorla
Request for Comments: 3218 RTFM, Inc.
Category: Informational January 2002
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.
版权所有（C）互联网协会（2002年）。版权所有。
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 . . . . . . . . . . . . . . . . . . . . . . . . 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
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
使用RSA加密数据时，必须将其填充到模的长度——通常为512到2048位。[PKCS-1-v1.5]中介绍了最常用的技术。然而，在1998年，Bleichenbacher描述了一种针对SSL[MMA]的自适应选择密文攻击。此攻击称为百万消息攻击，允许恢复单个PKCS-1加密块，前提是
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.
攻击者可以说服接收者充当一种特殊的甲骨文。（oracle是一个基于请求者不可用的信息（在本例中为私钥）回答查询的程序）。MMA也可以针对[CMS]。邮件列表代理是最有可能成为MMA目标的CMS实现，因为邮件列表代理是自动响应大量邮件的自动化服务器。本文档描述了抵御此类攻击的策略。
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.
RSA加密的第一个阶段是将要加密的消息（在CMS中为对称内容加密密钥（CEK））映射为一个整数，该整数的长度与收件人公钥的RSA模数（通常介于512和2048位之间）相同（但数值小于）。PKCS-1描述了此转换的最常见过程。
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.
我们从一个与模数长度相同的“加密块”开始。块的最右边字节被设置为要加密的消息。前两个字节是零字节和“块类型”字节。对于加密，块类型为2。剩余的字节用作填充。填充是通过生成一系列非零随机字节来构造的。最后一个填充字节为零，这允许将填充与消息区分开来。
+---+---+----------------------+---+---------------------+
| 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 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).
格式化块后，发送方必须将块转换为整数。这是通过将块视为大端形式的整数来实现的。因此，得到的数字小于模数（因为第一个字节为零），但在2^16的系数范围内（因为第二个字节为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.
在CMS中，消息始终是随机生成的对称内容加密密钥（CEK）。根据所使用的密码，它可能在8到32字节之间。
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
必须至少有8个字节的非零填充。填充可防止攻击者验证对加密消息的猜测。假设攻击者希望确定两个RSA加密密钥是否相同。因为至少有255^8（大约2^64）个不同的填充值，同一CEK的两种加密很可能会不同。填充还可以防止攻击者通过使用收件人的RSA密钥对猜测的CEK进行加密来验证这些CEK，因为他必须尝试每个潜在的CEK
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.
为每一个猜测做准备。请注意，一种成本较低的攻击是通过尝试解密内容并检查明文来彻底搜索CEK空间，看看它是否合理。
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.
百万消息攻击（MMA）的目的是在给定密文（加密块）的情况下恢复单个明文（格式化块）。攻击者首先捕获传输中的密文，然后将收件人用作oracle，通过发送转换后的密文版本并观察收件人的响应来恢复明文。
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].
调用密文C。然后攻击者生成一系列整数S并计算C'=C*（S^e）mod n。解密后，C'产生相应的明文M'。M'的大多数值看起来都是垃圾，但M'的一些值（大约2^16中的一个）的前两个字节00 02正确，因此看起来是正确的PKCS-1格式。攻击通过查找一系列值S进行，从而使生成的M'正确地格式化为PKCS-1。该信息可用于发现M。在操作上，该攻击通常需要大约2^20条消息和响应。有关详细信息，请参见[MMA]。
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.
由于MMA需要如此多的消息，因此必须针对愿意处理大量消息的受害者安装MMA。实际上，没有人愿意阅读这么多信息，因此MMA只能针对自动受害者安装。
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:
MMA还要求攻击者能够区分M'是PKCS-1格式的情况和不是PKCS-1格式的情况。在CMS的情况下，攻击者将发送带有C'替换包装的CEK的CMS消息。因此，有五种可能性：
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.
1. M'的格式不正确。2.M'格式正确，但CEK表面上是伪造的（长度错误等）。M'格式正确，CEK显示正常。存在签名或MAC，因此完整性检查失败。4.M'格式正确，未应用完整性检查。在这种情况下，CBC垫块可能会正确验证（约1/32）。（实际概率在很大程度上取决于接收实现。请参阅下面的“关于分组密码填充的注意事项”）。该消息在CMS级别上显示正常，但在应用程序级别上显示虚假。
5. M' is properly formatted and the resulting CEK is correct. This is extremely improbable but not impossible.
5. M'格式正确，生成的CEK正确。这是极不可能的，但并非不可能。
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.
MMA要求攻击者能够区分案例1和案例2-4。（当然，他总能分辨出案例5）。如果受害者针对每个案例返回不同的错误，则可能会发生这种情况。攻击者还可以根据时间区分这些情况——解密消息和验证签名需要一些时间。如果受害者对所有四个错误做出一致的反应，则不可能进行攻击。
[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:
[CMS]指定一种特殊的分组密码填充，其中最后一个密码块用包含填充长度的字节填充。例如，一个5字节的块将填充三个值为03的字节，如下所示：
XX XX XX XX XX 03 03 03
XX XX XX XX XX 03 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).
[CMS]未指定如何移除此填充，但仅观察到它是明确的。实现可能只是获取最后一个字节的值并进行适当的截断，或者验证所有填充字节是否正确。如果接收器只是截断，那么随机块被适当填充的概率大约为1/32。如果接收器检查所有填充字节，则概率为1/256+（1/256^2）+。。。（大约1/255）。
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.
即使没有对策，足够仔细的检查也会大大降低MMA的成功率。如果接收实现还检查CEK和奇偶校验位的长度（如果可用）并对所有此类错误做出相同的响应，则给定M’被正确格式化的机会将大大降低。这增加了恢复M所需的探测消息的数量。但是，这种检查只会增加工作系数，并不能完全消除攻击，因为某些消息的格式仍然正确，直到keylength。但是，所有三种检查（填充、长度、奇偶校验位）的组合会增加消息数量，使攻击变得不切实际。
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).
最简单的对策是将格式错误的消息视为PKCS-1格式正确。当受害者检测到格式不正确的消息时，他不是返回错误，而是替换随机生成的消息。在CMS中，由于消息始终是一个包装的内容加密密钥（CEK），受害者只需替换一个适当长度的随机生成的CEK并继续。最终，这将导致解密或签名验证错误，但这正是如果M'恰好格式正确但包含不正确的CEK时会发生的情况。请注意，这种方法还可以防止攻击者通过计时来区分各种故障情况，因为所有故障都返回大致相同的计时行为。（几乎在所有情况下，生成随机填充所需的时间都可以忽略不计。如果实现的PRNG非常慢，那么它可以为每条消息生成随机填充，如果CEK正确解密，则只需丢弃它）。
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.
在分层实现中，PKCS-1检查很可能发生在代码中预期CEK长度未知的点上。在这种情况下，实现必须确保错误的PKCS-1填充和具有错误长度CEK的外观正常的PKCS-1填充行为相同。一种简单的方法是，当在知道长度的层上处理长度错误或格式不正确的CEK时，也将其随机化。
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.
注意：使用固定的CEK是错误的，因为攻击者随后可能会生成使用该CEK加密的CMS消息。此消息将正确解密（即，对接收方而言，它似乎是完全有效的CMS应用程序），从而允许攻击者确定PKCS-1格式不正确。事实上，新的CEK应该是加密随机的，从而防止攻击者猜测下一个要使用的“随机”CEK。
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.
最佳非对称加密填充（OAEP）[OAEP，PKCS-1-v2]是将消息填充到RSA加密块中的另一种技术。使用OAEP的实现不受MMA的影响。但是，OAEP与PKCS-1不兼容。因此，S/MIME和CMS的实现必须在可预见的未来继续使用PKCS-1，如果它们希望与当前广泛部署的实现通信的话。OAEP被指定用于CMS中的AES密钥，因此这提供了到OAEP的升级路径。
This entire document describes how to avoid a certain class of attacks when performing PKCS-1 decryption with RSA.
整个文档描述了如何在使用RSA执行PKCS-1解密时避免某种类型的攻击。
Thanks to Burt Kaliski and Russ Housley for their extensive and helpful comments.
感谢Burt Kaliski和Russ Housley的广泛和有益的评论。
[CMS] Housley, R., "Cryptographic Message Syntax", RFC 2630, June 1999.
[CMS]Housley，R.，“加密消息语法”，RFC 2630，1999年6月。
[MMA] Bleichenbacher, D., "Chosen Ciphertext Attacks against Protocols based on RSA Encryption Standard PKCS #1", Advances in Cryptology -- CRYPTO 98.
[MMA]Bleichenbacher，D.，“针对基于RSA加密标准PKCS#1的协议的选择密文攻击”，密码学进展——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.
[MMAUPDATE]D.Bleichenbacher，B.Kaliski和J.Staddon，“PKCS#1：RSA加密标准的最新结果”，RSA实验室公告7，1998年6月26日。
[OAEP] Bellare, M., Rogaway, P., "Optimal Asymmetric Encryption Padding", Advances in Cryptology -- Eurocrypt 94.
[OAEP]Bellare，M.，Rogaway，P.，“最优非对称加密填充”，密码学进展——欧洲密码94。
[PKCS-1-v1.5] Kaliski, B., "PKCS #1: RSA Encryption, Version 1.5.", RFC 2313, March 1998.
[PKCS-1-v1.5]Kaliski，B.，“PKCS#1:RSA加密，版本1.5.”，RFC 2313，1998年3月。
[PKCS-1-v2] Kaliski, B., "PKCS #1: RSA Encryption, Version 2.0", RFC 2347, October 1998.
[PKCS-1-v2]Kaliski，B.，“PKCS#1:RSA加密，2.0版”，RFC 2347，1998年10月。
Eric Rescorla RTFM, Inc. 2064 Edgewood Drive Palo Alto, CA 94303
Eric Rescorla RTFM，Inc.加利福尼亚州帕洛阿尔托埃奇伍德大道2064号，邮编94303
Phone: (650) 320-8549 EMail: ekr@rtfm.com
电话：（650）320-8549电子邮件：ekr@rtfm.com
Copyright (C) The Internet Society (2002). All Rights Reserved.
版权所有（C）互联网协会（2002年）。版权所有。
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.
RFC编辑功能的资金目前由互联网协会提供。