攻撃計算量を正確に見積もるためのツールが満たすべき要件

48 満たすべきコンディションを導出し、その中から、モディフィケーション適用可能なコン ディションを、判別することが重要である。モディフィケーションとしては、ベーシック メッセージモディフィケーションと、アドバンストメッセージモディフィケーションに区 分されるが、ベーシックメッセージモディフィケーションについては、メッセージ拡大非 適用ステップにおける全てのコンディションが、その対象となると考えても大きな問題は 生じない[75]と考えられることから、本質的にはアドバンストメッセージモディフィケー ションに関する適用可能性について判別することが、攻撃計算量の厳密な評価につながる ことが分かる。

ハッシュ関数 SHA-1 に対するアドバンストメッセージモディフィケーションの手法と しては、文献[75]で提案された後、表 9 で示したように多くの改良が提案されている。こ れらのアドバンストメッセージモディフィケーションを適用する場合に注意すべき点とし て、いくつか挙げられる。

文献[76][77]では、マルチメッセージモディフィケーションの適用判定順序によって、

モディフィケーション可能なコンディションの個数が変化することが指摘されており、文 献 [95]では、判定順序、ならびにその判定法に関する提案がされている。探索計算量を見 積もる場合、単一のコンディションについて、マルチメッセージモディフィケーションが 適用可能であるかどうかを判定することも課題の一つではあるが、より本質的には、出来 る限り多くのコンディションをモディフィケーションする手段を見付けることが重要であ ると考えられる。よって探索計算量を評価する上では、コンディションに対する判定順序 を含めて適切に探索する必要がある。

通常コンディションの他に、「エクストラコンディション」と呼ばれるコンディションを 付加し、このコンディションを成立させておく必要がある。このエクストラコンディショ ンを適切に管理し、他のコンディションと矛盾ないようにしなければならない。また、エ クストラコンディションを全て満たしておかなければ、アドバンストメッセージモディフ ィケーションを行なうことができないため、このエクストラコンディション自身のモディ フィケーション計算量も考慮しなければならない。経験的にはステップ数が進んだ位置に あるコンディションほどモディフィケーションに必要なエクストラコンディションの個数 が増加し、アドバンストメッセージモディフィケーションは困難となる。

メッセージモディフィケーションは、メッセージ拡大非適用ステップ内のメッセージビ ットを複数変化させることで実施するが、この範囲に含まれるメッセージビット数は、

SHA-1 の場合 16 ステップ× 32 ビット と限りがある。そのため、この数を越えてメッセ ージモディフィケーションを行なうことは出来ない。

コリジョン探索において、ビットの値を自由に選択できるメッセージビットは「メッセ ージフリーダムビット」と呼ばれているが、コリジョン探索計算量が 2^K の時、メッセージ フリーダムビットの個数が K 個以下となった場合、メッセージの全探索空間を尽くしたと しても、その差分パスに従ったコリジョンメッセージが得られないことを意味するため、

コリジョン探索を行なう上で無意味である。この点は、差分パス探索でも指摘されている [83]が、メッセージモディフィケーションにおいても同様に考慮すべき課題である。

50