Data Encryption Standard

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

DESの起源は1970年代初めに遡る。1972年、アメリカ政府はコンピュータセキュリティが重要であるという研究結果を得た。そこでNBS（National Bureau of Standard。合衆国標準局。現在のNIST（アメリカ国立標準技術研究所））が、政府全体で機密情報を暗号化するための標準規格が必要だと判断した。それに応じて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構造に基づいて設計された。

詳細

DESは原型ともいうべきブロック暗号であり、固定ビット長の平文を入力とし、一連の複雑な操作によって同じ長さの暗号文を出力するアルゴリズムである。DESの場合、ブロック長は64ビットである。また、変換をカスタマイズする鍵を使うため、暗号化に使った鍵を知っている者だけが復号できる。鍵は見た目は64ビットだが、そのうち8ビットはパリティチェックに使うため、アルゴリズム上の実際の鍵の長さは56ビットである。
他のブロック暗号と同様、DES自体は暗号化の安全な手段ではなく、暗号利用モードで使う必要がある。FIPS-81 はDES用のいくつかのモードを示している。その他のDESの利用法については FIPS-74 に詳しい。

全体構造

アルゴリズムの全体構造を図1に示す。16の処理工程があり、それらを「ラウンド」と呼ぶ。また、最初と最後に並べ替え処理があり、それぞれ IP および FP と呼ぶ。IP と FP はちょうど逆の処理を行う。IP と FP は暗号化にはほとんど関係ないが、1970年代のハードウェアでブロックの入出力を行う部分として含まれており、同時にそれによってソフトウェアによるDESの処理が遅くなる原因にもなっている。
ラウンドでの処理の前にブロックは半分（32ビット）ずつに分けられ、それぞれ異なる処理を施される。この十字交差構造をFeistel構造と呼ぶ。Feistel構造を使うと、暗号化と復号は非常に良く似た処理になる。違いは、復号ではラウンド鍵を逆の順序で適用するという点だけであり、アルゴリズムは同一である。このため実装が単純化でき、特にハードウェアで実装する場合に両者を別々に実装する必要が無い。
⊕ という記号は排他的論理和 (XOR) を意味する。F-関数はブロックの半分を何からの鍵でかき混ぜる。F-関数の出力をブロックの残り半分と結合し、次のラウンドに行く前にその半分同士を入れ替える。最後のラウンドの後は入れ替えを行わない。これは、暗号化と復号を似たプロセスで行うFeistel構造の特徴である。

鍵スケジュール

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

総当り攻撃

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