Почему хэш-значения MD5 необратимы?
https://stackoverflow.com/questions/330207
-
11-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Одна из концепций, которая меня всегда интересовала, — это использование криптографических хэш-функций и значений.Я понимаю, что эти функции могут генерировать уникальное хеш-значение, которое практически невозможно обратить вспять, но вот что меня всегда интересовало:
Если на моем сервере, то в PHP я создаю:
md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"
Когда вы запускаете ту же строку через функцию MD5, вы получаете тот же результат при установке PHP.Процесс используется для создания некоторой ценности из некоторого начального значения.
Не означает ли это, что есть какой-то способ деконструировать происходящее и перевернуть значение хеш-функции?
Что такого особенного в этих функциях, что делает невозможным отслеживание результирующих строк?
Решение
Материал ввода может иметь бесконечную длину, длина выходного файла всегда составляет 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("stackoverflow.com");
Это выведет:
737461636b6f766572666c6f772e636f6d
Эта функция также обладает тем же свойством неинъективности, что подчеркнуто ответом Коди для MD5:Мы можем передавать строки любого размера (при условии, что они помещаются в наш компьютер), и он выведет только 32 шестнадцатеричные цифры.Конечно, оно не может быть инъективным.
Но в этом случае найти строку, которая соответствует тому же хэшу, тривиально (просто примените hex2bin на вашем хеше, и он у вас есть).Если ваша исходная строка имела длину 16 (как в нашем примере), вы даже получите эту исходную строку.Ничего подобного для MD5 быть не должно, даже если вы знаете, что длина ввода была довольно короткой (кроме перебора всех возможных входных данных, пока мы не найдем тот, который соответствует, напримергрубая атака).
Важными предположениями для криптографической хэш-функции являются:
- трудно найти строку, производящую заданный хеш (сопротивление прообразу)
- трудно найти другую строку, дающую тот же хеш, что и заданная строка (сопротивление второго прообраза)
- трудно найти пару строк с одинаковым хешем (устойчивость к коллизиям)
Очевидно, мой simple_hash функция не удовлетворяет ни одному из этих условий.(На самом деле, если мы ограничим входное пространство «16-байтовыми строками», тогда моя функция станет инъективной и, следовательно, даже доказуемой устойчивостью ко второму прообразу и коллизиям.)
В настоящее время существуют коллизионные атаки против MD5 (например.можно создать пару строк, даже с заданным одинаковым префиксом, которые имеют один и тот же хеш, приложив немалую работу, но не невозможную большую работу), поэтому вам не следует использовать MD5 для чего-либо критического.Прообраз-атаки пока нет, но атаки станут лучше.
Чтобы ответить на реальный вопрос:
Что такое в этих функциях, которые делают полученные строки невозможными для повторного просвещения?
Что эффективно делает MD5 (и другие хэш-функции, основанные на конструкции Меркла-Дамгарда), так это применяет алгоритм шифрования с сообщением в качестве ключа и некоторым фиксированным значением в качестве «простого текста», используя полученный зашифрованный текст в качестве хеша.(Перед этим входные данные дополняются и разбиваются на блоки, каждый из этих блоков используется для шифрования выходных данных предыдущего блока и подвергается операции XOR с его входными данными для предотвращения обратных вычислений.)
Современные алгоритмы шифрования (в том числе используемые в хэш-функциях) созданы таким образом, чтобы затруднить восстановление ключа, даже если имеется как открытый текст, так и зашифрованный текст (или даже когда злоумышленник выбирает один из них).Обычно они делают это, выполняя множество операций по перетасовке битов таким образом, что каждый выходной бит определяется каждым ключевым битом (несколько раз), а также каждым входным битом.Таким образом, вы сможете легко проследить, что происходит внутри, только если вы знаете полный ключ, а также ввод или вывод.
Для хэш-функций, подобных 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 был разработан для хэширования потоков данных переменной длины с фрагментом данных фиксированной длины, поэтому один хэш используется многими входными потоками данных.
Однако, если вам когда-либо нужно было узнать исходные данные из контрольной суммы, например, если у вас есть хеш-пароль и вам нужно узнать оригинальный пароль, часто быстрее всего просто Google (или любой другой поисковик, который вы предпочитаете) ) хеш за ответ, чем грубой силой его. Я успешно обнаружил несколько паролей, используя этот метод.
Лучший способ понять, что означают ответы, получившие наибольшее количество голосов, - это попытаться изменить алгоритм MD5. Я помню, что несколько лет назад я пытался отменить алгоритм MD5crypt , не для того, чтобы восстановить исходное сообщение, потому что это явно невозможно, а просто для того, чтобы сгенерировать сообщение, которое выдает тот же хеш, что и исходный хеш. Это, по крайней мере теоретически, дало бы мне возможность войти в систему на устройстве Linux, которое хранило пароль user: в файле / etc / passwd, используя сгенерированное сообщение (пароль) вместо использования исходного. Поскольку оба сообщения будут иметь одинаковый результирующий хэш, система распознает мой пароль (сгенерированный из исходного хэша) как действительный. Это не сработало вообще. Через несколько недель, если я правильно помню, использование соли в первоначальном сообщении убило меня. Мне нужно было создать не только правильное начальное сообщение, но и соленое правильное начальное сообщение, чего я никогда не мог сделать. Но знания, которые я получил от этого эксперимента, были хорошими.
по определению хеш-функция (криптографическая хеш-функция): не должна быть обратимой, не должна иметь коллизий (как можно меньше).
Отвечайте на ваш вопрос: это односторонний хэш. input (независимо от длины) сгенерирует вывод фиксированного размера (он будет дополнен на основе алгоритма (512-битная граница для MD5)). Информация сжимается (теряется) и практически не может быть сгенерирована из обратных преобразований.
дополнительная информация о MD5: она уязвима для столкновений. недавно прочитал эту статью, http://www.win.tue.nl/hashclash/Nostradamus/
открывает исходный код для реализации криптохеша (MD5 и SHA), который можно найти в коде Mozilla. (библиотека freebl).
Теперь дни хэшей MD5 или любые другие хэши в этом отношении предварительно вычисляются для всех возможных строк и сохраняются для легкого доступа. Хотя теоретически MD5 не является обратимым, но используя такие базы данных, вы можете узнать, какой текст привел к определенному значению хеш-функции.
Например, попробуйте следующий хэш-код на http://gdataonline.com/seekhash.php чтобы узнать, какой текст я использовал для вычисления хеша
aea23489ce3aa9b6406ebb28e0cda430
f (x) = 1 необратим. Хеш-функции не являются необратимыми.
На самом деле это требуется , чтобы они выполняли свою функцию определения, есть ли у кого-то нетленная копия хешированных данных. Это создает уязвимость к атакам грубой силы, которые в наши дни довольно сильны, особенно против MD5.
Здесь и в других местах существует путаница среди людей, которые имеют математические знания, но мало знаний о шифровании. Несколько шифров просто XOR данных с потоком ключей, и поэтому вы можете сказать, что зашифрованный текст соответствует всем открытым текстам этой длины, потому что вы могли бы использовать любой поток ключей.
Однако это игнорирует то, что разумный открытый текст, созданный из начального пароля , гораздо, гораздо более вероятен, чем другой, созданный из начального Wsg5Nm ^ bkI4EgxUOhpAjTmTjO0F! VkWvysS6EEMsIJiTZcvK @ WI $ IH $ TY! % & amp; Ue & nk55ak% BX% 9! NnG% 32ftud% YkBO $ U6o в той степени, в которой любой, кто утверждает, что второе было возможным, будет смеяться.
Таким же образом, если вы пытаетесь выбрать между двумя потенциальными паролями password и Wsg5Nm ^ bkI4EgxUO , это не так сложно сделать, как это делают некоторые математики. ты веришь?
Мне нравятся всевозможные аргументы.Очевидно, что реальная ценность хешированных значений заключается в том, чтобы просто предоставить нечитаемые для человека заполнители для строк, таких как пароли.Он не имеет конкретных преимуществ повышенной безопасности.Предполагая, что злоумышленник получил доступ к таблице с хешированными паролями, он/она может:
- Хешируйте пароль по своему выбору и поместите результаты в таблицу паролей, если у него есть права на запись/редактирование таблицы.
- Сгенерируйте хеш-значения общих паролей и проверьте наличие подобных хэш-значений в таблице паролей.
В этом случае слабые пароли не могут быть защищены одним лишь фактом их хеширования.
