LINUX.ORG.RU
ФорумTalks

[Интересная задача] Хеш хеша в хеше.


0

1

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

Итак, условие:

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

Вопрос: возможно ли такое? Если, например взять MD5.

Возможно.

Возможно.

Camel ★★★★★ ()

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

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

Deleted ()
Ответ на: комментарий от Deleted

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

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

AlexCones ★★★ ()
Ответ на: комментарий от AlexCones

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

Deleted ()
Ответ на: комментарий от baverman

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

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.

AlexCones ★★★ ()
Ответ на: комментарий от AlexCones

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

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

Sadler ★★★ ()

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

xorik ★★★★★ ()
Ответ на: комментарий от Sadler

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

Sadler ★★★ ()

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


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




Jetty ★★★★★ ()
Ответ на: комментарий от AlexCones

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

baverman ★★★ ()
Ответ на: комментарий от Jetty

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

Jetty ★★★★★ ()
Ответ на: комментарий от baverman

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

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

AlexCones ★★★ ()

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

Deleted ()
Ответ на: комментарий от AlexCones

>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 года размениваться:))

Zak ★★ ()
Ответ на: комментарий от Jetty

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

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

Sadler ★★★ ()

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

CYB3R ★★★★★ ()
Ответ на: комментарий от Sadler

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

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

Xenius ★★★★★ ()
Ответ на: комментарий от Xenius

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

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

Sadler ★★★ ()
Ответ на: комментарий от CYB3R

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

AlexCones ★★★ ()
Ответ на: комментарий от Sadler

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

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

MD5("1bc29b36f623ba82aaf6724fd3b16718") = 1bc29b36f623ba82aaf6724fd3b16718

AlexCones ★★★ ()
Ответ на: комментарий от AlexCones

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

CYB3R ★★★★★ ()
Ответ на: комментарий от AlexCones

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

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

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

Sadler ★★★ ()
Ответ на: комментарий от Sadler

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

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

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

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

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

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

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

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

AlexCones ★★★ ()
Ответ на: комментарий от AlexCones

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

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

Sadler ★★★ ()

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

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

anarquista ★★★★★ ()
Ответ на: комментарий от devnullopers

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

baverman ★★★ ()
Ответ на: комментарий от Deleted

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

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

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

3) Profit!!!

segfault ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.