Вопреки тому, что здесь подчеркивается в ответах, получивших наибольшее количество голосов, отсутствие инъекций (т.е. наличие нескольких строк, хэширующих одно и то же значение) криптографической хеш-функции, вызванное различием между большими (потенциально бесконечными) входными данными размер и фиксированный размер вывода не важен - на самом деле мы предпочитаем хэш-функции, в которых эти коллизии происходят как можно реже.
Рассмотрим эту функцию (в нотации 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 (и другие хэш-функции, основанные на конструкции Меркла-Дамгарда), так это применение алгоритма шифрования с сообщением в качестве ключа и некоторым фиксированным значением в качестве «простого текста», используя полученный зашифрованный текст в качестве хеша. (Перед этим ввод дополняется и разбивается на блоки, каждый из этих блоков используется для шифрования вывода предыдущего блока, с его вводом выполняется операция XOR, чтобы предотвратить обратные вычисления.)
Современные алгоритмы шифрования (в том числе те, которые используются в хэш-функциях) созданы таким образом, чтобы затруднить восстановление ключа, даже учитывая и открытый текст, и зашифрованный текст (или даже когда злоумышленник выбирает один из них). Обычно они делают это, выполняя множество операций перестановки битов таким образом, что каждый выходной бит определяется каждым битом ключа (несколько раз), а также каждым входным битом. Таким образом, вы можете легко проследить то, что происходит внутри, только если вы знаете полный ключ и вход или выход.
Для хэш-функций, подобных MD5, и атаки по прообразу (с одноблочной хешированной строкой, чтобы упростить задачу) у вас есть только ввод и вывод вашей функции шифрования, но не ключ (это то, что вы ищете).
person
Paŭlo Ebermann
schedule
22.08.2011
