Data Encryption Standard

DESの起源は1970年代初めに遡る。1972年、アメリカ政府はコンピュータセキュリティが重要であるという研究結果を得た。そこでNBS（National Bureau of Standard。合衆国標準局。現在のNIST（アメリカ国立標準技術研究所））が、政府全体で機密情報を暗号化するための標準規格が必要だと判断した^[1]。それに応じて1973年5月15日、NSAと相談の上、NBSが厳しい設計基準を満たした暗号を公募した。しかし応募のいずれも条件を満たしていなかったため、1974年8月27日に2回目の公募を行った。今回はIBMの応募した案が条件を満たしていると思われた。それは、以前からあったアルゴリズムに基づき1973年から1974年に開発されたホルスト・ファイステルのLucifer暗号だった。IBMでこの暗号の設計と解析を行ったチームにはファイステルの他に、ウォルト・タックマン (Walt Tuchman)、ドン・コッパースミス (Don Coppersmith)、アラン・コンハイム (Alan Konheim)、カール・メイヤー (Carl Meyer)、マイク・マーチャーシュ (Mike Matyas)、ロイ・アドラー (Roy Adler)、エドナ・グロスマン (Edna Grossman)、ビル・ノッツ (Bill Notz)、リン・スミス (Lynn Smith)、ブライアント・タッカーマン (Bryant Tuckerman) らがいた。

Lucifer・DESはホルスト・ファイステルらの考えたFeistel構造と呼ばれる構造をなしている。この事は後の共通鍵暗号研究に多大な影響を与え、後に提案された多くの共通鍵暗号方式がFeistel構造に基づいて設計された。

1975年3月17日、規格案としてのDESが Federal Register に発表された。そしてコメントが募集され、翌年には2回ワークショップを開催してこの規格案について議論した。各所から様々な批判が寄せられた。中には公開鍵暗号の先駆者であるマーティン・ヘルマンとホイットフィールド・ディフィーの批判があり、鍵長が短いという点と謎めいた「Sボックス」がNSAによる不適切な干渉を意味しているのではないかと指摘した。それは、このアルゴリズムを諜報機関が密かに弱め、その諜報機関だけが暗号化されたメッセージを容易に解読できるようにしたのではないかという疑いが持たれたのである^[2]。アラン・コンハイム（DES設計者の1人）はそれについて「我々はSボックスをワシントンに送った。戻ってきたものは送ったものとは全く異なっていた」と述べた^[3]。アメリカ合衆国上院諜報特別委員会がNSAの行為に不適切な干渉があったかどうかを調査した。調査結果の公開された要約には次のように書かれている。

「DESの開発において、NSAはIBMに対して鍵長が短くても大丈夫だと納得させ、Sボックスの開発を間接的に支援し、最終的なDESアルゴリズムが統計学的にも数学的にも考えられる最高のものだと保証した」^[4]

しかし、同時に次のようなことも判明している。

「NSAはいかなる形でもアルゴリズムの設計を改変していない。IBMはこのアルゴリズムを発明・設計し、関連する設計上の意思決定は全てIBMが行い、鍵長もDESのあらゆる商用の用途にとって十分な長さとして決定した」^[5]

DES設計チームのウォルト・タックマンは「我々はIBM内でIBMの人員だけでDESアルゴリズム全体を開発した。NSAに命じられて変更した部分は1つもない」と述べた^[6]。一方、機密解除されたNSAの暗号史に関する本には次のように書かれている。

「1973年、NBSはDESを民間企業に求めた。最初の応募案は満足のいくものではなかったため、NSAは独自にアルゴリズムの研究を始めた。そして、工学研究部門の代表であるハワード・ローゼンブラムは、IBMのウォルト・タックマンがLuciferを汎用化する修正を行っていることに気づいた。NSAはタックマンに人物証明を与え、当局と共にLuciferを修正する作業を行わせた」^[7]

Sボックスに関する嫌疑の一部は1990年に鎮められることになった。同年、エリ・ビハムとアディ・シャミア（RSAのS）が差分解読法を独自に発見して公表した。差分解読法はブロック暗号を破る汎用技法である。DESのSボックスは無作為に選ばれた場合よりもこの攻撃法にずっと抵抗力があり、IBMが1970年代にこの攻撃法を知っていたことを強く示唆していた。1994年、ドン・コッパースミスがSボックスの元々の設計基準について一部を公表したことで、それが裏付けられた^[8]。スティーブン・レビーによれば、IBMでは1974年に差分解読法を発見していたが、NSAがそれを秘密にするよう要請していたという^[9]。コッパースミスはIBMの方針について「（差分解読法）は非常に強力なツールであり、様々な方式に応用でき、これを公にすると国家の安全に悪い影響を及ぼすことが懸念された」と述べている。レビーはタックマンの言葉として「彼らは我々のあらゆる文書に極秘というスタンプを押させようとした…それらは合衆国政府の機密と見なされたので、我々は実際にそれらに番号を振り、金庫に入れた。彼らがそうしろと言ったから、そうしたまでだ」と書いている^[9]。

批判はあったがDESは1976年11月連邦規格として承認され、1977年1月15日には FIPS PUB 46 として公表され、非機密政府通信での利用が承認された。さらに1981年に ANSIとして制定され、民間標準規格にもなった。1983年、1988年（FIPS-46-1 に更新）、1993年 (FIPS-46-2)、1999年 (FIPS-46-3) と再承認され、最後にはトリプルDESが定められた。2002年5月26日、DESは公開のコンペティションで選ばれた Advanced Encryption Standard (AES) で置き換えられた。2005年5月19日、FIPS 46-3は公式に廃止となったが、NISTはトリプルDESについては政府の重要情報用に使うことを2030年まで承認している^[10]。

このアルゴリズムは ANSI X3.92^[11]、NIST SP 800-67^[10]、ISO/IEC 18033-3^[12] でも指定されている（TDEAの要素として）。

もう1つの理論的攻撃法である線形解読法は1994年に公表された。1998年には総当り攻撃で実用的な時間でDESを破れることが実証され、アルゴリズムの更新の必要性が高まった。これら攻撃法については後の節で詳述する。

DESの登場は暗号研究、特に暗号解読法の研究を活発化させる触媒の役割を果たした。NISTは後にDESについて次のように述べている。

DESは暗号アルゴリズムの非軍事的研究と開発を「ジャンプスタート」させたと言える。1970年代、暗号学者は軍隊や諜報機関以外にはほとんどおらず、暗号の学問的研究は限定的だった。今では多数の学者が暗号を研究し、数学関係の学科で暗号を教え、情報セキュリティ企業やコンサルタントが商売をしている。暗号解読者はDESアルゴリズムを解析することで経験を積んだ。暗号研究者ブルース・シュナイアーは「DESは暗号解読というフィールドを大いに活気付けた。今では研究すべきアルゴリズムのひとつだ」と述べている^[13]。1970年代から1980年代にかけて、暗号に関する多くの書籍がDESを扱っており、共通鍵暗号を比較する際の基準となっている^[14]。

 

 

 

DESは原型ともいうべきブロック暗号であり、固定ビット長の平文を入力とし、一連の複雑な操作によって同じ長さの暗号文を出力するアルゴリズムである。DESの場合、ブロック長は64ビットである。また、変換をカスタマイズする鍵を使うため、暗号化に使った鍵を知っている者だけが復号できる。鍵は見た目は64ビットだが、そのうち8ビットはパリティチェックに使うため、アルゴリズム上の実際の鍵の長さは56ビットである。

他のブロック暗号と同様、DES自体は暗号化の安全な手段ではなく、暗号利用モードで使う必要がある。FIPS-81 はDES用のいくつかのモードを示している^[18]。その他のDESの利用法については FIPS-74 に詳しい^[19]。

アルゴリズムの全体構造を図1に示す。16の処理工程があり、それらを「ラウンド」と呼ぶ。また、最初と最後に並べ替え処理があり、それぞれ IP および FP と呼ぶ。IP と FP はちょうど逆の処理を行う。IP と FP は暗号化にはほとんど関係ないが、1970年代のハードウェアでブロックの入出力を行う部分として含まれており、同時にそれによってソフトウェアによるDESの処理が遅くなる原因にもなっている。

ラウンドでの処理の前にブロックは半分（32ビット）ずつに分けられ、それぞれ異なる処理を施される。この十字交差構造をFeistel構造と呼ぶ。Feistel構造を使うと、暗号化と復号は非常に良く似た処理になる。違いは、復号ではラウンド鍵を逆の順序で適用するという点だけであり、アルゴリズムは同一である。このため実装が単純化でき、特にハードウェアで実装する場合に両者を別々に実装する必要が無い。

⊕ という記号は排他的論理和 (XOR) を意味する。F-関数はブロックの半分を何らかの鍵でかき混ぜる。F-関数の出力をブロックの残り半分と結合し、次のラウンドに行く前にその半分同士を入れ替える。最後のラウンドの後には入れ替えは行わない。これは、暗号化と復号を似たプロセスで行うFeistel構造の特徴である。

図2にあるF-関数はブロックの半分（32ビット）を一度に処理する。以下の4段階がある。

1. Expansion - expansion permutation と呼ばれる方式で32ビットを48ビットに拡張する。図では E で示されている部分である。入力のうち半分のビットの複製16ビット分を出力のビット列に追加する。その出力は8個の6ビットの部分からなり、それら6ビットのうちの中央4ビットは入力の対応する4ビットの部分と同じで、両端の1ビットずつは入力上で隣接する部分のビットの複製である。
2. Key mixing - ラウンド鍵と上の出力結果をXOR操作で結合する。ラウンド鍵は48ビットで、もともとの鍵から「鍵スケジュール」（後述）によって16個のラウンド鍵が生成される。
3. Substitution - ラウンド鍵を混ぜた後、6ビットずつに分けてSボックス (substitution box) に入力する。8個のSボックスは入力の6ビットから4ビットの出力を生成し、このときルックアップテーブルの形で提供される非線形な変換を行う。SボックスがDESの安全性の根幹であり、これが無かったならば暗号化の処理は線形であり容易に破ることができることになる。
4. Permutation - Sボックス群の出力である32ビットに固定の並べ替えを施す。図では P で示した部分である。このとき、各Sボックスの出力が次のラウンドでSボックスに展開されるとき、6個の異なるSボックスに分散するよう並べ替える。

Sボックスでの置換とPボックスでの並べ替えとEでの拡張を交互に行うことで、クロード・シャノンが安全で実用的な暗号に必要な条件とした「拡散とかく乱」を提供する。

図3は暗号化での「鍵スケジュール」、すなわちラウンド鍵を生成するアルゴリズムを示している。まず64ビットの入力から56ビットを選択して並べ替えを行う Permuted Choice 1 (PC-1) がある。選ばれなかった8ビットは単に捨ててもよいし、パリティビットとして鍵のチェックに使ってもよい。その56ビットは2つの28ビットに分割され、その後別々に処理される。ラウンドを次に進める際にそれぞれを左に1ビットか2ビットローテートする（ラウンドによってローテートするビット数が異なる）。そして、それらを Permuted Choice 2 (PC-2) に入力して48ビットのラウンド鍵を出力する。このときそれぞれの半分（28ビット）から24ビットずつを選び、並べ替えも左右別々に行う。ローテートを行うことでラウンドごとに選択するビットが変化する（PC-2自体は固定であり、毎回同じ位置のビットを選んで同じ順序で並べ替える）。各ビットは16ラウンドのうち、だいたい14回使われる。

復号の際の鍵スケジュールもほぼ同様である。ラウンド鍵は暗号化のときとは逆順に適用される。その点を除けば暗号化と全く同じ工程で処理される。

DESについては安全性とソフトウェアによる処理が相対的に遅い点が懸念され、1980年代末から1990年代初めごろから研究者らが様々なブロック暗号を代替案として提案してきた。例えば、RC5、Blowfish、IDEA、NewDES、SAFER、CAST5、FEALなどがある。その多くはDESと同じ64ビットのブロック長で、そのまま代替として使えるようになっているが、鍵には64ビットか128ビットを使っているものが多い。ソビエト連邦ではGOSTアルゴリズムが導入された。これはブロック長64ビットで256ビットの鍵を使っており、後にロシアでも使われた。

DES自身をもっと安全な形にして再利用することもできる。かつてDESを使っていたところでは、DESの特許権保持者の1人が考案したトリプルDES (TDES) を使っている（FIPS Pub 46-3 参照）。この方式では2つ (2TDES) ないし3つ (3TDES) の鍵を用いて、暗号‐復号‐暗号の順でDESを3回行なう事で暗号化する。TDESは十分安全だが、極めて時間がかかる。それほど計算量が増えない代替方式としてDES-Xがあり、鍵長を長くしてDESの処理の前後で外部鍵をXORする。GDESはDESの暗号処理を高速にする方式だが、差分解読法に弱いことが分かっている。

その後NISTがDESに代わる米国標準暗号方式 Advanced Encryption Standard (AES) を公募した。そして2000年10月、ベルギーのホァン・ダーメン（英語版）とフィンセント・ライメンにより提案されたRijndael（ラインデール）が新しい米国標準暗号方式AESに選ばれた。トリプルDESのようなad-hocな方法で設計された暗号方式とは異なり、AESはSPN構造と呼ばれるより整備された構造を持つ暗号方式である。公募には他にRC6、Serpent、MARS、Twofishも応募したがどれも選ばれなかった。AESは2001年11月に FIPS 197 として正式に公表された。

DESの解読法については他のブロック暗号よりも多数の情報があるが、今も最も実用的な攻撃法は総当り攻撃である。暗号解読上の各種特性が知られており、3種類の理論上の攻撃方法が知られている。それらは総当り攻撃よりも理論上は計算量が少ないが、非現実的な量の既知平文か選択平文を必要とし、実用化はされていない。

 

どんな暗号についても、最も基本となる攻撃法は総当り攻撃、すなわち鍵のとりうる値を全て試す方法である。鍵の長さが鍵のとりうる値の個数に直接関係してくるため、総当りが現実的かどうかも鍵の長さで決まる。DESについては標準として採用される以前から鍵の短さが懸念されていた。NSAを含む外部コンサルタントを交えた議論の結果、1つのチップで暗号化できるよう鍵の長さを128ビットから56ビットに減らすことになった^[20]。

学界では様々なDES解読機が提案されてきた。1977年、ディフィーとヘルマンは1日でDESの鍵を見つけることができるマシンのコストを2000万ドルと見積もった。1993年になると、ウィーナーは7時間で鍵を見つけることができる機械のコストを100万ドルと見積もった。しかし、そのような初期の提案に基づいて実際に解読機を製作した例はないし、少なくともそのような実例が公表されたことはなかった。DESの脆弱性が実際に示されたのは1990年代後半のことである。1997年、RSAセキュリティは一連のコンテストを主催し、DESで暗号化されたメッセージを最初に解読したチームに1万ドルを賞金として提示した。このコンテストで優勝したのは、Rocke Verser、Matt Curtin、Justin Dolske が主導する DESCHALL Project で、インターネット上の数千台のコンピュータのアイドル時間（何もしていない時間）を利用したプロジェクトだった。1998年には電子フロンティア財団 (EFF) が約25万ドルをかけてDES解読機を製作した。EFFの意図は、DESを理論上だけでなく実際に破ることができることを示すことであり、「多くの人々は実際に自分の目で見るまで真実を信じようとしない。DESを数日間で破ることができるマシンを実際に示すことで、DESによるセキュリティが信用できないことを明らかにできる」と述べている。この機械は2日強かけて総当り攻撃で鍵を見つけることができる。1999年1月に行われた3回目のコンテストでは、22時間でdistributed.netによりDESが解読された^[21]。この解読にはEFFのDES解読機とインターネット経由で募集された10万台の計算機が用いられた。

もう1つのDES解読機としてCOPACOBANA（cost-optimized parallel code breaker の略）が2006年、ドイツのルール大学ボーフムとキール大学のチームで開発された。EFFの解読機とは異なり、COPACOBANAは一般に入手可能な部品（集積回路）のみを使っている。20個のDIMMモジュールで構成され、それぞれに6個のFPGA（XILINX Spartan3-1000）を装備し、それらが並列に動作する。FPGAを使っているため、DES以外の暗号解読にも応用可能である。COPACOBANAの重要な特徴はその低コストであり、1台を約1万ドルで製作できる。EFFのDES解読機に比べて約25分の1であり、8年間の物価上昇率を考慮すれば約30分の1ということができる。

総当り攻撃よりも少ない計算量で16ラウンドのDESを破ることができる攻撃法が3種類知られている。差分解読法 (DC)、線形解読法 (LC)、Davies' attack である。しかし、これらの攻撃法は理論上のものであって、実際に応用するのは現実的ではない。これらを certificational weaknesses と呼ぶこともある。

差分解読法

1980年代末にエリ・ビハムとアディ・シャミアが再発見した。IBMとNSAにはそれ以前から知られていたが、秘密にされていた。16ラウンドのDESを破るには、2⁴⁷の選択平文を必要とする。DESはDCへの耐性を考慮して設計されている。

線形解読法

1993年、松井充が発見。2⁴³の既知平文を必要とする。これを実際に実装して(Matsui, 1994)、DESの解読実験が行われている。DESがこの解読法への耐性を考慮して設計されたという証拠はない。1994年には、これを拡張した multiple linear cryptanalysis (Kaliski and Robshaw) が提案され、その後も改良が Biryukov らによって行われている。研究によると、複数の線形近似を用いることで必要なデータ量が4分の1になる（つまり、2⁴³を2⁴¹に減らせる）ことが示唆されている。また、選択平文を使った線形解読法でも同様にデータ量を削減できる (Knudsen and Mathiassen, 2000)。Junod (2001) は実験によって線形解読法の時間計算量を測定し、DESの解読は予想よりも時間がかからず 2³⁹ から 2⁴¹ になるとした。

Davies' attack

差分解読法も線形解読法もDESだけに限らずに任意の暗号解読にも使えるが、Davies' attack はDES専用の解読法であり、ドナルド・デービスが1980年代に提案して、ビハムとBiryukov (1997) が改良を施した。最も強力な形式の攻撃には 2⁵⁰ の既知平文を必要とし、計算量も 2⁵⁰、成功率は51%である。

ラウンド数を減らした暗号（DESの16ラウンドを減らしたもの）への攻撃法も提案されている。そのような研究によってラウンド数がどれだけあれば安全かという考察も行われている。また、16ラウンドのDESにどれだけ安全マージンがあるかも研究されてきた。1994年にはラングフォードとヘルマンが差分解読法と線形解読法を組み合わせた差分線形解読法を提案した。改良版の解読法では、9ラウンドのDESを 2^15.8 の既知平文を使って 2^29.2 の時間計算量で破ることができる (Biham et al., 2002)。

DESには相補性がある。すなわち次が成り立つ。

E_k(P) = C ⇔ E_K(P) = C

ここで ${\displaystyle {\overline {x}}}$  は ${\displaystyle x}$  のビット毎の反転である。${\displaystyle E_{K}}$  は鍵 ${\displaystyle K}$  を使った暗号化を意味する。${\displaystyle P}$  は平文、${\displaystyle C}$  は暗号ブロック列である。相補性があるということは、総当り攻撃に必要な試行回数は2分の1で済むことを意味する。

DESには4つのいわゆる「弱い鍵」がある。暗号化 (E) と復号 (D) で弱い鍵を使うと、どちらも同じ効果がある。

${\displaystyle E_{K}(E_{K}(P))=P}$  または ${\displaystyle E_{K}=D_{K}}$ 

また、6組の「やや弱い鍵」もある。弱い鍵の1つ ${\displaystyle K_{1}}$  を使った暗号化は、ペアのもう一方の ${\displaystyle K_{2}}$  を使った復号と等価である。

${\displaystyle E_{K_{1}}(E_{K_{2}}(P))=P}$  または ${\displaystyle E_{K_{2}}=D_{K_{1}}}$ 

弱い鍵ややや弱い鍵を実装で使わないようにするのは容易である。もともと無作為に鍵を選んでも、それらを選ぶ確率は極めて低い。それらの鍵は理論上は他の鍵より弱いわけではなく、攻撃に際しても特に利用できるわけでもない。

DESは群にならないことが証明されている。つまり、集合 ${\displaystyle \{E_{K}\}}$ （鍵 ${\displaystyle K}$  がとりうる全ての値の集合）は関数合成において群ではないし、1つの群に閉じていない (Campbell and Wiener, 1992)。これがもし群であるならば、DESは容易に破ることができ、トリプルDESにしても安全性は向上しなかったとされている。

DESの暗号学的安全性は最大でも約64ビットである。例えば、個々のラウンド鍵を元の1つの鍵から生成せずそれぞれ独立に供給すれば、安全性は768ビットになりそうなものだが、この限界によりそうならないことが知られている。

• トリプルDES
• AES
• 暗号理論
• スキップジャック (暗号)
• 共通鍵暗号

• Biham, Eli and Adi Shamir (1991). “Differential Cryptanalysis of DES-like Cryptosystems”. Journal of Cryptology 4 (1): 3–72. doi:10.1007/BF00630563. http://www.springerlink.com/content/k54h077np8714058/.  (preprint)
• Biham, Eli and Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN 0-387-97930-1, ISBN 3-540-97930-1.
• Biham, Eli and Alex Biryukov:An Improvement of Davies' Attack on DES. J. Cryptology 10(3):195–206 (1997)
• Biham, Eli, Orr Dunkelman, Nathan Keller:Enhancing Differential-Linear Cryptanalysis. ASIACRYPT 2002:pp254–266
• Biham, Eli. A Fast New DES Implementation in Software Cracking DES:Secrets of Encryption Research, Wiretap Politics, and Chip Design, Electronic Frontier Foundation
• Biryukov, A, C. De Canniere and M. Quisquater (2004). “On Multiple Linear Approximations”. Lecture Notes in Computer Science 3152: 1–22. doi:10.1007/b99099. http://www.springerlink.com/content/16udaqwwl9ffrtxt/.  (preprint).
• Campbell, Keith W., Michael J. Wiener:DES is not a Group. CRYPTO 1992:pp512–520
• Coppersmith, Don. (1994). The data encryption standard (DES) and its strength against attacks. IBM Journal of Research and Development, 38(3), 243–250.
• Diffie, Whitfield and Martin Hellman, "Exhaustive Cryptanalysis of the NBS Data Encryption Standard" IEEE Computer 10(6), June 1977, pp74–84
• Ehrsam et al., Product Block Cipher System for Data Security, アメリカ合衆国特許第 3,962,539号, Filed February 24, 1975
• Gilmore, John, "Cracking DES:Secrets of Encryption Research, Wiretap Politics and Chip Design", 1998, O'Reilly, ISBN 1-56592-520-3.
• Junod, Pascal. On the Complexity of Matsui's Attack. - ウェイバックマシン（2009年5月27日アーカイブ分） Selected Areas in Cryptography, 2001, pp199–211.
• Kaliski, Burton S., Matt Robshaw:Linear Cryptanalysis Using Multiple Approximations. CRYPTO 1994:pp26–39
• Knudsen, Lars, John Erik Mathiassen:A Chosen-Plaintext Linear Attack on DES. Fast Software Encryption - FSE 2000:pp262–272
• Langford, Susan K., Martin E. Hellman:Differential-Linear Cryptanalysis. CRYPTO 1994:17–25
• Levy, Steven, Crypto:How the Code Rebels Beat the Government—Saving Privacy in the Digital Age, 2001, ISBN 0-14-024432-8.
• Matsui, Mitsuru (1994). “Linear Cryptanalysis Method for DES Cipher”. Lecture Notes in Computer Science 765: 386–397. doi:10.1007/3-540-48285-7. http://www.springerlink.com/content/92509p5l4ravyn62/. 
• Mitsuru Matsui (1994). “The First Experimental Cryptanalysis of the Data Encryption Standard”. Lecture Notes in Computer Science 839: 1–11. doi:10.1007/3-540-48658-5_1. http://www.springerlink.com/content/vrteugmt7erqqbw1/. 
• National Bureau of Standards, Data Encryption Standard, FIPS-Pub.46. National Bureau of Standards, U.S. Department of Commerce, Washington D.C., January 1977.

• FIPS 46-3:DES標準についての公式文書 (PDF);やや古いHTML版
• COPACOBANA 1万ドルでDESを破るマシン。ルール大学ボーフムとキール大学がFPGAを使って製作。
• RFC4772 :Security Implications of Using the Data Encryption Standard (DES)