Почему хэш-значения MD5 необратимы?
Одна концепция, о которой я всегда задумывался, - это использование криптографических хеш-функций и значений. Я понимаю, что эти функции могут генерировать хеш-значение, которое уникально и практически невозможно изменить, но вот что я всегда удивлялся:
Если на моем сервере, в PHP я выдаю:
md5("stackru.com") = "d0cc85b26f2ceb8714b978e07def4f6e"
Когда вы запускаете эту же строку через функцию MD5, вы получаете тот же результат при установке PHP. Процесс используется для получения некоторой ценности из некоторой начальной стоимости.
Не значит ли это, что есть какой-то способ деконструировать происходящее и обратить вспять хэш-значение?
Что в этих функциях делает невозможным отслеживание полученных строк?
16 ответов
Входной материал может быть бесконечной длины, где выходной файл всегда имеет длину 128 бит. Это означает, что бесконечное количество входных строк будет генерировать один и тот же результат.
Если вы выберете случайное число и поделите его на 2, а запишете только остаток, вы получите либо 0, либо 1 - четное или нечетное соответственно. Можно ли взять это 0 или 1 и получить оригинальный номер?
Если бы такие хеш-функции, как MD5, были обратимыми, это было бы переломным моментом в истории алгоритмов сжатия данных! Легко видеть, что если бы MD5 был обратимым, то произвольные порции данных произвольного размера могли бы быть представлены просто 128 битами без какой-либо потери информации. Таким образом, вы смогли бы восстановить исходное сообщение из 128-битного числа независимо от размера исходного сообщения.
Вопреки тому, что подчеркивают здесь большинство проголосовавших ответов, неинъективность (то есть наличие нескольких строк, хэширующих одно и то же значение) криптографической хеш-функции, вызванной разницей между большим (потенциально бесконечным) размером ввода и фиксированным размером вывода, не является важный момент - на самом деле, мы предпочитаем хеш-функции, где такие коллизии происходят как можно реже.
Рассмотрим эту функцию (в нотации PHP, как вопрос):
function simple_hash($input) {
return bin2hex(substr(str_pad($input, 16), 0, 16));
}
Это добавляет некоторые пробелы, если строка слишком короткая, а затем занимает первые 16 байтов строки, а затем кодирует ее как шестнадцатеричный. Он имеет тот же размер вывода, что и хеш MD5 (32 шестнадцатеричных символа или 16 байт, если мы опускаем часть bin2hex).
print simple_hash("stackru.com");
Это выведет:
737461636b6f766572666c6f772e636f6d
Эта функция также обладает тем же свойством неинъективности, что было выделено в ответе Коди для MD5: мы можем передавать строки любого размера (если они вписываются в наш компьютер), и она будет выводить только 32 шестнадцатеричных числа. Конечно, это не может быть инъективным.
Но в этом случае тривиально найти строку, которая отображается на тот же хеш (просто примените hex2bin
на твой хеш, и он у тебя есть). Если ваша исходная строка имела длину 16 (как в нашем примере), вы даже получите эту исходную строку. Ничего подобного не должно быть возможным для MD5, даже если вы знаете, что длина ввода была достаточно короткой (кроме как при пробовании всех возможных вводов, пока мы не найдем тот, который соответствует, например, атака методом грубой силы).
Важные допущения для криптографической хеш-функции:
- трудно найти какую-либо строку, производящую данный хеш (сопротивление прообразу)
- трудно найти какую-либо другую строку, производящую тот же хеш, что и данная строка (сопротивление второго прообраза)
- трудно найти пару строк с одинаковым хешем (сопротивление столкновению)
Очевидно, мой simple_hash
Функция не удовлетворяет ни одному из этих условий. (На самом деле, если мы ограничим входное пространство "16-байтовыми строками", то моя функция станет инъективной, и, таким образом, даже доказуемо устойчивой ко второму изображению и столкновению.)
В настоящее время существуют атаки коллизий на MD5 (например, можно создать пару строк, даже с заданным одинаковым префиксом, которые имеют одинаковый хэш, с довольно большой работой, но не без особой работы), поэтому не следует использовать MD5 для чего-нибудь критического. Пока нет прообразной атаки, но атаки станут лучше.
Чтобы ответить на актуальный вопрос:
Что в этих функциях делает невозможным отслеживание полученных строк?
Что эффективно делает MD5 (и другие хеш-функции, основанные на конструкции Меркле-Дамгарда), так это применяет алгоритм шифрования с сообщением в качестве ключа и некоторым фиксированным значением в качестве "простого текста", используя полученный зашифрованный текст в качестве хеша. (Перед этим вход дополняется и разделяется на блоки, каждый из этих блоков используется для шифрования выходных данных предыдущего блока, XORed с его входом для предотвращения обратных вычислений.)
Современные алгоритмы шифрования (включая те, которые используются в хэш-функциях) сделаны таким образом, чтобы затруднить восстановление ключа, даже с учетом открытого текста и зашифрованного текста (или даже когда злоумышленник выбирает один из них). Обычно они делают это путем выполнения множества операций перестановки битов таким образом, что каждый выходной бит определяется каждым битом ключа (несколько раз), а также каждым входным битом. Таким образом, вы можете легко проследить, что происходит внутри, если вы знаете полный ключ и либо ввод, либо вывод.
Для хэш-функций, подобных MD5, и для атаки на прообраз (с хеш-строкой из одного блока, чтобы упростить задачу) у вас есть только вход и выход вашей функции шифрования, но не ключ (это то, что вы ищете).
Ответ Коди Брошиуса является правильным. Строго говоря, вы не можете "инвертировать" хеш-функцию, потому что многие строки отображаются в один и тот же хеш. Заметьте, однако, что либо обнаружение одной строки, сопоставленной с данным хешем, либо обнаружение двух строк, сопоставленных с одним и тем же хешем (т. Е. Коллизия), станет большим прорывом для криптоаналитика. Большая трудность обеих этих проблем является причиной того, что хорошие хеш-функции полезны в криптографии.
MD5 не создает уникальное хеш-значение; Целью MD5 является быстрое получение значения, которое значительно изменяется в зависимости от незначительного изменения источника.
Например,
"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"
(Очевидно, что это не фактическое шифрование MD5)
Большинство хэшей (если не все) также не являются уникальными; скорее, они достаточно уникальны, поэтому столкновение крайне маловероятно, но все же возможно.
Хороший способ подумать о алгоритме хеширования - подумать об изменении размера изображения в Photoshop... скажем, у вас есть изображение размером 5000x5000 пикселей, а затем вы измените его размер до 32x32. То, что у вас есть, по-прежнему является представлением исходного изображения, но оно намного меньше и эффективно "отбрасывает" определенные части данных изображения, чтобы оно соответствовало меньшему размеру. Поэтому, если бы вы изменили размер изображения 32x32 до 5000x5000, все, что вы получите, - это размытый беспорядок. Однако из-за того, что изображение размером 32x32 не так велико, теоретически можно предположить, что другое изображение можно уменьшить, чтобы получить точно такие же пиксели!
Это просто аналогия, но она помогает понять, что делает хеш.
Поскольку число возможных входных файлов больше, чем количество 128-битных выходных данных, невозможно однозначно назначить хэш MD5 для каждого возможного.
Криптографические хеш-функции используются для проверки целостности данных или цифровых подписей (хеш подписывается для эффективности). Следовательно, изменение исходного документа должно означать, что исходный хеш не соответствует измененному документу.
Эти критерии иногда используются:
- Сопротивление прообразу: для данной хэш-функции и данного хеша должно быть трудно найти входные данные, которые имеют данный хэш для этой функции.
- Сопротивление второго прообраза: для данной хэш-функции и входных данных должно быть трудно найти второй, другой, вход с одинаковым хеш-значением.
- Сопротивление столкновению: для заданного имеет функцию, должно быть трудно найти два разных входа с одинаковым хешем.
Эти критерии выбираются таким образом, чтобы затруднить поиск документа, соответствующего данному хешу, в противном случае можно было бы подделать документы, заменив оригинал тем, который соответствует хешу. (Даже если замена является бредом, простая замена оригинала может вызвать сбои.)
Номер 3 подразумевает номер 2.
Что касается MD5, в частности, было показано, что он имеет недостатки: как взломать MD5 и другие хеш-функции.
Столкновение хешей гораздо более вероятно, чем вы думаете. Взгляните на парадокс дня рождения, чтобы лучше понять, почему это так.
Но здесь вступают в игру радужные столы. В основном это просто большое количество значений, хэшированных отдельно, а затем результат сохраняется на диск. Тогда бит реверса "просто" для поиска в очень большой таблице.
Очевидно, что это возможно только для подмножества всех возможных входных значений, но если вы знаете границы входного значения, возможно, будет возможно вычислить его.
Китайский ученый нашел способ, который называется "столкновения с выбранным префиксом", чтобы создать конфликт между двумя разными строками.
Вот пример: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip
Исходный код: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5_source.zip
Лучший способ понять, что означают ответы, получившие наибольшее количество голосов, - это попытаться восстановить алгоритм MD5. Я помню, что несколько лет назад я пытался вернуть алгоритм MD5crypt не для того, чтобы восстановить исходное сообщение, потому что это явно невозможно, а просто для того, чтобы сгенерировать сообщение, которое выдает тот же хеш, что и исходный хеш. Это, по крайней мере теоретически, дало бы мне возможность войти в систему на устройстве Linux, которое хранило пароль user: в файле / etc / passwd, используя сгенерированное сообщение (пароль) вместо использования исходного. Поскольку оба сообщения будут иметь одинаковый результирующий хэш, система распознает мой пароль (сгенерированный из исходного хэша) как действительный. Это не сработало вообще. Через несколько недель, если я правильно помню, использование соли в первоначальном сообщении убило меня. Мне нужно было создать не только правильное начальное сообщение, но и соленое правильное начальное сообщение, чего я так и не смог сделать. Но знание, которое я получил от этого эксперимента, было приятно.
Как уже говорилось в большинстве, MD5 был разработан для потоков хеширования данных переменной длины, чтобы хэшироваться с порцией данных фиксированной длины, поэтому один хеш-код разделяется многими потоками входных данных.
Однако, если вам когда-либо нужно было узнать исходные данные из контрольной суммы, например, если у вас есть хеш-пароль и вам необходимо выяснить оригинальный пароль, часто быстрее просто Google (или любой поисковик, который вы предпочитаете) хеш-код для ответа, чем для грубой силы. Я успешно узнал несколько паролей, используя этот метод.
Теперь хэши MD5 дней или любые другие хэши по этому вопросу предварительно вычисляются для всех возможных строк и сохраняются для легкого доступа. Хотя теоретически MD5 не является обратимым, но используя такие базы данных, вы можете узнать, какой текст привел к определенному значению хеш-функции.
Например, попробуйте следующий хеш-код на http://gdataonline.com/seekhash.php чтобы узнать, какой текст я использовал для вычисления хеша
aea23489ce3aa9b6406ebb28e0cda430
f(x) = 1 необратим. Хеш-функции не являются необратимыми.
Это на самом деле требуется, чтобы они выполняли свою функцию определения, есть ли у кого-то нетленная копия хешированных данных. Это повышает восприимчивость к атакам грубой силы, которые в наши дни довольно мощные, особенно против MD5.
Здесь и в других местах есть путаница среди людей, у которых есть математические знания, но мало шифрующих знаний. Несколько шифров просто XOR данных с потоком ключей, и поэтому вы можете сказать, что зашифрованный текст соответствует всем открытым текстам этой длины, потому что вы могли бы использовать любой поток ключей.
Тем не менее, это игнорирует, что разумный открытый текст, полученный из семян password
намного, намного более вероятно чем другой произведенный семенем Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6o
до такой степени, что любой, утверждающий, что второе было возможностью, будет смеяться.
Точно так же, если вы пытаетесь выбрать между двумя потенциальными паролями password
а также Wsg5Nm^bkI4EgxUO
это не так сложно сделать, как некоторые математики заставили бы вас поверить.
По определению хеш-функция (криптографическая хеш-функция): не должна быть обратимой, не должна иметь коллизий (как можно меньше).
regd ваш вопрос: это односторонний хэш. input (независимо от длины) будет генерировать вывод фиксированного размера (он будет дополнен на основе алгоритма (512-битная граница для MD5)). Информация сжимается (теряется) и практически не может быть сгенерирована из обратных преобразований.
дополнительная информация о MD5: он уязвим для столкновений. недавно прочитал эту статью, http://www.win.tue.nl/hashclash/Nostradamus/
открывает исходный код для реализации крипто-хеша (MD5 и SHA) можно найти в коде Mozilla. (библиотека Freebl).
Мне нравятся все различные аргументы. Очевидно, что реальная ценность хэшированных значений заключается просто в предоставлении нечитаемых человеком заполнителей для таких строк, как пароли. У него нет особого преимущества для безопасности. Предполагая, что злоумышленник получил доступ к таблице с хэшированными паролями, он / она может:
- Хэш-пароль по своему выбору и поместите результаты в таблицу паролей, если он / она имеет права на запись / редактирование таблицы.
- Создайте хешированные значения общих паролей и проверьте наличие аналогичных хешированных значений в таблице паролей.
В этом случае слабые пароли не могут быть защищены одним лишь фактом их хеширования.