Можно ли с достаточной информацией перевернуть хэш?

Question

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

К примеру, у меня есть файл, и я запустить его через md5(), и получил 6513F99D206D8714EA9EAA4A1EEA8538, затем добавить немного предсказуемый мусора в нижней части файла и запустить его снова, чтобы получить CBB04474C52FF68F6B2AC38A9A8356A5.

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

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

Answer 1

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

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

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

Answer 2

В настоящее время принятый ответ не совсем прав. Реальный ответ: Это зависит от модели..

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

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

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