Data Encryption Standard

NSAの設計への関与

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

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

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

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

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

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

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

標準暗号としての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日に脆弱なため DES (FIPS 46-3) は廃止となった。トリプルDESの方は2023年12月31日に廃止となった。

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

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

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

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

年表

全体構造

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

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

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

Feistel(F)関数

図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については標準として採用される以前から鍵の短さが懸念されていた。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ということができる。

総当り攻撃よりも高速な攻撃法

総当り攻撃よりも少ない計算量で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ビットになりそうなものだが、この限界によりそうならないことが知られている。

総当り攻撃での所要時間

Hashcat を使用すると総当り攻撃で解読にかかる所要時間がわかる。Hashcat のベンチマーク結果で x H/s の時、2⁵⁶ ÷ x ÷ 2 秒が平均所要時間となる。最後の ÷ 2 は全 2⁵⁶ 通りのうち平均所要時間は半分なので2で割っている。

• NVIDIA GeForce RTX 4090 1枚 - 146.6 GH/s なので68時間16分
• NVIDIA GeForce RTX 4090 8枚 - 1152.4 GH/s なので8時間41分
• NVIDIA GeForce RTX 5090 Founders Edition 1枚 - 179.4 GH/s なので55時間47分

クラウドで一時的に多数のGPUをレンタルし並列化すると短い所要時間で解読できる。GeForce RTX 4090 を136枚レンタルすると30分で解読できる。例えば2026年7月2日現在 Vast.ai では GeForce RTX 4090 を$0.35/時でレンタルできるので、解読コストは$23.80（3832円）である。