Data Encryption Standard

data encryption standard
	DESのファイステル関数（F関数）
一般
設計者	IBM
初版発行日	1977年（標準化は1979年1月）
派生元	Lucifer
後継	トリプルDES, GDES, DES-X, LOKI89（英語版）, ICE（英語版）
暗号詳細
鍵長	56ビット
ブロック長	64ビット
構造	均衡型Feistel構造
ラウンド数	16
最良の暗号解読法
	DESは今では総当り攻撃で解読可能であるため、安全ではない。2008年現在、最良の攻撃法は線形解読法で、243の既知平文を必要とし、時間計算量は239–43である(Junod, 2001)。選択平文を前提とすれば、データ計算量は4分の1に減じることができる(Knudsen and Mathiassen, 2000)。

Data Encryption Standard︵データ暗号化標準︶、略してDES︵デス、ディーイーエス^[要出典]︶は、アメリカ合衆国の旧国家暗号規格、もしくはその規格で規格化されている共通鍵暗号である。ブロック暗号の一種であり、1976年国立標準局 (NBS) がアメリカ合衆国の公式連邦情報処理標準 (FIPS) として採用し、その後国際的に広く使われた。56ビットの鍵を使った共通鍵暗号を基盤としている。そのアルゴリズムは、機密設計要素、比較的短い鍵長、アメリカ国家安全保障局 (NSA) がバックドアを設けたのではないかという疑いなどで、当初物議をかもしていた。結果としてDESは、現代のブロック暗号とその暗号解読の理解に基づいて学究的に徹底した精査を受けた。

DESは今では多くの用途において安全ではないと見なされている。これは主に56ビットという鍵長が短すぎることに起因する。1999年1月、distributed.netと電子フロンティア財団は共同で、22時間15分でDESの鍵を破ったことを公表した。この暗号の理論上の弱さを示した解析結果もあるが、そのような弱さを実際に利用することが可能というわけではない。アルゴリズム自体は実用上安全であるとされ、トリプルDESという形で使われているが、理論的攻撃方法は存在する。近年、Advanced Encryption Standard (AES)に取って代わられた。なお、標準としてのDESとアルゴリズムを区別することがあり、アルゴリズムを Data Encryption Algorithm (DEA)と称することがある。

DESが制定されるまでの経緯

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構造に基づいて設計された。

NSAの設計への関与

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

批判はあったが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]。

年表

日付	出来事
1973年5月15日	NBSが標準暗号アルゴリズムの要求仕様を公開（1回目）。
1974年8月27日	NBSが標準暗号アルゴリズムの要求仕様を公開（2回目）。
1975年3月17日	コメントを求めるため、DESが Federal Register で公表された。
1976年8月	DESに関する最初のワークショップ開催。
1976年9月	2回目のワークショップ。DESの数学的基盤について議論。
1976年11月	DESを標準として承認。
1977年1月15日	DESを FIPS PUB 46 として公表。
1983年	DESについて、1回目の再承認を実施。
1986年	HBOがDESをベースとした衛星テレビ放送のスクランブリングシステム Videocipher II を実用化。
1988年1月22日	DES について2回目の再承認を行い、FIPS PUB 46 を置き換える FIPS 46-1 を制定。
1990年7月	ビハムとシャミアが差分解読法を再発見し、DESに似た15ラウンドの暗号に適用。
1992年	ビハムとシャミアが総当り攻撃よりも計算量が少ない理論上の攻撃法（差分解読法）があることを発表。ただし、必要とする選択平文数は非現実的な2⁴⁷だった。
1993年12月30日	DES について3回目の承認を行い、FIPS 46-2 とした。
1994年	線形解読法を用いた既知平文攻撃によって、DESの解読が初めて実際に行われた (松井充)。平文と暗号文の組数は、2⁴³だった。
1997年6月	DESCHALL（英語版）によりDESで暗号化されたメッセージの解読が行われ、初めて一般に公表。
1998年7月	電子フロンティア財団のDESクラッカー（英語版）が56時間でDESの鍵を破った。
1999年1月	Deep Crack と distributed.net が共同で22時間15分でDESの鍵を破った。
1999年10月25日	DESについて4回目の承認を行い FIPS 46-3としたが、トリプルDESの使用を推奨し、シングルDESは古いシステムでのみ使用することとした。
2001年11月26日	Advanced Encryption Standard (AES) を FIPS 197として公表。
2002年5月26日	AES規格が発効。
2004年7月26日	FIPS 46-3（および関連する規格群）の廃止が Federal Register で提案された^[15]。
2005年5月19日	NISTがFIPS 46-3を廃止^[16]
2006年4月	ルール大学ボーフムとキール大学でFPGAを使った並列マシンCOPACOBANAを開発し、1万ドルのハードウェアコストで9日間をかけてDESを破った^[17]。その後1年以内にソフトウェアを改良し、平均で6.4日で破れるようになった。

詳細

図 1— DESのFeistel構造全体

図 2— DESのFeistel関数（F-関数）

図 3— DESの鍵スケジュール

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構造の特徴である。

Feistel(F)関数

図2にあるF-関数はブロックの半分︵32ビット︶を一度に処理する。以下の4段階がある。 (一)Expansion - expansion permutation と呼ばれる方式で32ビットを48ビットに拡張する。図では Eで示されている部分である。入力のうち半分のビットの複製16ビット分を出力のビット列に追加する。その出力は8個の6ビットの部分からなり、それら6ビットのうちの中央4ビットは入力の対応する4ビットの部分と同じで、両端の1ビットずつは入力上で隣接する部分のビットの複製である。 (二)Key mixing - ラウンド鍵と上の出力結果をXOR操作で結合する。ラウンド鍵は48ビットで、もともとの鍵から﹁鍵スケジュール﹂︵後述︶によって16個のラウンド鍵が生成される。 (三)Substitution - ラウンド鍵を混ぜた後、6ビットずつに分けてSボックス (substitution box) に入力する。8個のSボックスは入力の6ビットから4ビットの出力を生成し、このときルックアップテーブルの形で提供される非線形な変換を行う。SボックスがDESの安全性の根幹であり、これが無かったならば暗号化の処理は線形であり容易に破ることができることになる。 (四)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に代わるアルゴリズム

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種類の理論上の攻撃方法が知られている。それらは総当り攻撃よりも理論上は計算量が少ないが、非現実的な量の既知平文か選択平文を必要とし、実用化はされていない。

総当り攻撃

The EFFが25万ドルで製作したDES解読機。1,856のカスタムチップで構成され、DESの鍵を総当りで数日間で破ることができる。写真は Deap Crack チップをいくつか装備したDES解読機用回路基板。

どんな暗号についても、最も基本となる攻撃法は総当り攻撃、すなわち鍵のとりうる値を全て試す方法である。鍵の長さが鍵のとりうる値の個数に直接関係してくるため、総当りが現実的かどうかも鍵の長さで決まる。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 ここで

{\overline {x}}

は

x

のビット毎の反転である。

E_{K}

は鍵

K

を使った暗号化を意味する。

P

は平文、

C

は暗号ブロック列である。相補性があるということは、総当り攻撃に必要な試行回数は2分の1で済むことを意味する。 DESには4つのいわゆる﹁弱い鍵﹂がある。暗号化 (E) と復号 (D) で弱い鍵を使うと、どちらも同じ効果がある。

{\displaystyle E_{K}(E_{K}(

または

E_{K}=D_{K}

また、6組の﹁やや弱い鍵﹂もある。弱い鍵の1つ

K_{1}

を使った暗号化は、ペアのもう一方の

K_{2}

を使った復号と等価である。

{\displaystyle E_{K_{1}}(E_{K_{2}}(

または

E_{K_{2}}=D_{K_{1}}

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

\{E_{K}\}

︵鍵

K

がとりうる全ての値の集合︶は関数合成において群ではないし、1つの群に閉じていない (Campbell and Wiener, 1992)。これがもし群であるならば、DESは容易に破ることができ、トリプルDESにしても安全性は向上しなかったとされている。 DESの暗号学的安全性は最大でも約64ビットである。例えば、個々のラウンド鍵を元の1つの鍵から生成せずそれぞれ独立に供給すれば、安全性は768ビットになりそうなものだが、この限界によりそうならないことが知られている。

脚注・出典

(一)^ Walter Tuchman (1997). "A brief history of the data encryption standard". Internet besieged:countering cyberspace scofflaws. ACM Press/Addison-Wesley Publishing Co. New York, NY, USA. pp. 275–280. (二)^ RSA Laboratories. “Has DES been broken?”. 2009年5月27日閲覧。 (三)^ Schneier. Applied Cryptography (2nd ed.). p. 280 (四)^ Davies, D.W.; W.L. Price (1989). Security for computer networks, 2nd ed.. John Wiley & Sons (五)^ Robert Sugarman (editor) (July 1979). “On foiling computer crime”. IEEE Spectrum (IEEE). (六)^ P. Kinnucan (October 1978). “Data Encryption Gurus:Tuchman and Meyer”. Cryptologia 2(4): 371. doi:10.1080/0161-117891853270. (七)^ Thomas R. Johnson. “American Cryptology during the Cold War, 1945-1989.Book III:Retrenchment and Reform, 1972-1980”. United States Cryptologic History 5(3). (八)^ Konheim. Computer Security and Cryptography. p. 301 (九)^ ^a ^bLevy, Crypto, p. 55 (十)^ ^a ^b“NIST Special Publication 800-67 Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher, Version 1.1” (PDF) (English). National Institute of Standards and Technology. p. 6. 2016年10月9日閲覧。 (11)^ American National Standards Institute, ANSI X3.92-1981 American National Standard, Data Encryption Algorithm (12)^ “ISO/IEC 18033-3:2005 Information technology — Security techniques — Encryption algorithms — Part 3:Block ciphers”. Iso.org (2008年10月15日). 2009年6月2日閲覧。 (13)^ Bruce Schneier, Applied Cryptography, Protocols, Algorithms, and Source Code in C, Second edition, John Wiley and Sons, New York (1996) p. 267 (14)^ William E. Burr, "Data Encryption Standard", in NIST's anthology "A Century of Excellence in Measurements, Standards, and Technology:A Chronicle of Selected NBS/NIST Publications, 1901–2000. HTML PDF (15)^ “FR Doc 04-16894”. Edocket.access.gpo.gov. 2009年6月2日閲覧。 (16)^ “Federal Register vol 70, number 96” (PDF) (English). Office of the Federal Register, National Archives and Records Administration (2005年5月19日). 2016年10月9日閲覧。 (17)^ S. Kumar, C. Paar, J. Pelzl, G. Pfeiffer, A. Rupp, M. Schimmler, "How to Break DES for Euro 8,980". 2nd Workshop on Special-purpose Hardware for Attacking Cryptographic Systems — SHARCS 2006, Cologne, Germany, April 3-4, 2006. (18)^ “FIPS 81 - Des Modes of Operation”. Itl.nist.gov. 2016年10月9日閲覧。 (19)^ “FIPS 74 - Guidelines for Implementing and Using the NBS Data”. Itl.nist.gov. 2014年1月3日時点のオリジナルよりアーカイブ。2016年10月9日閲覧。 (20)^ Stallings, W. Cryptography and network security:principles and practice. Prentice Hall, 2006. p. 73 (21)^ “US GOVERNMENT'S ENCRYPTION STANDARD BROKEN IN LESS THAN A DAY” (PDF) (English). distributed.net (1999年1月19日). 2016年10月9日閲覧。

参考文献

Biham, Eli and Adi Shamir (1991). “Differential Cryptanalysis of DES-like Cryptosystems”. Journal of Cryptology 4 (1): 3–72. doi:10.1007/BF00630563. (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. (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.
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.
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)

[

[2]

[3]

[4]

[5]

[6]

[

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]