Что самой короткой является пара строк, которая вызывает коллизию MD5?
До какой длины строки возможно использовать MD5 в качестве хеша, не имея необходимость волноваться о возможности коллизии?
Это было бы, по-видимому, вычислено путем генерации хеша MD5 для каждой возможной строки в конкретном наборе символов в увеличивающейся длине, пока хеш не появляется во второй раз (коллизия). Максимальная возможная длина строки без коллизии затем была бы одним символом меньше, чем самая длинная из сталкивающейся пары.
Это было уже протестировано на MD5, SHA1, и т.д.?
2 ответа
] Математика парадокса [] дня рождения [] делает точку перегиба вероятности столкновения примерно вокруг sqrt(N), где N - число различных бин в хэш-функции, так что для 128-битного хэша, по мере того, как вы получаете около 64 бит, вы имеете умеренную вероятность 1 столкновения. Так что я думаю, что для полного набора 8-байтных строк это несколько вероятно будет иметь столкновение, а для 9-байтных строк это крайне вероятно.[
]. [][] edit:[] это предполагает, что хэш-алгоритм MD5 вызывает отображение от входного байтстринга к выходному хэшу, близкому к "случайному". (в сравнении с тем, который более равномерно распределяет строки между множеством возможных хэшей, и в этом случае он был бы более близок к 16 байтам)[
]. [] Также для более конкретного численного ответа, если вы посмотрите на [] одно из приближений [] для вычисления вероятности столкновения, вы получите [
]. []p(k) ≈ 1 - e[]-k(k-1)/(2*2[]128[])[] где k = размер пространства возможных входов = 2[]m[] где входной байтстринг равен m бит длиной.[
]. []набор из 8-ми байтных строк: p(2[]64[]) ≈ 1 - e[]-0.5[] ≈ 0.3935[
] [] набор из 9 строк байт: p(2[]72[]) ≈ 1 - e[]-2[]144[]/(2*2[]128[])[] = 1 - e[]-2[]15[][] = 1 - e[]-32768[] ≈ 1[
] [] Также обратите внимание, что они предполагают [] полный [] набор m/8-байтовых строк. Если вы используете только буквенно-цифровые символы, вам понадобится больше байтов, чтобы получить вероятное столкновение.[
].Сомневаюсь, что есть полезная длина, на которой не будет возможных столкновений. Эти алгоритмы на самом деле не используются для этой цели. Они предназначены для того, чтобы попытаться быть уникальными для небольших изменений данных (например, поврежденных файлов), а не уникальными для всех возможных наборов данных.