Возможно ли изменить файл чтобы совпадали первые 8 байт MD5 хэша?

Добрый день!

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

 

так может будет проще пропатчить эти 8 байт?

 

Можно, но проблема в том, что при изменении файла в 1 бите меняеются все байты хеша. По теории вероятности тебе придется перебрать примерно 0FFFFFFFFh байт. Удачи

П.С.: как встретишь новый год... )

 

Пропатчить к сожалению нельзя, так как проверка содержится в прошивке устройства.

 

Так поменяй файл и пересчитай хэшЪ... Или алгоритма хэшового нет и взять негде ?

 

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

 

Я думаю что это вполне возможно. Коллизии для MD5 сейчас ищутся достаточно быстро.

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

 

В файле есть картинки примерно 50K которые можно поменять.
Требуется информация по быстрому алгоритму реализация MD5,
и порядку замены байтов в файле для быстрейшего поиска коллизий.

P.S. На крайний случай попробую тупым перебором.

 

Требуется информация — гугл в помощь. Там все есть. Я сильно сомневаюсь что тут кто-то занимался чем-то подобным и готов об этом рассказать

Тупой перебор можень не пробовать, 2^64 — это много.

 

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

 

а смысл хранить внешний файл если его вообще поменять нельзя ? чтото здесть не чисто =) может он хэшь не всего файла считает ? или у устройства есть механизм обновления хэша при обновлении файла производителем ?

 

halyavin
Это не так. Существующие методы могут быть обобщены для построения коллизий при условии различных начальных состояний. Да, дифф. характеристику прийдется пересчитывать

 

Ссылки на статьи у вас есть? Было бы интересно почитать.

 

Ссылок нет, это моё предположение
Я не вижу причин почему начальную дельту необходимо брать нулевой.

 

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

 

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

 

halyavin
Да, знаком. Нет, не является.
Коллизии ищутся немного иначе и гораздо быстрее. Вот тут есть хорошие ссылки:
http://cryptography.hyperlink.cz/MD5_collisions.html

 

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

 

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

 

ИМХО неподьемная задача.

Только вычисление хеша MD5 для блока длинной несколько килобайт займет немало (тысячи) тиков процессора.

Так что подобный перебор будет ну очень долгим ...