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

Question

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

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

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

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

Answer 1

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

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

РЕДАКТИРОВАТЬ на основании комментария:

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

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

Answer 6

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