Насколько вероятно, что два блока данных могут давать одно и то же значение CRC64?
У меня есть приложение для кэширования, которое использует значение CRC64 для обеспечения целостности данных. Я думаю о том, чтобы добавить дополнительное поле, временную метку, которая будет передаваться между данными между различными серверами кеша и сравниваться, чтобы увидеть, изменились ли данные.
Однако это требует изменения протокола. Хотя это не так уж и сложно, у меня уже есть CRC64, который можно использовать как индикатор того, что что-то изменилось.
Кто-нибудь знает статистику вокруг двух блоков данных, производящих один и тот же CRC64? Если нет, как я могу рассчитать это или оценить его вероятность?
3 ответа
Если вы предполагаете, что crc64 "идеален", то цифры довольно разумные:
Для вероятности столкновения 1% вам нужно 6,1 × 10^8 записей. Для вероятности столкновения 50% необходимо 5,1 × 10^9 записей.
Конечно, если данные могут быть предоставлены злонамеренными источниками, то могут легко генерироваться коллизии в хэше, столь же простом, как crc64, и коллизии могут быть безудержными. То, пойдете ли вы по этому маршруту или нет, зависит от источника входных данных и возможных последствий столкновений.
Вероятность столкновения любых двух заданных блоков составляет 1/264 или 1 примерно в 1,8 × 1019.
Однако вероятность быстро становится более вероятной, если вас интересует частота столкновений из любых двух блоков из популяции размера N.
Для получения дополнительной информации см. День рождения в Википедии, в которой есть формулы и приближения.
Вероятность того, что два CRC64 для разных случайных данных будут идентичными, будет примерно равна 1 вероятности в 2** 64. Но поскольку CRC несколько чувствительны к шаблонам данных, могут быть вырожденные случаи, когда вы потеряете несколько двоичных порядков защиты. Вероятно, невозможно придумать точное число, но вы, скорее всего, будете уверены, что наихудший шанс столкновения будет меньше, чем 1 шанс из 2** 50 или около того.
Вы были бы уверены, что приблизитесь к теоретическому пределу, если будете использовать криптографический хеш вместо CRC64, но криптографический хеш, как правило, намного дороже для вычисления.