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

Тема в разделе "WASM.CRYPTO", создана пользователем Goldy, 31 дек 2007.

  1. Goldy

    Goldy New Member

    Публикаций:
    0
    Регистрация:
    13 сен 2005
    Сообщения:
    36
    Адрес:
    Russia
    Добрый день!

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

    Stub New Member

    Публикаций:
    0
    Регистрация:
    11 май 2004
    Сообщения:
    311
    Адрес:
    Siberia
    так может будет проще пропатчить эти 8 байт?
     
  3. MSoft

    MSoft New Member

    Публикаций:
    0
    Регистрация:
    16 дек 2006
    Сообщения:
    2.854
    Можно, но проблема в том, что при изменении файла в 1 бите меняеются все байты хеша. По теории вероятности тебе придется перебрать примерно 0FFFFFFFFh байт. Удачи ;)

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

    Goldy New Member

    Публикаций:
    0
    Регистрация:
    13 сен 2005
    Сообщения:
    36
    Адрес:
    Russia
    Пропатчить к сожалению нельзя, так как проверка содержится в прошивке устройства.
     
  5. dag

    dag New Member

    Публикаций:
    0
    Регистрация:
    17 авг 2004
    Сообщения:
    446
    Так поменяй файл и пересчитай хэшЪ... Или алгоритма хэшового нет и взять негде ?
     
  6. Goldy

    Goldy New Member

    Публикаций:
    0
    Регистрация:
    13 сен 2005
    Сообщения:
    36
    Адрес:
    Russia
    Используемый алгоритм MD5 зашит в прошивке, там же зашито и 8 первых байт хэша, с которыми происходит сравнение.
    Так что смысла твоего предложения я не понял.
     
  7. flankerx

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    Я думаю что это вполне возможно. Коллизии для MD5 сейчас ищутся достаточно быстро.

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

    Goldy New Member

    Публикаций:
    0
    Регистрация:
    13 сен 2005
    Сообщения:
    36
    Адрес:
    Russia
    В файле есть картинки примерно 50K которые можно поменять.
    Требуется информация по быстрому алгоритму реализация MD5,
    и порядку замены байтов в файле для быстрейшего поиска коллизий.

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

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    Требуется информация — гугл в помощь. Там все есть. Я сильно сомневаюсь что тут кто-то занимался чем-то подобным и готов об этом рассказать :)

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

    halyavin New Member

    Публикаций:
    0
    Регистрация:
    13 май 2005
    Сообщения:
    252
    Адрес:
    Russia
    При поиске коллизий подбираются оба файла сразу, а не по одному находится другой. Это задачи принципиально разные. Никаких алгоритмов поиска коллизий к конкретному файлу/хэшу кроме тупого перебора пока не придумано.
     
  11. dag

    dag New Member

    Публикаций:
    0
    Регистрация:
    17 авг 2004
    Сообщения:
    446
    а смысл хранить внешний файл если его вообще поменять нельзя ? чтото здесть не чисто =) может он хэшь не всего файла считает ? или у устройства есть механизм обновления хэша при обновлении файла производителем ?
     
  12. flankerx

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    halyavin
    Это не так. Существующие методы могут быть обобщены для построения коллизий при условии различных начальных состояний. Да, дифф. характеристику прийдется пересчитывать :)
     
  13. halyavin

    halyavin New Member

    Публикаций:
    0
    Регистрация:
    13 май 2005
    Сообщения:
    252
    Адрес:
    Russia
    Ссылки на статьи у вас есть? Было бы интересно почитать.
     
  14. flankerx

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    Ссылок нет, это моё предположение :)
    Я не вижу причин почему начальную дельту необходимо брать нулевой.
     
  15. Goldy

    Goldy New Member

    Публикаций:
    0
    Регистрация:
    13 сен 2005
    Сообщения:
    36
    Адрес:
    Russia
    Быстро ознакомившись с алгоритмом генерации хэша MD5, в мою нетрезвую голову
    закралась мысль по ускорению скорости перебора в случае, если заменяемые байты для подборв будут находятся в конце файла. Ведь тогда можно запомнить состояние всех регистров перед данным блоком и все последующие операции производить только с остатком. Прав ли я?
     
  16. halyavin

    halyavin New Member

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

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    halyavin
    Да, знаком. Нет, не является.
    Коллизии ищутся немного иначе и гораздо быстрее. Вот тут есть хорошие ссылки:
    http://cryptography.hyperlink.cz/MD5_collisions.html
     
  18. halyavin

    halyavin New Member

    Публикаций:
    0
    Регистрация:
    13 май 2005
    Сообщения:
    252
    Адрес:
    Russia
    Да, не является. Но его все равно принципиально нельзя применить к данной задаче. Алгоритм основан на процедуре нахождения двух блоков с некоторой фиксированной разницей хэшей. Это никак не помогает найти блок с заданным хэшем или заданной частью хэша.
     
  19. halyavin

    halyavin New Member

    Публикаций:
    0
    Регистрация:
    13 май 2005
    Сообщения:
    252
    Адрес:
    Russia
    Если же вы пытаетесь построить именно коллизию, то во-первых несовпадение хэшей перед последними 2 блоками накорню убивает алгоритм. А во-вторых, даже если бы не убивало - на исходное сообщение, к которому ищется коллизия, очень строгие условия. Вероятность их выполнения где-то 2^{-250}, как я понял из статьи.
     
  20. asmlamo

    asmlamo Well-Known Member

    Публикаций:
    0
    Регистрация:
    18 май 2004
    Сообщения:
    1.729
    ИМХО неподьемная задача.

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

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