弱鍵

ほとんどすべてのローター式暗号機 (1925年式以降) には、相当数の弱鍵が生成される実装上の欠陥がある。現代のブロック暗号やストリーム暗号と同じように、ある暗号機には他の暗号機より多くの弱鍵の問題が存在する。

ドイツのエニグマ暗号機には10種類程度の異なる暗号機設計が存在するが、それぞれに固有の問題がある。軍用のエニグマ暗号機は、3番ローターと4番ローターの実装に弱鍵に相当する問題があった。ローターの順番、回転、そして初期鍵の特定の組み合わせは、他の組み合わせより根本的に弱かった。エニグマでは、リフレクターを使用すると文字がそれ自体に暗号化されることが決してないことが保証されていた。つまり、Aが暗号化の結果、再びAになることは決してなかった。これは、ポーランドと、後には英国による暗号解読作業に役立った (エニグマの暗号解析とエニグマのローターの詳細を参照のこと)。

最初のストリーム暗号機もローター式であり、従来のローター式と同様の弱鍵の問題を抱えていた。T52は弱鍵の問題を有するストリーム暗号機の1つであった。

英国は1942年の夏と秋にT52の通信を初めて検出した。通信リンクの1つはシチリアとリビア間のもので「チョウザメ (Sturgeon)」のコードネームが付けられ、もう1つはエーゲ海からシチリアに向かうもので「サバ (Mackerel)」のコードネームが付けられた。両リンクの操作者は習慣的に同じ暗号機設定で複数のメッセージを暗号化しており、そのため大量のdepthが生成された。

T52にはいくつかの (大半は互換性のない) バージョンがあった。T52aとT52b (電気ノイズ抑制の点だけが異なっていた)、T52c、T52d、そしてT52eである。T52a/bとT52cは暗号理論的に弱かったが、最後の2機種はより高度な機器であった。ホイールを進めるかどうかの決定はホイール自体をホイールからの入力データとして受け取る論理回路によって制御されたため、ホイールの動きが散発的であった。

加えて、コンセプト上の欠陥 (非常に微妙なものを含め) が取り除かれた。そのような欠陥にはキーストリームを特定の点にリセットする機能があったが、これが原因で訓練されていない暗号機操作者が鍵を再利用してしまっていた。

ブロック暗号のDESには「弱鍵」と「準弱鍵」と称される特定の鍵がいくつかある。これらの鍵によってDESの暗号化モードがDESの復号モードと全く同じように動作する (異なる鍵のものとなる可能性はあるが)。

操作においては、56ビットの秘密鍵はDESの鍵スケジュールに従って16個のサブ鍵に分割される。1つのサブ鍵は16回のDESラウンドのそれぞれで使用される。DESの弱鍵からは16個の全く同じサブ鍵が生成される。これは鍵 (16進数表記) が以下の場合に発生する:

• 交互に現れる1 + 0 (0x0101010101010101)
• 交互に現れる'F' + 'E' (0xFEFEFEFEFEFEFEFE)
• '0xE0E0E0E0F1F1F1F1'
• '0x1F1F1F1F0E0E0E0E'

実装がパリティビットを考慮しない場合、反転したパリティビットを持つ鍵も弱鍵として機能する可能性がある:

• すべてゼロ (0x0000000000000000)
• すべて1(0xFFFFFFFFFFFFFFFF)
• '0xE1E1E1E1F0F0F0F0'
• '0x1E1E1E1E0F0F0F0F'

弱鍵を使うと、DESの鍵スケジュールの転置選択肢1 (PC1) の結果から、すべてゼロのパターン、すべて1のパターン、またはゼロと1が交互に現れるパターンのいずれかであるラウンド鍵が生成される。

すべてのサブ鍵が同一であり、DESがFeistelネットワークであるため、暗号化機能は自己反転的である。つまり、暗号化を1度適用するとセキュアに見える暗号文が得られるが、暗号化を2度適用すると元の平文が生成される。

DESには準弱鍵も存在しており、これを使うと異なるサブ鍵が2つしか生成されず、それぞれがDESアルゴリズムで8回使用される。つまりK₁とK₂のペアとなるが、これには以下の性質がある:

${\displaystyle E_{K_{1}}(E_{K_{2}}(M))=M}$

ここでE_K(M)はメッセージMを鍵Kで暗号化する暗号化アルゴリズムである。準弱鍵のペアは6組ある:

• 0x011F011F010E010E と 0x1F011F010E010E01
• 0x01E001E001F101F1 と 0xE001E001F101F101
• 0x01FE01FE01FE01FE と 0xFE01FE01FE01FE01
• 0x1FE01FE00EF10EF1 と 0xE01FE01FF10EF10E
• 0x1FFE1FFE0EFE0EFE と 0xFE1FFE1FFE0EFE0E
• 0xE0FEE0FEF1FEF1FE と 0xFEE0FEE0FEF1FEF1

異なるサブ鍵を (16種類ではなく) 4種類しか生成しない弱鍵の候補が48個ある[1]。

これらの弱鍵と準弱鍵はDESの「致命的欠陥」とは見なされていない。DESには鍵候補が2⁵⁶ (7.21 × 10¹⁶、約7.2京) 個あり、そのうち4個が弱鍵で、12個が準弱鍵である。これは考え得る鍵空間においてはユーザーが心配する必要もない程度にわずかである。必要であれば、鍵の生成時に弱鍵または準弱鍵であるかチェックすることができる。弱鍵や準弱鍵はほとんどないので、判別は容易である。ただし、PCの拡張カード数枚程度のハードウェア初期費用ですべてのDES鍵を総当たり攻撃できるため、現在DESの一般利用はすでに非推奨となっている。

• DES。詳細は前述。
• RC4。RC4の弱い初期化ベクトルのため攻撃者は既知平文攻撃が実施可能である。また、RC4はWEPのセキュリティ侵害に広く利用された[2]。
• IDEA。IDEAの弱鍵は選択平文攻撃で識別できる。この弱鍵により、平文のビットのXOR合計と暗号文のビットが予測可能になる。弱鍵の一覧は存在しないが、鍵の「構造」から識別できる。
• Blowfish。BlowfishのSボックスは鍵依存のため、弱鍵から劣悪なSボックスが生成される。ラウンド縮減型Blowfishに対して弱鍵を使用する効率的な選択平文攻撃が存在する。これは完全な16ラウンド型Blowfishの場合、問題ではない。

「フラット」な鍵空間 (つまりすべての鍵が同等に強い) を持つという目標は、常に暗号設計の目標である。DESの例のように、弱鍵がすべて識別済みか識別可能であれば、多少の存在は許容できる場合がある。未知の弱鍵があるアルゴリズムは信頼感に乏しい。

弱鍵の不注意な使用を防ぐ対策には以下の2つがある:

• 生成した鍵を既知の弱鍵の一覧と突き合わせる、または鍵スケジュールに弱鍵を却下する処理を組み込む。
• 弱鍵の数が (鍵空間の大きさと比べて) 非常に少ないと分かっている場合、鍵を一様にランダムに生成することで、弱鍵となる確率が (既知の) 非常に小さな数になることが確実になる。

弱鍵が多数存在することは、どのような暗号設計においても深刻な欠陥である。ランダムに生成された鍵が弱鍵となり、暗号化されたメッセージのセキュリティが損なわれる可能性が高くなる (ひょっとするとあまりにも高くなりすぎる) ためである。またそのような場合、ランダムに生成された鍵の弱さをチェックするのに時間がかかるので、「効率性」という手っ取り早い利益へと駆り立てられることになる。

しかし弱鍵は、ブロック暗号をセキュアな暗号学的ハッシュ関数の構築を意図した暗号利用モードで使用する (Davies–Meyer等) 場合等、アドバーサリが使用する鍵の選択をある程度制御できる場合に問題となることの方が多い。

• 認証
• 強力な認証
• 多要素認証

1. NIST, Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher, Special Publication 800-67, page 14
2. FLUHRER, S., MANTIN, I., AND SHAMIR, A. Weaknesses in the key scheduling algorithm of RC4.