Structural Analysis of Cryptographic Sequences using Stringology-Based Fingerprinting

技術的概要：文字列論に基づく指紋認証を用いた暗号シーケンスの構造分析

問題定義
ストリーム暗号、疑似乱数生成器（PRNG）、ブロック暗号モードなどの暗号プリミティブは、ランダムデータと統計的に区別がつかないシーケンスを生成するように設計されている。従来の評価は、頻度分布、ラン長、エントロピーなどのグローバルな特性を検証するために、NIST STS や TestU01 などの統計的ランダム性テストスイートに大きく依存している。しかし、これらのテストは主に理想的なランダム性からの顕著な逸脱を検出するために設計されており、基盤となる決定論的生成器の特定の構造的挙動を特徴づけるものではない。暗号アルゴリズムは、モジュラ加算、ビット回転、置換、XOR といった構造化された内部演算に依存しているため、純粋な統計的手法では検出できない微妙な構造的特徴を導入する可能性がある。これらのシーケンスを記号文字列として解釈し、その内部のパターン構造を分析するための枠組みが必要である。

手法：文字列論に基づく指紋認証（SBF）枠組み
本論文は、暗号出力を記号文字列として扱い、構造的パターン統計を抽出する「文字列論に基づく指紋認証（SBF）」枠組みを提案する。この枠組みは、以下のワークフローで動作する。

1. シーケンス変換：暗号出力（鍵ストリーム、暗号文）は、二進記号文字列（$S \in \{0, 1\}^n$）に変換される。
2. パターン抽出：スライディングウィンドウ分析を用いて、複数のパターン長（$m$）にわたって部分文字列の頻度統計を計算する。シーケンス $S$ 内のパターン $P$ の出現回数は、$f(P, S) = |\{i \mid S_{i:i+m-1} = P\}|$ として定義される。
3. 特徴集約：抽出された統計量は、以下の要素を捉える特徴ベクトルに集約される。
   • 部分文字列頻度分布：パターン出現の正規化されたカウント。
   • 再発パターン：特定の部分文字列がどの程度頻繁に繰り返されるか。
   • エントロピー特性：分布の均一性の尺度。
4. 指紋構築：これらの特徴は、シーケンス生成器の構造的挙動を特徴づけるコンパクトな指紋ベクトル（$X \in \mathbb{R}^d$）にマッピングされる。
5. 比較分析：この枠組みは、パターン逸脱スコア（$D$）やパターンエントロピー（$H$）などの指標を用いて、暗号生成シーケンス（CGS）からの指紋と均一ランダムシーケンス（URS）からの指紋を比較する。

主な貢献

• SBF 枠組みの導入：文字列論の技術を用いた暗号シーケンスの構造分析のための新規枠組みを提案する。
• パターンベースの指紋認証：グローバルなランダム性指標だけでなく、部分文字列統計を用いてシーケンス生成器を特徴づける表現手法を提案する。
• 実験的実証：実験的評価を通じて、文字列論に基づくパターン分析が、暗号シーケンスと均一ランダムシーケンス間の測定可能な構造的差異を明らかにし得ることを実証する。

実験結果
評価には、それぞれ 2,048 ビット（$2^{12}$）長のシーケンス 20,000 件（CGS 10,000 件、URS 10,000 件）のデータセットが使用された。長さ 8 ビット、16 ビット、32 ビットの部分文字列パターンが分析された。

• パターン頻度：暗号生成シーケンスは、ランダムシーケンスと比較してわずかに高い構造的集中を示した（例：8 ビットパターンの正規化頻度が 0.54 対 0.50）。
• 逸脱スコア：パターン逸脱指標（$D$）は、すべてのパターン長で一貫して非ゼロのスコア（0.09 から 0.13 の範囲）を生成し、2 つのソース間の測定可能な構造的変動を示した。
• エントロピー：暗号生成シーケンスは、ランダムシーケンスの理論的最大値と比較してわずかに低いエントロピー値を示した（例：8 ビットパターンで 7.6 対 8.0）。これは、わずかなパターン集中を示唆する。
• 再発：部分文字列の再発カウントの分析により、2 つのシーケンスタイプ間で、反復挙動に小さくも明確な差異があることが明らかになった。

意義と主張
本論文は、観察された構造的シグナルは小さいものの、測定可能であり、均一ランダムシーケンスに見られるノイズとは区別されると主張している。著者らは、これらの発見が実用的な暗号的弱点を意味するものではないことを強調している。現代のアルゴリズムは、計算量的にランダムデータと区別がつかないままである。むしろ、SBF 枠組みの意義は、追加的な分析視点を提供する点にある。それは、従来のグローバル統計テストを補完し、暗号生成器の構造的挙動と内部規則性を研究するためのツールとして機能する。この研究は、暗号評価ワークフローに文字列論の技術を統合することが、シーケンス生成器の構造的堅牢性に対する理解を豊かにし得ることを示唆している。