File: rfc3218.txt

package info (click to toggle)
doc-rfc 20181229-2
  • links: PTS, VCS
  • area: non-free
  • in suites: buster
  • size: 570,944 kB
  • sloc: xml: 285,646; sh: 107; python: 90; perl: 42; makefile: 14
file content (395 lines) | stat: -rw-r--r-- 16,047 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
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]