DESの設計とLucifer暗号

1971年、IBM ResearchのHorst Feistelは、Lloyd's of London向けの銀行セキュリティプロジェクトの一環として、Luciferという暗号を開発しました。Luciferは最初期の近代的なブロック暗号の1つで、128ビットの鍵と128ビットのブロックを使用していました。

Luciferは、半ブロックに対して置換と転置を交互に適用するFeistel構造を使って、強力なブロック暗号を構築できることを示しました。LuciferはDESの直接の祖先です。

DESは、64ビットのブロックに対してFeistel構造を16ラウンド適用します。各ラウンドで、64ビットのブロックを32ビットずつの半分に分割します。右半分を48ビットに拡張し、48ビットのサブキーとXORを取り、Sボックスを通し、転置した後、左半分とXORします。

その後、左右の半分を入れ替えて処理を繰り返します。16ラウンドの後、最終転置によって64ビットの暗号文が生成されます。復号では、サブキーを逆順にして同じ構造を実行します。

DESは64ビット（8バイト）のブロック単位でデータを暗号化します。この固定ブロックサイズは1977年のハードウェアには適していましたが、現在ではセキュリティ上の問題になっています。十分な量のデータがあると、誕生日のパラドックスによる衝突が起こりやすくなります。

64ビットのブロックでは、約2^32ブロック（同じ鍵で暗号化した約32GBのデータ）の後に統計的なパターンが現れます。このSweet32攻撃により、3DESはHTTPSのような大量のトラフィックには安全でなくなりました。

DESは64ビットの鍵を使用しますが、そのうち8ビットは暗号化ではなくエラー検出に使うパリティビットです。したがって、実効鍵長はわずか56ビットです。

つまり、DESの鍵として可能なのは2^56個（約7京個）だけです。1977年の基準では、これは十分だと考えられていました。しかし1997年までには、強い意志を持つ攻撃者なら破れることが実証されました。

DESは初期転置（IP）から始まり、平文ブロックの64ビットを並べ替えます。そして、完全な逆変換である最終転置（IP^-1）で終わります。これらの転置は、暗号学的な強度を高めません。

これらは、特定の1970年代のチップアーキテクチャでハードウェア効率を高めるために設計され、ビットをレジスタにより高速に読み込めるようにしたものです。現代の分析でも、セキュリティには何も寄与しないことが確認されています。

8つのSボックス（Substitution boxes）は、DESの非線形性の中心です。各Sボックスは6ビットの入力を受け取り、固定のルックアップテーブルを使って4ビットの出力を生成します。外側の2ビットで行を選択し、内側の4ビットで列を選択します。

Sボックスによる非線形性がなければ、DESは線形代数で容易に破れる純粋な線形暗号になってしまいます。DESのSボックスの具体的な設計は、差分解読法に耐えるようになっています。

Sボックスの後で、DESはPボックスによる転置を適用し、Sボックスからの32ビットの出力を並べ替えます。これにより拡散が生じ、各Sボックスの出力が次のラウンドで複数のSボックスに影響するようになります。

Pボックスは拡散を最大化するよう慎重に設計されています。あるSボックスの各出力ビットが、次のラウンドで少なくとも2つの異なるSボックスに影響し、高速なアバランチ効果を確保します。

DESは、56ビットのマスターキーから、各ラウンド用に1個ずつ、異なる48ビットのサブキーを16個導出します。鍵スケジュールではまず、置換選択（PC-1）を適用してパリティビットを除去し、鍵ビットの順序を入れ替えます。

56ビットは28ビットずつの2つの半分に分割され、各ラウンドで1ビットまたは2ビット左にローテーションされます。次に、置換選択（PC-2）によって56ビットのうち48ビットを選択し、各ラウンドのサブキーを形成します。

NSAはDESの開発中にIBMと協力し、鍵長をLuciferの128ビットから56ビットに短縮するとともに、S-boxの設計を変更しました。これにより、バックドアが導入されたのではないかという論争が何十年にもわたって続きました。

1990年代、NSAの当局者は、1974年にIBMが発見した手法である差分解読法に対する耐性を高めるため、S-boxを強化したことを認めました。NSAは学術界より何年も前から差分解読法を知っていたため、DESを弱めたのではなく、より耐性の高いものにしたことが示唆されます。

DESは、競争的な評価プロセスを経て、1977年1月に連邦情報処理規格46として採用されました。機密扱いではない政府データの標準暗号となり、銀行や産業界にも広く採用されました。

DESの標準化は歴史的に重要でした。DESは、一般に公開された政府承認の暗号アルゴリズムとして初めてのものでした。また、ハードウェア実装の開発を促進し、その後の暗号標準化プロセスのひな型を確立しました。

DES自体はブロック暗号であり、1回にちょうど64ビットを暗号化します。実際のメッセージはこれより長いため、動作モードによって暗号を複数のブロックに適用する方法を定義します。一般的なモードには、ECB（各ブロックを個別に暗号化）、CBC（暗号化前に各ブロックと直前の暗号文をXOR）、CFB、OFB、CTRがあります。

ECBは最も弱いモードです。同一の平文ブロックからは同一の暗号文ブロックが生成されるため、パターンが目に見える形で現れます。CBCモードとCTRモードではこの弱点が解消されるため、実用的なDESや3DESではこちらが推奨されます。

DESの設計パラメーターに関する知識を確認しましょう。

DESはIBMのLucifer暗号から発展し、64ビットブロックと実効56ビット鍵を持つ16ラウンドのFeistel暗号になりました。その安全性は、攪乱をもたらす8個の非線形S-box、拡散をもたらすP-box、そして雪崩効果を増幅する16ラウンドによって実現されています。

S-boxの設計へのNSAの関与は物議を醸しましたが、最終的には差分解読法への耐性を高めました。1977年当時のハードウェアを想定して設計されたDESの56ビット鍵は、1990年代後半までに不十分であることが明らかになりました。