問題タブ [hash-collision]

シナリオ

レポートをその場で (SQL データベースから取得した情報に基づいて) 生成できる Web アプリケーションを構築しています。これらのレポートにはグラフが含まれており、オンザフライで生成することもできます。これらのチャートには機密情報が含まれているため、サードパーティのチャート API (つまり、Google チャート) を使用することは問題外です。

問題

これらのチャートを生成するために PHP の GD 拡張機能を使用しています。かなり遅いです。キャッシュは有効な方法ですが、問題は膨大な数のチャートが存在することです。ただし、要求されるチャートの大部分は、以前に生成されたものになると思います。

部分解

グラフは、データとその他の情報 (サイズ、グラフの種類など) を使用して生成されます。これらはチャートを一意に識別できるため、この情報に基づいて各チャートに一意のハッシュを与えて保存します。これで、新しくリクエストされたチャートのハッシュを計算し、すでにレンダリングされているかどうかを確認できます。

これに関する問題は、衝突のイベントです。それを回避するために、ハッシュとシリアル化された形式のデータを SQL テーブルに保存することを考えています。その後、キャッシュ ヒットが発生した場合でも、データ自体を比較します。

私はこれを過剰に設計していますか？(これは 160 ビットのハッシュ - SHA1 です)
これを処理するより良い方法はありますか?

文字列「temp」のハッシュ関数による配列インデックスが 155 で、位置 155 が事前に占有されていると仮定し、位置 156 が試行されます。場所 156 が利用可能であると仮定すると、このエントリは場所 155 ではなく場所 156 に保存されます。後で、場所 156 にマップされる別の文字列「another_temp」を見つけます。これも、次に利用可能な場所 157 に保存されます。

問題は、後で「another_temp」の場所を知りたい場合、ハッシュ関数が 156 を返したとしても、それが 156 ではなく 157 であることをどのように知ることができるでしょうか?

ありがとう。

Unicode / UTF-16 でエンコードされたパスがあります。パス区切り文字は U+005C '\' です。パスは、null で終わるルート相対 Windows ファイル システム パスです (例: "\windows\system32\drivers\myDriver32.sys")。

このパスを64 ビットの符号なし整数にハッシュしたいと考えています。「暗号的に健全」である必要はありません。ハッシュは大文字と小文字を区別しない必要がありますが、ASCII 以外の文字を処理できます。明らかに、ハッシュも適切に分散する必要があります。

私が持っていたいくつかのアイデアがあります：

A) Windows ファイル識別子を「ハッシュ」として使用する。私の場合、ファイルが移動された場合にハッシュを変更したいので、これはオプションではありません。

B) 通常の文字列ハッシュを使用するだけです: ハッシュ += プライム * ハッシュ + 文字列全体のコードポイント。

パスが「セグメント」(フォルダー名と最終的なファイル名) で構成されているという事実を活用できると感じています。

ニーズをまとめると、次のようになります。

1) 64 ビット ハッシュ
2) 適切な分散/ファイル システム パスの競合が少ない。
3) 効率的
4) 安全である必要がない
5) 大文字と小文字 を区別しない

メモリの浪費を最小限に抑えるために負荷係数が 1 に近い場合、どのハッシュマップ衝突処理スキームが優れていますか?

個人的には、衝突が発生した場合に追加のストレージ スペースを必要としないため、答えはリニア プロービングによるオープン アドレッシングだと思います。これは正しいです？

ハッシュテーブルでのキーの並べ替え/挿入チェックがどのように機能するかを理解しようとしています。オブジェクトをハッシュテーブルに追加すると、実行時に同じキーがまだ入力されていないかどうかがチェックされることを理解しました。

私のテストでは、キーが入力される2つのハッシュテーブルがあります。1-整数2-常に1を返すようにGetHashCodeメソッドをオーバーライドしたオブジェクト。

ここでの私の問題：同じintキーを追加すると最初のテストが壊れていますが、2番目のテストは壊れていません！どうして？挿入時にチェックする必要のあるハッシュコードはすべて1を返します。

前もって感謝します！

私のコード：

}

日付を表す1つのDateWrapperが必要です（Hibernateの永続性のために構築されていますが、これは別の話です）-せいぜい同じ日付で同時に存在します。

衝突とハッシュの適切なキーについて少し混乱しています。私はDateWrapperオブジェクトのファクトリを書いています。他の人が行っているのを見たように、解析された日付のミリ秒をキーとして使用することを考えました。しかし、もし衝突したらどうなるでしょうか？. ミリ秒は常に互いに異なりますが、内部テーブルは存在する可能性のある Long よりも小さい場合があります。ハッシュ マップに衝突が発生すると、equals が使用されますが、Long から 2 つの異なるオブジェクトをどのように区別できるでしょうか? たぶん、挿入したい値を削除（上書き）するのはputメソッドです...では、このコードは安全ですか、それともバグですか??

MD5 コリジョンを作成するだけで大​​まかな証明書を作成する方法がわかりません。元のハッシュと一致する別の文字列を見つけることができたとしても、どのように署名しますか? 認証局の秘密鍵にアクセスできませんか?

4 文字のハッシュが必要です。現時点では、md5()ハッシュの最初の 4 文字を取得しています。80 文字以下の文字列をハッシュしています。これは衝突につながりますか？^{または、65,536 (16 4} )未満の異なる要素をハッシュすると仮定すると、衝突の可能性はどのくらいですか?

私はメッセージダイジェストの分野でいくつかの予備調査を行ってきました。具体的には、 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）になりますが、ブルートフォースよりも時間計算量が少ない方法はありますか？

ユーザーがコンテンツをアップロードできるサイトを構築しています。相変わらず世界制覇を目指しているので、同じファイルを2度保存するのは避けたいところです。たとえば、ユーザーが同じファイルを 2 回アップロードしようとした場合 (名前を変更するか、過去に行ったことを単に忘れて)。

私の現在のアプローチは、アップロードされた各ファイルを追跡するデータベースに、各ファイルに関する次の情報を保存することです。

• ファイル サイズ (バイト)
• ファイル内容の MD5 サム
• ファイル内容の SHA1 合計

次に、これら 3 つの列の一意のインデックスです。2 つのハッシュを使用して、誤検知のリスクを最小限に抑えます。

だから、私の質問は本当に:同じサイズの 2 つの異なる (「実世界の」) ファイルが同一の MD5およびSHA1 ハッシュを持つ確率はどれくらいですか?

または：同様の（非）複雑さのよりスマートな方法はありますか？

（確率はファイルサイズに依存する可能性があることを理解しています）。

ありがとう！