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

halyavin
Не убивает. Идея в том что можно искать коллизии для разных начальных IV.
Вот и в гугле нашлось на эту тему: http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/

 

Убивает, потому что начальные IV должны совпадать у 2 сообщений, (но могут не совпадать со стартовыми) . А у нас они будут разные.

 

Почитайте http://www.win.tue.nl/hashclash/SoftIntCodeSign/

Если коротко: ребята взяли два .exe (с разными хешами), после чего "прицепили" к ним специально подобранные данные таким образом, что хеши у этих двух файлов совпали.

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

 

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

 

Формально можно перепатчить или добавить 8 байт под заданные 8 байт хеша. Но практически это нереализуемая задача - такой полный перебор. Так что это невозможно. Поэтому программерам консоли было даже лень проверять все 16 байт хеша =)))

 

Файл на компе, а устройство подцеплено к компу? Может быть проще поискать приемлемый метод подсовывать устройству на проверку оригинальный файл?

 

Goldy

А что за устройство?

 

Электронная книжка для чтения.
Подрбности тут
http://www.wasm.ru/forum/viewtopic.php?id=24617&p=4
Никто не в курсе вроде на видеокартах последних поколений вычисление
хэша в десятки раз можно ускорить?

 

можно, nVidia 8xxx нужны карточки
http://www.passwords.ru/edpr.html

 

2^64 вычислений MD5, в принципе, задача вполне реализуемая (разумеется, не в одиночку) - RC5-64 посчитали еще в 2002 году. Если есть несколько тысяч машин и несколько лет времени - почему бы и нет. Но для электронных книжек, к тому же старых, это вряд ли окупится...

 

Немного не в тему, но интересно. На Вики есть несколько примеров полиномов, пригодных для CRC64. Я просто убежден, что нет другого способа выбора простого полинома для CRC64, кроме как прогнать его в регистре с обратными связями и проверить, что период равен 2^64-1. Скока на это уходит времени?

 

persicum

Во-первых, то, что вы называете "простым полиномом" на самом деле называется "примитивным полиномом".

Во-вторых, в CRC примитивность полиномов не требуется. Более того, иногда даже не требуют, чтобы они были неприводимыми, и даже совсем наоборот - требуют, чтобы они имели предписанные делители, в частности, x+1. Например, таким является полином из стандарта ECMA-182, упомянутый в википедии. См. http://relf.livejournal.com/2379.html

В-тертьих, предположение об отсутствии другого способа проверки полиномов на примитивность в корне неверно. Для этого есть эффективные алгоритмы - см. главу 38.5 (и в частности раздел 38.5.2) в книжке Algorithms for programmers.

 

Фигня все это, ведь их роль сродни простым числам

Составной полином низачто и никогда не даст все 2^n-1 комбинаций, в лучшем случай - произведение периодов сомножителей.

Простой полином - это еще полдела, это только предпосылка.
Для CRC нужны не всякие простые полиномы, а только избранные - простые полиномы максимального периода. А вот это и проверяется прогонкой по всем состояниям. Или тоже самое, что они делят 2^2^n+1, но не делят полиномы короче. Блин, если прогонять CRC64 со скоростью 4Гига в секунду, то потребуется 120 лет!

 

persicum,
Как вы думаете, зачем у математических терминов есть общепринятые значения? Рекомендую впредь осваивать терминологию прежде чем задавать вопросы.

Похоже, что я неправильно понял ваши "простые полиномы". Судя по вышеотквоченному, так вы называете неприводимые полиномы.

Небольшой ликбез:
неприводимый полином - полином, который нельзя представить в виде произведения двух других полиномов степени >=1;
примитивный полином - это неприводимый полином максимального периода.

А теперь идите и читайте о том, как эффективно проверять полиномы на примитивность - ссылку я дал выше. Проверять "прогонкой по всем состояниям" совсем необязательно.

 

persicum

Еще раз повторяю: для CRC этого вообще говоря не требуется. Если полином не даст все 2^n-1 комбинаций, ничего страшного не случится. Про выбор полиномов для CRC читайте A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS.

 

Например, полином из стандарт ECMA-182 не является даже неприводимым (а уж тем более, не может быть примитивным) - над GF(2) он факторизуется так:

x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 + x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 + x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9 + x^7 + x^4 + x + 1
= (x + 1)
* (x^15 + x + 1)
* (x^15 + x^10 + x^5 + x + 1)
* (x^15 + x^12 + x^3 + x + 1)
* (x^17 + x^14 + x^12 + x^11 + x^10 + x^9 + x^8 + x^5 + x^4 + x^3 + 1)

 

Кстати, в пресловутой книжке "Алгебраические и алгоритмические основы: Элементарное введение в эллиптическую криптографию" тестирование неприводимости и примитивности полиномов тоже описано (на русском):

 

Большое спасибо, Relf! Вы мне очень помогли, обязательно найду все и перечитаю.
Только вот замечу, что такая фигня как ECMA-182 мне и даром не нужна.
Я предпочитаю использовать несколько разных полиномов для CRC32, скрепленных в Энигму или в счетчик электроэнергии. Они естественно пробегают по всем состояниям, за исключения нулей.

 

Вообще говоря, тут логическое противоречие. Если найти нормальный примитивный полином на 64 разряда не так уж и сложно, то к чему такая туфта типа ЭКМА-182?
Разве полноценный неприводимый полином был бы хуже?

 

persicum

А вы попробуйте для начала внятно объяснить, чем именно неприводимый (или даже примитивный) полином в CRC лучше не неприводимый? Боюсь, что обосновать это будет не так-то просто.

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

Например, наличие у полинома множителя (x+1) (что для полиномов над GF(2) равносильно наличию у полинома четного числа ненулевых коэффициентов) желательно в случае, когда хочется гарантированно распознавать однобитовые ошибки. Гарантированно здесь означает, что изменение одного бита обязательно приведет к изменению значения CRC, и поэтому будет распознано. В частности, здесь нельзя даже намеренно изменить один бит так, чтобы значение CRC не изменилось.
Более того, полином с множителем (x+1) автоматически оказывается способным к гарантированному распознаванию ошибок в любом нечетном количестве битов.
Поэтому, в частности, совсем не удивительно, что полином стандарта ECMA-182 делится на (x+1).

Примитивность же полинома в CRC на самом деле решает похожую проблему - а именно, распознавание двухбитовых ошибок. Но здесь ситуация сложнее. При достаточном объеме данных гарантированно распознать двухбитовую ошибку нельзя даже теоретически. Но отодвинуть этот самый "достаточный объем" на практически запредельную величину можно. Формально говоря, для любого полинома f (степени d), существует некоторая константа m такая, что если длина данных не превосходила m битов, то любая двухбитовая ошибка будет распознана CRC с полиномом f. Более того, это m есть ничто иное как период полинома f над полем GF(2). Поэтому, если задаться целью получить m как можно более большим, то нужно брать примитивный полином, для которого m = 2^d - 1, то есть максимально возможное значение среди всех полиномов степени d.

Далее, можно попробовать совместить гарантированное распознавание ошибок в нечетном числе битов и практически-гарантированное распознавание двухбитовых ошибок. В этом случае полином нужно взять вида f=(x+1)*g, где g является примитивным полиномом степени d-1. Он будет гарантированно распознавать ошибки в нечетном числе битов, а двухбитовые ошибки будет распознавать при условии, что длина данных не превосходит 2^(d-1)-1 битов.