5

データの整合性を確保するためにCRC64値を使用するキャッシュアプ​​リケーションがあります。さまざまなキャッシュサーバー間でデータとともに渡され、データが変更されたかどうかを比較するためのタイムスタンプである、追加のフィールドを配置することを考えています。

ただし、これにはプロトコルの変更が必要です。それは大したことではありませんが、何かが変わったことを示す指標として使用できるCRC64をすでに持っています。

同じCRC64を生成する2つのデータブロックの統計を知っている人はいますか？そうでない場合、どうすればそれを計算したり、その可能性を推定したりできますか？

4

3 に答える 3

7

crc64が「完璧」であると仮定すると、数値はかなり合理的です。

衝突の確率が1％の場合、6.1×10^8のエントリが必要です。衝突の確率が50％の場合、5.1×10^9のエントリが必要です。

もちろん、データが悪意のあるソースから提供される可能性がある場合は、crc64のような単純なハッシュでの衝突を簡単に生成でき、衝突が横行する可能性があります。したがって、このルートを使用するかどうかは、入力データのソースと衝突の潜在的な影響によって異なります。

于 2011-05-17T02:04:10.067 に答える
3

任意の2つのブロックが衝突する確率は、 1/2 64、つまり約1.8×1019の1です。

ただし、サイズNの母集団からの任意の2つのブロックからの衝突率に関心がある場合は、確率が急速に高くなります。

詳細については、数式と近似値が記載されているWikipediaの誕生日の問題を参照してください。

于 2011-05-17T02:00:55.043 に答える
0

異なるランダムデータ上の2つのCRC64が同一である確率は、2 ** 64で1回に近い確率です。ただし、CRCはデータパターンにある程度敏感であるため、保護の2進順序がいくつか失われるという退化したケースが発生する可能性があります。確かな数字を思い付くのはおそらく不可能ですが、最悪の場合の衝突の可能性は2**50程度で1回未満であると想定しても安全でしょう。

CRC64の代わりに暗号化ハッシュを使用した場合は理論上の限界に近づくことが保証されますが、暗号化ハッシュは一般に計算にはるかに費用がかかります。

于 2011-05-17T02:21:30.983 に答える