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

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

  1. Neuron

    Neuron New Member

    Публикаций:
    0
    Регистрация:
    17 сен 2006
    Сообщения:
    10
    http://www.codeproject.com/KB/security/HackingMd5.aspx
     
  2. flankerx

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    Neuron
    Это _совсем_ не в тему.
     
  3. Neuron

    Neuron New Member

    Публикаций:
    0
    Регистрация:
    17 сен 2006
    Сообщения:
    10
    Интересно, почему это?
     
  4. flankerx

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    Neuron
    Потому что читать нужно внимательнее постановку задачи :derisive:
     
  5. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Relf,
    а этот полином из Wiki примитивен? 64,4,3,1,0

    построил на его основе генератор случайных чисел, нужно чтобы период был оччень большим...
     
  6. RElf

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159
    persicum
    Да, это примитивный полином над GF(2).
    Его период соответственно равен 2^64 - 1 = 18446744073709551615.
     
  7. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Генератор работает по стандартной CRC-шной табличной схеме:
    x = (x shr 8) xor Table[x and 255]

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

    И еще, у Вас не в загашнике коэффициентов для 64-битного конгруэнтного генератора
    x = (a x + b) mod 2^64 ???
     
  8. RElf

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159
    persicum
    А почему бы тогда не воспользоваться Mersenne Twister с быстрой реализацией и периодом аж 2^19937 - 1 ?

    Насчет параметров конгруэнтного генератора - есть известная теорема, в точности устанавливающая при каких условиях его период максимален. С ее помощью можно легко подобрать нужные параметры самому.
     
  9. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Спасибки, почитал и скачал... Да простится мне мое мракобесие, но коренных отличий между "вихрем" мерсенна и обычным регистром с обратными связами я как-то не уловил, а что до 623 плоскостей и большого периода так это видимо только за счет здорового seed'a размером как раз в 623 машинных слова...
    А так, чем плох генератор на полиноме 64,4,3,1,0? Свой период и белый спектр он отрабатывает, уж точно не хуже конгруэнтного генератора такого же размера.

    А кста, по сабжу, можно ли у MD5 подогнать 64 первых бит иначе как полным перебором?
     
  10. RElf

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159
    persicum
    Ну во-первых, он не "обычный" регистр с обратными связями, а "переплетенный" (twisted) - если я правильно помню, там одновременно несколько последовательностей генерируется и они хитросплетаются.
    А во-вторых, хозяин-барин - нравится полином от CRC64 - используй на здоровье.

    А про MD5 тут уже все сказали.
     
  11. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    То бишь коллизии устраивать уже давно умеют,
    но подгонять даже частично еще не умеют, публикаций не было, так?
     
  12. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    А зачем козе баян? У моего простейшего генератора на полиноме CRC64 по тестам ЭНТ получается хи-квадрат даже лучше, чем у радиоактивного источника из их ридмишки (ближе к 50%) Аффигеть... Хотя есть и другие критерии, но меня интересует только ранговый - чтобы доля обратимых достаточно больших случайных матриц была 0.288...

    Entropy = 7.999996 bits per byte.
    Chi square distribution for 50000000 samples is 252.51, and randomly
    would exceed this value 53.23 percent of the times.

    Entropy = 1.000000 bits per bit.
    Chi square distribution for 400000000 samples is 0.59, and randomly
    would exceed this value 44.09 percent of the times.
     
  13. HN2008

    HN2008 New Member

    Публикаций:
    0
    Регистрация:
    1 апр 2008
    Сообщения:
    7
    Просьба пояснить про MD5

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

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

    Итак эти последовательности должны иметь следующую структуру.

    HЧ+ИЧ1+ИЧ2+X ,

    где HЧ - неизменяемая часть строки, никаким предварительными условиями(за исключением длины) она ограничиваться не может
    ИЧ1 - эту часть строки можем изменять как хотим, а можем не изменят, но она должна состоять из читаемых символов и на неё будет накладываться ещё одно условие, которое будет дальше
    ИЧ2 - эту часть строки нам надо изменять, то есть во всех наших последовательностях эта часть должна быть разная, и на неё следующее ограничение - эта часть должна быть одинакова по размеру во всех последовательностях и в ней могут быть представлены только 10 символов.
    Х - эта строка должна быть хэшем от НЧ+ИЧ1


    Насколько сложна такая задача?
     
  14. valterg

    valterg Active Member

    Публикаций:
    0
    Регистрация:
    19 авг 2004
    Сообщения:
    2.105
    HN2008
    Также нерешабельна, как все остальные подгонки MD5.
    Без Х еще можно было как-то извратиться, наверное, но вычислений будет много...
     
  15. HN2008

    HN2008 New Member

    Публикаций:
    0
    Регистрация:
    1 апр 2008
    Сообщения:
    7
    так вот дело в том, что "остальные подгонки" как-бы уже решаемы
    например вот ссылка на архив с экзешником - http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip , который делает отдаленно, но похожую вещь.
    Берется файл, запускается экзешник, на выходе получаем 2 файла с началом в виде первоначального файла и с разными дописками, но с ! одинаковыми хэшами. Процесс занимает секунды :dntknw:

    Вот и хочется узнать, насколько озвученная выше мной задача сложнее того, что реализовано в этом экзешнике?
     
  16. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.152
    persicum
    хехехе, товарищ, ты случаем не хочешь сказать, что твой гсч надёжней изотопа:))?? усреднённые стат. характеристики ровным счётом ни о чём не говорят - важно отсутствие явной ф-ной зависимости между значениями гсч. вот если твой гсч делает это и не "разагревается" аля "столько не живут", то я дико буду просится к тебе в ученики:)))
     
  17. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.152
    HN2008
    что-то мне это до боли напоминает часть схемы подтверждения платежа в инет магазине:derisive:
     
  18. HN2008

    HN2008 New Member

    Публикаций:
    0
    Регистрация:
    1 апр 2008
    Сообщения:
    7
    Это полная схема (а не часть) одной онлайновой процедуры, связанной с деньгами.

    Если реализация задачи (генерация за минуту или несколько как можно большего числа последовательностей вида HЧ+ИЧ1+ИЧ2+Х с одинаковыми хэшами и с разным ИЧ2) стоит не миллионы у.е., а скажем порядка 100 тыс. у.е

    То это означает, что скорее всего это реализовано, и систематически (ежеминутно) производится кидок клиентов на деньги.
     
  19. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.152
    HN2008
    ну, спокойно, товарищ, даже если генерить альтернативу - это не делает акт взлома завершённым, потому что случайная строка каждый раз разная.
     
  20. HN2008

    HN2008 New Member

    Публикаций:
    0
    Регистрация:
    1 апр 2008
    Сообщения:
    7
    Там не взлом.
    Там путем подписи(хэша) всей строки HЧ+ИЧ1+ИЧ2+X, один гарантирует другому неизменность ИЧ2.
    Так вот, если потратив много денег, можно решить проблему как менять ИЧ2, но при этом хэш от всей строки будет не меняться, то этого достаточно для того, чтобы эти много денег окупить :)

    Я сразу не сказал, что это за схема - по причине того, что вот сейчас скажу - и сразу интерес у великих мира криптографии пропадет ввиду незначительности. А на самом деле задача интересная и довольнозначимая в узком (но не очень) кругу.

    Есть одно казино в онлайне. Оно убеждает клиентов в своей честности тем, что предоставляет до начала игры хэш строки, в которой присуствуют заранее сгенерированные результаты(числа) на рулетке.
    Строка эта имеет как раз вид вот такой - HЧ+ИЧ1+ИЧ2+X
    НЧ - здесь имя игрока и дата
    ИЧ1 - пароль (неизвестная до конца игры игроку часть строки) казино говорит что оно его не меняет, игрок наверняка это знать не может.
    ИЧ2 - собственно сама строка с результатами. Казино естественно тоже говорит, что оно эту загаданную строку не меняет в процессе игры и гарантия этому предоставленный до начала игры ХЭШ всей строки.
    Х2 - это хэш от НЧ+ИЧ1 ... Раньше этой дописки не было, но потом игроки начали требовать гарантий, что казино не добивается неизменности подписи всей строки посредством совместных манипуляций ИЧ1 и ИЧ2 (Ведь реально до конца игры игрок не знает ИЧ1 и ИЧ2). Поэтому в качестве дополнительной гарантии неизменности ИЧ1 казино в конец строки вставляет подпись НЧ+ИЧ1.
    Вот и вопрос. Насколько железные эти гарантии? Ведь по сути до конца игры игроку неизвестны три подстроки.
    ИЧ1, ИЧ2 (сами результаты) и Х, при этом ИЧ1 и X связаны между собой. Изначально у казино (если оно хочет обмануть игрока и заработать на этом больше) есть необходимость иметь возможность менять ИЧ2 как только оно хочет, но при этом надо тогда таким образом изменять ИЧ1, чтобы при этом соблюдалась неизменность хэша всей строки....

    Одно описание сложно, а реализовать (причем в ограниченный минутами промежуток) вообще не представляется возможным.... Но при этом можно задать такой вопрос. А ведь множество вариантов удвлетворяющих условию состоит не только из 1 варианта? Может есть алгоритм со использованием "специальнозаточенных" ИЧ1 , который позволяет эти множества вариантов очень быстро генерить????