Какова вероятность, что первые 4 байта хеша MD5, вычисленного из содержания файла, столкнутся?
Предположим, что Вы создаете CMS для веб-сайта, где Ваши страницы находятся в древовидной структуре, с говорят корень, являющийся домашней страницей.
предположим также Ваш {user|client|customer|boss} запрашивает поместить пройденный путь на каждой странице для показа, где Вы находитесь в дереве.
Для любой данной страницы n, Вы будете, может хотеть приблизиться к родителю n и его родителю, и так далее, рекурсивно создать список узлов назад до корня дерева страницы.
, Конечно, Вы поражаете дб несколько раз на страницу в том примере, таким образом, можно хотеть использовать некоторое искажение SQL, где Вы ищете таблицу страниц как a и таблицу страниц снова как b, и присоединяетесь к a.id с b.parent, таким образом, Вы заставляете базу данных сделать рекурсивные соединения. Это было некоторое время, таким образом, мой синтаксис, вероятно, не полезен.
С другой стороны, можно просто хотеть только вычислить это однажды и снабдить его записью страницы, только обновляя его при перемещении страницы. Это, вероятно, было бы более эффективным.
Так или иначе, это составляет мои.02$
6 ответов
В отсутствие дополнительной информации о вероятности байтовых значений, я бы сказал, что это 1 из 2 ^ 32.
EDIT . Действительно, 1 из 2 ^ 16, если вы берете шестнадцатеричные символы вместо чистых байтов.
РЕДАКТИРОВАТЬ на основе комментария:
Можно ли считать MD5 такой унифицированной что вычисленные значения абсолютно случайный?
Алгоритм хеширования MD5 спроектирован таким образом, что небольшое изменение во входных данных приводит к совершенно другому хешу, поэтому я бы сказал, что байты хэша MD5 распределяются с равной вероятностью (я бы все равно ничего не ставил на это). В любом случае вы можете применить постобработку к вашему хешу (например, вы можете использовать MD5 с ключом ), чтобы увеличить его случайность (и, кстати, сделать его более безопасным, поскольку простые хеши MD5 имеют оказалась небезопасной ).
Для идеальной хеш-функции выходные данные распределяются равномерно, поэтому вероятность двух столкновений равна 1 к 2 ^ 32. Парадокс дня рождения, однако, говорит нам, что если мы сравниваем все пары хешей, мы должны ожидать столкновения, когда у нас будет 2 ^ 16 хешей, в среднем, поэтому не полагайтесь только на 4 байта на основании того, что «У меня намного меньше 4 миллиардов значений».
MD5 не является идеальной хеш-функцией, как мы знаем, но слабые стороны здесь несколько случайны: обнаружение коллизии на 4 байтах находится в пределах разумной атака методом грубой силы, поэтому нет необходимости прибегать к криптографическим слабостям. Если вас беспокоят только случайно выбранные данные, вы не увидите значительного статистического отклонения от случайности.
Если вас интересуют шансы двух конкретных входных данных, имеющих одинаковый 4-байтовый хэш, то это всего лишь 1/2 ^ 32. Если вас интересуют шансы двух входов из набора из X общих входов, имеющих одинаковые шансы, это остается довольно низким, пока вы не начнете приближаться к 2 ^ 16 = 65536 отдельным входам в вашем наборе, где оно достигнет около 50% ( это явление известно как парадокс дня рождения).
В общем, одним из критериев криптографической полезности хеш-функции является единообразие по всем битам.
Вероятность коллизии в n-битном хэше составляет примерно 1 к 2 ^ (n / 2) из-за парадокса дня рождения - так что примерно 1 из 2 ^ 16 в этом случае. Если по какой-то причине вы имели в виду использование 32-битного шестнадцатеричного кодирования, конечно, это были бы только первые 16 фактических битов, поэтому вероятность столкновения будет примерно 1 из 2 ^ 8.
С учетом конкретного фиксированный файл, вероятность того, что любой другой файл, выбранный случайным образом, будет иметь такой же хэш, как этот файл, составляет около 2 ^ n. Что касается криптографических хэшей, разница между ними заключается в том, что первое - это коллизия, а второе - прообраз.
При таком размере хеша слабые места в MD5 не имеют большого значения, так как самые известные атаки на MD5 требуют примерно 2 ^ 32 вычислений. ,
Хеши MD5 обычно шестнадцатеричные, поэтому для каждого байта есть 16 возможных значений. Следовательно, для четырех байтов существует 16 * 16 * 16 * 16 = 65536 возможных комбинаций, что составляет вероятность хеш-коллизии 1: 65536.
md5 является шестнадцатеричным, поэтому каждый символ может быть любым из 16 аллелей.
Таким образом, получается 16 ^ n
Для 4 символов получается 65536 различных возможных комбинаций.