Я знаю, что у MD5 были некоторые столкновения, но это скорее вопрос высокого уровня о хэш-функциях.
Если MD5 хэширует любую произвольную строку в 32-значное шестнадцатеричное значение, то согласно Принцип Pigeonhole уверенно это не может быть уникальным, так как есть более уникальные произвольные строки, чем уникальные 32-значные шестнадцатеричные значения.
Вы правы, что он не может гарантировать уникальность, однако есть приблизительно 3.402823669209387e + 38 различных значений в 32-разрядном шестнадцатеричном значении (16 ^ 32). Это означает, что, предполагая, что математика за алгоритмом дает хорошее распределение, ваши шансы феноменально малы, что будет дубликат. Вы должны иметь в виду, что можно дублировать, когда вы думаете о том, как он будет использоваться. MD5 обычно используется, чтобы определить, было ли что-то изменено (например, контрольная сумма). Было бы невероятно маловероятно, чтобы что-то можно было изменить и привести к той же контрольной сумме MD5.
Изменить: (учитывая недавние новости re: SHA1 хэши) Ответ выше, по-прежнему сохраняется, но вы не должны ожидать, что хеш MD5 будет служить как любая проверка безопасности против манипуляции. SHA-1 хешируется как 2 ^ 32 (более 4 миллиардов) раз меньше, чем вероятность столкновения, и было продемонстрировано, что можно получить вход для получения того же значения. (Это было продемонстрировано против MD5 довольно давно). Если вы хотите, чтобы никто не злонамеренно модифицировал что-то, чтобы получить такое же значение хэша, в наши дни вам нужно иметь SHA-2, чтобы получить надежную гарантию.
С другой стороны, если это не в контексте проверки безопасности, MD5 по-прежнему имеет свою полезность.
Можно было бы утверждать, что хэш SHA-2 достаточно дешев для вычисления, что вы все равно должны использовать его.
Вы абсолютно правы. Но хеши не о "уникальном", они о "достаточно уникальном".
Как указывали другие, цель хеш-функции, такой как MD5, заключается в том, чтобы предоставить возможность легко проверить, эквивалентны ли два объекта, не зная, из чего они были (пароли), или сравнивая их полностью (большие файлы).
Скажем, у вас есть объект O и его хэш h O. Вы получаете еще один объект P и хотите проверить, равно ли оно O. Это может быть пароль или файл, который вы загрузили (в этом случае у вас не будет O, а скорее хеш его h O, который поставляется с P, скорее всего). Во-первых, вы hash P, чтобы получить h P.
Теперь есть 2 возможности:
O и P отличаются друг от друга, поскольку использование одного и того же хэша на 2 значениях/объектах должно давать одно и то же значение. Хеши детерминированы. Нет ложных негативов.h O и h P равны. Как вы заявили, из-за принципа Pigeonhole это может означать, что разные объекты хэшируются до одного и того же значения, и, возможно, потребуется предпринять дополнительные действия.
а. Поскольку количество возможностей настолько велико, если у вас есть вера в вашу хеш-функцию, может быть достаточно сказать: "Ну, была вероятность столкновения (идеальный случай) в 1 из 2 128 поэтому мы можем предположим O= P. Это может работать для паролей, если вы ограничиваете длину и сложность символов, например. Именно поэтому вы видите хэши паролей, хранящихся в базах данных, а не сами пароли.
б. Вы можете решить, что только потому, что хэш вышел равным, не означает, что объекты равны, и прямое сравнение O и P. У вас может быть ложный положительный результат.
Итак, если у вас могут быть ложные положительные совпадения, у вас не будет ложных негативов. В зависимости от вашего приложения и ожидаете ли вы, что объекты всегда будут равны или всегда будут разными, хеширование может быть лишним шагом.
Криптографические односторонние хэш-функции по определению не являются Injective. В терминах хеш-функций "уникальный" довольно бессмыслен. Эти функции измеряются другими атрибутами, что влияет на их силу, затрудняя создание предварительного изображения данного хэша. Например, мы можем заботиться о том, сколько бит изображения зависит от изменения одного бита в предварительном изображении. Мы можем заботиться о том, как трудно провести атаку грубой силы (найти предварительное изображение для заданного хеш-изображения). Мы можем заботиться о том, как трудно найти столкновение: найти два изображения, которые имеют одинаковое хэш-изображение, которые будут использоваться в атаке дня рождения.
Вероятно, что вы получаете столкновение, если значения, которые будут хэшированы, намного дольше, чем полученный хеш, число конфликтов все еще достаточно низкое для большинства целей (есть 2 128 возможных хэшей, поэтому вероятность двух случайных строк, создающих один и тот же хеш, теоретически близка к 1 в 10 38).
MD5 был создан прежде всего для проверки целостности, поэтому он очень чувствителен к минимальным изменениям. Небольшая модификация входа приведет к значительному разному. Вот почему трудно угадать пароль, основанный только на хэш-значении.
В то время как сам хэш не обратим, все равно можно найти возможное значение ввода с помощью чистой грубой силы. Вот почему вы всегда должны обязательно добавлять соль, если используете MD5 для хранения хэшей паролей: если вы включаете соль во входную строку, соответствующая строка ввода должна содержать точно такую же соль, чтобы привести к тому же поскольку в противном случае исходная строка ввода, соответствующая результату, не будет соответствовать после автоматического засоления (т.е. вы не можете просто "отменить" MD5 и использовать его для входа в систему, потому что обратный хеш MD5, скорее всего, не будет соленой строка, которая первоначально привела к созданию хэша).
Таким образом, хеши не уникальны, но механизм аутентификации может быть сделан для того, чтобы сделать его достаточно уникальным (что является одним из правдоподобных аргументов для ограничений паролей вместо соления: набор строк, которые приводят к одному и тому же хэшу, вероятно, будет содержать много строки, которые не подчиняются ограничениям пароля, поэтому сложнее перевернуть хэш грубой силой - очевидно, соли все же хорошая идея, тем не менее).
Большие хэши означают больший набор возможных хэшей для одного и того же набора входных данных, так что вероятность совпадения меньше, но до тех пор, пока процессорная мощность не достигнет достаточного уровня, чтобы сделать MD5 тривиальным, он по-прежнему является достойным выбором для большинства целей.
(Кажется, это функция Hash Sunday).
Криптографические хеш-функции рассчитаны на очень, очень, очень низкие уровни дублирования. По очевидной причине вы указываете, что ставка никогда не может быть равна нулю.
страница Википедии является информативной.
Как Майк (и в основном каждый другой) сказал, что он не идеален, но он выполняет эту работу, а производительность столкновения действительно зависит от алгоритма (что на самом деле довольно хорошо).
Что представляет реальный интерес, так это автоматическое манипулирование файлами или данными, чтобы сохранить один и тот же хэш с разными данными, см. Демо
Как и другие, хеш-функции по определению не гарантируют возврата уникальных значений, поскольку существует фиксированное количество хэшей для бесконечного числа входов. Их ключевым качеством является то, что их столкновения непредсказуемы.
Другими словами, они нелегко обратимы, поэтому, хотя может быть много разных входов, которые будут приводить к одному и тому же результату хэша ( "столкновение" ), поиск любых двух из них является вычислительно неосуществимым.