Возможно.

Возможно.

Вероятность коллизии существует, если использовать plain-text то есть шанс добить непечатными символами до нужного хеша.

Гораздо интереснее такое направление творчества Куайн.

>если использовать plain-text то есть шанс добить непечатными символами до нужного хеша.

Я имел в виду следующее: в файле записан хеш файла. А хеш, обычно, выражается печатными символами {0..F}.

И да,

10 List

google://md5 fixed points

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

Т.е. возможно, но не в этой жизни?

Since the hash is irreversible, this would be very hard to figure out. The only way to solve this, would be to calculate the hash on every possible output of the hash, and see if you came up with a match.

To elaborate, there are 16 bytes in an MD5 hash. That means there are 2^(16*8) = 3.4 * 10 ^ 38 combinations. If it took 1 millisecond to compute a hash on a 16 byte value, it would take 10790283070806014188970529154.99 years to calculate all those hashes.

> Я имел в виду следующее: в файле записан хеш файла. А хеш, обычно, выражается печатными символами {0..F}.

Давайте устраним лишнюю сущность - файл. Задача: найти такой набор байт, чтобы его хэш совпал с ним самим.

Лучше бы чем полезным занялся :)

Чтобы это точно было возможно, разрешим в качестве входного текста иметь N раз повторённый хэш.

это называется квайн

Вообще возможно, но весьма сложно, если формализовать, то получится что:

x = g(f(x))
где:
f - md5 hash generation
g - функция преобразования bin -> hex-string

Сложность нахождения обратного значения — одно из условий криптостойкого хеша. Остается только уповать на гениальных математиков.

Собственно если подставить сюда реальные формулы, то получится совсем не маленькое уравнение, решив которое мы получим адовый результат.... Только боюсь что решить его будет совсем не просто.

точнее не быстро.

>одно из условий криптостойкого хеша.

MD5 вскрывается за час на оборудовании 2004 года (см. википедию). Так что подбор такого значения, что md5(x) = x можно сделать не через перебор, I think.

Теоретически это можно, но на практике реально найти такой хеш только для CRC32 :) Или будучи гениальным математиком.

>To elaborate, there are 16 bytes in an MD5 hash. That means there are 2^(16*8) = 3.4 * 10 ^ 38 combinations. If it took 1 millisecond to compute a hash on a 16 byte value, it would take 10790283070806014188970529154.99 years to calculate all those hashes.

Ужеб округлили бы до 10790283070806014188970529155, чего уж там 0,1 года размениваться:))

> Собственно если подставить сюда реальные формулы, то получится совсем не маленькое уравнение, решив которое мы получим адовый результат.... Только боюсь что решить его будет совсем не просто.

Если вся проблема в объёме, его можно загнать в мат. пакет.

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

> Давайте устраним лишнюю сущность - файл. Задача: найти такой набор байт, чтобы его хэш совпал с ним самим.

А кстати, как вы определяете хеш? Ведь тот же md5 можно записать сырыми данными, f36abc3 — в нижнем регистре, F33ABE9 — в верхнем регистре, кроме того в каждой вариации есть 'hash' и 'hash\n'

> А кстати, как вы определяете хеш?

Раз не определил, значит на усмотрение. Хотя в идеале хотелось бы побитовое совпадение исходника и хэша.

Где спрашивали и кто отвечал? Может люди далекие от программирования отвечали? ИМХО брутфорсом такое сделать можно, но долго. Когда-нибудь да совпало бы.

хотелось бы побитовое совпадение исходника и хэша.

Биты глазами читать сложнее, чем строку, я бы настаивал на чем то типа

MD5("1bc29b36f623ba82aaf6724fd3b16718") = 1bc29b36f623ba82aaf6724fd3b16718

Не, ну хоть как-нибудь бы уже решили =)

> Где спрашивали и кто отвечал? Может люди далекие от программирования отвечали?
Вроде бы на старом Дваче было ещё до его смерти. Там ещё не такой сброд был, как сейчас на бордах. Как анонимуса угадаешь, далёк он от программирования или нет? Но дискуссия по этому поводу была бурная.

Я не очень хорошо знаю баш, но думаю там это займет не более 10 строк.

it would take 10790283070806014188970529154.99

Эту задачу надо дать японцам или китайцам.

> Я не очень хорошо знаю баш, но думаю там это займет не более 10 строк.

А причём тут строки? Мы о решениях. Хотите полным перебором подобрать? Удачи.

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

Хотите полным перебором подобрать? Удачи.

Хм... Тогда предлагаю идти с конца. Знаете, есть такая задача на логику для детей:

Идет крестьянин и плачется: «Эхма! Жизнь моя горькая! Заела нужда совсем! Вот в кармане только несколько грошей медных болтается, да и те сейчас нужно отдать. И как это у других бывает, что на всякие свои деньги они еще деньги получают? Право, хоть бы кто помочь мне захотел».

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

— Что ж, — говорит, — если хочешь, я тебе помогу. И это совсем нетрудно. Вот видишь этот мост через реку? — Вижу! — говорит крестьянин, а сам заробел. — Ну, так стоит тебе перейти только через мост — у тебя будет вдвое больше денег, чем есть. Перейдешь назад, опять станет вдвое больше, чем было. И каждый раз, как ты будешь переходить мост, у тебя будет ровно вдвое больше денег, чем было до этого перехода. — Ой ли? — говорит крестьянин. — Верное слово!— уверяет черт. — Только, чур, уговор! За то, что я тебе удваиваю деньги, ты каждый раз, перейдя через мост, отдавай мне по 24 копейки. Иначе не согласен. — Ну, что же, это не беда! — говорит крестьянин. — Раз деньги все будут удваиваться, так отчего же 24 копейки тебе каждый раз не дать? Ну-ка, попробуем!

Перешел он через мост один раз, посчитал деньги. Действительно, стало вдвое больше. Бросил он 24 копейки черту и перешел через мост второй раз. Опять денег стало вдвое больше, чем перед этим. Отсчитал он 24 копейки, отдал черту и перешел через мост в третий раз. Денег стало снова вдвое больше. Но только и оказалось их равнехонько 24 копейки, которые по уговору он должен был отдать черту. Отдал он их и остался без копейки.

Сколько же у крестьянина было денег сначала?

Решение просто - нужно идти назад по шагам. Насколько я понимаю, в MD5 такой метод может и прохлять. Am I right?

> Решение просто - нужно идти назад по шагам. Насколько я понимаю, в MD5 такой метод может и прохлять. Am I right?

Нет, не может.

Куда более простая задача написать программу, которая печатает md5sum своих исходников. Решается для любой хеш-функции.

А вот есть ли неподвижная точка в md5 — сложный вопрос, пока не решен.

мд5 признан небезопасным в 2004 году. уповайте дальше

по сути, 10790283070806014188970529154 китайце-лет это не так уж и много

мд5 признан небезопасным в 2004 году.

И как это облегчает сабжевую задачу, мой дорогой слышатель звона?

например так

Дерзай. За работу «использование дырки с коллизиями в MD5 для нахождения ее неподвижных точек» тебе будет невероятный почет и уважуха. Прямо как гениальному математику. Хе-хе.

> Гораздо интереснее такое направление творчества Куайн.

1) Берем любой интерпретируемый язык программирования

2) Заставляем программу открывать свой файл и выкидывать его на экран.

3) Profit!!!