データ暗号化規格
データ暗号化規格
DESのFeistel関数（F関数）
一般的な
デザイナーIBM
初版1975年（連邦官報）（1977年1月に標準化）
由来ルシファー
後継者トリプルDES、G-DES、DES-X、LOKI89、ICE
暗号の詳細
キーサイズ56ビット
ブロックサイズ64ビット
構造バランス型フェイステルネットワーク
ラウンド16
最高の公開暗号解読
DESは、ブルートフォース攻撃の実行可能性のため、当初から安全ではないと考えられてきました。[ 1 ]こうした攻撃は実際に実証されており（EFF DESクラッカーを参照）、現在ではサービスとして市場に出回っています。2008年現在、最も優れた解析的攻撃は線形暗号解読であり、これは2の43乗の既知平文を必要とし、計算時間は2の39乗から43乗です。

データ暗号化規格（DES / ˌ d iː ˌ iː ˈ ɛ s , d ɛ z /）は、デジタルデータの暗号化に使用される対称鍵アルゴリズムです。鍵長が56ビットと短いため、現代のアプリケーションには安全性が低すぎるものの、暗号技術の進歩に大きな影響を与えてきました。

このアルゴリズムは1970年代初頭にIBMで開発され、ホルスト・ファイステルによる初期の設計に基づいていました。機密扱いではない電子政府データの保護のための候補を提案するよう、米国標準局（NBS）から要請を受け、NBSに提出されました。1976年、国家安全保障局（NSA）との協議を経て、NBSは若干の修正を加えたバージョン（差分暗号解読法に対する耐性は強化されましたが、ブルートフォース攻撃に対する耐性は弱められました）を選択し、 1977年に米国の公式連邦情報処理標準（FIPS）として公開されました。 [ 2 ]

NSA承認の暗号化規格の公開は、その迅速な国際的採用と広範な学術的精査につながった。機密扱いの設計要素、対称鍵ブロック暗号設計における比較的短い鍵長、そしてNSAの関与が論争を引き起こし、バックドアの疑惑が浮上した。こうした疑惑を引き起こしたSボックスは、NSAが秘密裏に知っていた脆弱性（差分暗号解読）に対処するために設計されたものであった。しかし、NSAは鍵長を大幅に削減することも確実にしていた。[ 2 ] このアルゴリズムは長年にわたり学術的精査を受け、ブロック暗号とその暗号解読に関する現代的な理解が生まれた。

DESは、鍵サイズが56ビットと比較的短いため安全ではありません。1999年1月、distributed.netと電子フロンティア財団が協力し、22時間15分でDES鍵を公開解読しました（§ 年表を参照）。この暗号の理論的な弱点を示す分析結果もいくつかありますが、実際には実行不可能です。[ 3 ] DESはNISTによって標準としては撤回されました。[ 4 ]その後、セキュリティレベルを高めるためにトリプルDESという変種が開発されましたが、これも今日でも安全ではないと考えられています。DESは、Advanced Encryption Standard（AES） に取って代わられました。

一部の文書では、DES 標準とそのアルゴリズムを区別し、アルゴリズムをDEA (データ暗号化アルゴリズム) と呼んでいます。

歴史

DESの起源は1972年にさかのぼります。当時、米国政府のコンピュータセキュリティに関する国立標準局の調査で、機密扱いされていない機密情報を暗号化するための政府全体の標準が必要であることが判明しました。[ 5 ]

同じ頃、エンジニアのモハメド・アタラは1972年にアタラ社を設立し、最初のハードウェア・セキュリティ・モジュール（HSM）である「アタラ・ボックス」を開発し、1973年に商品化されました。これは安全なPIN生成キーでオフラインデバイスを保護し、商業的に成功を収めました。銀行やクレジットカード会社はアタラが市場を独占することを恐れ、国際的な暗号化規格の開発が促進されました。[ 4 ]アタラは銀行市場におけるIBMの初期の競合企業であり、DES規格の開発に携わったIBMの従業員から影響を受けた企業として挙げられています。[ 6 ]その後、 IBM 3624は、以前のアタラシステムと同様のPIN検証システムを採用しました。[ 7 ]

1973年5月15日、NBSはNSAと協議した後、厳格な設計基準を満たす暗号の提案を募集した。提出された提案はどれも適切ではなかった。2度目の募集は1974年8月27日に発行された。この時はIBMが、1973年から1974年にかけて開発された、以前のアルゴリズムであるホルスト・ファイステルのルシファー暗号をベースにした暗号を、適切と判断された候補として提出した。暗号の設計と分析に関わったIBMのチームには、ファイステル、ウォルター・タックマン、ドン・コッパースミス、アラン・コンハイム、カール・マイヤー、マイク・マティアス、ロイ・アドラー、エドナ・グロスマン、ビル・ノッツ、リン・スミス、ブライアント・タッカーマンがいた。

NSAの設計への関与

1975年3月17日、DESの提案が連邦官報に掲載されました。一般からの意見募集が行われ、翌年には提案された標準について議論するための公開ワークショップが2回開催されました。公開鍵暗号の先駆者であるマーティン・ヘルマン氏とホイットフィールド・ディフィー氏[ 1 ]からは批判が寄せられ、鍵長の短縮と謎の「Sボックス」がNSAによる不正な干渉の証拠であると指摘されました。NSAがアルゴリズムを密かに弱体化させ、他の誰にも暗号化されたメッセージを容易に解読できないようにしたのではないかという疑惑が持たれました。DESの設計者の一人であるアラン・コンハイム氏は、「我々はSボックスをワシントンに送りました。戻ってきたら、全てが異なっていました」と述べています。[ 9 ]米国上院情報特別委員会は、 NSAの行動を審査し、不正な関与があったかどうかを判断しました。1978年に公表された非機密扱いの調査結果概要の中で、委員会は次のように記しています。

DESの開発において、NSAはIBMに鍵サイズの縮小で十分であると納得させ、Sボックス構造の開発を間接的に支援し、最終的なDESアルゴリズムがNSAの知る限り統計的または数学的な弱点がないことを証明した。[ 10 ]

しかし、

NSAはアルゴリズムの設計に一切手を加えなかった。IBMはアルゴリズムを発明・設計し、それに関するすべての重要な決定を下し、合意された鍵サイズがDESが想定されるすべての商用アプリケーションにとって十分すぎるほどであることに同意した。[ 11 ]

DESチームのもう一人のメンバーであるウォルター・タックマンは、「DESアルゴリズムはIBM社内でIBM社員を使って完全に開発された。NSAは一本の線さえも指示しなかった！」と述べています。[ 12 ] 対照的に、NSAの暗号の歴史に関する機密解除された本には次のように記されています。

1973年、NBSは民間企業に対しデータ暗号化規格（DES）の策定を要請しました。最初の提案は期待外れだったため、NSAは独自のアルゴリズムの開発に着手しました。その後、研究・エンジニアリング担当副長官のハワード・ローゼンブラムは、IBMのウォルター・タックマンがルシファーの一般利用に向けた改良版を開発していることを知りました。NSAはタックマンに認可を与え、NSAと共同でルシファーの改良版を開発するよう依頼しました。[ 13 ]

そして

NSAはIBMと緊密に協力し、ブルートフォース攻撃を除くあらゆる攻撃に対するアルゴリズムの強化と、Sボックスと呼ばれる置換表の強化を図りました。一方で、NSAはIBMに対し、鍵長を64ビットから48ビットに短縮するよう説得を試みました。最終的にIBMは56ビット鍵で妥協しました。[ 14 ] [ 15 ]

Sボックスに隠された脆弱性についての疑惑の一部は、イーライ・ビハムとアディ・シャミールがブロック暗号を解読する一般的な方法である差分暗号解読法を独立に発見し、公開した1990年に払拭されました。DESのSボックスは、ランダムに選択された場合よりも攻撃に対してはるかに耐性があり、IBMが1970年代にこの手法を知っていたことを強く示唆しています。これは実際に当てはまり、1994年にドン・カッパースミスがSボックスの元の設計基準の一部を発表しました。[ 16 ]スティーブン・レヴィによると、IBMワトソンの研究者は1974年に差分暗号解読攻撃を発見し、NSAからその手法を秘密にしておくように求められました。[ 17 ]コッパースミスはIBMの秘密保持の決定について、「差分暗号解析は非常に強力なツールであり、多くの計画に利用される可能性があり、そのような情報が公になると国家安全保障に悪影響を与える可能性があるという懸念があったためだ」と述べている。レヴィはウォルター・タックマンの言葉を引用している。「彼らは我々にすべての文書に機密スタンプを押すように要求した。…実際、それらは米国政府の機密文書とみなされていたため、それぞれに番号を付けて金庫に保管した。彼らはそうするように言ったので、私はそうしました」。[ 17 ]ブルース・シュナイアーは、「NSAの『微調整』がDESのセキュリティを実際に向上させたことを学界が理解するのに20年かかった」と述べている。[ 18 ]

標準としてのアルゴリズム

批判にもかかわらず、DESは1976年11月に連邦標準規格として承認され、1977年1月15日にFIPS PUB 46として発行され、すべての非機密データへの使用が認可されました。その後、1983年、1988年（FIPS-46-1として改訂）、1993年（FIPS-46-2）、そして1999年（FIPS-46-3）にも標準規格として再承認され、後者は「トリプルDES」（下記参照）を規定しました。2002年5月26日、DESは公募を経て、最終的に高度暗号化標準規格（AES）に置き換えられました。2005年5月19日、FIPS 46-3は正式に廃止されましたが、NISTは2030年まで機密性の高い政府情報に対してトリプルDESを承認しています。 [ 19 ]

このアルゴリズムはANSI X3.92（現在X3はINCITS、ANSI X3.92はANSI INCITS 92として知られています） [ 20 ]、NIST SP 800-67 [ 19 ]、ISO/IEC 18033-3 [ 21 ] （ TDEAの構成要素として）でも規定されています。

もう一つの理論的な攻撃法である線形解読法は1994年に発表されましたが、 DESが非常に実用的に攻撃可能であることを実証し、代替アルゴリズムの必要性を浮き彫りにしたのは、1998年に電子フロンティア財団が公開したDESクラッカーでした。これらの方法やその他の解読法については、この記事の後半でより詳細に説明します。

DESの導入は、暗号学、特にブロック暗号の解読法に関する学術研究のきっかけとなったと考えられています。NISTのDESに関する回顧録によると、

DESは、非軍事分野における暗号アルゴリズムの研究と開発を「活性化させた」と言えるでしょう。1970年代には、軍や諜報機関に所属する者を除けば暗号学者はほとんどおらず、暗号に関する学術研究もほとんど行われていませんでした。しかし現在では、多くの学術界で活躍する暗号学者、強力な暗号プログラムを持つ数学科、そして民間の情報セキュリティ企業やコンサルタントが存在します。暗号解読者の一世代は、DESアルゴリズムの解析（つまり「解読」）に携わってきました。暗号学者ブルース・シュナイアーの言葉によれば[ 22 ]、「DESは暗号解読分野を活性化させる上で、他の何よりも大きな役割を果たしました。今や研究すべきアルゴリズムが生まれたのです。」1970年代と1980年代の暗号に関する公開文献の驚くほど多くの部分がDESを扱っており、DESはそれ以降のあらゆる対称鍵アルゴリズムの基準となっています[ 23 ] 。

年表

日付 年 イベント
5月15日 1973 NBSが標準暗号化アルゴリズムの最初の要求を公開
8月27日 1974 NBSが暗号化アルゴリズムに関する2回目の要求を公開
3月17日 1975 DESは連邦官報にコメント募集のために 掲載されている
8月 1976 DESに関する最初のワークショップ
9月 1976 DESの数学的基礎を議論する第2回ワークショップ
11月 1976 DESが標準として承認される
1月15日 1977 DESはFIPS標準FIPS PUB 46として公開されています。
6月 1977 ディフィーとヘルマンはDES暗号は総当たり攻撃によって解読できると主張している。[ 1 ]
1983 DESが初めて再確認される
1986 DESに基づくテレビ衛星スクランブルシステムである Videocipher IIがHBOで使用開始
1月22日 1988 DESはFIPS 46-1として2度目の再確認を受け、FIPS PUB 46に取って代わりました。
7月 1991 ビハムとシャミールは差分暗号解読法を再発見し、それを 15 ラウンドの DES のような暗号システムに適用しました。
1992 ビハムとシャミールは、総当たり攻撃よりも複雑さの少ない最初の理論的攻撃法である差分解読法を報告した。しかし、この攻撃には非現実的な247個の選択平文が必要となる。
12月30日 1993 DESはFIPS 46-2として3度目の再確認を受けました。
1994 DES の最初の実験的な暗号解読は線形暗号解読を使用して実行されました (Matsui、1994)。
6月 1997 DESCHALLプロジェクトは、 DES で暗号化されたメッセージを初めて公開で解読しました。
7月 1998 EFFのDES クラッカー(Deep Crack)は56 時間で DES キーを解読します。
1月 1999 Deep Crackとdistributed.net を組み合わせると、22 時間 15 分で DES キーを解読できます。
10月25日 1999 DES は、トリプル DESの推奨使用を指定し、シングル DES はレガシー システムでのみ許可される、 FIPS 46-3 として 4 回目の再確認されました。
11月26日 2001 高度暗号化規格はFIPS 197で公開されている。
5月26日 2002 AESが発効
7月26日 2004 FIPS 46-3（および関連するいくつかの規格）の撤回が連邦官報で提案されている[ 24 ]
5月19日 2005 NISTはFIPS 46-3を撤回しました（連邦官報第70巻、第96号を参照）。
4月 2006 ドイツのボッフム大学とキール大学のFPGAベースの並列マシンCOPACOBANAは、1万ドルのハードウェアコストで9日間でDESを解読しました。 [ 25 ] 1年以内にソフトウェアの改良により平均時間は6.4日に短縮されました。
11月 2008 COPACOBANAの後継機であるRIVYERA マシンでは、平均時間が 1 日未満に短縮されました。
8月 2016 オープンソースのパスワードクラッキングソフトウェアhashcatは、汎用GPU上でDESブルートフォース攻撃を実行できるようになりました。ベンチマークテストでは、市販の1,000ドルのNvidia GeForce GTX 1080 Ti GPU 1基で平均15日（完全な網羅的検索には30日）でキーを復元できることが示されています。8基のGTX 1080 Ti GPUを搭載したシステムでは、平均2日以内にキーを復元できます。
7月 2017 レインボーテーブルを用いた選択平文攻撃は、特定の選択平文1122334455667788のDES鍵を25秒で復元できます。平文ごとに新しいレインボーテーブルを計算する必要があります。レインボーテーブルは限定的にダウンロード可能です。[ 26 ]

説明

Initial permutationFeistel functionFeistel functionFeistel functionFeistel functionFinal permutationXORXORXORXOR
図1 — DESの全体的なFeistel構造

DESは典型的なブロック暗号です。DESは、固定長の平文ビット列を一連の複雑な演算によって同じ長さの暗号文ビット列に変換するアルゴリズムです。DESの場合、ブロックサイズは64ビットです。DESはまた、変換をカスタマイズするために鍵を使用するため、暗号化に使用された特定の鍵を知っている人だけが復号を実行できるとされています。鍵は表面上は64ビットで構成されていますが、実際にアルゴリズムで使用されるのはそのうち56ビットだけです。8ビットはパリティチェックのみに使用され、その後は破棄されます。したがって、有効な鍵長は56ビットです。

鍵は通常、奇数パリティ付きの8バイトで保存または送信されます。ANSI X3.92-1981（現在はANSI INCITS 92–1981として知られています）のセクション3.5によると、以下のようになります。

KEYの各8ビットバイトの1ビットは、鍵の生成、配布、および保存におけるエラー検出に利用されます。ビット8、16、…、64は、各バイトが奇数パリティであることを保証するために使用されます。

他のブロック暗号と同様に、DES自体は安全な暗号化手段ではなく、特定の動作モードで使用する必要があります。FIPS-81は、DESで使用するためのいくつかのモードを規定しています。[ 27 ] DESの使用に関する詳細なコメントは、FIPS-74に記載されています。[ 28 ]

復号化では暗号化と同じ構造が使用されますが、キーは逆の順序で使用されます。（これにより、双方向で同じハードウェアまたはソフトウェアを使用できるという利点があります。）

全体的な構造

アルゴリズムの全体構造は図1に示されている。ラウンドと呼ばれる16の同一の処理段階がある。また、 IPとFPと呼ばれる初期順列と最終順列があり、これらは逆の動作をする（IPはFPの動作を「元に戻す」、FPはIPの動作を「元に戻す」）。IPとFPは暗号学的な意味合いを持たないが、1970年代半ばの8ビットベースのハードウェアへのブロックの読み込みを容易にするために追加された。[ 29 ]

メインラウンドの前に、ブロックは32ビットの2つの半分に分割され、交互に処理されます。この交差はFeistel方式として知られています。Feistel構造により、復号と暗号化は非常によく似たプロセスになります。唯一の違いは、復号時にサブキーが逆の順序で適用されることです。アルゴリズムの残りの部分は同一です。これにより、暗号化と復号のアルゴリズムを別々に用意する必要がないため、特にハードウェア実装が大幅に簡素化されます。

⊕記号は 排他的論理和（XOR）演算を表します。F関数は、ブロックの半分と鍵の一部をスクランブルします。F関数の出力は、ブロックの残りの半分と結合され、次のラウンドの前に半分が入れ替えられます。最終ラウンドの後、半分が入れ替えられます。これは、暗号化と復号化を同様のプロセスにするFeistel構造の特徴です。

フェイステル（F）関数

図 2 に示す F 関数は、一度に半分のブロック (32 ビット) を操作し、次の 4 つのステージで構成されます。

Expansion functionSubstitution box 1Substitution box 2Substitution box 3Substitution box 4Substitution box 5Substitution box 6Substitution box 7Substitution box 8PermutationXOR
図2 —DESのFeistel関数（F関数）
  1. 拡張：32ビットのハーフブロックは、図中のEで示される拡張順列を用いて、ビットの半分を複製することで48ビットに拡張されます。出力は8つの6ビット（8 × 6 = 48ビット）の断片で構成され、各断片には対応する4つの入力ビットのコピーと、各入力断片の両側のすぐ隣のビットのコピーが含まれます。
  2. キーミキシング：結果はXOR演算によってサブキーと結合されます。16個の48ビットサブキー（各ラウンドに1つずつ）は、キースケジュール（後述）に基づいてメインキーから生成されます。
  3. 置換：サブキーを混合した後、ブロックは8つの6ビットの断片に分割され、Sボックス（置換ボックス）で処理されます。8つのSボックスはそれぞれ、ルックアップテーブルとして提供される非線形変換に従って、6つの入力ビットを4つの出力ビットに置き換えます。SボックスはDESのセキュリティの中核を担っており、Sボックスがなければ暗号は線形になり、簡単に解読できてしまいます。
  4. 順列：最後に、Sボックスからの32個の出力は、固定順列（Pボックス）に従って並べ替えられます。これは、順列処理後、このラウンドの各Sボックスの出力ビットが、次のラウンドで4つの異なるSボックスに分散されるように設計されています。

S ボックスからの置換の交互、および P ボックスと E 展開からのビットの順列は、それぞれいわゆる「混乱と拡散」をもたらします。これは、1940 年代にクロード・シャノンが安全かつ実用的な暗号に必要な条件として 特定した概念です。

主なスケジュール

Permuted choice 1Permuted choice 2Permuted choice 2Permuted choice 2Permuted choice 2Left shift by 1Left shift by 1Left shift by 1Left shift by 1Left shift by 2Left shift by 2Left shift by 1Left shift by 1
図3 — DESの鍵スケジュール

図3は、暗号化のための鍵スケジュール、つまりサブキーを生成するアルゴリズムを示しています。まず、Permuted Choice 1（PC-1）によって、最初の64ビットから56ビットの鍵が選択されます。残りの8ビットは破棄されるか、パリティチェックビットとして使用されます。次に、56ビットは28ビットずつ2つの半分に分割され、各半分は個別に扱われます。次のラウンドでは、両方の半分が1ビットまたは2ビット（ラウンドごとに指定）だけ左に回転され、Permuted Choice 2（PC-2）によって48ビットのサブキーが選択されます。これは、左半分から24ビット、右半分から24ビットです。この回転（図では「<<<」で示されています）は、各サブキーで異なるビットセットが使用されることを意味します。各ビットは、16個のサブキーのうち約14個で使用されます。

復号の鍵スケジュールも同様で、サブ鍵の順序は暗号化とは逆になります。この変更点を除けば、プロセスは暗号化と同じです。すべてのローテーションボックスに同じ28ビットが渡されます。

擬似コード

DES アルゴリズムの 疑似コードは次のとおりです。

// すべての変数は符号なし64ビットです// 前処理: バイト単位のサイズ差でパディングし、長さが64ビットの倍数になるようにメッセージをパディングします。var key // ユーザーが指定したキーvar keys [ 16 ] var left , right// キーを生成する// PC1 (64 ビットから 56 ビット) key := permutation ( key , PC1 ) left := ( key rightshift 28 ) and 0xFFFFFFF right := key and 0xFFFFFFFiが1から16の場合、右: =右左回転KEY_shift [ i ]左:=左左回転KEY_shift [ i ] var concat := (左左シフト28 )または右// PC2 (56ビットから48ビット)キー[ i ] := permutation ( concat , PC2 )で終了// メッセージを復号するには、キーの順序を逆にします。//パディングされたメッセージの64ビットチャンクごとに暗号化または復号化します。do var tmp// IP chunk := permutation ( chunk , IP ) left := chunk rightshift 32 right := chunk and 0xFFFFFFFF for i from 1 to 16 do tmp := right // E (32bits to 48bits) right := expansion ( right , E ) right := right xor keys [ i ] // Substitution (48bits to 32bits) right := substitution ( right ) // P right := permutation ( right , P ) right := right xor left left := tmp end for // Concat right and left var cipher_chunk := ( right leftshift 32 ) or left // FP cipher_chunk := permutation ( cipher_chunk , FP ) end for

セキュリティと暗号解読

DESの暗号解読に関する情報は他のどのブロック暗号よりも多く公開されているものの、現在までに最も実用的な攻撃は依然としてブルートフォース攻撃である。いくつかのマイナーな暗号解読特性が知られており、理論的な複雑さはブルートフォース攻撃よりも低いものの、実行には非現実的な数の既知または選択平文が必要となる3つの理論的な攻撃が可能である。これらの攻撃は実際には問題にならない。

ブルートフォース攻撃

あらゆる暗号において、最も基本的な攻撃方法は総当たり攻撃、つまり可能なすべての鍵を順番に試すことです。鍵の長さによって可能な鍵の数が決まり、したがってこのアプローチの実現可能性も決まります。DESについては、標準として採用される前から鍵サイズの妥当性について疑問が投げかけられていました。理論的な暗号解読ではなく、鍵サイズの小ささが代替アルゴリズムの必要性を決定づけました。NSAを含む外部コンサルタントとの議論の結果、鍵サイズは256ビットから56ビットに縮小され、1つのチップに収まるようになりました。[ 30 ]

EFFの 25 万ドルのDES クラッキング マシンには 1,856 個のカスタム チップが含まれており、数日間で DES キーを総当たり攻撃で解読できます。写真は、いくつかの Deep Crack チップが取り付けられた DES クラッカーの回路基板を示しています。

学界では、DESを解読するマシンに関する様々な提案がなされた。1977年、ディフィーとヘルマンは、DES鍵を1日で発見できるマシンを、推定2000万ドル（2024年時点で1億377万8144ドル相当）で提案した。[ 1 ] [ 31 ] 1993年までに、ウィーナーは、7時間以内に鍵を発見できる100万ドル（2024年時点で217万6687ドル相当）の鍵探索マシンを提案した。しかし、これらの初期の提案はどれも実装されず、少なくとも実装が公に認められることもなかった。DESの脆弱性は、1990年代後半に実証された。[ 32 ] 1997年、RSAセキュリティは一連のコンテストを後援し、DESで暗号化されたメッセージを最初に解読したチームに1万ドルの賞金を提供した。このコンテストは、ロック・ヴァーサー、マット・カーティン、ジャスティン・ドルスケが率いるDESCHALLプロジェクトが、インターネット上の何千台ものコンピュータのアイドルサイクルを使用して優勝した。DESを迅速に解読することが可能であることが実証されたのは1998年、サイバースペースの公民権団体である電子フロンティア財団（EFF）が約25万ドル（2024年に482,289ドルに相当）の費用をかけてカスタムDESクラッカーを構築したときだった（ EFF DESクラッカーを参照）。彼らの目的は、DESが理論だけでなく実際にも破られることを示すことでした。「多くの人は、自分の目で確かめるまでは真実を信じようとしません。数日でDESを解読できる物理的なマシンを彼らに見せることが、DESにセキュリティを託すのは無理だと人々に納得させる唯一の方法です。」マシンは、わずか2日間強の探索で鍵を総当たり攻撃で解読しました。

次に確認されたDESクラッカーは、ドイツのボッフム大学とキール大学のチームによって2006年に構築されたCOPACOBANAマシンでした。EFFマシンとは異なり、COPACOBANAは市販の再構成可能な集積回路で構成されています。XILINX Spartan-3 1000タイプのこれらのフィールドプログラマブルゲートアレイ（FPGA）120個が並列に実行されます。これらは20個のDIMMモジュールにグループ化されており、各モジュールには6個のFPGAが含まれています。再構成可能なハードウェアを使用することで、このマシンは他のコード解読タスクにも適用できます。[ 33 ] COPACOBANAの興味深い側面の1つは、そのコスト要因です。1台のマシンは約10000ドル（2024年には15,165ドルに相当）で構築できます。[ 34 ] EFFマシンに比べて約25分の1にコストが削減されたことは、デジタルハードウェアの継続的な改善の一例です（ムーアの法則を参照） 。 2007年以降、COPACOBANAの2つのプロジェクトパートナーからスピンオフしたSciEngines GmbHは、COPACOBANAの後継機の改良と開発を行ってきました。2008年には、同社のCOPACOBANA RIVYERAが128個のSpartan-3 5000を用いてDESの解読時間を1日未満に短縮しました。SciEngines RIVYERAは、128個のSpartan-3 5000 FPGAを用いて、総当たり攻撃によるDES解読の記録を保持していました。同社の256個のSpartan-6 LX150モデルは、この時間をさらに短縮しました。 [ 35 ]

2012年、デビッド・ハルトンとモクシー・マーリンスパイクは、48個のザイリンクスVirtex-6 LX240T FPGAを搭載したシステムを発表しました。各FPGAには、400MHzで動作し、総容量は768ギガキー/秒である。[ 36 ]このシステムは56ビットDES鍵空間全体を約26時間で網羅的に検索することができ、このサービスはオンラインで有料で提供されている。[ 37 ]ただし、このサービスは2024年からメンテナンスのためにオフラインになっている。 [ 37 ]

力ずくよりも速い攻撃

ブルートフォース検索よりも少ない複雑さでDESの16ラウンドすべてを破ることができる攻撃法として、差分解読法（DC）[ 38 ] 、線形解読法（LC）[ 39 ] 、およびデイヴィス攻撃[ 40 ]の3つが知られています。しかし、これらの攻撃法は理論上のものであり、実際には実行不可能であると一般的に考えられています。このような攻撃法は認証の弱点と呼ばれることもあります。

  • 差分解読法は1980年代後半にイーライ・ビハムとアディ・シャミールによって再発見されました。これはIBMとNSAの両方に以前から知られていましたが、秘密にされていました。16段の解読には、差分解読法で2の47乗個の選択平文が必要です。[ 38 ] DESは差分解読法に耐性を持つように設計されました。
  • 線形解読法は松井充によって発見され、2 43 個の既知の平文を必要とする。[ 39 ]この方法は松井によって 1994 年に実装され、報告された最初の DES の実験的解読法であった。DES がこの種の攻撃に耐えられるように調整されたという証拠はない。LC の一般化である多重線形解読法は 1994 年に提案され、ビリユコフらによってさらに改良された。彼らの分析によると、多重線形近似を使用することで、攻撃に必要なデータ量を少なくとも 4 分の 1 (つまり、2 43ではなく2 41 ) に削減できることが示唆されている。[ 41 ]線形解読法の選択平文バリアントでも、同様のデータ複雑性削減を実現できる。[ 42 ]ジュノーは線形暗号解読の実際の時間計算量を決定するためにいくつかの実験を行い、予想よりもいくらか速く、DES評価の2 39-41回に相当する時間が必要であると報告した。[ 43 ]
  • 改良デイヴィス攻撃：線形暗号解読法と差分暗号解読法は一般的な手法であり、多くの方式に適用できますが、デイヴィス攻撃はDESに特化した手法で、 80年代にドナルド・デイヴィスによって最初に提案され、1997年にビハムとビリュコフによって改良されました。 [ 40 ] [ 44 ]最も強力な攻撃では、2 50の既知の平文が必要で、計算量は 2 50で、成功率は 51% です。

DES暗号のラウンド数を減らしたバージョン、つまり16ラウンド未満のバージョンに対する攻撃も提案されています。このような分析により、安全性を確保するために必要なラウンド数や、フルバージョンでどの程度のセキュリティマージンが確保されているかについての洞察が得られます。

差分線形暗号解読法は1994年にラングフォードとヘルマンによって提案されたもので、差分暗号解読法と線形暗号解読法を1つの攻撃に組み合わせたものである。[ 45 ]この攻撃法の強化版では、2の15.8乗個の平文を選択して9ラウンドのDESを解読することができ、計算時間は2の29.2乗である。 [ 46 ]

マイナーな暗号解読特性

DESは相補性の性質を示し、すなわち

EK（P）＝C⟺EK¯（P¯）＝C¯{\displaystyle E_{K}(P)=C\iff E_{\overline {K}}({\overline {P}})={\overline {C}}}

ここで、はのビット補数であり、鍵を用いた暗号化を表し、はそれぞれ平文ブロックと暗号文ブロックを表します。補数性は、選択平文仮定の下で、ブルートフォース攻撃の作業量を2分の1（または1ビット）削減できることを意味します。定義により、この性質はTDES暗号にも適用されます。[ 47 ]ׯ{\displaystyle {\overline {x}}}×。{\displaystyle x.}EK{\displaystyle E_{K}}K。{\displaystyle K.}P{\displaystyle P}C{\displaystyle C}

DESには、いわゆる「弱い鍵」が4つあります。弱い鍵による暗号化（E）と復号化（D）は同じ効果を持ちます（「反転」を参照）。

EK（EK（P））＝P{\displaystyle E_{K}(E_{K}(P))=P}あるいは同等に、EK＝DK。{\displaystyle E_{K}=D_{K}.}

6組の準弱鍵も存在します。準弱鍵のペアの1つである を用いた暗号化は、もう1つの を用いた復号と同様に動作します。 K1{\displaystyle K_{1}}K2{\displaystyle K_{2}}

EK1（EK2（P））＝P{\displaystyle E_{K_{1}}(E_{K_{2}}(P))=P}あるいは同等に、EK2＝DK1。{\displaystyle E_{K_{2}}=D_{K_{1}}.}

実装において、弱い鍵と半弱い鍵を回避するのは容易です。明示的にテストするか、鍵をランダムに選択するだけで済みます。偶然に弱い鍵や半弱い鍵が選ばれる確率はごくわずかです。これらの鍵は攻撃に何のメリットももたらさないため、実際には他の鍵よりも弱いわけではありません。

DESは群ではないことも証明されている。より正確には、関数合成による集合（すべての可能なキーについて）は群ではないし、群に「近い」ものでもない。[ 48 ]これは長い間未解決の問題であったが、もしそうであればDESを破ることができただろうし、トリプルDESのような複数の暗号化モードでもセキュリティは向上しなかっただろう。なぜなら、異なるキーで繰り返し暗号化（および復号化）しても、別の単一のキーで暗号化した場合と同等になるからだ。[ 49 ]{EK}{\displaystyle \{E_{K}\}}K{\displaystyle K}

簡易DES

簡易DES（SDES）は、学生が現代の暗号解読技術を習得できるよう、教育目的のみで設計されました。SDESはDESと同様の構造と特性を持ちますが、鉛筆と紙を使って手作業で暗号化と復号をはるかに容易に行えるよう簡素化されています。SDESを学ぶことで、DESやその他のブロック暗号、そしてそれらに対する様々な暗号解読攻撃への理解が深まると考える人もいます。[ 50 ] [ 51 ] [ 52 ]

置換アルゴリズム

セキュリティへの懸念とDESのソフトウェアにおける動作速度の遅さから、研究者たちは1980年代後半から1990年代初頭にかけて、様々な代替ブロック暗号設計を提案し始めた。例えば、 RC5、Blowfish、IDEA、NewDES、SAFER、CAST5、FEALなどである。これらの設計のほとんどはDESの64ビットブロックサイズを維持し、「ドロップイン」代替として機能できたが、通常は64ビットまたは128ビットの鍵を使用していた。ソビエト連邦では、64ビットブロックサイズと256ビット鍵を使用するGOST 28147-89アルゴリズムが導入され、後にロシアでも使用された。

DESを強化するもう一つのアプローチは、トリプルDES（3DES）の開発でした。これは、各データブロックにDESアルゴリズムを3回適用することでセキュリティを強化するものです。しかし、3DESは非効率性と特定の暗号攻撃に対する脆弱性から、後にNISTによって非推奨となりました。

DESの重要な側面の一つは、その順列と鍵スケジューリングであり、これらは暗号化プロセスにおいて重要な役割を果たします。これらの順列を分析することで、DESのセキュリティ上の限界と代替アルゴリズムの必要性を理解するのに役立ちます。DESの順列と暗号化におけるその役割の詳細な分析は、データ暗号化標準の順列に関するこの分析でご覧いただけます。[ 53 ]

DES自体は、より安全な方式に適応・再利用することができます。かつてDESを利用していた多くのユーザーは、 DESの特許保有者の1人によって記述・解析されたトリプルDES（TDES）を使用しています（FIPS Pub 46–3参照）。TDESは、2つ（2TDES）または3つ（3TDES）の異なる鍵を用いてDESを3回適用する方式です。TDESは十分に安全であると考えられていますが、非常に低速です。より計算コストの低い代替方式としてDES-Xがあります。これは、DESの前後に追加の鍵素材を排他的論理和することで鍵サイズを増加させます。GDESは暗号化を高速化する方法として提案されたDESの派生型ですが、差分解読法の脆弱性が明らかになりました。

1997年1月2日、NISTはDESの後継暗号を選定したいと発表しました。[ 54 ] 2001年、国際コンペティションを経て、NISTはDESの後継として新しい暗号であるAdvanced Encryption Standard (AES)を選択しました。 [ 55 ] AESとして選定されたアルゴリズムは、設計者によってRijndaelという名前で提出されました。NIST AESコンペティションの最終候補には、 RC6、Serpent、MARS、Twofishな​​どがありました。

参照

参考文献

  1. ^ a b c d Diffie, Whitfield; Hellman, Martin E. (1977年6月). 「NBSデータ暗号化規格の徹底的な暗号解析」(PDF) . Computer . 10 (6): 74– 84. doi : 10.1109/CM.1977.217750 . S2CID  2412454. 2014年2月26日時点のオリジナル(PDF)からのアーカイブ。
  2. ^ a b「DESの遺産 - シュナイアーのセキュリティに関する見解」 www.schneier.com 2004年10月6日。
  3. ^ Menezes, AJ; van Oorschot, PC; Vanstone, SA (1996). Handbook of Applied Cryptography . CRC Press. pp.  388– 392. ISBN 0849385237。
  4. ^ a bバティス・ラゾ、ベルナルド（2018年）『キャッシュ・アンド・ダッシュ：ATMとコンピューターは銀行業務をどう変えたか』オックスフォード大学出版局、284～311頁。ISBN 9780191085574。
  5. ^ウォルター・タックマン (1997). 「データ暗号化規格の簡潔な歴史」. 『インターネット包囲：サイバースペースの違法行為への対抗』. ニューヨーク：ACM Press/Addison-Wesley Publishing Co. pp.  275– 280. ISBN 978-0201308204。
  6. ^ 「NISTのデータ暗号化標準（DES）プログラムの経済的影響」（PDF）。米国国立標準技術研究所（NIST）。米国商務省。2001年10月。 2017年8月30日時点のオリジナル（PDF）からアーカイブ。 2019年8月21日閲覧。
  7. ^ Konheim, Alan G. (2016年4月1日). 「自動現金自動預け払い機：その歴史と認証プロトコル」 . J​​ournal of Cryptographic Engineering . 6 (1): 1– 29. doi : 10.1007/s13389-015-0104-3 . ISSN 2190-8516 . S2CID 1706990. 2019年7月22日時点のオリジナルよりアーカイブ。 2019年8月28日閲覧。  
  8. ^ RSA Laboratories. 「PKCS #7 - 暗号化メッセージ構文標準 - 3.2.2 DES - DESは破られたか？」 www.emc.com 。 2016年5月17日時点のオリジナルからアーカイブ。 2009年11月8日閲覧。
  9. ^シュナイアー著『応用暗号』（第2版）p. 280. doi : 10.1002/9781119183471 . ISBN 9780471128458。
  10. ^ Davies, DW; Price, WL (1989). 『コンピュータネットワークのセキュリティ：テレプロセシングと電子資金移動におけるデータセキュリティ入門』（第2版）John Wiley & Sons. ISBN 978-0471921370。
  11. ^シュガーマン、R.（1979年7月）「コンピュータ犯罪の阻止について」IEEE Spectrum 16 ( 7): 31-32 .
  12. ^ P. Kinnucan (1978年10月). 「データ暗号化の達人：TuchmanとMeyer」. Cryptologia . 2 (4): 371. doi : 10.1080/0161-117891853270 .
  13. ^ Thomas R. Johnson (2009年12月18日). 「冷戦期のアメリカ暗号学、1945-1989。第3巻：縮減と改革、1972-1980、232ページ」(PDF) .国家安全保障局(NSA), DOCID 3417193 (2009年12月18日公開、nsa.govでホスト).オリジナル(PDF)から2013年9月18日にアーカイブ。 2014年7月10日閲覧。
  14. ^ Thomas R. Johnson (2009年12月18日). 「冷戦期のアメリカ暗号学、1945-1989。第3巻：縮減と改革、1972-1980、232ページ」(PDF) .国家安全保障局(NSA) . 2015年4月25日時点のオリジナルよりアーカイブ(PDF) . 2015年7月16日閲覧–国家安全保障アーカイブへの情報公開請求による。このバージョンはNSAウェブサイトに掲載されているバージョンとは編集内容が異なっている。
  15. ^ Thomas R. Johnson (2009年12月18日). 「冷戦期のアメリカ暗号学、1945-1989。第3巻：縮減と改革、1972-1980、232ページ」(PDF) .国家安全保障局(NSA) . 2015年4月25日時点のオリジナルよりアーカイブ(PDF) . 2015年7月16日閲覧–国家安全保障アーカイブへの情報公開請求による。このバージョンはNSAウェブサイトに掲載されているバージョンとは編集内容が異なっている。
  16. ^ Konheim.コンピュータセキュリティと暗号化. p. 301.
  17. ^ a bレヴィ『暗号』 55ページ
  18. ^ Schneier, Bruce (2004年9月27日). 「データ暗号化の伝統に敬意を表す」 . CNet . 2015年7月22日閲覧。
  19. ^ a bアメリカ国立標準技術研究所、NIST 特別出版 800-67トリプルデータ暗号化アルゴリズム (TDEA) ブロック暗号に関する勧告、バージョン 1.1
  20. ^アメリカ規格協会、ANSI X3.92-1981（現在はANSI INCITS 92-1981として知られている）アメリカ規格、データ暗号化アルゴリズム
  21. ^ 「ISO/IEC 18033-3:2010 情報技術 - セキュリティ技術 - 暗号化アルゴリズム - パート3：ブロック暗号」 . Iso.org. 2010年12月14日. 2011年10月21日閲覧。
  22. ^ブルース・シュナイアー著『応用暗号、プロトコル、アルゴリズム、C言語によるソースコード』第2版、ジョン・ワイリー・アンド・サンズ、ニューヨーク（1996年）267ページ
  23. ^ William E. Burr、「データ暗号化規格」、NISTのアンソロジー「計測、標準、技術における卓越性の世紀：NBS/NIST出版物の選集、1901-2000」所収。HTML アーカイブ： 2009-06-19 at the Wayback Machine PDFアーカイブ：2006-08-23 at the Wayback Machine
  24. ^ "FR Doc 04-16894" . Edocket.access.gpo.gov . 2009年6月2日閲覧。
  25. ^ S. Kumar、C. Paar、J. Pelzl、G. Pfeiffer、A. Rupp、M. Schimmler、「8,980ユーロでDESを破る方法」。暗号システム攻撃のための特殊用途ハードウェアに関する第2回ワークショップ—SHARCS 2006、ドイツ、ケルン、2006年4月3日～4日。
  26. ^ 「Crack.sh | 世界最速の DES クラッカー」。
  27. ^ 「FIPS 81 - Des動作モード」 . csrc.nist.gov . 2009年6月2日閲覧。
  28. ^ 「FIPS 74 - NBSデータの実装と使用に関するガイドライン」 Itl.nist.gov。2014年1月3日時点のオリジナルよりアーカイブ。2009年6月2日閲覧。
  29. ^シュナイアー『応用暗号』（第1版）271ページ。
  30. ^ Stallings, W. (2006). 『暗号化とネットワークセキュリティ：原理と実践』（第4版）. Pearson/Prentice Hall. p. 73. ISBN 9780131873162。
  31. ^ Turover、D. 「Bruting DES」。ハンバーグステーキ.サンドイッチ.ネット。自費出版。
  32. ^ van Oorschot, Paul C.; Wiener, Michael J. (1991), Damgård, Ivan Bjerre (ed.), "A Known-Plaintext Attack on Two-Key Triple Encryption", Advances in Cryptology – EUROCRYPT '90 , vol. 473, Berlin, Heidelberg: Springer Berlin Heidelberg, pp.  318– 325, doi : 10.1007/3-540-46877-3_29 , ISBN 978-3-540-53587-4{{citation}}: CS1 maint: ISBNによる作業パラメータ（リンク）
  33. ^ Paar, C.; Schimmler, L. (2006年12月12日). 「COPACOBANA — コスト最適化並列コードブレーカー入門」(PDF) . ドイツ. 2012年5月15日時点のオリジナル(PDF)からアーカイブ。 2012年3月6日閲覧。
  34. ^ウォブスト、ラインハルト（2007年10月16日）『暗号解読』ジョン・ワイリー・アンド・サンズ、ISBN 9780470060643。
  35. ^ 「DESを1日未満で破る」 www.sciengines.com SciEngines GmbH. 2017年8月28日時点のオリジナルよりアーカイブ。
  36. ^ Hulton, David; Foster, Ian (2017年7月25日).複雑なパスワードで安全を確保できると思うか? (PDF) . BSidesLv 2017. 2025年11月18日閲覧。
  37. ^ a b「DESクラッカーは現在メンテナンスのため停止しています」。crack.sh。ToorCon , Inc.
  38. ^ a b Biham, E.; Shamir, A (1993).データ暗号化標準の差分暗号解析. Shamir, Adi. ニューヨーク: Springer-Verlag. pp.  487– 496. doi : 10.1007/978-1-4613-9314-6 . ISBN 978-0387979304. OCLC  27173465 . S2CID  6361693 .
  39. ^ a b松井充 (1993-05-23). 「DES暗号の線形解読法」.暗号学の進歩 — EUROCRYPT '93 . コンピュータサイエンス講義ノート. 第765巻. Springer, ベルリン, ハイデルベルク. pp.  386– 397. doi : 10.1007/3-540-48285-7_33 . ISBN 978-3540482857。
  40. ^ a b Davies, DW (1987). 「DESアルゴリズムの潜在的な弱点の調査、Private Communications」 . Private Communications .
  41. ^ビリュコフ, アレックス; カニエール, クリストフ・ドゥ; キスクアター, ミカエル (2004-08-15). 「多重線形近似について」.暗号学の進歩 – CRYPTO 2004.コンピュータサイエンス講義ノート. 第3152巻. シュプリンガー, ベルリン, ハイデルベルク. pp.  1– 22. doi : 10.1007/978-3-540-28628-8_1 . ISBN 9783540226680。
  42. ^ Knudsen, Lars R.; Mathiassen, John Erik (2000-04-10). 「DESに対する選択平文線形攻撃」.高速ソフトウェア暗号化. コンピュータサイエンス講義ノート. 第1978巻. Springer, ベルリン, ハイデルベルク. pp.  262– 272. doi : 10.1007/3-540-44706-7_18 . ISBN 978-3540447061。
  43. ^ Junod, Pascal (2001-08-16). 「Matsuiの攻撃の複雑さについて」.暗号技術の特定分野. コンピュータサイエンス講義ノート. 第2259巻. Springer, ベルリン, ハイデルベルク. pp.  199– 211. doi : 10.1007/3-540-45537-X_16 . ISBN 978-3540455370。
  44. ^ Biham, Eli; Biryukov, Alex (1997-06-01). 「DaviesのDES攻撃の改良」 . Journal of Cryptology . 10 (3): 195– 205. doi : 10.1007/s001459900027 . ISSN 0933-2790 . S2CID 4070446 .  
  45. ^ Langford, Susan K.; Hellman, Martin E. (1994-08-21). 「差分線形暗号解析」.暗号学の進歩 — CRYPTO '94 . コンピュータサイエンス講義ノート. 第839巻. Springer, ベルリン, ハイデルベルク. pp.  17– 25. doi : 10.1007/3-540-48658-5_3 . ISBN 978-3540486589。
  46. ^ Biham, Eli; Dunkelman, Orr; Keller, Nathan (2002-12-01). 「差分線形暗号解析の強化」.暗号学の進歩 — ASIACRYPT 2002.コンピュータサイエンス講義ノート. 第2501巻. Springer, Berlin, Heidelberg. pp.  254– 266. doi : 10.1007/3-540-36178-2_16 . ISBN 978-3540361787。
  47. ^ Menezes, Alfred J.; van Oorschot , Paul C.; Vanstone, Scott A. (1996). Handbook of Applied Cryptography . CRC Press. p.  257. ISBN 978-0849385230。
  48. ^ブリッケル、アーネスト・F.（1992年8月16日）.キャンベル・アンド・ウィーナー, 1992. pp.  512– 520. ISBN 9783540573401。
  49. ^ 「Double DES」（PDF）。2011年4月9日時点のオリジナルよりアーカイブ（PDF） 。
  50. ^ Stallings, William (2011). 『暗号化とネットワークセキュリティ：原理と実践』（PDF）（第5版）ボストン：Prentice Hall. pp. G1-9. ISBN 0136097049。
  51. ^ Schaefer, Edward F. (1996年1月). 「簡略化されたデータ暗号化標準アルゴリズム」. Cryptologia . 20 (1): 77– 84. doi : 10.1080/0161-119691884799 .
  52. ^ 「暗号化研究：高度暗号化標準（AES）のより良い教育・学習方法の考案」 www.scu.eduサンタクララ大学 2011年。 2011年8月29日時点のオリジナルよりアーカイブ。
  53. ^ 「データ暗号化規格 | DES 64ビット順列」 . 2025年3月24日. 2025年3月25日閲覧。
  54. ^ 「高度暗号化標準FIPSの開発を発表 | CSRC」 2017年1月10日。
  55. ^連邦情報処理標準出版物197 | 高度暗号化標準（AES）の発表（PDF）（レポート）。2001年11月26日。fips-197。
ウィキメディア コモンズには、データ暗号化標準に関連するメディアがあります。
「 https://en.wikipedia.org/w/index.php?title=Data_Encryption_Standard&oldid=1328019817」より取得