MD5 collisions - дайте пример
а бывают?
если бы не было, md5 был бы отличным архиватором 
А как насчёт деархивирования?
md5 был бы плохим архиватором, потому что восстановить нельзя, даже если точно уверен что не совпадет.
Я думаю например что на русских текстах размером до 2 Мб md5 не совпадет ни разу.
Я думаю например что на русских текстах размером до 2 Мб md5 не совпадет ни разу.
Бывают-бывают.
Из-за того, что md5 принимает конечное количество значений - бывают теоретически, а последние годы есть и практически.
Гуглем уже нашёл исходники генераторов (обещают, что подсчёт на современном компе занимает полминуты) и два ps-файла с одинаковым md5.
Просто хочется найти короткие, и, желательно, осмысленные строки...
Из-за того, что md5 принимает конечное количество значений - бывают теоретически, а последние годы есть и практически.
Гуглем уже нашёл исходники генераторов (обещают, что подсчёт на современном компе занимает полминуты) и два ps-файла с одинаковым md5.
Просто хочется найти короткие, и, желательно, осмысленные строки...
тяжело, но полным перебором обязательно можно было бы восстановить оригинал.
Я думаю например что на русских текстах размером до 2 Мб md5 не совпадет ни разу.Да, вот тут предыдущий метод про полный перебор уже не подойдет, т.к. не формализовано понятие русских текстов
ты меня разочаровываешь, гугл на запрос "сollisions md5" выдаёт на первой странице ссылку на работу Wang со товарищами где есть такие коллизии.
и в википедии ссылки есть.
и в википедии ссылки есть.
Я думаю например что на русских текстах размером до 2 Мб md5 не совпадет ни разу.Уверен?
Ну пусть русский язык состоит из 2^17 (сто тысяч) слов (примерно так и есть, вроде бы).
Тогда два слова дадут тебе 2^34 вариантов, три - 2^51, а уже текстов из семи слов получается гораздо больше, чем всех md5-хэшей.
И где там два мегабайта
осмысленных текстов длиной, например, одна страница уже сильно меньше
Википедию читал.
Да, ссылки там есть.
Но они все - либо на длинные статьи с описанием алгоритмов, либо на код генераторов коллизий, либо вот эти два ps-файла.
Конкретных текстов не было.
Что я делаю не так?
Да, ссылки там есть.
Но они все - либо на длинные статьи с описанием алгоритмов, либо на код генераторов коллизий, либо вот эти два ps-файла.
Конкретных текстов не было.
Что я делаю не так?
Вопрос о существующих текстах. А не о всем, что теоретически можно написать.
Книги, например.
Книги, например.
Ладно, пусть есть, например, 2^10 существительных в именительном падеже каждого рода, 2^10 прилагательныхкаждого рода, 2^10 глаголов каждого рода.
Это уже даёт 2^50 предложений вида "мокрая бабушка пнула далёкий презерватив", вполне так осмысленных.
Это уже даёт 2^50 предложений вида "мокрая бабушка пнула далёкий презерватив", вполне так осмысленных.
Я-то не о существующих текстах говорил.
А насчёт книг - ну это-то очевидно, этих книг в мире на порядки меньше, чем сумм.
А насчёт книг - ну это-то очевидно, этих книг в мире на порядки меньше, чем сумм.
Просто хочется найти короткие, и, желательно, осмысленные строки...полностью осмысленных ты точно не найдёшь, бинарный блок доводящий до коллизии всегда нужен.
Ага, полным перебором за 2^128 тактов?
Ты где такой компьютер нашёл, чтобы дожить до этого?
Ты где такой компьютер нашёл, чтобы дожить до этого?
я ж говорю, что понятие осмысленный неформализуемо. В одной стороны, "мокрая бабушка пнула далекий презерватив" выглядит совершенно осмысленно и даже такое может случиться, но человек, прочитавший это, вероятнее всего скажет "Что за фигня!?!. Вот если архивировать то, что не выходит за рамки "разумно-осмысленных" текстов, их реально может оказаться совсем немного
Слышал про русский ламповый компьютер под рабочим названием Иван-Дурак? Считает туго, но зато ему везет
Что я делаю не так?я нашёл меньше чем за минуту, и у меня нет никакого желания облегчать тебе жизнь. ищи.
бинарный блок доводящий до коллизии всегда нуженНе всегда.
За 2^64 с помощью birthday attack можно с достаточно большой вероятностью получить коллизию вида md5(предложение1текст1)=md5(предложение2текст2 где текст1 и текст2 - какие хочется, а предложение1 и предложение2 - случайные, типа тех, которые у меня в предыдущем посте (их генерить легко).
2^64 - это ведь совсем немного, какие-то там 10^20, за нормальное время (день/месяц/год) на кластере такое точно можно посчитать - наверняка ведь кто-то это уже сделал?
Спасибо, почти то, что надо!
А "осмысленных текстов" нету?
А "осмысленных текстов" нету?
Ладно, как-то формализую - "мокрая бабушка пнула далёкий презерватив" я считаю осмысленным, а "d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5bd8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70" - нет.
55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5bd8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70" - нет.
За 2^64 с помощью birthday attackэто самое тупое что можно сделать, зря что-ли md5 китайцы и французы ковыряли.
там уже значительно уменьшена оценка введением ограничений на подбираемые блоки.
достаточно научится строить осмысленные фразы заданной длины с этими ограничениями, но это никому не нужно, т.к. повсеместно используются форматы в которые можно пихать бинарный мусор без ущерба для содержимого.
осмысленных текстов в твоем смысле действительно больше, чем md5-хешей. А вот фраз, которые напишет здоровый человек без цели поприкалываться сильно меньше. Т.е. те же книги реально "сжать", при наличии на обоих сторонах большого словаря
это hex-код, болван =)
это самое тупое что можно сделатьНу а я про что?
Тут просто говорят "надо обязательно бинарные блоки" - а получается, что даже если использовать самый тупой метод, вполне реально такие строки найти.
повсеместно используются форматы в которые можно пихать бинарный мусор без ущерба для содержимого.Ну а емсли интересно?
это hex-код, болван =)Думаешь, я не заметил?
А я говорил про то, что как текст я это осмысленным не считаю.
А вот фраз, которые напишет здоровый человек без цели поприкалываться сильно меньше.А вот как ты такие фразы перечислишь?
Заведёшь сверхгигантский словарь?
И ещё, в современной поэзии "мокрая бабушка пнула далёкий презерватив" вполне так может встретиться
Где искал?
Какие ключевые слова вводил?
Какие ключевые слова вводил?
А вот как ты такие фразы перечислишь?
Заведёшь сверхгигантский словарь?
ага
И ещё, в современной поэзии "мокрая бабушка пнула далёкий презерватив" вполне так может встретитьсяДа, но с маленькой вероятностью. При архивации, если предложения нет в словаре, записываем без изменений с пометкой "не архивировано". Получится, что современная поэзия будет архивироваться хуже
агаИ что дальше?
Каждую фразу архивировать в её md5? Приличные архиваторы без такого изврата сжимают гораздо лучше.
А заархивировать текст целиком... ну вот, например: "Л.Толстой, Война и Мир" - весит в архивированном виде всего 22 байта, а сколько в себе содержит! Вот только словарь для этого нужен размером во весь объём всей литературы...
Каждую фразу архивировать в её md5? Приличные архиваторы без такого изврата сжимают гораздо лучше.можно не фразу, а сразу страницу.
про то, что в реальности это применять нельзя, я вроде и не спорил
Оставить комментарий
kruzer25
гуглем ничего не нашёл, кто-нибудь знает две не очень длинные строки, дающие одни и тот же md5?