Chosen prefix collision on md5 + brute by round/step

Сейчас на форуме: johnniewalker, Magister Yoda, Kybyx, vsv1, r0lka (+5 невидимых)

Посл.ответ	Сообщение
DenCoder Ранг: 324.3 (мудрец), 221thx Активность: 0.48↘0.37 Статус: Участник	Создано: 06 октября 2010 19:57 · Поправил: DenCoder · Личное сообщение · #1 Собственно, поднимаю тему http://www.exelab.ru/f/action=vthread&forum=2&topic=15795&page=0#8 ввиду того, что многие насчет сего чуда ошибаются! (Среди них ntldr, Crawler... Archer ближе всех к теме....) Криптоанализ md5 показывает, во-первых, что его невозможно решить как стандартное алгебраическое уравнение, во-вторых, не все так трудно - если б была добавлена в каждый шаг еще одна переменная, тогда б md5 был неуязвим... и то правда лишь до появления 256-ядерных процессоров, наверное... Жертвуя всем временем, не получая ничего за это, в перерывах между заработками, обнаружил брешь в md5. Алгоритм поиска коллизий md5, представленный авторами статьи "Chosen prefix collision on md5", я до сих пор не понял до конца в виду языковой разности и терминологии криптографов, но могу с уверенностью сказать, что мой алгоритм имеет общее с их + свои наработки. ntldr писал: "Это даже теоретически невозможно, если sizeof(String) >= 16, если меньше - то тоже невозможно, но лишь практически." В чем-то ntldr прав, что невозможно... но только в том, что если длина строки < 16, и то все-таки можно подобрать за секунды, если не противоречит условиям алгоритма. Думайте P.S. Этот топик не провокационный и только для возрождения усопших надежд, своими наработками делиться не буду - твердо обдуманная позиция. ----- IZ.RU

PE_Kill Ранг: 793.4 (! !), 568thx Активность: 0.74↘0 Статус: Участник Шаман	Создано: 06 октября 2010 20:23 · Личное сообщение · #2 Не хватает только онлайн опроса. У DenCoder: Пися больше всех Большая пися Нормальная пися Пися чуть меньше средних размеров Затрудняюсь ответить ----- Yann Tiersen best and do not fuck
int Ранг: 101.0 (ветеран), 344thx Активность: 1.15↘0 Статус: Участник	Создано: 06 октября 2010 20:27 · Личное сообщение · #3 ->Затрудняюсь ответить
DenCoder Ранг: 324.3 (мудрец), 221thx Активность: 0.48↘0.37 Статус: Участник	Создано: 06 октября 2010 20:29 · Личное сообщение · #4 PE_Kill, ну чего-то подобного я и ожидал LoL.... Это не пиар, читать PS! ----- IZ.RU
Isaev Ранг: 756.3 (! !), 113thx Активность: 0.61↘0.05 Статус: Участник Student	Создано: 06 октября 2010 20:30 · Личное сообщение · #5 DenCoder ну так ты продолжай, очень инетересно ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh
DenCoder Ранг: 324.3 (мудрец), 221thx Активность: 0.48↘0.37 Статус: Участник	Создано: 06 октября 2010 20:32 · Личное сообщение · #6 Опрос такой более уместен: сколько нетрезвых прочитало этот топик и решило ответить Ждем еще HiEndSoft'а ----- IZ.RU
tihiy_grom Ранг: 441.3 (мудрец), 297thx Активность: 0.41↘0.04 Статус: Участник	Создано: 06 октября 2010 20:39 · Личное сообщение · #7 PE_Kill +1 DenCoder а в чём смысл топика? моя твоя не понимать
Isaev Ранг: 756.3 (! !), 113thx Активность: 0.61↘0.05 Статус: Участник Student	Создано: 06 октября 2010 20:44 · Личное сообщение · #8 DenCoder пишет: своими наработками делиться не буду - твердо обдуманная позиция. если это про паблик, то смысл топика вообще не ясен если будет развиваться небольшой группой, то определённо полезно ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh
DenCoder Ранг: 324.3 (мудрец), 221thx Активность: 0.48↘0.37 Статус: Участник	Создано: 06 октября 2010 20:49 · Личное сообщение · #9 Смысл топика изначально был в другом. Ну, видимо, MasterSoft был прав... через 2 часа закрою топик, кому надо поднимет ----- IZ.RU
ZLOvar Ранг: 40.4 (посетитель), 3thx Активность: 0.08↘0 Статус: Участник	Создано: 06 октября 2010 20:54 · Личное сообщение · #10 DenCoder Мдяя.. По моему кому-то делать нечего. Что ты хотел сказать? Что все что созданно человеком - ломаемо? Так ведь нельзя все ломать, нужно и на чем-то сидеть =)
DenCoder Ранг: 324.3 (мудрец), 221thx Активность: 0.48↘0.37 Статус: Участник	Создано: 06 октября 2010 21:02 · Личное сообщение · #11 Ну, верно, нельзя ВСЁ ломать. Но ведь кто-то, их малые проценты, уже давно взломал, и не сомневайтесь Я к тому, что некотрые наивные защитчики защищают свои проги именно md5, и считают, что невозможно сбрутить... 2 (или 3) месяца назад как раз встала задача слома защиты, и решалась просто распаковкой msi-архива, но я пошел дальше и вот заболел md5, чего и всем желаю... хотя не, лучше заболейте все AES - не такой уж он надежный, особенно если проц с его поддержкой в имении ----- IZ.RU
rmn Ранг: 158.4 (ветеран), 123thx Активность: 0.14↗0.49 Статус: Участник	Создано: 06 октября 2010 21:08 · Поправил: rmn · Личное сообщение · #12 DenCoder md5 необратим. можно избавиться от последнего раунда при переборе, если исходная строка <=, чем, если память не изменяет, 5 символов. Но, конечно, если у тебя есть алгоритм, который ломает этот хеш - покажи исходную строку: bbaf4f28bb346e77e340d19234c23df1
4kusNick Ранг: 748.2 (! !), 390thx Активность: 0.37↘0 Статус: Участник bytecode!	Создано: 06 октября 2010 21:11 · Личное сообщение · #13 Странный топик. Что-то вроде: смотрите, у меня есть последняя ида. Но я её никому не дам. Зато она есть, радуйтесь. Либо я чего-то не понял ----- Флэш, ява, дотнет - на завтрак, обед и ужин. Unity3D на закуску.
PE_Kill Ранг: 793.4 (! !), 568thx Активность: 0.74↘0 Статус: Участник Шаман	Создано: 06 октября 2010 21:12 · Личное сообщение · #14 Непонятен смысл топика. Кому надо будет обсудить, тот сам создаст топик и первым начнет дискуссию, помогать таким людям фейковым топиком нет необходимости. Если есть что показать, сделай сервис, помоги страждущим, или по мылу, как анпакер аспра, топик тогда прикрепим. Хочешь запостить но не для всех стукни модерам, помогут ;) А так, весь смысл в опросе размера гениталий не больше. ----- Yann Tiersen best and do not fuck
DenCoder Ранг: 324.3 (мудрец), 221thx Активность: 0.48↘0.37 Статус: Участник	Создано: 06 октября 2010 21:16 · Поправил: DenCoder · Личное сообщение · #15 rmn, хеш взят, отлажу прогу, отвечу здесь же Потом, раунда всего 4, шагов в раунде 16 и заключительный шаг - сложение с первообразными константами = md5-хеш. Это для строк < 0x38 байт и >= 0x10 байт, я думаю все поняли. Хотя, если принимать только 0x10 байт и символы строк от 0 до 0xFF, коллизии будут на каждую строку длиной 0x10 байт к строкам меньше 0x10 байт. Почему? А вот все дело в bitlength по смещению 0x38. Ок, Archer ))) _____________________________________ 31.01.2011 Два месяца, как поставил проект на паузу. Скоро вернусь, только разгребу дела. Честно, поторопился выкладывать - та моя теория оказалась несовершенна, да и сейчас нет, но лучше, чем была. Суть нового используемого способа - решение СБУ(системы бинарных уравнений) при помощи теории графов. По теории СБУ много есть в интернете, но все же нужная часть как раз закрыта от простого люда... Также можно найти по ключу "системы бинарных уравнений" планы некоторых НИИ на ближайшие 5-10 лет. 11.05.2011 Наконец проработал схему структур подграфа для вычислений. Используются понятия "подграф" (элементарная часть - шаблон для построения графа), "субграф" (выборка связанных подграфов), "вариантный субграф" (выборка связанных подграфов, имеющих только определённый набор вариантов решения). Вдалеке кажется непреодолимая трудность: необходимость учитывать различные варианты для разных субграфов может привести к труднооценимой нехватке памяти и может оказаться, что в скорости не будет выигрыша по сравнению с брутом... Но проверить основательно это пока всё ещё невозможно. По приблизительным подсчётам, на построение всех подграфов на бумаге ушло бы не меньше 42 суток непрерывной работы или 126 дней ежедневных рабочих дней... ----- IZ.RU
Isaev Ранг: 756.3 (! !), 113thx Активность: 0.61↘0.05 Статус: Участник Student	Создано: 06 октября 2010 21:31 · Поправил: Isaev · Личное сообщение · #16 rmn в общем это не будет исходная строка, будет строка которая даст тот же md5 или DenCoder просто ясновидящий ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh
Archer Ранг: 2014.5 (!!!!), 1278thx Активность: 1.34↘0.25 Статус: Модератор retired	Создано: 06 октября 2010 21:43 · Личное сообщение · #17 Ладно, будем считать, хотел кинуть понты, неудачно. Будет исходная строка под хеш или ПОЛЕЗНАЯ инфа-тогда открою.

Для печати