Как похожи на хеш-функции уникальный MD5?

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

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

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

Допустим, у вас есть объект O и его хэш h _O . Вы получаете другой объект P и хотите проверить, равен ли он O . Это может быть пароль или загруженный вами файл (в этом случае у вас не будет O , а будет его хеш h _O , который идет с P ], наверняка). Сначала вы хешируете P , чтобы получить h _P .

Теперь есть 2 возможности:

1. h _O и h _P разные. Это должно означать, что O и P различны, потому что использование одного и того же хеша для 2 значений / объектов должно давать одно и то же значение. Хэши детерминированы. Ложноотрицательных результатов нет.

2. h _O и h _P равны. Как вы заявили, из-за принципа голубятни это может означать, что разные объекты хешируются с одним и тем же значением, и могут потребоваться дальнейшие действия.

   а. Поскольку количество возможностей настолько велико, если вы доверяете своей хеш-функции, может быть достаточно сказать: «Ну, вероятность столкновения составляла 1 из 2 ¹²⁸ (идеальный случай), поэтому мы можем предположить O = P . Это может работать для паролей, например, если вы ограничиваете длину и сложность символов.Вот почему вы видите хэши паролей, хранящиеся в базах данных, а не сами пароли. b. Вы можете решить, что тот факт, что хэш оказался равным, не означает, что объекты равны, и проведите прямое сравнение O и P . У вас может быть ложное срабатывание.

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

Хотя вполне вероятно, что вы получите коллизии, если значения для хеширования будут намного длиннее, чем результирующий хеш, количество коллизий по-прежнему достаточно мало для большинства для целей (существует 2 ¹²⁸ возможных хешей, поэтому вероятность того, что две случайные строки произведут один и тот же хеш, теоретически близка к 1 из 10 ³⁸ ).

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

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

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

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

Криптографические односторонние хэш-функции по природе определения не являются инъективными. С точки зрения хэш-функций, "уникальность" довольно бессмысленна. Эти функции оцениваются по другим атрибутам, что влияет на их силу, затрудняя создание предварительного образа данного хэша. Например, нам может быть важно, сколько битов изображения будет затронуто изменением одного бита в предварительном образе. Нам может быть важно, насколько сложно провести атаку методом перебора (найти предварительный образ для данного хэш-образа). Нас может волновать, насколько сложно найти коллизию: найти два предварительных изображения, которые имеют одинаковый хэш-образ, чтобы использовать их в атаке на день рождения.

Вы абсолютно правы. Но хэши - это не про "уникальность", это про "достаточную уникальность".

(Кажется, сегодня воскресенье хэш-функций.)

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

Информативной является страница Википедии.

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

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