[要約] RFC 3218は、暗号化メッセージ構文におけるミリオンメッセージ攻撃を防ぐためのガイドラインを提供しています。このRFCの目的は、セキュリティ上の脆弱性を解決し、暗号化メッセージの信頼性を向上させることです。
Network Working Group E. Rescorla
Request for Comments: 3218 RTFM, Inc.
Category: Informational January 2002
Preventing the Million Message Attack on Cryptographic Message Syntax
暗号メッセージ構文に対する100万メッセージ攻撃の防止
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.
Copyright（C）The Internet Society（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
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 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.
RSAを使用してデータを暗号化する場合は、モジュラスの長さ（通常512〜2048ビット）までパディングする必要があります。これを行うための最も一般的な手法は、[PKCS-1-v1.5]で説明されています。ただし、1998年にBleichenbacherは、SSL [MMA]に対する適応型暗号文攻撃を説明しました。この攻撃はミリオンメッセージ攻撃と呼ばれ、攻撃者が受信者を特定の種類のオラクルとして振る舞わせることができれば、単一のPKCS-1暗号化ブロックの回復を可能にしました。 （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バイトは、ゼロバイトと「ブロックタイプ」バイトです。暗号化の場合、ブロックタイプは2です。残りのバイトはパディングとして使用されます。パディングは、一連のゼロ以外のランダムバイトを生成することによって構築されます。最後のパディングバイトはゼロです。これにより、パディングをメッセージと区別できます。
+---+---+----------------------+---+---------------------+
| 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番目のバイトが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 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.
ゼロ以外の埋め込みが少なくとも8バイト必要です。パディングは、攻撃者が暗号化されたメッセージに関する推測を検証することを防ぎます。攻撃者が2つのRSA暗号化キーが同じかどうかを判断したいとします。高い確率で少なくとも255 ^ 8（約2 ^ 64）の異なるパディング値があるため、同じCEKの2つの暗号化は異なります。また、攻撃者はすべての推測に対して各潜在的なパッドを試行する必要があるため、攻撃者が受信者のRSAキーでそれらを試行暗号化することにより、推測されたCEKを検証することを防ぎます。より低コストの攻撃は、コンテンツを試行的に復号化し、プレーンテキストを調べて妥当であるかどうかを確認することにより、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.
Million Message Attack（MMA）の目的は、暗号文（暗号化されたブロック）が与えられた単一の平文（フォーマットされたブロック）を復元することです。攻撃者は最初に転送中の暗号文をキャプチャし、次に受信者をオラクルとして使用して、変換されたバージョンの暗号文を送信し、受信者の応答を観察することで平文を復元します。
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に約1）は、最初の2バイトが正しく00 02であるため、適切にPKCS-1フォーマットされているように見えます。攻撃は、結果のM 'が適切にPKCS-1でフォーマットされるように、値のシーケンスSを見つけることによって進行します。この情報は、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は自動化された犠牲者に対してのみマウントできます。
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でフォーマットされた場合とそうでない場合を攻撃者が区別できることも要求します。 CMSの場合、攻撃者はラップされたCEKの代わりにC 'を使用してCMSメッセージを送信します。したがって、5つの可能性があります。
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は一見偽物です（長さが間違っているなど）。3. M'は適切にフォーマットされており、CEKはOKと表示されます。署名または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を区別できます）。これは、被害者がケースごとに異なるエラーを返した場合に発生する可能性があります。攻撃者はまた、タイミングに基づいてこれらのケースを区別できる可能性があります。メッセージの復号化と署名の検証には時間がかかります。被害者が4つすべてのエラーに均一に応答する場合、攻撃は不可能です。
[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バイトのブロックには3バイトの値03が埋め込まれます。
XX XX XX XX XX 03 03 03
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).
[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を回復するために必要なプローブメッセージの数が増加します。ただし、この種のチェックでは作業係数が増加するだけで、攻撃が完全に排除されるわけではありません。ただし、3種類のチェック（パディング、長さ、パリティビット）をすべて組み合わせると、メッセージ数が増加し、攻撃が現実的ではなくなります。
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.
階層化された実装では、予想されるCEKの長さがわからないコードのポイントでPKCS-1チェックが発生する可能性があります。その場合、実装は、不正なPKCS-1パディングと、正しくない長さのCEKを持つok-looking 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で暗号化されたCMSメッセージを生成する可能性があるため、固定CEKを使用するのは誤りです。このメッセージは適切に復号化される（つまり、受信者にとって完全に有効な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暗号化ブロックにメッセージをパディングするためのもう1つの手法です。 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。、「Cryptographic Message Syntax」、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 Encryption Standardに関する最近の結果」、RSA Laboratories 'Bulletin＃7、1998年6月26日。
[OAEP] Bellare, M., Rogaway, P., "Optimal Asymmetric Encryption Padding", Advances in Cryptology -- Eurocrypt 94.
[OAEP] Bellare、M.、Rogaway、P。、「最適な非対称暗号化パディング」、暗号学の進歩-Eurocrypt 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 Encryption、Version 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 Encryption、Version 2.0」、RFC 2347、1998年10月。
Eric Rescorla RTFM, Inc. 2064 Edgewood Drive Palo Alto, CA 94303
Eric Rescorla RTFM、Inc. 2064 Edgewood Drive Palo Alto、CA 94303
Phone: (650) 320-8549 EMail: ekr@rtfm.com
電話：（650）320-8549メール：ekr@rtfm.com
Copyright (C) The Internet Society (2002). All Rights Reserved.
Copyright（C）The Internet Society（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 Editor機能への資金提供は、現在Internet Societyから提供されています。