技術要約：汎用的なPNEフレームワーク：シンコペーションによってChaChaをさらに進化させる

1. 問題提起

ストリーム暗号であるChaCha、特に256ビット・バリアントは、TLS、SSH、QUICなどの実世界のプロトコルで広く展開されている。その広範な使用にもかかわらず、ラウンド削減されたChaChaのセキュリティ・マージンは、激しい暗号解読研究の対象となってきた。本研究以前、256ビットChaChaに対する最も効果的な鍵復元攻撃は、7ラウンド（時間計算量はしばしば$2^{220}$を超える）または7.25ラウンドに限定されており、単一鍵設定において7.5ラウンドに対して総当たり攻撃（$2^{256}$）よりも高速な攻撃が成功した例はなかった。さらに、関連鍵設定における8ラウンド・バリアント（ChaCha8）の安全性については、効率的な攻撃による調査がほとんど行われていなかった。

差分暗号解読における核心的な課題は、特定された確率的中立ビット（PNB）の数と、逆方向近似の相関性の間のトレードオフにある。従来の手法は、高い相関性を維持しつつ多数のPNBを同時に見つけることに苦慮することが多く、これがミート・イン・ザ・ミドル攻撃の効率を制限している。加えて、「強い鍵」（適切なIVが存在せず、差分特性を満たせない鍵）に関する従来の分析は、すべてのケースに対して包括的な理論的根拠を欠いていた。

2. 手法

本論文は、確率的中立ビット（PNB）に基づく洗練された差分暗号解読フレームワークを導入し、これを**確率的中立式（PNE）**に基づくフレームワークへと一般化している。この手法は、主に3つの技術的柱で構成される。

2.1 PNBのためのシンコペーション（切分）技術

著者らは、多数のPNBを見つけることと高い相関性を維持することの間の矛盾に対処するために、「シンコペーション（syncopation）」を導入している。

• 概念: 逆方向近似関数 $f$ を $f = f_1 \circ f_0$ と分解する。この技術は、特定の非PNBビット（制限ビット）に制約を課すことで、第1部（$f_0$）の出力がPNB（シンコペーション・ビット）に依存しないようにすることを目的とする。
• メカニズム: ARX構造における加算および減算の特性を利用することで、著者らはキャリー伝播を制御できる条件を導出している。これにより、特定のセグメントの出力が既知の公開値と非PNBのみによって決定されるようになり、未知のPNBへの依存性を事実上「シンコペーション（切分）」することができる。
• 結果: この技術は、逆方向近似の相関性を大幅に増幅させる。また、著者らは、収益性の高いシンコペーション・セグメントを体系的に決定するためのツール（アルゴリズム1）と、条件付きPNB（CPNB）の最適な集合を構築するための貪欲法（アルゴリズム2）を提供している。

2.2 汎用PNEフレームワーク

効率をさらに向上させるため、本論文はPNBの概念を**確率的中立式（PNE）**へと一般化している。

• 鍵推測戦略: 元の鍵ビットを直接推測する代わりに、暗号の構造（回転やXORを含む線形結合など）に合わせて調整された可逆関数 $H$ を用いて、等価な鍵 $H(K)$ を推測する。
• キャリー保持技術: モジュロ加算に関する新しい技術が導入されている。公開データに線形条件を課すことにより、未知の鍵ビット（PNB）を知ることなく、モジュロ加算のキャリー・ベクトルを決定できる。これにより、非線形操作が簡略化され、高い相関を維持しながら、近似が未知の鍵部分を無視することを可能にする。
• 統合: このフレームワークにより、従来のPNBが乏しいシナリオ（特に後半のラウンドや状態行列の特定の対角線上）においても、より多くの中立要素（PNE）を発見することが可能となる。

2.3 洗練された前方差分分析

本論文は、ChaChaの第1ラウンドを支配する差分方程式の深い理論的分析を提供している。

• 強い鍵の分析: 著者らは、「強い鍵」（差分を満たすIVが存在しない鍵）の存在に関する包括的な理論的説明を提供しており、これは内部状態変数の8つのケースすべてをカバーしている（従来の作業は2つのケースしかカバーしていなかった）。著者らは、約29.6875%の鍵が強い鍵であることを証明している。
• 効率的なペア生成: 差分方程式を分析することで、著者らは差分制約を満たす確率が高い特定のIVビットを特定し、正しいペアを見つけるために必要なデータ複雑度を低減させている。

3. 主な貢献

1. シンコペーション技術: ARX構造の特性を利用して逆方向近似の相関を増幅させる新しい手法であり、より効率的なPNB選択を可能にする。
2. 汎用PNEフレームワーク: 等価鍵表現とキャリー保持技術を用いたPNB手法の拡張であり、より少ない推測ビット数と高い相関での攻撃を可能にする。
3. 理論的完全性: 第1ラウンドにおけるすべての差分ケースに対する強い鍵の確率に関する完全な理論的導出を行い、従来の不完全な分析を修正および拡張した。
4. 新たな攻撃結果:
   • 256ビットChaCha: 総当たり攻撃（$2^{256}$）よりも高速な、7.5ラウンドに対する初の鍵復元攻撃（時間計算量 $2^{254.6}$）。7ラウンドおよび7.25ラウンドに対する、計算量を低減した改良された攻撃。
   • ChaCha8 (関連鍵): 256ビットChaCha8（8ラウンド）に対する初の関連鍵攻撃を示し、固定された差分を持つ鍵ペアを使用した場合の時間計算量 $2^{253.3}$ を実証した。
   • 128ビットChaCha: 6.5ラウンドに対する改良された攻撃、および7ラウンド（最後の回転を除く、$7\ll$ と表記）に対する新しい攻撃。

4. 結果

本論文は以下の具体的な攻撃複雑度（時間/データ）を提示している：

• 256ビットChaCha7:
  • $2^{210.3}$ 時間 / $2^{103.3}$ データ（89個のCPNBを使用）。
  • $2^{216.9}$ 時間 / $2^{68.9}$ データ（74個のCPNBを使用）。
  • 5ラウンドのDLディスティングイッシャーに対するシンコペーションを用いて、$2^{187.2}$ 時間 / $2^{108.2}$ データに改善。
• 256ビットChaça7.25:
  • $2^{220.0}$ 時間 / $2^{109}$ データ。
• 256ビットChaCha7.5:
  • $2^{254.6}$ 時間 / $2^{125.3}$ データ。 これは、7.5ラウンドの256ビットChaChaに対して、総当たり（$2^{256}$）よりも高速な初の攻撃である。
• 256ビットChaCha8 (関連鍵):
  • $2^{253.3}$ 時間 / $2^{99.2}$ データ。 これは、特定の差分を持つ鍵ペアが許容される場合、ChaCha8の256ビットのセキュリティ主張を打破するものである。
• 128ビットChaCha:
  • ChaCha6.5: $2^{114.3}$ 時間 / $2^{100.3}$ データ。
  • ChaCha7$\ll$: $2^{122.9}$ 時間 / $2^{108.8}$ データ。

実験的な検証は、64個の未知の鍵ビットを持つ5ラウンドおよび6ラウンドのChaChaに対して行われ、理論的な相関の向上と成功確率（5ラウンドで約70%、6ラウンドで62.5～71.4%）が確認された。

5. 意義と主張

本論文は、ChaChaの安全性分析において「小さくも困難な一歩」を踏み出したと主張している。その主な意義は以下の通りである：

• 7.5ラウンドの壁を打破: 256ビットChaChaの7.5ラウンドに対して、総当たり探索よりも効率的な鍵復元攻撃が示されたのは初めてである。
• ChaCha8に対する初の関連鍵攻撃: 特定の差分を持つ鍵ペアが許可される場合、ChaCha8が256ビットのセキュリティを達成できないことを示し、8ラウンド・バリアントの実用的なセキュリティ仮定に疑問を投げかけている。
• 手法の進展: シンコペーション技術および汎用PNEフレームワーク（キャリー保持および新しい鍵推測戦略を含む）の導入は、SalsaやChaskeyのような他の設計にも適用可能な、ARXベースの暗号を分析するためのより強力なツールキットを提供する。

著者らは、これらの攻撃は実際の運用で使用されているフル20ラウンドのChaChaを脅かすものではないと明言しているが、削減されたラウンドのセキュリティ・マージンを著しく狭め、8ラウンドの関連鍵設定における理論的な弱点を浮き彫りにしている。