Чем уникальны хэш-функции, такие как MD5?

Question

Я знаю, что у MD5 были некоторые коллизии, но это скорее вопрос высокого уровня о хэш-функциях.

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

Answer 1

Вы правы, что это не может гарантировать уникальность, однако в 32-значном шестнадцатеричном значении есть приблизительно 3.402823669209387e + 38 различных значений (16 ^ 32). Это означает, что, если математика, лежащая в основе алгоритма, дает хорошее распределение, ваши шансы феноменально малы, что будет дубликат. Вы должны иметь в виду, что возможно дублировать, когда вы думаете о том, как это будет использоваться. MD5 обычно используется для определения того, было ли что-то изменено (т.е. это контрольная сумма). Было бы невероятно невероятно, чтобы что-то могло быть изменено и приводить к той же контрольной сумме MD5.

Редактировать: (учитывая последние новости о: хэши SHA1) Ответ выше остается верным, но вы не должны ожидать, что хеш MD5 послужит какой-либо проверкой безопасности от манипуляций. SHA-1 уменьшает вероятность столкновения в 2 ^ 32 (более 4 миллиардов) раз, и было продемонстрировано, что можно придумать вход для получения того же значения. (Это было продемонстрировано против MD5 довольно давно). Если вы хотите убедиться, что никто не злонамеренно что-то изменил, чтобы получить такое же значение хеш-функции, в настоящее время вам нужно в SHA-2 иметь надежную гарантию.

С другой стороны, если это не в контексте проверки безопасности, MD5 все еще имеет свою полезность.

Можно утверждать, что хеш SHA-2 достаточно дешев, чтобы его можно было вычислить, и вы все равно должны его использовать.

Answer 2

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

Answer 3

Как уже отмечали другие, цель хеш-функции, такой как 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. Это может работать, например, для паролей, если вы ограничиваете длину и сложность символов, поэтому вы видите хеши паролей, хранящиеся в базах данных, а не сами пароли. б. Вы можете решить, что только то, что хеш получился равным, не означает, что объекты равны, и проведите прямое сравнение O и P. Возможно, у вас ложный положительный результат.

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

Answer 4

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

Answer 5

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

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

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

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

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

Answer 6

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

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

Answer 7

(Похоже на хэш-функцию в воскресенье.)

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

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

Answer 8

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

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