差分解読法(さぶんかいどくほう、英: differential cryptanalysis)は、主にブロック暗号に対して用いられる暗号解読法の一種である。ストリーム暗号やハッシュ関数の攻撃にも用いられる。広い意味では、入力差分がどのように出力差分に影響を及ぼすか考察することである。ブロック暗号においては、置換ネットワークを通してどのように差分が波及するかを追跡することによって、暗号アルゴリズムの非ランダム性を発見し、秘密鍵を復元するような性質を発見することを意味する。 差分解読法の発見はEli Biham
歴史
DESは差分解読法に対して耐性を持つように設計されていたが、他の暗号は脆弱であった。最も初期の攻撃対象は、ブロック暗号FEALであった。最初に提案された4段のFEAL (FEAL-4) はたった8個の選択平文で解読可能であった。31段でさえも攻撃は可能である。
差分攻撃法が一般に認知された後は、この攻撃に対して耐性を持たせることが暗号設計者にとって基本的問題であり、新しい暗号アルゴリズムには、この攻撃に対して耐性があることが望まれるべき性質になっている。AESをはじめとする多くの暗号は、この攻撃に対して安全であると数学的に証明されている(証明可能安全性)。 差分解読法は、攻撃者が自由に選択した平文に対する暗号文が入手できるという条件で可能な攻撃法であり、選択平文攻撃に分類できる。DESを解読するためには、247の選択平文が必要である。しかしながら、既知平文攻撃や暗号文単独攻撃を適用できるような拡張も存在する。基本的な手法においては、ある固定された差を持つ二つの平文の組を用いる。差の定義にはいくらかの変形があるが、たいていは排他的論理和が用いられる。 攻撃者は、暗号文の組の差を計算し、その分布の中に統計的パターンを発見しようとする。これらの差を差分と呼ぶ。この統計的性質は、暗号化に用いられるSボックスの性質に由来している。それゆえ攻撃者はこれらのSボックス S {\displaystyle S} に対して、 ( Δ X , Δ Y ) {\displaystyle (\Delta _{X},\Delta _{Y})} (ただし Δ Y = S ( X ) ⊕ S ( X ⊕ Δ X ) {\displaystyle \Delta _{Y}=S(X)\oplus S(X\oplus \Delta _{X})} )となるような差分を解析する。基本的な攻撃では、ひとつの特徴的な暗号文差分が高い確率で生起することが期待される。このようにして、暗号アルゴリズムは、ランダム関数と区別される。さらに洗練された手法では、全数探索法より速く鍵を復元できる。ほとんどの暗号では、攻撃が成功するためには、差分を注意深く選ぶ必要がある。解析はアルゴリズムの内部構造を調査する。標準的な手法では、それぞれの段の高確率の差分のパスを追跡することによって行われる。このようにして得られたものを差分特性と呼ぶ。
攻撃手法
参考文献^ a b c Coppersmith, Don (May 1994). ⇒“The Data Encryption Standard (DES) and its strength against attacks” (PDF). IBM Journal of Research and Development 38 (3): 243. ⇒http://www.research.ibm.com/journal/rd/383/coppersmith.pdf.
^ Levy, Steven
^ Matt Blaze, sci.crypt, 15 August 1996, Re: Reverse engineering and the Clipper chip"
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