Wie wahrscheinlich ist es, dass zwei Datenblöcke denselben CRC64-Wert ergeben?

Question

Ich habe eine Caching-Anwendung, die einen CRC64-Wert verwendet, um die Datenintegrität zu gewährleisten. Ich denke darüber nach, ein zusätzliches Feld einzufügen, einen Zeitstempel, der mit den Daten zwischen den verschiedenen Cache-Servern weitergegeben und verglichen wird, um festzustellen, ob sich die Daten geändert haben.

Dies erfordert jedoch eine Änderung des Protokolls. Das ist zwar keine große Sache, aber ich habe bereits einen CRC64, der als Indikator dafür dienen könnte, dass sich etwas geändert hat.

Kennt jemand die Statistiken über zwei Datenblöcke, die denselben CRC64 erzeugen? Wenn nicht, wie könnte ich sie berechnen oder ihre Wahrscheinlichkeit abschätzen?

Answer 1

Wenn man davon ausgeht, dass crc64 "perfekt" ist, dann sind die Zahlen ziemlich vernünftig:

Für eine Kollisionswahrscheinlichkeit von 1 % benötigt man 6,1 × 10^8 Einträge. Für eine 50%ige Kollisionswahrscheinlichkeit werden 5,1 × 10^9 Einträge benötigt.

Wenn die Daten möglicherweise aus böswilligen Quellen stammen, können Kollisionen in einem so einfachen Hash wie crc64 natürlich leicht erzeugt werden, und die Kollisionen könnten überhand nehmen. Ob Sie sich für diesen Weg entscheiden, hängt also von der Quelle der Eingabedaten und den möglichen Auswirkungen von Kollisionen ab.

Answer 2

Die Wahrscheinlichkeit, dass zwei beliebige gegeben kollidierende Blöcke ist 1/2 64 oder 1 in etwa 1,8 × 10 19 .

Die Wahrscheinlichkeit wird jedoch schnell wahrscheinlicher, wenn man sich für die Häufigkeit von Kollisionen aus zwei beliebige Blöcke aus einer Population der Größe N.

Weitere Informationen finden Sie unter Geburtstagsproblem auf Wikipedia, die Formeln und Näherungswerte enthält.

Answer 3

Die Wahrscheinlichkeit, dass zwei CRC64s über verschiedene Zufallsdaten identisch sind, liegt bei etwa 1 Chance zu 2** 64. Da CRCs jedoch etwas empfindlich auf Datenmuster reagieren, könnte es degenerierte Fälle geben, in denen man mehrere binäre Schutzstufen verliert. Es ist wahrscheinlich nicht möglich, eine konkrete Zahl zu nennen, aber man kann wohl davon ausgehen, dass die Wahrscheinlichkeit einer Kollision im schlimmsten Fall weniger als 1 zu 2** 50 beträgt oder so.

Wenn Sie einen kryptografischen Hash anstelle eines CRC64 verwenden, kommen Sie sicher näher an die theoretische Grenze heran, aber der kryptografische Hash ist in der Regel sehr viel teurer zu berechnen.