Как может быть невозможно “дешифровать” хеш MD5? [дубликат]

Я просто не могу понять, как вы конвертируете что-то в одну вещь, используя какой-то алгоритм, и нет никакого способа конвертировать это обратно, используя алгоритм в обратном порядке.

Вы можете превратить корову в гамбургер, но вы не можете превратить гамбургер в корову.

Преобразование уменьшает существующие данные, уничтожая их, и эти данные невозможно восстановить.

Вот простой ответ ...

Существует конечное количество хеш-значений и бесконечное количество хешируемых значений открытого текста.

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

Отвечая на вторую часть вашего вопроса (ответ на первую часть был более чем адекватно дан другими выше): MD5 считается слабым из-за доказательства атак на шифр (т. е. изменения, которые могут быть сделаны в открытом тексте, но не приводят к изменениям в сумме MD5).Другие методы хеширования могут быть не так легко восприимчивы к по существу произвольным коллизиям хешей (по крайней мере, пока не было показано, что такие произвольные коллизии возможны с набором хэшей SHA-2 и т. Д.), И, следовательно, злоумышленник является с меньшей вероятностью сможет реплицировать хеш-хеш с использованием техники, отличной от MD5 (теоретически, конечно, атаки хеш-коллизии возможны против любой хеш-функции; если бы это не было, она не была бы успешной в качестве хеш-функции; вопрос в том, насколько легко злоумышленник может преуспеть в «подделке» «правильного» открытого текста, то есть текста, хэширующего с тем же значением хеш-функции).

Между прочим, сумма MD5 открытого текста не обязательно безопасна, потому что она содержит «меньше» данных или «с потерями», но потому, что из произвольного открытого текста она вычисляет значение суммы в фиксированном диапазоне (для открытых текстов < 128 битов, сумма MD5 на самом деле содержит больше информации, чем открытый текст ...), и, следовательно, некоторое количество (теоретически бесконечное) открытого текста может быть выровнено по одному и тому же хешу MD5.

Хм, не хочу показаться грубым, но мне кажется, что все ответы на тему «меньше информации выходит, чем входит» потерять суть.

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

Возьмем упрощенный пример: предположим, что наш алгоритм хеширования «берет последние две цифры». Итак, если мой пароль - «12345678», хэш-код - «78». Есть ли способ вернуться с «78» на «12345678»? Нет. Но если я взламываю пароли, мне все равно, знаю ли я, какой у вас был исходный пароль. Я просто хочу, чтобы пароль позволил мне войти. Так что, если бы я знал, что это алгоритм, я бы сказал отлично, я бы использовал пароль «99978». Он хеширует до «78», поэтому алгоритм проверки пароля его передаст, и я в деле.

Очевидно, MD5 гораздо труднее отменить, даже в этом смысле «все, что будет хешировать до правильного значения», тогда упрощенный алгоритм типа «взять две последние цифры». Но разве это невозможно? Меня это тоже озадачивает. Так что конечно, информация отбрасывается по ходу дела.Но не мог ли я вернуться к «любому» значению, заполнив любое случайное значение в любой точке, где информация отбрасывается? Я не рассматривал реальный алгоритм MD5. Я полагаю, что это непросто изменить, например, поменять все плюсы на минусы или что-то в этом роде, иначе кто-то сделал бы это давным-давно. Учитывая тот факт, что миллионы хакеров пытались взломать это, даже если это теоретически возможно, это должно быть невероятно сложно.

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

Рассмотрим следующую функцию: f (x) = x x. Теперь, если вы знаете, что f (x) = 25, что такое x? Ну, ответ может быть 5 или ответ может быть -5. Вы не можете восстановить входные данные для f, потому что существует некоторое значение в диапазоне f, такое, что более одного элемента домена f сопоставляется с этим значением в f. Следовательно, функция f необратима. Та же концепция применима к MD5; есть несколько входов для алгоритма MD5, которые, несмотря на разные входные данные, в результате будут давать одно и то же хеш-значение. Другими словами, алгоритм MD5, например f (x) = x x, не является взаимно однозначной и, следовательно, не является обратимой функцией.

Однако это не означает, что вы не можете восстановить ввод в MD5. Это просто означает, что вы не можете восстановить входные данные и MD5 со 100% уверенностью. Чтобы сделать это более конкретным, давайте снова посмотрим на функцию f (x) = x * x. А что, если бы я сказал вам, что для любого заданного значения f вероятность того, что он будет положительным, составляет 99%? В этом случае вы можете очень хорошо предположить, что хэш 25 получен из значения 5, а не -5. Именно так люди могут взламывать хэш-функции (включая MD5, который, как оказалось, не очень хорошая криптографическая хеш-функция). Что касается паролей, есть определенные пароли, которые используются гораздо чаще, чем другие пароли. Все, что вам нужно сделать, это взять MD5 этого пароля и сравнить его с некоторым хешем, и если они совпадают, то вполне разумно предположить, что он исходит из этого пароля.

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

Кроме того, поскольку несколько строк могут создать один и тот же хэш MD5, поскольку в нем меньше данных, чем во входной строке, как будет работать любая другая система хеширования {{ 1}} лучше?

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

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

Для MD5 размер хэша составляет 128 бит. Перефразируя Дугласа Адамса, 128-битное пространство велико. Действительно большой. Вы просто не поверите, насколько он невероятно велик. Количество возможных хешей составляет 2 ¹²⁸ или 3,40282367 × 10 ³⁸ . Это 34 с 37 нулями! Если бы вы могли сосчитать до триллиона за одну секунду, вам все равно потребовалось бы 10 миллиардов тысячелетий, чтобы пересчитать все 128-битные числа.

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

Вот параллель:

Сложите возраст всех членов вашей семьи. Сохраняйте только две последние цифры.

А теперь назовите мне возраст каждого на основе этого числа.

Подумайте об этом:

У меня есть числовая строка, скажем, «12345678».

У меня есть алгоритм хеширования, он просто возвращает сумму всех отдельных чисел, назовем его f ()

, поэтому f ("12345678") = 1 + 2+ .. + 8 = 36.

Тогда вопрос:

известно, что f (x) = 36, возможно ли получить исходное значение x?

Мы не можем, потому что алгоритм f () вызывает потерю информации.

MD5 - это алгоритм хеширования, подобный f (), но гораздо более сложный.

Кроме того, поскольку несколько строк могут создавать один и тот же хеш MD5, поскольку в нем меньше данных, чем во входной строке, как любая другая система хеширования может быть лучше? ?

Известна атака на MD5, которая позволяет злоумышленнику создать несколько документов с разным содержимым, но с одинаковым хешем MD5. Эта атака возможна с вычислительной точки зрения и в качестве демонстрации использовалась для «предсказания» результатов президентских выборов. (Злоумышленник опубликовал хэш перед выборами, а затем показал документ с этим хешем, в котором указано имя победителя.Но на самом деле у злоумышленника был документ для каждого кандидата, все с одним и тем же хешем.)

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

Еще худшая система допускала бы атаку, при которой, получив доступ к любому хешу, вы могли бы создать документ с этим хешем. Известная система CRC, которая до сих пор используется во многих аппаратных системах (например, Ethernet), уязвима для этой атаки. Как и MD5, это хэш-функция, в которой вывод не восстанавливается из ввода, но с учетом любого вывода легко создать документ с заданной подписью CRC-32 или CRC-64. Хуже того, вы можете поместить в такой документ любой текст, который вам нравится, а затем получить нужную CRC, просто добавив в конце мусор.

Это не совпадение, что CRC-32 может быть вычислен очень быстро, MD5 занимает значительно больше времени, а SHA-1 занимает несколько больше времени. И модели затрат, и модели доверия сложны.

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

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

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

Если вы все еще не уверены, попробуйте самостоятельно отменить шаги MD5 или любой другой криптографической хеш-функции; -)