探索計算量の導出方針検討

コリジョン探索で必要となる計算量の概算値は、数式 5 を元に数式 6 で与えられること が知られている。

数式 6．コリジョン探索計算量

（コリジョン探索計算量）＝2

×B

ただし

N = 満たすべき全てのコンディションの数

n = メッセージモディフィケーションが適用可能なコンディションの数 B = マルチブロックコリジョンにおけるブロック数

数式 6 により、「コリジョン探索計算量」を見積もるためには、内部状態が満たすべき「コ ンディション」と「メッセージモディフィケーションが適用可能なコンディション」をそ れぞれ導出すればよいことになる。ところでメッセージモディフィケーションには、「ベー シックメッセージモディフィケーション」と「アドバンストメッセージモディフィケーシ ョン」があり、数式 6 における「メッセージモディフィケーションが適用可能なコンディ ションの数」とは、両者のうちのいずれかが適用可能であるコンディションの数のことを 言う。攻撃者の立場でのコリジョン探索計算量の概算見積もりにおいては、メッセージ拡 大非適用ステップに存在する全ての「コンディション」には「ベーシックメッセージモデ ィフィケーション」が適用可能と仮定しても大きな問題はない。そこで今回のツールの検 討においては、メッセージ拡大適用ステップに存在するコンディションのみを安全性算出 の対象とし、これらのコンディションの総数と、アドバンストメッセージモディフィケー ションが適用可能なコンディションの数とを考慮して安全性を算出することにした。コリ ジョン探索計算量の考え方のイメージを図 13 に示す。

図 1 に示したような算術演算をベースとするハッシュ関数について、数式 6 にてコリジ ョン探索計算量を評価する方法を検討したところ、図 14 に示す５個のモジュールで評価を 行えばよいことが判明した。各モジュールの仕様検討は次節以降にて行う。なお、図 14 に は各モジュールの入出力が記載されているが、実装の際にはこれらの他に制御用のパラメ ータなども入出力を要する可能性がある。

ベーシックメッセージ モディフィケーション

適用可能

ベーシックメッセージ モディフィケーション

適用不可能

アドバンストメッセージ モディフィケーション

適用可能

コリジョン探索 計算量に影響を

及ぼす コンディション

図 13．コリジョン探索計算量の考え方

54

ローカルコリジョン 構成モジュール

ディスターバンス ベクトル 構成モジュール

安全性 算出モジュール メッセージ

モディフィケーション 適用判定モジュール

差分パス 構成モジュール

データ ツール ハッシュ関数

アルゴリズム

差分パスとコンディ ションの存在箇所

ディスターバンス ローカル ベクトル

コリジョン

本質的なディスタ ーバンスベクトル

適用可否 判定結果

安全性 評価結果

図 14．コリジョン探索計算量評価の処理のフロー

（上記の各モジュールには、上記のほかに制御パラメータなども入出力される）