ハッシュの衝突確率を評価するにはどうすればよいですか?

StackOverflow https://stackoverflow.com/questions/862346

質問

検索システムのバックエンド アプリケーションを開発しています。検索システムはファイルを一時ディレクトリにコピーし、ランダムな名前を付けます。次に、一時ファイルの名前をアプリケーションに渡します。私のアプリケーションは、限られた時間内に各ファイルを処理する必要があります。処理しないとシャットダウンされます。これは、ウォッチドッグのようなセキュリティ対策です。ファイルの処理には時間がかかる可能性があるため、このシナリオを処理できるアプリケーションを設計する必要があります。次回、検索システムが同じファイルのインデックスを作成しようとしたときにアプリケーションがシャットダウンされた場合、別の一時的な名前が付けられる可能性があります。

明らかな解決策は、検索システムとバックエンドの間に中間層を提供することです。リクエストをバックエンドのキューに入れ、結果が到着するのを待ちます。中間層でリクエストがタイムアウトしても問題ありません。バックエンドは引き続き動作し、中間層のみが再起動され、後で検索システムによってリクエストが繰り返されたときにバックエンドから結果を取得できます。

問題はファイルをどのように識別するかです。彼らの名前はランダムに変わります。MD5 のようなハッシュ関数を使用してファイルの内容をハッシュするつもりです。私はよく知っています 誕生日のパラドックス リンクされた記事からの推定値を使用して確率を計算しました。ファイルが 100,000 個以下であると仮定すると、2 つのファイルが同じ MD5 (128 ビット) を持つ確率は約 1,47x10 です。-29.

このような衝突の可能性を考慮すべきでしょうか、それともハッシュ値が等しいということはファイルの内容が等しいと仮定するだけなのでしょうか?

役に立ちましたか？

解決

悪意のある誰かがファイルをいじってコリジョンを挿入しない限り、等しいハッシュは等しいファイルを意味します。(インターネットからダウンロードしている場合はこれに該当する可能性があります) その場合は、SHA2 ベースの機能を使用してください。

偶発的な MD5 衝突はありません。1,47x10-29 本当に本当に本当に小さな数字です。

大きなファイルの再ハッシュの問題を克服するには、3 段階の ID スキームを使用します。

  1. ファイルサイズのみ
  2. ファイルサイズ + ファイル内のさまざまな位置にある 64K * 4 のハッシュ
  3. 完全なハッシュ

したがって、新しいサイズのファイルが表示された場合は、重複がないことが確実にわかります。等々。

他のヒント

確率は1 / Xであるため、

ただ、それはあなたがXレコードを持ってまで、それはあなたに起こらないことを意味するものではありません。それはあなたが勝つ可能性がないなら、宝くじのようなものだが、の誰かのそこにのの意志の勝利ます。

コンピュータの高速化、大容量で、これらの日だけ重要なもののためにMD5よりも大きな/より良いハッシュ関数を使用しない理由は本当にありません（でも、セキュリティ、信頼性だけの話ではありません）。 SHA-1へのステップアップして、あなたが夜によく眠れる助けるが、あなたは余分に慎重になりたいならば、SHA-265に行き、決して再びそれについて考える必要があります。

パフォーマンスは本当に問題がある場合は、MD5よりも、実際に高速ですが、同等以上の性能を持ちながら、衝突が少ない可能性を高めるために256+ビットをサポートしていますBLAKE2を使用しています。 BLAKE2がよく採用されていながら、しかし、それはおそらくあなたのプロジェクトに新しい依存関係を追加することが必要になります。

私はあなたがいけないと思います。

あなたが別の（本当の名前ではなく、MD5ベース）を有する二つの等しいファイルの概念を持っている場合は、

しかし、あなたがする必要があります。同様に、検索システムに2つの文書は、まったく同じ内容を持っていますが、彼らは別の場所に位置しているので明確なことかもしれません。

私は衝突せずにシリアライズする必要があり、分散システムのためのUUIDを使用しながら、安全に眠ることができるようにモンテカルロ法を思い付います。

from random import randint
from math import log
from collections import Counter

def colltest(exp):
    uniques = []
    while True:
        r = randint(0,2**exp)
        if r in uniques:
            return log(len(uniques) + 1, 2)
        uniques.append(r)

for k,v in Counter([colltest(20) for i in xrange(1000)]):
    print k, "hash orders of magnitude events before collission:",v

のようなものを印刷します：

5 hash orders of magnitude events before collission: 1
6 hash orders of magnitude events before collission: 5
7 hash orders of magnitude events before collission: 21
8 hash orders of magnitude events before collission: 91
9 hash orders of magnitude events before collission: 274
10 hash orders of magnitude events before collission: 469
11 hash orders of magnitude events before collission: 138
12 hash orders of magnitude events before collission: 1

私は前に式を聞いた：あなたは（X / 2）キーを記録保存する必要がある場合は、少なくとも鍵空間eを持つハッシュ関数を使用**（x）の

繰り返し実験は、1000年のログ-20スペースの人口のために、あなたは時々、早けれログ（X / 4）などの衝突を得ることを示しています。

私は約2 ** 31項目を持ってまで、いくつかのコンピュータがランダムUUID年代を選択しながら、私は安全に眠る意味122ビットであるuuid4ください。私は考えていますシステムのピークのトランザクションは、毎秒およそ10〜20のイベント、私は極度のパラノイアことを考えると、私は約10年間の動作ウィンドウを与える7の平均を想定していますされます。

ここでは、任意のハッシュサイズとオブジェクトの数の衝突の確率を推定することができますインタラクティブ電卓だ - <のhref =「http://everydayinternetstuff.com/2015/04/hash-collision-probability-calculator/」のrel = "nofollowを"> http://everydayinternetstuff.com/2015/04/hash-collision-probability-calculator/ の

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top