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

http://www.codeproject.com/KB/security/HackingMd5.aspx

 

Neuron
Это _совсем_ не в тему.

 

Интересно, почему это?

 

Neuron
Потому что читать нужно внимательнее постановку задачи

 

Relf,
а этот полином из Wiki примитивен? 64,4,3,1,0

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

 

persicum

Да, это примитивный полином над GF(2).
Его период соответственно равен 2^64 - 1 = 18446744073709551615.

 

Генератор работает по стандартной CRC-шной табличной схеме:
x = (x shr 8) xor Table[x and 255]

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

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

 

persicum
А почему бы тогда не воспользоваться Mersenne Twister с быстрой реализацией и периодом аж 2^19937 - 1 ?

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

 

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

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

 

persicum
Ну во-первых, он не "обычный" регистр с обратными связями, а "переплетенный" (twisted) - если я правильно помню, там одновременно несколько последовательностей генерируется и они хитросплетаются.
А во-вторых, хозяин-барин - нравится полином от CRC64 - используй на здоровье.

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

 

То бишь коллизии устраивать уже давно умеют,
но подгонять даже частично еще не умеют, публикаций не было, так?

 

А зачем козе баян? У моего простейшего генератора на полиноме 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.

 

Просьба пояснить про MD5

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

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

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

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

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


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

 

HN2008

Также нерешабельна, как все остальные подгонки MD5.
Без Х еще можно было как-то извратиться, наверное, но вычислений будет много...

 

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

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

 

persicum

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

 

HN2008

что-то мне это до боли напоминает часть схемы подтверждения платежа в инет магазине

 

Это полная схема (а не часть) одной онлайновой процедуры, связанной с деньгами.

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

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

 

HN2008
ну, спокойно, товарищ, даже если генерить альтернативу - это не делает акт взлома завершённым, потому что случайная строка каждый раз разная.

 

Там не взлом.
Там путем подписи(хэша) всей строки 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 , который позволяет эти множества вариантов очень быстро генерить????