feal-differential-cryptanalysis

FEAL 差分解読

概要

このスキルでは、FEAL および類似する Feistel ネットワーク型ブロック暗号に対する差分解読攻撃の実装を、体系的にガイドします。差分解読では、特定の入力差分が暗号の各ラウンドを、予測可能な確率でどのように伝播するかを利用して、鍵を復元します。

基本原則

実装の前に理論を理解する

攻撃コードを書く前に、次のことを行います。

1. 暗号の構造を理解する - Feistel ネットワークの構成、ラウンド関数（F 関数）、鍵スケジュール、ラウンド数を特定します
2. F 関数の差分特性を調べる - どの入力差分が、どの出力差分を高い確率で生み出すかを特定します
3. 差分特性を特定する - 暗号のラウンドを通じた確率の高い差分経路を見つけます
4. 攻撃方程式を定式化する - 鍵ビットと観測可能な出力差分との関係を理解します

差分解読が機能する理由

この攻撃では、正しい鍵で復号した中間値が実際の暗号状態を表し、ラウンド関数の方程式を満たすことを利用します。誤った鍵では、これらの値は基本的にランダムな値となり、差分関係を満たしません。

判別の特性となるのはFeistel 構造との整合性であり、エントロピー、分散、ハミング重みなどの統計量ではありません。

アプローチ

ステップ 1：暗号を解析する

1. 暗号の完全な構造（ラウンド、鍵の混合、F 関数）を書き出します
2. どの鍵ビットがどの中間計算に影響するかを特定します
3. 鍵の一部を推測した場合に、どの中間値を計算できるかを明らかにします
4. 平文、暗号文、鍵ビット間の依存関係を記録します

ステップ 2：差分特性を調べる

1. F 関数の差分特性を解析します
2. 予測可能な出力 XOR 差分を生み出す入力 XOR 差分を見つけます
3. 各差分特性の確率を計算します
4. 確率の高い複数ラウンドにわたる差分経路を特定します

ステップ 3：選択平文を設計する

1. 特定した差分特性を利用する、特定の XOR 差分を持つ平文ペアを選びます
2. 平文差分が確率の高い差分特性に沿うようにします
3. 各平文の選択について、理論的根拠を記録します
4. 理論的な根拠のない任意の平文は使用しません

ステップ 4：鍵復元を実装する

1. 各鍵候補について、部分復号を使って中間値を計算します
2. 計算した値が予測される差分関係を満たすか確認します
3. 各鍵候補に「票を投じる」平文ペアの数を数えます
4. 正しい鍵には、整合するペアが大幅に多くなります

ステップ 5：段階的に検証する

1. 組み合わせる前に、各要素を個別に検証します
2. 既知のテストケースでは、中間値が予測される状態と一致することを確認します
3. 正しい鍵と誤った鍵の動作を直接比較します
4. 次の段階に進む前に、攻撃の各段階の確実性を高めます

検証方法

直接比較法

デバッグ時には、正しい鍵と誤った鍵の両方について中間値を計算します。

1. 既知の鍵を使ってテストケースを生成します
2. 正しい鍵で中間状態を計算します
3. 複数の誤った鍵で中間状態を計算します
4. 実験的に判別特性を特定します

方程式の検証

各平文ペアと鍵の推測について、次のことを行います。

1. 推定した中間状態を計算します
2. 状態が予測される差分方程式を満たすか確認します
3. 鍵候補ごとに合格数と不合格数を記録します
4. 差分特性が優れている場合、正しい鍵の合格率はほぼ 100% になるはずです

妥当性チェック

1. ランダムな鍵では、攻撃は失敗するはずです（誤った答えを返します）
2. オラクルにアクセスできる場合、中間計算の結果が実際の暗号状態と一致するはずです
3. ラウンド数を減らすと、攻撃は容易になるはずです
4. 平文ペアを増やすと、信頼性が向上するはずです

よくある落とし穴

落とし穴 1：差分方程式ではなく統計的ヒューリスティックを使う

誤ったアプローチ：エントロピー、ハミング重みの分散、衝突数、その他の統計的な指標を使って、正しい鍵と誤った鍵を区別します。

失敗する理由：これらの指標は、正しい鍵と誤った鍵で似た値を示すことがよくあります。両者を区別する特性は統計的なものではなく、構造的なもの（差分方程式を満たすこと）です。

正しいアプローチ：計算した中間値が、暗号の構造から導かれる期待される差分関係を満たしているか確認します。

落とし穴 2：平文を根拠なく選ぶ

誤ったアプローチ：理論的な根拠なしに、i * 0x0101010101010101 のような平文やランダムな値を使います。

失敗する理由：差分攻撃では、暗号を通じて有用な差分を生み出す、特定の平文 XOR 差分が必要です。

正しいアプローチ：F 関数の高確率な差分特性に一致する XOR 差分を持つ平文ペアを選びます。

落とし穴 3：ヒューリスティックを次々と試す

誤ったアプローチ：うまくいくものが見つかることを期待して、さまざまなスコアリング関数（エントロピー、分散、最小値／最大値、衝突数）を試します。

失敗する理由：各アプローチが失敗する理由を理解していなければ、新たな試みも同様に失敗する可能性が高くなります。

正しいアプローチ：アプローチが失敗したときは、その理由を分析します。正しい鍵と誤った鍵の挙動を直接比較し、段階的に理解を深めます。

落とし穴 4：暗号固有の文献を無視する

誤ったアプローチ：FEAL 固有の弱点を調べずに、汎用的な「差分攻撃」を実装します。

失敗する理由：FEAL の差分特性は広く文書化されています。この分野の知見を無視すると、車輪の再発明を質の低い形で行うことになります。

正しいアプローチ：対象の暗号に対する既存の差分攻撃を調べます。効果が実証されている差分を把握します。

落とし穴 5：部分復号の検証が不十分

誤ったアプローチ：既知の中間状態と照合して検証せずに、部分復号コードが正しいと判断します。

失敗する理由：部分復号のバグは、意味のない中間値を生み出します。その結果、識別方法にかかわらず攻撃が不可能になります。

正しいアプローチ：既知の鍵を使って、計算した中間値が各ラウンドにおける実際の暗号内部状態と一致することを確認します。

FEAL 固有の攻撃に関する重要な知見

1. ラウンド鍵の独立性：異なるラウンド鍵が異なる中間値に影響することがあります。どの計算が対象の鍵ビットに依存するかを特定します。

2. シードの制約：鍵生成で小さなシード空間（例：16 ビット）を使う場合、総当たり検索は実行可能ですが、それでも信頼できる識別方法が必要です。

3. L/R 状態の分離：Feistel ネットワークでは、左半分と右半分で依存関係が異なります。これを利用して、鍵ビットの影響を切り分けます。

4. F 関数の弱点：FEAL の F 関数には既知の差分上の弱点があります。F 関数に入力差分 0x80800000 を与えると、特定の高確率な出力差分が生じます。

デバッグ用チェックリスト

攻撃が正しくない結果を返す場合：

• 既知の鍵について、部分復号で正しい中間値が計算されることを確認する
• 平文ペアの XOR 差分が意図したものになっていることを確認する
• 差分方程式がラウンド構造を正しくモデル化していることを確認する
• デバッグ出力で、正しい鍵と誤った鍵の投票数を比較する
• F 関数の実装が暗号仕様と一致していることを確認する
• ラウンド数を減らしてテストし、攻撃がどこで破綻するかを特定する