差分解読法
差分解読法（Differential Cryptanalysis）は、主にブロック暗号に対する暗号解読手法の一つです。ストリーム暗号やハッシュ関数の攻撃にも応用されることがあります。この手法は、入力データの差分が暗号化処理を通してどのように出力データの差分に影響を与えるかを分析することに焦点を当てています。特にブロック暗号においては、置換ネットワークを通過する際の差分の伝播を追跡することで、暗号アルゴリズムの非ランダムな特性を明らかにし、最終的には秘密鍵を特定することを目的としています。
差分解読法は、1980年代後半にEli BihamとAdi Shamirによって一般に公開されました。しかし、IBMでは1970年代にはすでにこの手法が知られており、DES（Data Encryption Standard）のSボックスの設計に影響を与えたとされています。DES開発者の一人であるDon Coppersmithは、1974年初頭にはIBM内で差分解読法が認識されており、DESがこの攻撃に対する耐性を持つように設計されたと述べています。
Steven Levyによれば、IBMは自社で差分解読法を発見し、NSA（アメリカ国家安全保障局）もその技術を把握していたと考えられています。IBMは、この手法を公開することで暗号技術におけるアメリカの優位性を損なうことを懸念し、秘密を守ったとされています。IBMでは、差分解読法は「T-attack」または「Tickle attack」と呼ばれていました。
DESは差分解読法に対して比較的耐性を持つように設計されていましたが、他の初期の暗号は脆弱でした。特に、初期のブロック暗号FEALは、わずかな選択平文で解読が可能でした。例えば、4段のFEAL（FEAL-4）はわずか8個の選択平文で解読され、31段のFEALでさえも攻撃に晒されました。
差分解読法が広く知られるようになった後、この攻撃に対する耐性を持つことは暗号設計者にとって必須の課題となりました。新しい暗号アルゴリズムは、この攻撃に対して安全であることが求められるようになりました。AES（Advanced Encryption Standard）をはじめとする多くの暗号は、差分解読法に対して数学的に安全であると証明されています（証明可能安全性）。
差分解読法は、攻撃者が自由に選択した平文に対する暗号文を入手できる、選択平文攻撃のカテゴリに分類されます。DESを解読するためには、約2^47個の選択平文が必要とされていますが、既知平文攻撃や暗号文単独攻撃にも応用が可能です。
基本的な手法では、特定の差を持つ2つの平文の組を利用します。差の定義にはいくつかの変形がありますが、通常は排他的論理和（XOR）が用いられます。攻撃者は、暗号文の組の差を計算し、その分布に現れる統計的なパターンを観察します。この差分は、暗号化処理に用いられるSボックスの特性に依存します。
具体的には、攻撃者はSボックスSに対して、(ΔX, ΔY)のペア（ここで、ΔY = S(X) ⊕ S(X ⊕ ΔX)）となるような差分を分析します。基本的な攻撃では、ある特定の暗号文の差が非常に高い確率で発生することが期待されます。これにより、暗号アルゴリズムがランダムな関数とは異なることが判明します。さらに高度な手法では、総当たり攻撃よりも効率的に鍵を復元することができます。
ほとんどの暗号では、攻撃を成功させるためには、差分を注意深く選択する必要があります。解析はアルゴリズムの内部構造を調査し、各段における高確率の差分の経路を追跡することで行われます。この経路は差分特性と呼ばれます。
Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN 0-387-97930-1, ISBN 3-540-97930-1.
Biham, E. and A. Shamir. (1990). Differential Cryptanalysis of DES-like Cryptosystems. Advances in Cryptology — CRYPTO '90. Springer-Verlag. 2–21.
Eli Biham, Adi Shamir,"Differential Cryptanalysis of the Full 16-Round DES," CS 708, Proceedings of CRYPTO '92, Volume 740 of Lecture Notes in Computer Science, December 1991. (Postscript)
Eli Biham, slides from "How to Make a Difference: Early History of Differential Cryptanalysis" (PDF, 850 KiB) , March 16, 2006, FSE 2006, Graz, Austria
暗号理論
ブロック暗号
線形解読法
差分確率
関連した攻撃：切詰差分解読法 / 高階差分解読法 / 丸め差分攻撃 / 不能差分攻撃 / ブーメラン攻撃
A tutorial on differential (and linear) cryptanalysis
Helger Lipmaa's links on differential cryptanalysis
A description of the attack applied to DES
歴史
差分解読法は、1980年代後半にEli BihamとAdi Shamirによって一般に公開されました。しかし、IBMでは1970年代にはすでにこの手法が知られており、DES（Data Encryption Standard）のSボックスの設計に影響を与えたとされています。DES開発者の一人であるDon Coppersmithは、1974年初頭にはIBM内で差分解読法が認識されており、DESがこの攻撃に対する耐性を持つように設計されたと述べています。
Steven Levyによれば、IBMは自社で差分解読法を発見し、NSA（アメリカ国家安全保障局）もその技術を把握していたと考えられています。IBMは、この手法を公開することで暗号技術におけるアメリカの優位性を損なうことを懸念し、秘密を守ったとされています。IBMでは、差分解読法は「T-attack」または「Tickle attack」と呼ばれていました。
DESは差分解読法に対して比較的耐性を持つように設計されていましたが、他の初期の暗号は脆弱でした。特に、初期のブロック暗号FEALは、わずかな選択平文で解読が可能でした。例えば、4段のFEAL（FEAL-4）はわずか8個の選択平文で解読され、31段のFEALでさえも攻撃に晒されました。
差分解読法が広く知られるようになった後、この攻撃に対する耐性を持つことは暗号設計者にとって必須の課題となりました。新しい暗号アルゴリズムは、この攻撃に対して安全であることが求められるようになりました。AES（Advanced Encryption Standard）をはじめとする多くの暗号は、差分解読法に対して数学的に安全であると証明されています（証明可能安全性）。
攻撃手法
差分解読法は、攻撃者が自由に選択した平文に対する暗号文を入手できる、選択平文攻撃のカテゴリに分類されます。DESを解読するためには、約2^47個の選択平文が必要とされていますが、既知平文攻撃や暗号文単独攻撃にも応用が可能です。
基本的な手法では、特定の差を持つ2つの平文の組を利用します。差の定義にはいくつかの変形がありますが、通常は排他的論理和（XOR）が用いられます。攻撃者は、暗号文の組の差を計算し、その分布に現れる統計的なパターンを観察します。この差分は、暗号化処理に用いられるSボックスの特性に依存します。
具体的には、攻撃者はSボックスSに対して、(ΔX, ΔY)のペア（ここで、ΔY = S(X) ⊕ S(X ⊕ ΔX)）となるような差分を分析します。基本的な攻撃では、ある特定の暗号文の差が非常に高い確率で発生することが期待されます。これにより、暗号アルゴリズムがランダムな関数とは異なることが判明します。さらに高度な手法では、総当たり攻撃よりも効率的に鍵を復元することができます。
ほとんどの暗号では、攻撃を成功させるためには、差分を注意深く選択する必要があります。解析はアルゴリズムの内部構造を調査し、各段における高確率の差分の経路を追跡することで行われます。この経路は差分特性と呼ばれます。
参考文献
Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN 0-387-97930-1, ISBN 3-540-97930-1.
Biham, E. and A. Shamir. (1990). Differential Cryptanalysis of DES-like Cryptosystems. Advances in Cryptology — CRYPTO '90. Springer-Verlag. 2–21.
Eli Biham, Adi Shamir,"Differential Cryptanalysis of the Full 16-Round DES," CS 708, Proceedings of CRYPTO '92, Volume 740 of Lecture Notes in Computer Science, December 1991. (Postscript)
Eli Biham, slides from "How to Make a Difference: Early History of Differential Cryptanalysis" (PDF, 850 KiB) , March 16, 2006, FSE 2006, Graz, Austria
関連項目
暗号理論
ブロック暗号
線形解読法
差分確率
関連した攻撃：切詰差分解読法 / 高階差分解読法 / 丸め差分攻撃 / 不能差分攻撃 / ブーメラン攻撃
外部リンク
A tutorial on differential (and linear) cryptanalysis
Helger Lipmaa's links on differential cryptanalysis
A description of the attack applied to DES
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。