Почему значения хэша MD5 необратимы?

Question 1

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

Если на моем сервере, в PHP я создаю:

md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"

Когда вы запускаете ту же строку через функцию MD5, вы получаете тот же результат при установке PHP. Процесс используется для получения некоторого значения из некоторого начального значения.

Разве это не означает, что есть способ деконструировать происходящее и изменить хеш-значение?

Что же такого особенного в этих функциях, что делает невозможным восстановление результирующих строк?

Question 2

Входной материал может быть бесконечной длины, а выходной всегда 128 бит. Это означает, что бесконечное количество входных строк будет генерировать один и тот же результат.

Если вы выберете случайное число и разделите его на 2, но запишете только остаток, вы получите либо 0, либо 1 - четное или нечетное соответственно. Можно ли взять этот 0 или 1 и получить исходное число?

Question 3

Если бы хэш-функции, такие как MD5, были обратимыми, это было бы переломным моментом в истории алгоритмов сжатия данных! Легко видеть, что если бы MD5 был обратимым, то произвольные фрагменты данных произвольного размера могли быть представлены всего лишь 128 битами без какой-либо потери информации. Таким образом, вы могли бы восстановить исходное сообщение из 128-битного числа независимо от размера исходного сообщения.

Question 4

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

Рассмотрим эту функцию (в нотации 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, и атаки по прообразу (с использованием одноблочной хешированной строки, чтобы упростить задачу) у вас есть только ввод и вывод вашей функции шифрования, но не ключ (это то, что вы ищете).

Question 5

Ответ Коди Броциуса правильный. Строго говоря, вы не можете «инвертировать» хеш-функцию, потому что многие строки отображаются в один и тот же хеш. Заметьте, однако, что либо поиск одной строки, которая отображается на данный хэш, либо обнаружение двух строк, которые отображаются на один и тот же хэш (т. Е. Коллизия ), будет большим прорывом для криптоаналитика. Большая сложность обеих этих проблем является причиной того, почему хорошие хеш-функции полезны в криптографии.

Question 6

MD5 не создает уникального хеш-значения; цель MD5 - быстро произвести значение, которое значительно изменится при незначительном изменении источника.

Например,

"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"

(Очевидно, что это не настоящее шифрование MD5)

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

Question 7

Хороший способ придумать хэш-алгоритм - подумать об изменении размера изображения в Photoshop ... скажем, у вас есть изображение размером 5000x5000 пикселей, а затем вы измените его размер до 32x32. То, что у вас есть, по-прежнему является представлением исходного изображения, но оно намного меньше и фактически «отбрасывает» определенные части данных изображения, чтобы оно соответствовало меньшему размеру. Так что, если бы вы изменили размер этого изображения 32x32 до 5000x5000, все, что вы получили бы, - это размытый беспорядок. Однако, поскольку изображение 32x32 не такое большое, теоретически можно было бы уменьшить размер другого изображения для получения точно таких же пикселей!

Это просто аналогия, но она помогает понять, что делает хеш.

Question 8

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

Question 9

Поскольку количество возможных входных файлов больше, чем количество 128-битных выходных файлов, невозможно однозначно назначить хеш MD5 каждому из возможных.

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

Иногда используются следующие критерии:

Сопротивление прообразу: для заданной хеш-функции и заданного хеш-кода должно быть сложно найти вход, который имеет заданный хеш-код для этой функции.
Сопротивление второго прообраза: для данной хэш-функции и ввода должно быть сложно найти второй, другой ввод с таким же хешем.
Устойчивость к коллизиям: для данной функции has должно быть сложно найти два разных входа с одним и тем же хешем.

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

Число 3 подразумевает число 2.

Что касается, в частности, MD5, было показано, что в нем есть недостатки: как сломать MD5 и другие хэш-функции .

Question 10

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

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

Question 11

Китайские ученые нашли способ, называемый «коллизией выбранных префиксов», для создания конфликта между двумя разными строками.

Вот пример: 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

Question 12

Лучший способ понять, что означают все ответы, получившие наибольшее количество голосов, - это на самом деле попытаться вернуть алгоритм MD5. Я помню, что несколько лет назад я пытался вернуть алгоритм MD5crypt , но не для восстановления исходного сообщения, потому что это явно невозможно, а просто для создания сообщения, которое будет выдавать тот же хэш, что и исходный хеш. Это, по крайней мере теоретически, предоставит мне способ войти в систему на устройстве Linux, на котором хранится пароль user: password в файле / etc / passwd, используя сгенерированное сообщение (пароль) вместо исходного. Поскольку оба сообщения будут иметь один и тот же результирующий хэш, система распознает мой пароль (сгенерированный из исходного хеша) как действительный. Это совсем не сработало. Через несколько недель, если я правильно помню, употребление солив исходном сообщении убил меня. Мне нужно было создать не только действительное начальное сообщение, но и солидное действительное начальное сообщение, чего я никогда не мог сделать. Но знания, которые я получил в результате этого эксперимента, были хорошими.

Question 13

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

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

Question 14

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

regd ваш вопрос: это односторонний хэш. input (независимо от длины) будет генерировать вывод фиксированного размера (он будет дополнен на основе алгоритма (512-битная граница для MD5)). Информация сжимается (теряется) и ее практически невозможно сгенерировать из обратных преобразований.

дополнительная информация о MD5: он уязвим для коллизий. недавно просмотрел эту статью http://www.win.tue.nl/hashclash/Nostradamus/

открытый исходный код для реализации крипто-хэша (MD5 и SHA) можно найти в коде Mozilla. (библиотека freebl).

Question 15

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

Например, попробуйте следующий хэш-код на http://gdataonline.com/seekhash.php, чтобы узнать, какой текст я использовал для вычисления хеша.

aea23489ce3aa9b6406ebb28e0cda430

Question 16

f (x) = 1 необратимо. Хеш-функции не являются необратимыми.

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

Есть также путаница здесь и повсюду среди людей, которые обладают математическими знаниями, но мало разбираются в шифровании. Некоторые шифры просто выполняют XOR данных с потоком ключей, поэтому можно сказать, что зашифрованный текст соответствует всем открытым текстам такой длины, потому что вы могли использовать любой поток ключей.

Однако при этом игнорируется тот факт, что разумный открытый текст, созданный из семени password, намного, намного более вероятен, чем другой, созданный семенем, Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6oдо такой степени, что любой, кто будет утверждать, что второй был возможен, был бы посмеян.

Точно так же, если вы пытаетесь выбрать между двумя потенциальными паролями passwordи Wsg5Nm^bkI4EgxUO, это не так сложно, как думают некоторые математики.

Question 17

Мне нравятся всевозможные аргументы. Очевидно, что реальная ценность хешированных значений состоит в том, чтобы просто предоставить нечитаемые человеком заполнители для строк, таких как пароли. У него нет особых преимуществ в плане безопасности. Если злоумышленник получил доступ к таблице с хешированными паролями, он / она может:

Зашешируйте пароль по своему выбору и поместите результаты в таблицу паролей, если он / она имеет права на запись / редактирование таблицы.
Сгенерируйте хешированные значения общих паролей и проверьте наличие подобных хешированных значений в таблице паролей.

В этом случае слабые пароли не могут быть защищены одним лишь фактом их хеширования.

Answer 1

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

Если на моем сервере, в PHP я создаю:

md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"

Когда вы запускаете ту же строку через функцию MD5, вы получаете тот же результат при установке PHP. Процесс используется для получения некоторого значения из некоторого начального значения.

Разве это не означает, что есть способ деконструировать происходящее и изменить хеш-значение?

Что же такого особенного в этих функциях, что делает невозможным восстановление результирующих строк?

Answer 2

54

Например, простой пример необратимого значения - по модулю. Например, 10% 3 = 1, но вы не можете поменять местами 1 на 10, так как это также может быть 4

Габ Ройер

Answer 3

57

Если бы вы могли реконструировать данные, у вас был бы самый эффективный алгоритм сжатия без потерь на свете :)

Дэн Дипло

Answer 4

205

Входной материал может быть бесконечной длины, а выходной всегда 128 бит. Это означает, что бесконечное количество входных строк будет генерировать один и тот же результат.

Если вы выберете случайное число и разделите его на 2, но запишете только остаток, вы получите либо 0, либо 1 - четное или нечетное соответственно. Можно ли взять этот 0 или 1 и получить исходное число?

Серафина Бросиус
источник

4

Другими словами, ни число -> остаток, ни строка -> md5 не являются «инъективными функциями».

Федерико А. Рампони,

Федерико, вы наверняка имеете в виду, что ни то, ни другое не являются биективными функциями? Оба они инъективны.

Михай Лимбэцан

10

moocha: Injective означает 1 к 1. MD5 определенно не 1 к 1, так как домен больше диапазона. Еще один момент, который стоит отметить, заключается в том, что с учетом контрольной суммы MD5 очень трудно найти даже одну строку, которая хеширует ее. Возможно, стоит добавить к ответу для пояснения.

биоцинк, 02

4

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

Serafina Brocious

4

Я предлагаю, чтобы ваш ответ не касался ключевого момента. Как упоминалось в biozinc, для безопасного хэша пароля важно то, что вы не можете найти никакого ввода, которое создает вывод, а не то, что вы не можете найти исходный ввод. Кстати, MD5 не обязательно так безопасен, как мог бы ( en.wikipedia.org/wiki/MD5#Collision_vulnerabilities ).

Майк Пелли

Answer 5

4

Другими словами, ни число -> остаток, ни строка -> md5 не являются «инъективными функциями».

Федерико А. Рампони,

Answer 6

Федерико, вы наверняка имеете в виду, что ни то, ни другое не являются биективными функциями? Оба они инъективны.

Михай Лимбэцан

Answer 7

10

moocha: Injective означает 1 к 1. MD5 определенно не 1 к 1, так как домен больше диапазона. Еще один момент, который стоит отметить, заключается в том, что с учетом контрольной суммы MD5 очень трудно найти даже одну строку, которая хеширует ее. Возможно, стоит добавить к ответу для пояснения.

биоцинк, 02

Answer 8

4

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

Serafina Brocious

Answer 9

4

Я предлагаю, чтобы ваш ответ не касался ключевого момента. Как упоминалось в biozinc, для безопасного хэша пароля важно то, что вы не можете найти никакого ввода, которое создает вывод, а не то, что вы не можете найти исходный ввод. Кстати, MD5 не обязательно так безопасен, как мог бы ( en.wikipedia.org/wiki/MD5#Collision_vulnerabilities ).

Майк Пелли

Answer 10

Если бы хэш-функции, такие как MD5, были обратимыми, это было бы переломным моментом в истории алгоритмов сжатия данных! Легко видеть, что если бы MD5 был обратимым, то произвольные фрагменты данных произвольного размера могли быть представлены всего лишь 128 битами без какой-либо потери информации. Таким образом, вы могли бы восстановить исходное сообщение из 128-битного числа независимо от размера исходного сообщения.

Answer 11

9

подумайте, как быстро было бы загружать дистрибутивы Linux, если бы вместо этого вы могли просто получить md5 :)

Колин Пикард

Answer 12

16

@ Колин Пикард: мы больше не будем загружать дистрибутивы Linux, мы будем их записывать . :)

tzot

Answer 13

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

Рассмотрим эту функцию (в нотации 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, и атаки по прообразу (с использованием одноблочной хешированной строки, чтобы упростить задачу) у вас есть только ввод и вывод вашей функции шифрования, но не ключ (это то, что вы ищете).

Answer 14

4

Да, я знаю, что это довольно поздний ответ, но принятый ответ нельзя допускать.

Паоло Эберманн,

Answer 15

Я думаю, что ваша критика имеет определенную ценность, но вы не смогли ответить на вопрос: «Что такого в этих функциях, что делает невозможным восстановление результирующих строк?» Ваш ответ фокусируется на качествах, которыми должен обладать криптографический хеш, но не имеет никакого объяснения того, как они реализованы в md5. Здесь вы можете указать точный алгоритм вычисления сумм MD5, чтобы показать, что он необратим, но другие ответы дают более простое объяснение, не вдаваясь в подробности.

Autodidact

Answer 16

(продолжение ...) 2. В этих объяснениях используется "математика", чтобы показать фундаментальную проблему, из-за которой такие операции теряют информацию и становятся необратимыми.

Autodidact

Answer 17

1

@SandeepDatta Я добавил несколько абзацев об этом.

Паоло Эберманн

Answer 18

2

Хотя другой ответ в этой ветке более технически правильный, этот ответ является наиболее полезным. Неинъективная функция f (x) = 1 необратима, но не интересна. Полезность хеширования заключается в сопротивлении прообразу, когда трудно найти какой-либо ввод, дающий определенный вывод.

Джастин Дж. Старк

Answer 19

Ответ Коди Броциуса правильный. Строго говоря, вы не можете «инвертировать» хеш-функцию, потому что многие строки отображаются в один и тот же хеш. Заметьте, однако, что либо поиск одной строки, которая отображается на данный хэш, либо обнаружение двух строк, которые отображаются на один и тот же хэш (т. Е. Коллизия ), будет большим прорывом для криптоаналитика. Большая сложность обеих этих проблем является причиной того, почему хорошие хеш-функции полезны в криптографии.

Answer 20

MD5 не создает уникального хеш-значения; цель MD5 - быстро произвести значение, которое значительно изменится при незначительном изменении источника.

Например,

"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"

(Очевидно, что это не настоящее шифрование MD5)

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

Answer 21

Хороший способ придумать хэш-алгоритм - подумать об изменении размера изображения в Photoshop ... скажем, у вас есть изображение размером 5000x5000 пикселей, а затем вы измените его размер до 32x32. То, что у вас есть, по-прежнему является представлением исходного изображения, но оно намного меньше и фактически «отбрасывает» определенные части данных изображения, чтобы оно соответствовало меньшему размеру. Так что, если бы вы изменили размер этого изображения 32x32 до 5000x5000, все, что вы получили бы, - это размытый беспорядок. Однако, поскольку изображение 32x32 не такое большое, теоретически можно было бы уменьшить размер другого изображения для получения точно таких же пикселей!

Это просто аналогия, но она помогает понять, что делает хеш.

Answer 22

3

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

Паоло Эберманн,

Answer 23

4

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

Гамич
источник

1

Существует 365 возможных значений дня рождения, от 2 ^ 8 до 2 ^ 9. 128-битный хеш имеет 2 ^ 128 возможных значений - в 2 ^ 120 раз больше. Да, столкновения более вероятны, чем вы можете себе представить, но они все же астрономически маловероятны.

Тим Китинг

Вам понадобится около 2 ^ 64 разных значений, чтобы иметь хороший шанс на хэш-коллизию. Все еще довольно много.

Паоло Эберманн,

Answer 24

1

Существует 365 возможных значений дня рождения, от 2 ^ 8 до 2 ^ 9. 128-битный хеш имеет 2 ^ 128 возможных значений - в 2 ^ 120 раз больше. Да, столкновения более вероятны, чем вы можете себе представить, но они все же астрономически маловероятны.

Тим Китинг

Answer 25

Вам понадобится около 2 ^ 64 разных значений, чтобы иметь хороший шанс на хэш-коллизию. Все еще довольно много.

Паоло Эберманн,

Answer 26

Поскольку количество возможных входных файлов больше, чем количество 128-битных выходных файлов, невозможно однозначно назначить хеш MD5 каждому из возможных.

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

Иногда используются следующие критерии:

Сопротивление прообразу: для заданной хеш-функции и заданного хеш-кода должно быть сложно найти вход, который имеет заданный хеш-код для этой функции.
Сопротивление второго прообраза: для данной хэш-функции и ввода должно быть сложно найти второй, другой ввод с таким же хешем.
Устойчивость к коллизиям: для данной функции has должно быть сложно найти два разных входа с одним и тем же хешем.

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

Число 3 подразумевает число 2.

Что касается, в частности, MD5, было показано, что в нем есть недостатки: как сломать MD5 и другие хэш-функции .

Answer 27

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

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

Answer 28

Ах да. Мне понравилось читать сообщение Джеффа о хэш-таблицах ( codinghorror.com/blog/archives/000949.html ), и эта ветка помогла в понимании концепции.

barfoon 01

Answer 29

Китайские ученые нашли способ, называемый «коллизией выбранных префиксов», для создания конфликта между двумя разными строками.

Вот пример: 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

Answer 30

Лучший способ понять, что означают все ответы, получившие наибольшее количество голосов, - это на самом деле попытаться вернуть алгоритм MD5. Я помню, что несколько лет назад я пытался вернуть алгоритм MD5crypt , но не для восстановления исходного сообщения, потому что это явно невозможно, а просто для создания сообщения, которое будет выдавать тот же хэш, что и исходный хеш. Это, по крайней мере теоретически, предоставит мне способ войти в систему на устройстве Linux, на котором хранится пароль user: password в файле / etc / passwd, используя сгенерированное сообщение (пароль) вместо исходного. Поскольку оба сообщения будут иметь один и тот же результирующий хэш, система распознает мой пароль (сгенерированный из исходного хеша) как действительный. Это совсем не сработало. Через несколько недель, если я правильно помню, употребление солив исходном сообщении убил меня. Мне нужно было создать не только действительное начальное сообщение, но и солидное действительное начальное сообщение, чего я никогда не мог сделать. Но знания, которые я получил в результате этого эксперимента, были хорошими.

Answer 31

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

Dave L.

Answer 32

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

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

Answer 33

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

regd ваш вопрос: это односторонний хэш. input (независимо от длины) будет генерировать вывод фиксированного размера (он будет дополнен на основе алгоритма (512-битная граница для MD5)). Информация сжимается (теряется) и ее практически невозможно сгенерировать из обратных преобразований.

дополнительная информация о MD5: он уязвим для коллизий. недавно просмотрел эту статью http://www.win.tue.nl/hashclash/Nostradamus/

открытый исходный код для реализации крипто-хэша (MD5 и SHA) можно найти в коде Mozilla. (библиотека freebl).

Answer 34

0

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

Например, попробуйте следующий хэш-код на http://gdataonline.com/seekhash.php, чтобы узнать, какой текст я использовал для вычисления хеша.

aea23489ce3aa9b6406ebb28e0cda430

Бабар
источник

Ах да, хеш банального семибуквенного слова. Теперь используйте его, чтобы выяснить текст песни из 11 слов с пробелами и знаками препинания: 9f2c08d4e6158bd4854b15be50c8daa8. Увидимся через несколько тысячелетий.

Тим Китинг,

6fba2bbab8a8366309bf67c7df12c622? Подсказка: это может быть OEM-версия конкретной версии Mac OS X!

Scherand

@ Тим Китинг, @scherand: Просто указываю на слабость алгоритмов хеширования, потому что хеш строки всегда один и тот же, нам не обязательно взламывать алгоритм, чтобы определить фактическую строку.

Бабар

2

Но ты сказал не это. Вы сказали, что хэши «предварительно вычисляются для всех возможных строк и сохраняются для легкого доступа», что явно неверно (набор «всех возможных строк» бесконечен ... и даже набор «всех правдоподобных строк» действительно очень велик ). ИМХО, это искажает представление о том, насколько легко выполнить словарную атаку против разумной ключевой фразы.

Тим Китинг,

Answer 35

Ах да, хеш банального семибуквенного слова. Теперь используйте его, чтобы выяснить текст песни из 11 слов с пробелами и знаками препинания: 9f2c08d4e6158bd4854b15be50c8daa8. Увидимся через несколько тысячелетий.

Тим Китинг,

Answer 36

6fba2bbab8a8366309bf67c7df12c622? Подсказка: это может быть OEM-версия конкретной версии Mac OS X!

Scherand

Answer 37

@ Тим Китинг, @scherand: Просто указываю на слабость алгоритмов хеширования, потому что хеш строки всегда один и тот же, нам не обязательно взламывать алгоритм, чтобы определить фактическую строку.

Бабар

Answer 38

2

Но ты сказал не это. Вы сказали, что хэши «предварительно вычисляются для всех возможных строк и сохраняются для легкого доступа», что явно неверно (набор «всех возможных строк» бесконечен ... и даже набор «всех правдоподобных строк» действительно очень велик ). ИМХО, это искажает представление о том, насколько легко выполнить словарную атаку против разумной ключевой фразы.

Тим Китинг,

Answer 39

f (x) = 1 необратимо. Хеш-функции не являются необратимыми.

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

Есть также путаница здесь и повсюду среди людей, которые обладают математическими знаниями, но мало разбираются в шифровании. Некоторые шифры просто выполняют XOR данных с потоком ключей, поэтому можно сказать, что зашифрованный текст соответствует всем открытым текстам такой длины, потому что вы могли использовать любой поток ключей.

Однако при этом игнорируется тот факт, что разумный открытый текст, созданный из семени password, намного, намного более вероятен, чем другой, созданный семенем, Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6oдо такой степени, что любой, кто будет утверждать, что второй был возможен, был бы посмеян.

Точно так же, если вы пытаетесь выбрать между двумя потенциальными паролями passwordи Wsg5Nm^bkI4EgxUO, это не так сложно, как думают некоторые математики.

Answer 40

Где взять большинство шифров, просто XOR данных с знанием ключевого потока ? Это верно для потоковых шифров, но есть и блочные шифры, которые так не работают.

Palo Ebermann

Answer 41

Мне нравятся всевозможные аргументы. Очевидно, что реальная ценность хешированных значений состоит в том, чтобы просто предоставить нечитаемые человеком заполнители для строк, таких как пароли. У него нет особых преимуществ в плане безопасности. Если злоумышленник получил доступ к таблице с хешированными паролями, он / она может:

Зашешируйте пароль по своему выбору и поместите результаты в таблицу паролей, если он / она имеет права на запись / редактирование таблицы.
Сгенерируйте хешированные значения общих паролей и проверьте наличие подобных хешированных значений в таблице паролей.

В этом случае слабые пароли не могут быть защищены одним лишь фактом их хеширования.

Answer 42

Настоящая ценность «хешированных значений» не в том, чтобы предоставлять заполнители, нечитаемые человеком. Если 'password1' хешируется в 'newval', не скрывает ли это значение аналогичным образом, хотя хеш читается и имеет смысл? Более того, пароли - ПЛОХОЙ пример, потому что их НИКОГДА не следует хешировать. Если предположить, что у злоумышленника есть доступ для записи в указанную базу данных, это определенно возможно. Однако кажется, что вы просто отказываетесь от правильного использования таких хеш-функций, один пример приведен во многих ответах выше - целостность сообщения. Собственно, это причина, по которой я сегодня нахожусь в этой теме.

Шейн

Почему значения хэша MD5 необратимы?

Ответы: