2

私はメッセージダイジェストの分野でいくつかの予備調査を行ってきました。具体的には、 Postscriptの例やX.509証明書の複製など、MD5やSHA-1などの暗号化ハッシュ関数の衝突攻撃。

ポストスクリプト攻撃の場合に私が知ることができることから、特定のデータが生成され、ポストスクリプトファイルのヘッダー内に埋め込まれ（レンダリング中に無視されます）、md5の内部状態が変更された文言のような状態になりましたドキュメントの最終的なMD値は、元のポストスクリプトファイルと同等になります。X.509も同様のアプローチを採用しており、証明書のコメント/空白セクション内にデータが挿入されています。

さて、ここに私の質問があります、そして私はこの質問をしている人を見つけることができないようです：

  1. 消費されているデータのみの長さが、MD計算の最後のブロックとして追加されないのはなぜですか？

  2. X.509の場合-MDの一部として空白とコメントが考慮されるのはなぜですか？

提案された衝突攻撃を解決するには、次のいずれかのような単純なプロセスでは不十分です。

  1. MD（M + | M |）= xyz
  2. MD（M + | M | + | M | * magicseed_0 + ... + | M | * magicseed_n）= xyz

どこ ：

  1. M：メッセージです
  2. | M | ：メッセージのサイズ
  3. MD：メッセージダイジェスト関数です（例：md5、sha、whirlpoolなど）
  4. xyz：は、メッセージMと|M|の実際のメッセージダイジェスト値のペアです。<M、| M |>
  5. magicseed_ {i}：サイズが追加される前の内部状態に基づいてシードで生成されたランダムな値のセットです。

これまでのところ、このような衝突攻撃はすべて、元のメッセージにデータを追加することに依存しているため、この手法は機能するはずです。

つまり、次のような衝突メッセージの生成に伴う難易度。

  1. 同じMDを生成するだけではありません
  2. しかし、理解可能/解析可能/準拠している
  3. また、元のメッセージと同じサイズですが、

ほぼ不可能ではないにしても、非常に困難です。このアプローチについて議論されたことはありますか？論文などへのリンクがあればいいのですが。

さらなる質問：Uからランダムに選択されたハッシュ関数Hの共通の長さのメッセージの衝突の下限は何ですか？ここで、Uはユニバーサルハッシュ関数のセットですか？

1 / N（Nは2 ^（| M |））ですか、それとも大きいですか？それが大きい場合は、特定のHの同じMD値にマップされる長さNのメッセージが複数あることを意味します。

その場合、これらの他のメッセージを見つけることはどれほど実用的ですか？ブルートフォースはO（2 ^ N）になりますが、ブルートフォースよりも時間計算量が少ない方法はありますか？

4

2 に答える 2

0

残りの質問について話すことはできませんが、最初の質問はかなり単純です-ハッシュプロセスの任意の段階（最初のブロック、N番目のブロック、最後のブロック）でmd5の入力に長さデータを追加すると、出力が変わるだけですハッシュ。その後、出力ハッシュ文字列からその長さを取得できませんでした。また、そもそもまったく同じ長さの別の文字列から衝突が発生しないことも考えられません。したがって、衝突する文字列も17バイトになる可能性があるため、「元の文字列は17バイトでした」と言っても意味がありません。

例えば

md5("abce(17bytes)fghi") = md5("abdefghi<long sequence of text to produce collision>")

まだ可能です。

于 2011-01-14T05:51:55.423 に答える
0

特に X.509 証明書の場合、「コメント」はプログラミング言語の意味でのコメントではありません。それらは、コメントとして解釈されることを示す OID を持つ単なる追加の属性です。tbsCertificate証明書の署名は、すべての追加属性を含む構造全体 (「署名される」証明書) の DER 表現を超えるように定義されます。

ただし、ハッシュ関数の設計はかなり深い理論であり、Theoretical CS Stack Exchangeでより適切に提供される可能性があります。

ただし、@Marc が指摘するように、ハッシュ関数の出力に含まれるよりも多くのビットを変更できる限り、ピジョンホールの原則により、いくつかの入力ペアに対して衝突が存在する必要があります。暗号化ハッシュ関数は一般に、入力に対して擬似ランダムに動作するように設計されているため、衝突は可能な入力に対して均一に分散される傾向があります。

編集:メッセージの長さをハッシュ関数の最後のブロックに組み込むことは、入力メッセージの前に行ったすべての長さを追加することと同じであるため、これ自体を行うためにハッシュ関数を変更する必要はありません。むしろ、特定のコンテキストでの使用法の一部として指定してください。メッセージの長さを変更すると、攻撃によって変更された領域の「下流」に変更されたフィールドがあるため、これにより一部のタイプの衝突攻撃が実行されにくくなることがわかります。ただし、これはX.509 中間 CA 偽造攻撃を必ずしも妨げるとはtbsCertificate限りません。

于 2011-01-14T05:54:30.973 に答える