Какова вероятность того, что первые 4 байта MD5-хэша, вычисленные из содержимого файла, будут сталкиваться?

Question

Это комбинаторный вопрос с некоторой теорией в требуемых алгоритмах хеширования.

Допустим, вход может быть любая случайная последовательность байтов 30 кбайт до 5 МБ размера (я предполагаю, что делает довольно много комбинаций входных значений :))

Какова вероятность того, что первые 4 байта (или первые n байтов) хэша MD5, вычисленного из последовательности байтов, будет одинаковым для разных файлов?

В случае, если это невозможно вычислить специально для хэша MD5, то какова вероятность того, что любая хеш-функция, которая генерирует равномерно распределенные х-байтовые хэши, вычислит хэш с столкновением на первые n байтов для заданного диапазона входов?

Answer 1

В случае отсутствия дополнительной информации о вероятности байтовых значений, я бы это день 1 в 2^32.

EDIT. Действительно, 1 в 2^16, если вы берете шестнадцатеричные символы вместо чистых байтов.

EDIT на основе комментариев:

Может MD5 считать, что равномерная что а вычисленные значения абсолютно случайным образом?

MD5 хэш-алгоритм разработан таким образом, что небольшое изменение в результатах ввода в совершенно другой хэш, так что я бы сказал, что MD5 хэш-байты распределены с равной вероятностью (я бы ничего не на него ставку в любом случае). В любом случае вы можете применить пост-обработку к своему хешу (например, вы можете использовать keyed MD5), чтобы увеличить его случайность (и сделать его более безопасным, кстати, с plain MD5 hashes have been proved to be insecure).

Answer 2

Хеши MD5 обычно являются шестнадцатеричными, поэтому для каждого байта имеется 16 возможных значений. Поэтому для четырех байтов существует 16 * 16 * 16 * 16 = 65536 возможных комбинаций, что делает вероятность хэш-столкновения 1: 65536.

Answer 3

md5 является шестнадцатеричным, поэтому каждый символ может быть любым из 16 аллелей. Таким образом, что бы сделать 16^n

Для 4 символов, что делает 65536 различных возможных комбинаций.

Answer 4

Для идеальной хеш-функции выходы распределены равномерно, поэтому вероятность двух столкновений одна из 2^32. Парадокс дня рождения, однако, говорит нам, что если мы сравниваем все пары хэшей, мы должны ожидать столкновения, как только у нас есть 2^16 хэшей, в среднем - поэтому не полагайтесь только на 4 байта на основании того, что «У меня намного меньше 4 миллиардов значений».

MD5 не является идеальной хеш-функцией, как мы знаем, но недостатки здесь несколько случайны: обнаружение столкновения на 4 байта находится в пределах разумной атаки грубой силы, поэтому нет необходимости прибегать к помощи к криптографическим слабостям. Если вас беспокоят только случайные данные, вы не увидите значительного статистического отклонения от случайности.

Answer 5

Если вас интересуют коэффициенты двух конкретных входов, имеющих один и тот же 4-байтовый хэш, то это всего лишь 1/2^32.Если вас интересуют коэффициенты двух входов из набора из X суммарных входов, имеющих одинаковые коэффициенты, это остается довольно низким, пока вы не начнете приближаться к 2^16 = 65536 отдельным входам в вашем наборе, где он достигает около 50% (это явление известно как парадокс дня рождения).

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

Answer 6

Вероятность столкновения в n-битном хэше составляет около 1 в 2^(n/2) из-за birthday paradox - примерно 1 в 2^16 в этом случае. Если по какой-то причине вы ссылались на использование 32 бит шестнадцатеричной кодировки, конечно, это были бы только первые 16 действительных бит, поэтому вероятность столкновения была бы около 1 в 2^8.

Учитывая определенный фиксированный файл, вероятность того, что любой другой файл, выбранный случайным образом, будет иметь один и тот же хэш, так как этот файл составляет около 2^n. В терминах криптографических хэшей разница между ними - первая, это столкновение, другая - прообраз.

При этом размере хэша слабые стороны MD5 довольно неактуальны, так как наиболее известные атаки на MD5 занимают примерно 2^32 вычисления, тогда как можно создать конфликт даже в идеальном безопасном 32-битном хэше около 2^16 вычислений (так как, просто выбирая случайные входы, у вас есть вероятность 1 в 2^16 столкновения, поэтому после примерно 2^16 случайных догадок вы, вероятно, найдете встречную пару входов).