Временная сложность встроенной грубой силы MD5sum

Question

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

Редактировать: Если это еще не было ясно.Я ищу ответ с сложностью времени и объяснением этого.

Answer 1

Это можно решить за постоянное время.

Файл, содержащий все возможные дайджесты MD5, содержит дайджест этого файла.

Answer 2

Для этого вы должны найти столкновение . Это можно сделать, используя префиксную атаку против md5 . Имейте в виду, что это возможно только потому, что MD5 очень сломан. Эта атака имеет временную сложность 2 ^ 24,1 , которая находится в пределах досягаемости современного рабочего стола.

Answer 3

Это также зависит от обстоятельств.Если задан двоичный файл, и в каком-то месте должен быть вставлен только md5, ответ может быть следующим: 0. Поскольку возможно (и я бы предположил, что, возможно, почти во всех случаях, подобных этому), нет md5, который вставил быдает тот же md5.

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

Answer 4

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

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

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

Answer 5

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

С другой стороны, если вы хотите проверить,ваш двоичный файл не поврежден и не изменен, вам будет лучше разделить ваш двоичный файл на 3 части: часть двоичного файла перед хешем, сам хэш и часть после хеша.Объедините первую и последнюю части, вычислите хэш md5 и внедрите его в двоичный файл.

Вот так (пример):

foo098f6bcd4621d373cade4e832627b4f6bar
foo | 098f6bcd4621d373cade4e832627b4f6 | bar
md5(foo+bar) = 3858f62230ac3c915f300c664312c63f
foo3858f62230ac3c915f300c664312c63fbar

Answer 6

Почти то же самое, что и грубая сила: вычисление суммы md5 тривиально, но создание файла, соответствующего известной сумме md5, сложно.

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