Насколько вероятна коллизия хешей при одинаковой длине файла?

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

Я не совсем доверяю атрибуту «измененная дата» в файловой системе, поэтому хочу сравнить фактические байты в файле.

Я думаю, что самый быстрый способ сделать это (поскольку отправка всех байтов через Интернет занимает некоторое время) - это отправить на сервер длину файла и байты хэша. Затем сервер сначала проверяет длину файла и, если они совпадают, вычисляет хэш для файла, расположенного на сервере, а затем проверяет, совпадает ли он с тем, который вычислил клиент.

Может ли кто-нибудь сказать мне, насколько вероятны хеш-коллизии при одинаковом размере файла? (В настоящее время я использую MD5 для его скорости).

Могу ли я предположить, что если размер файла такой же, а хеш такой же, то и содержимое такое же?

Спасибо!


person Jakob Høgenes    schedule 09.12.2010    source источник


Ответы (1)


Случайные столкновения в MD5 настолько маловероятны, что их почти наверняка безопасно игнорировать.

Однако было показано, что MD5 криптографически слаб, поэтому злоумышленник может намеренно создавать файлы, которые конфликтуют. Известный пример:

30 декабря 2008 года группа исследователей объявила на 25-м Конгрессе по коммуникациям Хаоса, как они использовали коллизии MD5 для создания промежуточного сертификата центра сертификации, который оказался легитимным при проверке через его хэш MD5.

Источник

person Mark Byers    schedule 09.12.2010
comment
Спасибо! Вредоносный аспект проблемы не волнует :) Вы знаете порядок коллизии? Как один к чему? - person Jakob Høgenes; 09.12.2010
comment
@Jakob: Для двух конкретных файлов вероятность столкновения составляет примерно 1 из 340282366920938463463374607431768211456. Вероятность столкновения в наборе файлов выше (но все же чрезвычайно, невероятно, невероятно, удивительно маловероятно). - person Mark Byers; 09.12.2010
comment
Я очень счастлив, когда шансы так низки! Еще раз спасибо! - person Jakob Høgenes; 09.12.2010
comment
Чтобы быть немного более общим, для N-битного криптографически безопасного хеша вероятность коллизии довольно близка к 1 из 2 ^ N. - person Slartibartfast; 11.12.2010