スライド攻撃

スライド攻撃は、弱い暗号でもラウンド数を増やすことで非常に強力になり、差分攻撃を回避できるという一般的な考えに対処するために設計された暗号解読の一形態です。スライド攻撃は、暗号のラウンド数を無関係にする方法で機能します。ブロック暗号のデータランダム化の側面を見るのではなく、スライド攻撃は、キースケジュールを分析し、その弱点を利用して暗号を破ります。最も一般的な弱点は、キーが循環的に繰り返されることです。

この攻撃は、 David WagnerとAlex Biryukovによって初めて説明されました。Bruce Schneier が最初に彼らに「スライド攻撃」という用語を提案し、彼らは 1999 年にこの攻撃を説明した論文でこの用語を使用しました。

スライド攻撃が暗号に対して機能するための唯一の要件は、同一のF関数の複数のラウンドに分解できることです。これは、おそらく循環キースケジュールがあることを意味します。F関数は既知平文攻撃に対して脆弱である必要があります。スライド攻撃は関連キー攻撃と密接に関連しています。

スライド攻撃のアイデアは、1977 年にエドナ グロスマンとブライアント タッカーマンがIBM テクニカル レポートで発表した論文に端を発しています。^{[1]グロスマンとタッカーマンは、} New Data Seal (NDS)という弱いブロック暗号に対する攻撃を実証しました。この攻撃は、暗号が各ラウンドで同一のサブキーを持つという事実に依存しており、暗号には 1 つのキーのみのサイクルを持つ循環キー スケジュールがあり、スライド攻撃の初期バージョンとなっています。NDS ブロック暗号と攻撃の説明を含むレポートの概要は、Cipher Systems (Beker & Piper、1982) に記載されています。

まず、いくつかの表記法を紹介します。このセクションでは、暗号がnビット ブロックを取り、任意の長さのキーを 使用するキー スケジュールを持っていると仮定します。${\displaystyle K_{1}\cdots K_{m}}$

スライド攻撃は、暗号を同一の順列関数Fに分割することによって機能します。このF関数は、暗号の複数のラウンドで構成できます。これは、キースケジュールによって定義されます。たとえば、暗号が各ラウンドでと を切り替える交互キースケジュールを使用する場合、 F関数は 2 つのラウンドで構成されます。 はそれぞれ、Fに少なくとも 1 回出現します。 ${\displaystyle K_{1}}$${\displaystyle K_{2}}$${\displaystyle K_{i}}$

次のステップは、平文と暗号文のペアを収集することです。暗号の特性によっては、より少ない数で十分な場合もありますが、誕生日問題により、必要以上の数は必要ありません。 と表記されるこれらのペアは、 と表記されるスライド ペアを見つけるために使用されます。スライド ペアは、 および という特性を持ちます。スライド ペアが特定されると、既知平文​​攻撃に対する脆弱性のため、暗号は破られます。このペアからキーを簡単に抽出できます。スライド ペアは、関数Fを 1 回適用した後にメッセージに何が起こるかと考えることができます。これは 1 回の暗号化ラウンドで「スライド」されるため、この攻撃の名前が付けられています。 ${\displaystyle 2^{n/2}}$${\displaystyle 2^{n/2}}$${\displaystyle (P,C)}$${\displaystyle (P_{0},C_{0})(P_{1},C_{1})}$${\displaystyle P_{0}=F(P_{1})}$${\displaystyle C_{0}=F(C_{1})}$

スライド ペアを見つけるプロセスは暗号ごとに多少異なりますが、基本的なスキームは同じです。Fの 1 回の反復からキーを抽出するのは比較的簡単であるという事実を利用します。任意の平文と暗号文のペアを選択し、とに対応するキーを確認します。これらのキーが一致する場合、これはスライド ペアです。そうでない場合は、次のペアに進みます。 ${\displaystyle (P_{0},C_{0})(P_{1},C_{1})}$${\displaystyle P_{0}=F(P_{1})}$${\displaystyle C_{0}=F(C_{1})}$

平文と暗号文のペアでは、暗号の構造に応じて、1 つのスライド ペアと少数の誤検知が予想されます。誤検知は、異なるメッセージと暗号文のペアのキーを使用して暗号化が正しいかどうかを確認することで排除できます。適切な暗号の場合、間違ったキーで 2 つ以上のメッセージが正しく暗号化される可能性は非常に低くなります。 ${\displaystyle 2^{n/2}}$

暗号の構造によっては、必要な平文と暗号文のペアの数が大幅に減り、作業量も大幅に削減されることがあります。最もわかりやすい例は、巡回鍵スケジュールを使用するFeistel 暗号です。この理由は、検索が であるためです。これにより 、ペアになる可能性のあるメッセージが から に減り(メッセージの半分が固定されているため)、スライド ペアを見つけるために必要な平文と暗号文のペアは最大でも になります。 ${\displaystyle P=(L_{0},R_{0})}$${\displaystyle P_{0}=(R_{0},L_{0}\bigoplus F(R_{0},K))}$${\displaystyle 2^{n}}$${\displaystyle 2^{n/2}}$${\displaystyle 2^{n/4}}$

• ヘンリー・ベーカー、フレッド・パイパー (1982)。『暗号システム：通信の保護』、ジョン・ワイリー・アンド・サンズ、pp. 263–267。ISBN 978-0-471-89192-5。（グロスマンとタッカーマンの論文の要約が含まれています）
• Alex BiryukovおよびDavid Wagner (1999 年 3 月)。スライド攻撃( PDF / PostScript ) 。第 6 回高速ソフトウェア暗号化に関する国際ワークショップ(FSE '99)。ローマ: Springer-Verlag。pp . 245–259。2007年 9 月 3 日閲覧。
• Alex Biryukov & David Wagner (2000 年 5 月)。高度なスライド攻撃(PDF/PostScript)。Advances in Cryptology、EUROCRYPT 2000の議事録。ブルージュ: Springer-Verlag。pp. 589–606。2007年 9 月 3 日閲覧。
• S. Furuya (2001 年 12 月)。既知平文暗号解読によるスライド攻撃(PDF)。第 4 回国際情報セキュリティおよび暗号学会議 (ICISC 2001)。ソウル: Springer-Verlag。pp. 214–225。2007年 9 月 3 日閲覧。
• Eli Biham (1994). 「関連キーを使用した新しいタイプの暗号解読攻撃」(PDF/PostScript) . Journal of Cryptology . 7 (4): 229–246. CiteSeerX  10.1.1.48.8341 . doi :10.1007/bf00203965. ISSN  0933-2790. S2CID  19776908 . 2007-09-03に取得。
• M. Ciet、G. Piret、J. Quisquater (2002)。「関連キー攻撃とスライド攻撃: 分析、接続、および改善」(PDF/PostScript) 。2007 年 9 月 4 日に取得。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要ですCS1 maint: 複数の名前: 著者リスト (リンク)