差分解読法
差分解読法 (さぶんかいどくほう、Differential cryptanalysis) は、主にブロック暗号に対して用いられる暗号解読法の一種である。ストリーム暗号やハッシュ関数の攻撃にも用いられる。広い意味では、入力差分がどのように出力差分に影響を及ぼすか考察することである。ブロック暗号においては、置換ネットワークを通してどのように差分が波及するかを追跡することによって、暗号アルゴリズムの非ランダム性を発見し、秘密鍵を復元するような性質を発見することを意味する。
歴史
差分解読法の発見はEli BihamおよびAdi Shamirによって1980年代の末に一般に発表された。BamfordのPuzzle Palaceでは、IBMでは1970年代にはすでに知られていて、それに基づいてDESのSボックスは小修正をされたとされている。1994年にDESを開発したメンバーの一人であるDon Coppersmithは、1974年のはじめにはIBM内で差分攻撃法が知られていて、DESの設計目標の中に差分攻撃法への耐性があったと論文内で述べている。[1] Steven Levyによると、IBMは差分解読法を自ら発見していて、NSAはそのテクニックをおそらくすでに知っていた。[2] 「NSAとの議論の後、設計方針の公開は多くの暗号に対して効果的なテクニックである差分解読法を暴露すると確信した。これは暗号学分野における合衆国の優位性を弱めることとなる」とCopperthmithが述べたように、IBMは秘密を守った。[1] IBMでは、差分解読法は "T-attack"[1] あるいは "Tickle attack".[3]と呼ばれていた。
DESは差分解読法に対して耐性を持つように設計されていたが、他の暗号は脆弱であった。最も初期の攻撃対象は、ブロック暗号FEALであった。最初に提案された4段のFEAL (FEAL-4) はたった8個の選択平文で解読可能であった。31段でさえも攻撃は可能である。
差分攻撃法が一般に知れ渡った後は、この攻撃に対して耐性を持たせることが暗号設計者にとって基本的問題であり、新しい暗号アルゴリズムには、この攻撃に対して耐性があることが望まれるべき性質になっている。AESをはじめとする多くの暗号は、この攻撃に対して安全であると数学的に証明されている（証明可能安全性）。
攻撃手法
差分解読法は、攻撃者が自由に選択した平文に対する暗号文が入手できるという条件で可能な攻撃法であり、選択平文攻撃に分類できる。 DESを解読するためには、247の選択平文が必要である。 しかしながら、既知平文攻撃や暗号文単独攻撃を適用できるような拡張も存在する。 基本的な手法においては、ある固定された差を持つ二つの平文の組を用いる。差の定義にはいくらかの変形があるが、たいていは排他的論理和が用いられる。 攻撃者は、暗号文の組の差を計算し、その分布の中に統計的パターンを発見しようとする。これらの差を差分と呼ぶ。 この統計的性質は、暗号化に用いられるSボックスの性質に由来している。 それゆえ攻撃者はこれらのSボックス に対して、 (ただし ) となるような差分を解析する。 基本的な攻撃では、ひとつの特徴的な暗号文差分が高い確率で生起することが期待される。このようにして、暗号アルゴリズムは、ランダム関数と区別される。さらに洗練された手法では、全数探索法より速く鍵を復元できる。 ほとんどの暗号では、攻撃が成功するためには、差分を注意深く選ぶ必要がある。解析はアルゴリズムの内部構造を調査する。標準的な手法では、それぞれの段の高確率の差分のパスを追跡することによって行われる。このようにして得られたものを差分特性と呼ぶ。
参考文献
- ^ 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.
- ^ Levy, Steven (2001). "Crypto: How the Code Rebels Beat the Government — Saving Privacy in the Digital Age. Penguin Books. pp. 55–56. ISBN 0-14-024432-8
- ^ 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