Вопреки тому, на что здесь акцентируется большинство проголосовавших ответов, неинъективность (то есть, что несколько строк хэшируют одно и то же значение) криптографической хеш-функции, вызванной разницей между большими (потенциально бесконечными ) входной размер и фиксированный выходной размер не является важным моментом - на самом деле, мы предпочитаем хеш-функции, где такие коллизии происходят как можно реже.
Рассмотрим эту функцию (в нотации PHP, как вопрос):
function simple_hash($input) {
return bin2hex(substr(str_pad($input, 16), 0, 16));
}
Это добавляет некоторые пробелы, если строка слишком короткая, а затем занимает первые 16 байтов строки, а затем кодирует ее как шестнадцатеричное. Он имеет тот же размер вывода, что и хеш MD5 (32 шестнадцатеричных символа или 16 байтов, если мы опускаем часть bin2hex).
print simple_hash("stackoverflow.com");
Будет выведено:
737461636b6f766572666c6f772e636f6d
Эта функция также обладает тем же свойством неинъективности, что было выделено в ответе Коди для MD5: мы можем передавать строки любого размера (если они вписываются в наш компьютер), и она будет выводить только 32 шестнадцатеричных числа. Конечно, это не может быть инъективным.
Но в этом случае тривиально найти строку, которая отображается на тот же хеш (просто примените hex2bin к вашему хешу, и он у вас есть). Если ваша исходная строка имела длину 16 (как в нашем примере), вы даже получите эту исходную строку. Ничего подобного не должно быть возможным для MD5, даже если вы знаете, что длина ввода была довольно короткой (кроме как при пробовании всех возможных вводов, пока мы не найдем тот, который соответствует, например, атака методом грубой силы).
Важные допущения для криптографической хеш-функции:
- трудно найти какую-либо строку, производящую данный хэш (сопротивление прообразу)
- трудно найти какую-либо другую строку, производящую тот же хеш, что и данная строка (сопротивление второму прообразу)
- трудно найти любую пару строк с одинаковым хешем (сопротивлением столкновению)
Очевидно, что моя simple_hash функция не удовлетворяет ни одному из этих условий. (На самом деле, если мы ограничим пространство ввода «16-байтовыми строками», то моя функция станет инъективной, и, следовательно, даже доказуемо устойчивой ко второму изображению и столкновению.)
В настоящее время существуют атаки коллизий на MD5 (например, можно создать пару строк, даже с данным одинаковым префиксом, которые имеют одинаковый хэш, с довольно большой работой, но не слишком большой работой), поэтому вам не следует Не используйте MD5 для чего-либо критического.
Пока еще нет атаки прообразом, но атаки станут лучше.
Чтобы ответить на актуальный вопрос:
Что в этих функциях делает
результирующие строки невозможно отследить?
То, что MD5 (и другие хеш-функции строят на основе конструкции Меркля-Дамгарда), эффективно применяет алгоритм шифрования с сообщением в качестве ключа и некоторым фиксированным значением в качестве «простого текста», используя полученный зашифрованный текст в качестве хеша. (Перед этим вход дополняется и разделяется на блоки, каждый из этих блоков используется для шифрования выходных данных предыдущего блока, XORed с его входом для предотвращения обратных вычислений.)
Современные алгоритмы шифрования (включая те, которые используются в хэш-функциях) сделаны таким образом, чтобы затруднить восстановление ключа, даже с учетом открытого текста и зашифрованного текста (или даже когда злоумышленник выбирает один из них).
Обычно они делают это, выполняя множество операций перестановки битов таким образом, что каждый выходной бит определяется каждым битом ключа (несколько раз), а также каждым входным битом. Таким образом, вы можете легко проследить, что происходит внутри, если вы знаете полный ключ и либо ввод, либо вывод.
Для MD5-подобных хеш-функций и атаки на прообраз (с хеш-строкой из одного блока, чтобы упростить задачу) у вас есть только вход и выход вашей функции шифрования, но не ключ (это то, что вы ищете для).