ما مدى احتمال إنتاج كتلتين من البيانات نفس قيمة CRC64؟

Question

لدي تطبيق للتخزين المؤقت يستخدم قيمة CRC64 لضمان سلامة البيانات. أفكر في وضع حقل إضافي، وتم تمرير الطابع الزمني مع البيانات بين خوادم ذاكرة التخزين المؤقت المختلفة ومقارنة مع معرفة ما إذا كانت البيانات قد تغيرت.

ومع ذلك، فإن هذا يتطلب تغييرات البروتوكول.في حين أن هذا ليس صفقة ضخمة، لدي بالفعل CRC64 التي يمكن استخدامها كمؤشر قد تغير شيء ما.

هل يعرف أحد الإحصائيات حول كتلتين من البيانات التي تنتج نفس crc64؟إذا لم يكن الأمر كذلك، فكيف يمكنني حسابها أو تقديرها لاحقا؟

Answer 1

If you assume that crc64 is 'perfect', then the numbers are pretty reasonable:

For a 1% probability of collision, you need 6.1 × 10^8 entries. For a 50% probability of collision, you need 5.1 × 10^9 entries.

Of course, if the data is potentially supplied by malicious sources, then collisions in a hash as simple as crc64 can be generated easily, and collisions could be rampant. So whether or not you go this route depends on the source of input data and the potential ramifications of collisions.

Answer 2

The probability of any two given blocks colliding is 1/2⁶⁴, or 1 in about 1.8 × 10¹⁹.

However, the probability rapidly becomes more likely if you are interested in the rate of collision out of any two blocks from a population of size N.

For more information, see Birthday Problem on Wikipedia, which has formulas and approximations.

Answer 3

The probability of two CRC64s over different random data being identical would be something close to 1 chance in 2** 64. But since CRCs are somewhat sensitive to data patterns, there could be degenerate cases where you'd lose several binary orders of protection. It's probably not possible to come up with a hard number, but you'd likely be safe in assuming the worst case chance of collision would be less than 1 chance in 2** 50 or so.

You'd be assured of getting closer to the theoretical limit if you used a cryptographic hash instead of a CRC64, but the crypto hash is generally much more expensive to compute.