Feistelネットワーク：現代暗号の構成要素

1970年代初頭、IBM ResearchのHorst FeistelはLucifer暗号に取り組む中で、基本的な着想を得ました。それは、可逆でないラウンド関数を使って可逆な暗号を構築できるということです。

これは画期的でした。安全性も備えた可逆関数を設計するのは難しいためです。Feistelの構成ではこの要件を完全に回避でき、任意に複雑な一方向のラウンド関数を使用できます。

Feistel暗号では、入力ブロックを2つの等しい半分、L（左）とR（右）に分割します。各ラウンドでは、Rにラウンド関数Fを適用し、その結果をLとXORしてから、左右を入れ替えます。

nラウンド後、2つの半分を再結合して暗号文を生成します。左右を入れ替えることで、各半分が交互のラウンドで処理され、全体が十分に混合されます。

Feistelネットワークのラウンド関数Fは、右半分とラウンドサブキーを入力として受け取り、左半分とXORする出力を生成します。重要なのは、Fが可逆である必要はないことです。

Fは、換字、置換、XOR、モジュラー演算を任意に組み合わせた、どのように複雑なものにもできます。Fが複雑で非線形であるほど暗号は強固になります。これは、復号時にFの逆関数を求める必要がないためです。

Feistel暗号の復号では、暗号化とまったく同じ構造を使用しますが、ラウンドサブキーを逆順に適用します。これは、XORが自分自身の逆演算であるため可能です。A XOR B = C なら、C XOR B = A となります。

復号でF^-1（Fの逆関数）を呼び出すことはないため、ラウンド関数には不可逆ハッシュ、ルックアップテーブル、その他の複雑な処理を使用しても、暗号全体の可逆性に影響しません。

Feistelネットワークの数学的な美しさは、Fがどのような処理を行うかにかかわらず、XOR構造によって可逆性が保証されることです。FがSHA-256のような一方向関数であっても、Feistel暗号全体は可逆のままです。

このため、Feistel暗号は非常に柔軟です。暗号技術者は、可逆性がネットワーク構造自体によって処理されることを把握したうえで、Fをできる限り攪乱と拡散に優れたものにすることだけに集中できます。

1977年に公開されたData Encryption Standard（DES）は、64ビットブロックと56ビット鍵を使用する16ラウンドのFeistel暗号です。各ラウンドでは、主鍵から導出された異なる48ビットのサブキーを使用します。

DESのラウンド関数には、拡張置換、サブキーとのXOR、非線形性をもたらす8個のS-box、そしてP-box置換が含まれます。この組み合わせにより、Shannonの暗号設計原則が求める攪乱と拡散の両方が実現されます。

Bruce Schneierが1993年に設計したBlowfishは、鍵長を32～448ビットの範囲で変更できる、16ラウンドのFeistel暗号です。鍵依存のS-boxを使用するため、事前計算による攻撃が実行困難になります。

AESの候補最終選考に残ったTwofishは、128ビットブロックと16ラウンドを採用してBlowfishの考え方を発展させたものです。どちらも未解読のままであり、変更を加えたBlowfishを使用するbcryptによるパスワードハッシュ化などの用途で使われています。

平衡型Feistel暗号では、ブロックを2つの等しい半分に分割します。非平衡型Feistelでは、3/4と1/4の分割のように、異なる大きさの半分に分割します。

非平衡型Feistelネットワークは、特定の状況でセキュリティ上の利点をもたらすことがあり、一部の特殊な暗号で使用されています。CAST暗号ファミリーは、平衡型の64ビットFeistel構造を使用します。

1988年、Michael LubyとCharles Rackoffは、擬似ランダムなラウンド関数を使用する3ラウンドのFeistelネットワークが安全な擬似ランダム置換（PRP）であり、4ラウンド版が強擬似ランダム置換であることを証明しました。

この理論的成果により、Feistelネットワークには経験的な信頼だけでなく、確固とした証明可能な安全性の基盤が与えられました。Feistel構造自体がラウンド関数を超えて安全性に寄与することも確認されました。

AESで使用される置換・転置ネットワーク（SPN）は、各ラウンドでブロックの半分だけを処理するのではなく、ブロック全体に対して同時に置換と転置を適用します。これにより、より速く拡散します。

AESはわずか4ラウンドで完全な拡散を実現します。一方、DESのFeistel構造では、同程度の拡散により多くのラウンドが必要です。AESのSPNは、SIMD命令を備えた最新のプロセッサーアーキテクチャにも適しています。

Luby-Rackoffの定理では、ラウンド関数Fを真にランダムな関数として扱います。実際には、Fは真のランダムオラクルではなく、擬似ランダム関数（鍵付き暗号またはハッシュ）です。

理論上の証明と実用的な実装の間にあるこの隔たりは、暗号技術に繰り返し現れるテーマです。証明は信頼性を与えますが、理想化されたモデルに基づいています。現実のセキュリティは、サイドチャネル脆弱性のない安全な実装にも左右されます。

Feistelネットワークの設計についての理解度を確認します。

Feistelネットワークは、可逆である必要のないラウンド関数を使用するブロック暗号の構造です。復号では、同じ構造をサブキーの順序だけ逆にして実行します。

DES、Blowfish、TwofishはいずれもFeistel暗号です。Luby-Rackoffの定理は、理論的な安全性の保証を与えます。一方、AESはSPN構造を使用し、1ラウンドあたりでより優れた拡散を実現します。