選択平文攻撃

選択平文攻撃（CPA）は、攻撃者が任意の平文の暗号文を入手できることを前提とした暗号解読の攻撃モデルである。^{[ 1 ]}この攻撃の目的は、暗号化方式のセキュリティを低下させる情報を得ることである。^{[ 2 ]}

現代の暗号は、選択平文攻撃下での暗号文の判別不能性とも呼ばれる意味的セキュリティを提供することを目的としており、そのため、正しく実装されていれば、設計上、選択平文攻撃の影響を受けないのが一般的です。

はじめに

選択平文攻撃では、攻撃者は（おそらく適応的に）任意の平文メッセージの暗号文を要求することができます。これは、攻撃者がブラックボックスとみなされる暗号化オラクルと対話できるようにすることで形式化されます。攻撃者の目的は、秘密の暗号鍵の全部または一部を明らかにすることです

実際には、攻撃者が与えられた平文から暗号文を取得することは不可能に思えるかもしれません。しかし、現代の暗号はソフトウェアまたはハードウェアで実装されており、多様な用途に利用されています。多くの場合、選択平文攻撃は非常に実行可能です（「実際の例」も参照）。選択平文攻撃は、暗号鍵が公開されているため攻撃者が任意の平文を暗号化できる 公開鍵暗号において極めて重要になります。

異なる形態

選択平文攻撃には2つの形態があります。

• バッチ選択平文攻撃。攻撃者は対応する暗号文を見る前に、すべての平文を選択します。これは、「選択平文攻撃」という言葉が特に限定されていない場合によく使われる意味です
• 適応型選択平文攻撃（CPA2）。攻撃者は、いくつかの平文の暗号文を見た後、追加の平文の暗号文を要求できます。

攻撃の一般的な方法

一般的なバッチ選択平文攻撃は次のように実行されます。

1. 攻撃者はn個の平文を選択できます。（このパラメータnは攻撃モデルの一部として指定され、制限されている場合とされていない場合があります。）
2. 次に、攻撃者はこれらのn 個のプレーンテキストを暗号化オラクルに送信します。
3. 暗号化オラクルは、攻撃者の平文を暗号化し、攻撃者に送り返します。
4. 攻撃者はオラクルからn 個の暗号文を受け取り、どの暗号文が各平文に対応するかを知ることができます。
5. 攻撃者は、平文と暗号文のペアに基づいて、オラクルが平文を暗号化するために使用した鍵の抽出を試みることができます。このタイプの攻撃では、攻撃者は必要に応じて平文を自由に作成できるため、攻撃の複雑さが軽減される可能性があります。

上記の状況の次の拡張を考えてみましょう。最後のステップの後、

1. 攻撃者は2つの平文m ₀とm ₁を出力します。
2. ビットbは均一にランダムに選択されます。${\displaystyle b\leftarrow \{0,1\}}$
3. 攻撃者はm _bの暗号化を受け取り、どの平文を受け取ったかを「推測」し、ビットb'を出力します。

上記の実験を行った後、攻撃者が1/2よりも無視できない確率で正しく推測できない場合（b = b'）、その暗号は選択平文攻撃に対して区別がつかない暗号化を持つ。 ^{[ 3 ]}

例

以下の例は、他のセキュリティ定義を満たす暗号が、選択平文攻撃によってどのように破られる可能性があるかを示しています

シーザー暗号

シーザー暗号に対する以下の攻撃により、秘密鍵を完全に復元できます

1. 敵が次のようなメッセージを送信したとしますAttack at dawn。
2. そして神託は返されるNggnpx ng qnja。
3. 攻撃者はシーザー暗号と同じ方法で鍵を復元することができます。攻撃者はA→N、T→Gなどの置換を推測することができます。これにより、攻撃者は13がシーザー暗号で使用された鍵であると特定することができます。

より複雑で複雑な暗号化方法を使用すると、復号化方法はより多くのリソースを消費することになりますが、中核となる概念はほぼ同じです。

ワンタイムパッド

ワンタイムパッドに対する次の攻撃により、秘密鍵を完全に復元できます。メッセージ長と鍵長がnで あると仮定します

1. 攻撃者はn 個のゼロで構成される文字列をオラクルに送信します。
2. オラクルでは、キーとゼロの文字列のビット単位の排他的論理和を返します。
3. オラクルによって返される文字列が秘密鍵です。

ワンタイムパッドは情報理論的に安全な暗号システムの例として用いられていますが、このセキュリティはCPAセキュリティよりも弱いセキュリティ定義の下でのみ成立します。これは、CPAセキュリティの正式な定義では、暗号化オラクルに状態が存在しないためです。この脆弱性はすべての実用的な実装に当てはまるとは限りません。鍵の再利用を避ければ、ワンタイムパッドは依然として安全です（これが「ワンタイム」パッドと呼ばれる理由です）。

実践

第二次世界大戦中、アメリカ海軍の暗号解読者は、日本が「AF」と呼ばれる場所を攻撃する計画を立てていることを発見しました。ハワイ諸島の他の場所には「A」で始まる暗号語が使用されていたため、 「AF」はミッドウェー島である可能性があると考えました。「AF」が「ミッドウェー島」に対応するという仮説を証明するために、彼らはミッドウェーのアメリカ軍に物資不足に関する平文メッセージを送信するよう依頼しました。日本軍はメッセージを傍受し、すぐに上層部に「AF」の水が不足していると報告しました。これにより海軍の仮説が裏付けられ、戦闘に勝利するための部隊配置が可能になりました。^{[ 3 ] [ 4 ]}

第二次世界大戦中、ブレッチリー・パークの連合軍暗号解読者は、ドイツ海軍のグリッド参照システムに略語や代替案がない位置に機雷を敷設するよう、イギリス空軍に要請することもあった。機雷を発見したドイツ軍がエニグマ暗号機を使って機雷に関する警告メッセージと、機雷除去後の「解除」メッセージを暗号化し、連合軍にドイツ海軍のエニグマ暗号を解読するのに十分な情報を与えることを期待していた。この既知平文を埋め込むプロセスはガーデニングと呼ばれていた。 ^{[ 5 ]}連合軍の暗号解読者は、二重スパイのフアン・プホル・ガルシアが送信したメッセージの作成にも協力した。プホル・ガルシアの暗号化された無線報告はマドリードで受信され、手作業で解読された後、エニグマ暗号機で再暗号化されてベルリンに送信された。^{[ 6 ]}この暗号解読者は、元のテキスト を提供することで、第二区間で使用された暗号を解読することができた。^{[ 7 ]}

現代では、対称暗号を解読するために選択平文攻撃（CPA）がしばしば用いられます。CPA安全とみなされるためには、対称暗号は選択平文攻撃に対して脆弱であってはなりません。したがって、対称暗号の実装者は、攻撃者がどのようにして暗号を解読しようとするかを理解し、適切な改良を行うことが重要です。

一部の選択平文攻撃では、攻撃者が平文のごく一部を選択するだけで済む場合があります。このような攻撃は、平文インジェクション攻撃と呼ばれます。

他の攻撃との関係

選択平文攻撃は既知平文攻撃よりも強力です。これは、攻撃者が特定の用語やパターンを自然出現を待つことなく直接標的とすることができるため、暗号解読に関連するデータをより迅速に収集できるためです。したがって、選択平文攻撃を防ぐ暗号は、既知平文​​攻撃や暗号文のみの攻撃に対しても安全です。

しかし、選択平文攻撃は、攻撃者が任意の暗号文の平文を取得できる選択暗号文攻撃ほど強力ではありません。CCA攻撃者は、CPAで安全なシステムを破ることができる場合があります。 ^{[ 3 ]}例えば、 エル・ガマル暗号は選択平文攻撃に対しては安全ですが、無条件に可鍛性があるため、選択暗号文攻撃に対しては脆弱です。

参照

• GMR（暗号）

参考文献

1. ロス・アンダーソン著、『セキュリティエンジニアリング：信頼できる分散システム構築ガイド』初版（2001年）： http://www.cl.cam.ac.uk/~rja14/book.html
2. Barrera, John Fredy; Vargas, Carlos; Tebaldi, Myrian; Torroba, Roberto (2010-10-15). 「ジョイント・トランスフォーム・コリレータ暗号化システムに対する選択平文攻撃」 . Optics Communications . 283 (20): 3917– 3921. Bibcode : 2010OptCo.283.3917B . doi : 10.1016/j.optcom.2010.06.009 . ISSN  0030-4018 .
3. カッツ、ジョナサン、リンデル、イェフダ (2007). 『現代暗号入門：原理とプロトコル』 ボカラトン: チャップマン・アンド・ホール/CRC. ISBN 978-1584885511 OCLC  893721520
4. ウィードン、パトリック・D. 「暗号学はいかにしてアメリカが太平洋戦争の流れを変えることができたか」 www.navy.mil .米海軍。2015年1月31日時点のオリジナルよりアーカイブ。2015年2月19日閲覧
5. モリス、クリストファー（1993年）「海軍ウルトラの貧しい関係」ヒンズリー、FH；ストリップ、アラン（編）『コードブレーカー：ブレッチリー・パークの内幕』オックスフォード：オックスフォード大学出版局、235ページ、ISBN 978-0-19-280132-6
6. ケリー、ジョン（2011年1月27日）。「ヒトラーを騙した一枚の紙」。BBC 。 2012年1月1日閲覧。ナチスは、アラリック・アラベルというコードネームで呼ばれたプジョールを、彼らの貴重な資産の1人だと信じていました
7. シーマン (2004) . 「ガルボが無線通信のためにドイツ人から与えられた最初のコードは、当時ドイツの回線で使用されていたコードと同一であることが判明した。」