Насколько вероятно, что два блока данных могут давать одно и то же значение CRC64?

Question

У меня есть приложение для кэширования, которое использует значение CRC64 для обеспечения целостности данных.Я подумываю над тем, чтобы добавить дополнительное поле - временную метку, которая будет передаваться между данными между различными серверами кэша, и сравниваться, чтобы увидеть, изменились ли данные.

Однако для этого требуются изменения протокола.Хотя это не так уж и сложно, у меня уже есть CRC64, который можно использовать как индикатор того, что что-то изменилось.Если нет, то как я могу рассчитать это или оценить его вероятность?

Answer 1

Если вы предполагаете, что crc64 «идеален», то цифры довольно разумны:

Для вероятности столкновения 1% вам нужно 6,1 × 10 ^ 8 записей.Для вероятности коллизии 50% вам потребуется 5,1 × 10 ^ 9 записей.

Конечно, если данные потенциально предоставляются злонамеренными источниками, тогда коллизии в хэше, столь же простом, как crc64, могутгенерируется легко, и столкновения могут быть безудержными.То, пойдете ли вы по этому маршруту или нет, зависит от источника входных данных и возможных последствий столкновений.

Answer 2

Вероятность любых двух при заданном блоках столкновения составляет 1/2 ⁶⁴ , или 1 при 1,8 × 10 ¹⁹ .

Однако вероятность быстро становится более вероятной, если вас интересует частота столкновений из любых двух блоков из популяции с размером N.

Для получения дополнительной информации см. День рождения.Задача в Википедии, которая имеет формулы и приближения.

Answer 3

Вероятность того, что два CRC64 по разным случайным данным будут идентичны, будет примерно равна 1 вероятности в 2 ** 64. Но поскольку CRC несколько чувствительны к шаблонам данных, могут быть вырожденные случаи, когда вы потеряете несколько двоичных порядковзащиты.Вероятно, невозможно придумать точное число, но вы, вероятно, будете уверены, что наихудший шанс столкновения будет меньше, чем 1 шанс из 2 ** 50 или около того.

Вы быбудьте уверены, что приблизитесь к теоретическому пределу, если вы использовали криптографический хеш вместо CRC64, но криптографический хеш, как правило, намного дороже для вычисления.