2

可変長のIDを使用するプログラムを実装しています。これらの ID はメッセージを識別し、何らかの操作を実行するブローカーに送信されます (質問には関係ありません)。ただし、ブローカーでのこの ID の最大長は 24 バイトです。ID を (ブローカーに送信する前に) SHA でハッシュし、24 バイトになるまでいくつかのバイトを削除することを考えていました。

ただし、これにより衝突がどれだけ増加するかを考えたいと思います。これは私が今まで得たものです:

「完全な」ハッシュのp^2 / 2^n+1場合、衝突の確率を記述する式があり、pはメッセージの数であり、nはメッセージのビット単位のサイズであることがわかりました。ここから私の問題が始まります。最終的なハッシュからいくつかのバイトを削除しても、関数は「完全」のままであり、同じ式を引き続き使用できると想定しています。したがって、これを仮定すると、次のようになります。

 5160^2 / 2^192 + 1 = 2.12x10^-51

5160 はメッセージの選択数で、192 は基本的に 24 バイトのビット数です。

私の質問:

  • 私の仮定は正しいですか?いくつかのバイトを削除することで、ハッシュは「完全」のままですか。

  • もしそうなら、確率は非常に小さいので、どのバイトを削除する必要がありますか? ほとんどまたはそれほど重要ではありませんか? それは本当に重要ですか?

PS: 同じ結果を達成するための他の提案を歓迎します。ありがとう。

4

1 に答える 1

4

ただし、ブローカーでのこの ID の最大長は 24 バイトです。ID を (ブローカーに送信する前に) SHA でハッシュし、24 バイトになるまでいくつかのバイトを削除することを考えていました。

SHA-1 は 20 バイト (160 ビット) しか出力しないため、パディングする必要があります。少なくともすべてのバイトが有効で、16 進または Base64 に制限されていない場合。代わりに切り捨てられた SHA-2 を使用することをお勧めします。

私の仮定は正しいですか?いくつかのバイトを削除することで、ハッシュは「完全」のままですか。

かなり。ハッシュを切り捨てると、重要なプロパティがすべて保存されます。明らかに、出力サイズが小さくなるため、セキュリティ レベルが低下します。

もしそうなら、確率は非常に小さいので、どのバイトを削除する必要がありますか? ほとんどまたはそれほど重要ではありませんか? それは本当に重要ですか?

それはまったく問題ではありません。NIST は、SHA-224 と呼ばれる切り詰められた SHA-2 バリアントを定義しました。これは、ハッシュ計算に異なる初期状態を使用して、SHA-256 の最初の 28 バイトを取得します。


最初の 24 バイトを保持して、SHA-256 を使用することをお勧めします。これには、1 つの衝突を見つけるのに約 2^96 回のハッシュ関数呼び出しが必要です。これは、非常に強力な攻撃者であっても現在実行不可能であり、偶発的な衝突に対しては本質的に不可能です.

于 2012-09-17T08:54:39.663 に答える