idnits 2.17.1 draft-ietf-smime-pkcs1-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Abstract section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'OAEP' is mentioned on line 181, but not defined == Missing Reference: 'PKCS1v2' is mentioned on line 181, but not defined -- Possible downref: Non-RFC (?) normative reference: ref. 'PKCS-1' -- Possible downref: Non-RFC (?) normative reference: ref. 'MMA' -- Possible downref: Non-RFC (?) normative reference: ref. 'CMS' Summary: 8 errors (**), 0 flaws (~~), 3 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET-DRAFT E. Rescorla 2 RTFM, Inc. 3 (March 2000 (Expires September 2001) 5 Preventing the Million Message Attack on CMS 7 Status of this Memo 9 This document is an Internet-Draft and is in full conformance with 10 all provisions of Section 10 of RFC2026. Internet-Drafts are working 11 documents of the Internet Engineering Task Force (IETF), its areas, 12 and its working groups. Note that other groups may also distribute 13 working documents as Internet-Drafts. 15 Internet-Drafts are draft documents valid for a maximum of six months 16 and may be updated, replaced, or obsoleted by other documents at any 17 time. It is inappropriate to use Internet-Drafts as reference mate- 18 rial or to cite them other than as ``work in progress.'' 20 To learn the current status of any Internet-Draft, please check the 21 ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow 22 Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), 23 munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or 24 ftp.isi.edu (US West Coast). 26 1. Introduction 28 When data is encrypted using RSA it must be padded out to the length 29 of the modulus--typically 512 to 2048 bits. he most popular tech- 30 nique for doing this is described in [PKCS-1]. However, in 1998 Ble- 31 ichenbacher described an adaptive chosen ciphertext attack on SSL 32 [MMA]. This attack, called the Million Message Attack, allowed the 33 recovery of a single PKCS-1 encrypted block, provided that the 34 attacker could convince the receiver to act as a particular kind of 35 oracle. The MMA is also possible against [CMS]. The CMS implementa- 36 tions most likely to be targets for the MMA are automated servers 37 such as mailing list agents, which will automatically respond to a 38 large number of messages. This document describes a strategy for 39 resisting such attacks. 41 2. Overview of PKCS-1 43 The first stage in RSA encryption is to map the message to be 44 encrypted (in CMS a symmetric Content Encryption Key (CEK)) into an 45 integer of the same order as (but less than) the RSA modulus of the 46 recipient's public key (typically somewhere between 512 and 2048 47 bits). PKCS-1 describes the most common procedure for this transfor- 48 mation. 50 We start with an "encryption block" of the same length as the modu- 51 lus. The rightmost bits of the string are set to the message to be 52 encrypted. The first two bytes are a zero byte and a "block type" 53 byte. For encryption the block type is 2. The remaining bytes are 54 used as padding. The padding is constructed by generating a series of 55 non-zero random bytes. The last padding byte is zero, which allows 56 the padding to be distinguished from the message. 58 |--------------------------------------------------------| 59 | 0 | 2 | Nonzero random bytes | 0 | Message | 60 |--------------------------------------------------------| 62 Once the block has been formatted, the sender must then convert the 63 block into an integer. This is done by treating the block as an inte- 64 ger in big-endian form. Thus, the resulting number is less than the 65 modulus (because the first byte is zero), but of more or less the 66 same order (because the second byte is 2). 68 In CMS, the message is always a randomly generated symmetric content 69 encryption key (CEK). Depending on the cipher being used it might be 70 anywhere from 64 to 256 bytes. 72 There must be at least 8 bytes of non-random. The padding prevents an 73 attacker from verifying guesses about the encrypted message. Imagine 74 that the attacker wishes to determine whether or not two RSA- 75 encrypted keys are the same. Because there are at least 2^64 differ- 76 ent padding value with high probability two encryptions of the same 77 message will be different. The padding also prevents the attacker 78 from verifying guessed CEKs by trial-encrypting them with the recipi- 79 ent's RSA key since he must try each potential pad for every guess. 80 Note that a lower cost attack would be to exhaustively search the CEK 81 space by trial-decrypting the content and examining the plaintext to 82 see if it appears reasonable. 84 2.1. The Million Message Attack 86 The purpose of the Million Message Attack (MMA) is to recover a sin- 87 gle plaintext given the ciphertext. The attacker first captures the 88 ciphertext in transit and then uses the recipient as an oracle to 89 recover the plaintext by sending transformed versions of the cipher- 90 text and observing the recipient's response. 92 Call the ciphertext C. The attacker then generates a series of inte- 93 gers S and computes C'=C(S^e) mod n. Upon decryption, C' produces a 94 corresponding plaintext M'. Most M's will appear to be garbage but 95 some M's (about one in 2^16) will have the correct first two bytes 00 96 02 and thus appear to be correctly PKCS-1 formatted. The attack pro- 97 ceeds by finding a sequence of values S such that the resulting M' is 98 correctly PKCS-1 formatted. This information can be used to discover 99 M. Operationally, this attack usually requires about 2^20 messages 100 and responses. Details can be found in [MMA]. 102 2.2. Applicability 104 Since the MMA requires so many messages, it must be mounted against a 105 victim who is willing to process a large number of messages. In prac- 106 tice, no human is willing to read this many messages and so the MMA 107 can only be mounted against an automated victim. 109 The MMA also requires that the attacker be able to distinguish cases 110 where M' was PKCS-1 formatted from cases where it was not. In the 111 case of CMS the attacker will be sending CMS messages with M' replac- 112 ing the wrapped CEK. Thus, there are five possibilities: 114 1. M' is improperly formatted. 115 2. M' is properly formatted but the CEK is prima facie bogus 116 (wrong length, etc.) 117 3. M' is properly formatted and the CEK appears OK. A signature 118 or MAC is present so integrity checking fails. 119 4. M' is properly formatted and no integrity check is applied. 120 In this case there is some possibility (approximately 1/8) that 121 the CBC padding block will verify correctly. The message will 122 appear OK at the CMS level but will be bogus at the application 123 level. 124 5. M' is properly formatted and the resulting CEK is correct. 125 This is extremely improbable but not impossible. 127 The MMA requires the attacker to be able to distinguish case 1 from 128 cases 2-4. (He can always distinguish case 5, of course). This might 129 happen if the victim returned different errors for each case. The 130 attacker might also be able to distinguish these cases based on tim- 131 ing--decrypting the message and verifying the signature takes some 132 time. If the victim responds uniformly to all four errors then no 133 attack is possible. 135 2.3. Countermeasures 137 2.3.1. Careful Checking 139 Even without countermeasures, sufficiently careful checking can go 140 quite a long way to mitigating the success of the MMA. If the 141 receiving implementation also checks the length of the CEK and the 142 parity bits (if available) AND responds identically to all such 143 errors, the chances of a given M' being correctly formatted are sub- 144 stantially decreased. This increases the number of probe messages 145 required to recover M. However, this sort of checking only increases 146 the workfactor and does not eliminate the attack entirely because 147 some messages will still be correctly formatted up to the point of 148 keylength. However, the combination of all three kinds of checking 149 (padding, length, parity bits) increases the number of messages to 150 the point where the attack is impractical. 152 2.3.2. Random Filling 154 The simplest countermeasure is to treat misformatted messages as if 155 they were correctly PKCS-1 formatted. When the victim detects an 156 incorrectly formatted message, instead of returning an error he sub- 157 stitutes a randomly generated message. In CMS, since the message is 158 always a wrapped content encryption key (CEK) the victm should simply 159 substitute a randomly generated CEK of appropriate length and con- 160 tinue. Eventually this will result in a decryption or signature veri- 161 fication error but this is exactly what would have happened if M' 162 happened to be correctly formatted. Note that the timing behavior 163 will also identical. 165 In a layered implementation it's quite possible that the PKCS-1 check 166 occurs at a point in the code where the length of the expected CEK is 167 not known. In that case the implementation must ensure that bad 168 PKCS-1 padding and ok-looking PKCS-1 padding with an incorrect length 169 CEK behave the same. An easy way to do this is to also randomize CEKs 170 that are of the wrong length or otherwise improperly formatted. 172 Note: It is a mistake to use a fixed CEK because the attacker could 173 then produce a CMS message encrypted with that CEK. This message 174 would decrypt correctly, thus allowing the attacker to determine that 175 the PKCS-1 formatting was incorrect. In fact, the randomly generated 176 CEK should be cryptographically random, thus preventing the attacker 177 from guessing the next "random" CEK to be used. 179 2.3.3. OAEP 181 Optimal Asymmetric Encryption Padding (OAEP) [OAEP, PKCS1v2] is 182 another technique for padding a message into an RSA encryption block. 183 Implementations using OAEP are not susceptible to the MMA. However, 184 OAEP is incompatible with PKCS-1. Implementations of S/MIME and CMS 185 must therefore continue to use PKCS-1 for the foreseable future. 187 2.4. Security Considerations 189 This entire document describes how to avoid a certain class of 190 attacks when performing PKCS-1 decryption with RSA. 192 References 193 [PKCS-1] 194 [MMA] 195 [CMS] 197 Author's Address 198 Eric Rescorla 199 RTFM, Inc. 200 2439 Alvin Drive 201 Mountain View, CA 94043 202 Phone: (650) 314-0116 203 Table of Contents 205 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 1 206 2. Overview of PKCS-1 . . . . . . . . . . . . . . . . . . . . . . . 1 207 2.1. The Million Message Attack . . . . . . . . . . . . . . . . . . 2 208 2.2. Applicability . . . . . . . . . . . . . . . . . . . . . . . . . 3 209 2.3. Countermeasures . . . . . . . . . . . . . . . . . . . . . . . . 3 210 2.3.1. Careful Checking . . . . . . . . . . . . . . . . . . . . . . 3 211 2.3.2. Random Filling . . . . . . . . . . . . . . . . . . . . . . . 4 212 2.3.3. OAEP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 213 2.4. Security Considerations . . . . . . . . . . . . . . . . . . . . 4 214 2.4. References . . . . . . . . . . . . . . . . . . . . . . . . . . 5 215 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . . 5