О сжатии, информационной энтропии и искусственном интеллекте

ты хоть по ссылке сходи, а потом подбери мне коллизию скажем к e28f0be3346162fffa121e2f768aa0aa, ну и возвращайся. Как подберёшь.

Чукча-писатель, как я посмотрю. Суть не в подборе конкретной коллизии (и не моё это дело), а в том, что хеш уязвим алгоритмически, и это доказано

конечные множества не равной мощности.

QED

у тебя с тервером беда.

на практике важно не_отсутствие совпадений, а их допустимо низкая встреча.

а отличии от декодера который должен выдавать нам эталон то его хэшу.

Чукча-писатель, как я посмотрю. Суть не в подборе конкретной коллизии (и не моё это дело), а в том, что хеш уязвим алгоритмически, и это доказано

ВНЕЗАПНО: _любой_ криптографический алгоритм уязвим алгоритмически. Вот тебе самый простой случай: пусть твой алгоритм держится на том факте, что перемножить два БОЛЬШИХ числа можно легко и просто, а вот разложить их на произведения — нельзя. На самом деле — можно. Только мы пока не знаем никакого более вменяемого алгоритма, акромя тупого перебора.

Точно также и с md5 — алгоритм нам не известен. Известно лишь что в некоторых случаях коллизии можно создать искусственно. Т.е. можно сделать две кучки мусора с одним и тем же md5. Также и про произведение нам такое известно. К примеру степень двойки разложить тривиально. Также нам известно, что если сумма цифр числа делится на M-1 (где M это основание СС), то и всё число делится на M-1. К примеру 111`111`111 делится на 9 в десятичной СС. Есть и множество других частных случаев, которые позволяют СИЛЬНО уменьшить время подбора. А толку-то?

Вот ты и доказал, что есть какой-то частный случай, для которого коллизии есть. Проблема только в том, что на практике он никак невозможен.

у тебя с тервером беда. на практике важно не_отсутствие совпадений, а их допустимо низкая встреча.

я это и пытался объяснить тем, у кого с тервером проблемы. Вероятность того, что сообщение будет тем самым мусором, для которого можно сгенерировать коллизию ничтожна. Она даже неизмеримо меньше вероятности, что мы подберём хеш простым подбором.

ВНЕЗАПНО: _любой_ криптографический алгоритм уязвим алгоритмически.

Попрошу доказательства этого утверждения для Serpent, к примеру

Только мы пока не знаем никакого более вменяемого алгоритма, акромя тупого перебора.

Алгоритмическая уязвимость подразумевает снижение стойкости ниже расчётной, а тупой перебор 2^n комбинаций (где n >= 128) это не алгоритм, это идиотизм, по определению

Точно также и с md5 — алгоритм нам не известен

/рукалицо...

Попрошу доказательства этого утверждения для Serpent, к примеру

учись читать: этот алгоритм уязвим для _неизвестных_ методов. Для доказательства его (не)уязвимости нужна машина времени.

Алгоритмическая уязвимость подразумевает снижение стойкости ниже расчётной, а тупой перебор 2^n комбинаций (где n >= 128) это не алгоритм, это идиотизм, по определению

почему «тупой»? Я же примеры дал, там описаны частные случаи, я вот например некоторые числа хоть в 2048 бит могу в уме разложить на множители. Потому-что знаю методы. В школе учился... И не факт, что твой враг не знает методов для твоих чисел.

Точно также и с md5 — алгоритм нам не известен

/рукалицо...

посильнее, со всей дури. Может читать научишься. Естественно речь не про сам алгоритм md5.

учись читать: этот алгоритм уязвим для _неизвестных_ методов. Для доказательства его (не)уязвимости нужна машина времени.

т.е. криптоаналитики (в т.ч. по ссылке, что я приводил) либо действительно ею пользуются, либо являются шарлатанами? феерично =)

почему «тупой»?

есть анекдот(?): поставили задачу перед физиком и математиком: лягушка за первый прыжок преодолевает половину условной дистанции, за второй - половину от предыдущего прыжка и т.д. вопрос: когда она преодолеет всю? математик сказал «через бесконечное количество времени», физик сказал «никогда». так вот, ответ математика тупой, как и твой перебор — потому, что нереальный

посильнее, со всей дури. Может читать научишься.

помогает? =)

Естественно речь не про сам алгоритм md5

Известно лишь что в некоторых случаях коллизии можно создать искусственно

Ну вот потрудись объяснить: как можно __искусственно__ создать коллизии не применяя соотв. алгоритма? Автор по ссылке разве пользуется «универсальным» «тупым» перебором? =)

может ты обрисуешь в двух словах, ЧТО ты пытаешься доказать?

и да, тебе на заметку: перебор это тоже алгоритм. И он бывает сильно разный. Для тебя должно быть очевидно, что про действительно «тупой» (последовательный например) перебор речи нет.

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

Только мы пока не знаем никакого более вменяемого алгоритма, акромя тупого перебора.

и да, тебе на заметку: перебор это тоже алгоритм. И он бывает сильно разный.

Ещё раз повторяю: перебор по разрядности шифра (>=128бит), т.е. брутфорс - это бесконечная по времени тупость, которой никто заниматься не будет. А вот перебор по с учётом коллизий - уже алгоритм, т.к. ведётся с определёнными правилами, позволяющими перебирать не все варианты из множества

Могу также пояснить тебе, что никакой «расчётной силы криптоалгоритма» нет, и быть не может.

Чушь собачья. Расчётная стойкость (в битах) есть у каждого криптоалгоритма, учи матчасть.

http://ru.wikipedia.org/wiki/A5#.D0.98.D0.B7.D0.B2.D0.B5.D1.81.D1.82.D0.BD.D1...

где там «не однозначность»? Даже к md5 коллизию никто не подобрал, а уж с sha256 и гадать нечего.

дурак?
http://habrahabr.ru/post/137316/
Да и чисто логически любой школьник догадается, что кличество вариантов md5 ограничено и если вариантов входных данных будет больше то как не крути начнутся коллизии.

имхо для подобной информации проще придумать специальный формат файла.

дурак?

579cb9e970c3e56f810a7cd0f9ebbe26

подбери.

579cb9e970c3e56f810a7cd0f9ebbe26
подбери.

Математические доказательства не для тебя, я понял. Только брутфорс, только хардкор.

579cb9e970c3e56f810a7cd0f9ebbe26
подбери.

Математические доказательства не для тебя, я понял. Только брутфорс, только хардкор.

ну если для тебя, то подбери.

Или признайся, что ты слил.

ну если для тебя, то подбери.
Или признайся, что ты слил.

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

Ты какойто неадекватный. Во первых, причем тут подбор md5 если тема про архивирование?

слился?

Да и чисто логически любой школьник догадается, что кличество вариантов md5 ограничено и если вариантов входных данных будет больше то как не крути начнутся коллизии.

это ты писал, а не я.

Во вторых, как ты думаешь сколько займет подбор?

больше, чем возраст вселенной.

В третьих, наркотики это очень вредно и ты живое тому доказательство.

а кто тебе сказал, что я употребляю наркотики?

слился?

Сначало обыясни где связь подбора мд5 с архивацией? md5 к архивации вообще ни как не относится. И почему я должен, что то подбирать?

это ты писал, а не я.

Ну, и в чем я не прав?

больше, чем возраст вселенной.

Это если ты с карандашем на бумаге подбирать будешь.

а кто тебе сказал, что я употребляю наркотики?

Это очень легко определить по тупняку который ты пишешь почти в каждой теме на лоре.

Сначало обыясни где связь подбора мд5 с архивацией?

учи матчасть. Мне сегодня лень ликбезом заниматься.

md5 к шифрованию вообще ни как не относится.

напрямую относится.

И почему я должен, что то подбирать?

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

Ну, и в чем я не прав?

в этом: «Да и чисто логически любой школьник догадается, что кличество вариантов md5 ограничено и если вариантов входных данных будет больше то как не крути начнутся коллизии.»

Это если ты с карандашем на бумаге подбирать будешь.

ну я же не ограничивал тебя? Можешь смело использовать свой GPU, я не против. Какая разница, 100500 миллиардов лет, или Over9000? Ты всё равно столько не проживёшь.

Это очень легко определить по тупняку который ты пишешь почти в каждой теме на лоре.

чини детектор.

учи матчасть. Мне сегодня лень ликбезом заниматься.

Ты заблуждаешься.)

напрямую относится.

Очень сильно заблуждаешься.)

в этом:...

Ну и? Где указание на ошибку?

ну я же не ограничивал тебя? Можешь смело использовать свой GPU, я не против. Какая разница, 100500 миллиардов лет, или Over9000? Ты всё равно столько не проживёшь.

Ты так и не объяснил зачем это нужно.

чини детектор.

Помойму он отлично работает.

Очень сильно заблуждаешься.)

Ну и? Где указание на ошибку?

и?...

Ты так и не объяснил зачем это нужно.

просто поверь старому человеку: ты не будешь жить вечно.

Помойму он отлично работает.

все так думают. Даже те, кто ещё не освоил правила русской грамматики и орфографии.

и?...

Что и? Слился?)

просто поверь старому человеку

Так вот оно что...

учи матчасть. Мне сегодня лень ликбезом заниматься.

учи матчасть. Мне сегодня лень ликбезом заниматься.

Спс но я ее лучше тебя знаю.

Спс но я ее лучше тебя знаю.

ну значит очень хорошо скрываешь свои знания. Может тебе в артисты пойти? Так натурально разыгрывать невежу ни у кого не получится...

ну значит очень хорошо скрываешь свои знания. Может тебе в артисты пойти? Так натурально разыгрывать невежу ни у кого не получится...

Отстань от меня уже, иди дерни еще косячек или что ты там употребляешь.

Отстань от меня уже, иди дерни еще косячек или что ты там употребляешь.

лучше скажи, что ТЫ употребляешь для того, что-бы для тебя стало «конечным» 2^128? А то для меня это бесконечность. В секундах это 10 790 283 070 806 014 188 970 529 154 990 лет, если верить моему калькулятору.

ну да, в тактах моего CPU это намного меньше, всего 3 371 963 459 626 879 434 053 лет.

Еще бы не справилась - для нее твой пример - это эталонная синтетическая задача.

лучше скажи, что ТЫ употребляешь для того, что-бы для тебя стало «конечным» 2^128?

.......

В секундах это 10 790 283 070 806 014 188 970 529 154 990 лет

.......

в практическом смысле это бесконечность. Хотя, если упортебить вещества, то конечно, это вполне конечная величина.

ЗЫЖ Отсыпешь?

кто ещё не освоил правила русской грамматики и орфографии

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

ваше мнение очень важно для нас

между прочим icfp 2013 было как раз про это :)

в практическом смысле это бесконечность. Хотя, если упортебить вещества, то конечно, это вполне конечная величина.

Еще раз для особо упоротых.
2^128 это конечное число, и равно оно 2^128. А возможных вариантов файлов для архивации бесконечное число, намнооооооого больше чем у тебя пальцев на руках, понимаешь?
Так вот 2^128 вариантов мд5 меньше чем бесконечное число возможных файлов.
Если ты заархивируешь файл алгоритмом мд5 то хешсумма будет соотвествовать не какому то отпределенному разархивированному файлу, а нескольким файлам. Потому что 2^128 это большое но конечное число, а бесконечность это бесконечность, это оооооочень много, больше чем у тебя пальцев на руках.
Из за того, что мд5 сумма (твой заархивированный файл) может соответствовать куче разархивированных файлов, это делает мд5 непригодным для архивации.
Например заархивировал картинку с поняшкой, а разархивировалась картинка с проном.

А на рассчеты скорости подбора мд5 тебя проперло потому, что вещества попались в этот раз ядренее чем обычно.

Это не мнение, это очевидный факт. Если для тебя он не очевидный, посмотри в историю своих сообщений.

Еще раз для особо упоротых. 2^128 это конечное число, и равно оно 2^128

в практическом смысле оно бесконечное, ибо ты не будешь жить вечно. Нет никакой разницы между 2^128 и бесконечностью ДЛЯ ТЕБЯ.

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

в математическом смысле их тоже конечное множество, ибо бесконечных файлов не бывает (я надеюсь, мы договоримся не жать /dev/random, ok?)

Если ты заархивируешь файл алгоритмом мд5 то хешсумма будет соотвествовать не какому то отпределенному разархивированному файлу, а нескольким файлам. Потому что 2^128 это большое но конечное число, а бесконечность это бесконечность, это оооооочень много, больше чем у тебя пальцев на руках.

2^128 это больше чем у тебя пальцев, больше чем у тебя файлов, и даже больше, чем магнитных доменов на всех твоих HDD (и вообще НА ВСЕХ). Потому коллизий не будет. Если только ты их специально не сделаешь.

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

«может» только лишь в теоретическом плане. На практике НЕ МОЖЕТ. Т.е. использование md5 на практике возможно, вот только нет способа найти файл по заданной md5 иначе, чем перебором. Теоретически это возможно, но нужно бесконечное время. А его у нас нет.

Например заархивировал картинку с поняшкой, а разархивировалась картинка с проном.

проблема в том, что такого прона НЕ СУЩЕСТВУЕТ. Есть только поняшка. Смирись с тем, что в природе (ВО ВСЕЙ ВСЕЛЕННОЙ) существует только ОДИН файл с md5 1cdfa5cc440f39de65ed238f63e71747. Это моя пони. Теоретически МОГУТ быть и другие файлы из множества файлов (множество имеет размер 2^100368, если договоримся, что ты знаешь, что моя пони весит 13К), потому-что 2^128 намного меньше, но на практике таких файлов НЕТ. Смирись с этим.

ЗЫЖ и да, если рассматривать ВСЕ файлы, то архиваторы НЕ НУЖНЫ. Вообще В ПРИНЦИПЕ. Ибо не сжимают ни разу. Это если упороться, и расматривать квантор всеобщности. Но на практике так не делают.

Это не мнение, это очевидный факт. Если для тебя он не очевидный, посмотри в историю своих сообщений.

нет, деточка, это лишь твоё мнение.

lzma/lzma2 в виде xz уже проверяли?

lzma/lzma2 в виде xz уже проверяли?

а какая разница? lzma сжимает тоже только то, что умеет сжимать. Файлы типа как в первом посте не умеет. Ну просто потому, что такие файлы никому не нужны. Если у тебя есть компьютер, то проще и быстрее их просчитать, и хранить их может только норкаман.

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

деточка

Избавь меня от своих жалких попыток задеть меня.

В чужом глазу соломинку видишь, а в своем бревно не замечаешь.

вот откуда вы такие берётесь? Всё я замечаю. Это не баг, а фича.

Ок, спорить с тобой по понятным причинам бесполезно.

кто же спорит?

в практическом смысле оно бесконечное, ибо ты не будешь жить вечно. Нет никакой разницы между 2^128 и бесконечностью ДЛЯ ТЕБЯ.

Ты запарил тупить.) Время подбора мд5 тут непричем.

в математическом смысле их тоже конечное множество, ибо бесконечных файлов не бывает

И чем же ограничен размер файла?

Потому коллизий не будет. Если только ты их специально не сделаешь.

Что значит не будет? Есть факт возможности коллизий => нет однозначности => один и тот же мд5 соответствует куче файлов. Как ты при разархивировании будешь определять в какой файл из всех возможных вариантов нужно разархивировать мд5?

«может» только лишь в теоретическом плане. На практике НЕ МОЖЕТ.

Вот прислали тебе «мд5 архив» по почьте, он соответствует куче файлов в которые его можно разархивировать.

Смирись с тем, что в природе (ВО ВСЕЙ ВСЕЛЕННОЙ) существует только ОДИН файл с md5 1cdfa5cc440f39de65ed238f63e71747. Это моя пони. Теоретически МОГУТ быть и другие файлы из множества файлов (множество имеет размер 2^100368, если договоримся, что ты знаешь, что моя пони весит 13К), потому-что 2^128 намного меньше, но на практике таких файлов НЕТ. Смирись с этим.

Коллизии в мд5 на практике вполне себе находятся http://habrahabr.ru/post/137316/
и даже соревнуются чей алгоритм быстрее.

Ты запарил тупить.) Время подбора мд5 тут непричем.

время тут имеет ключевое значение. Оно на самом деле конечное, но НА ПРАКТИКЕ нет никакой разницы между этой конечностью и обычной бесконечностью. Т.е. ты прав только теоретически, а на практики твои выводы абсолютно бесполезны.

И чем же ограничен размер файла?

чем угодно. Если мы про HDD, то количеством магнитных доменов. Битов ТЕОРЕТИЧЕСКИ не может быть больше, чем этих самых доменов. И число их вполне себе конечное. Даже /dev/random и то ограничено, и очень сильно. Если не веришь, то попробуй оттуда прочитать хотя-бы мегабайт. Как закончишь, вернёмся к спору.

Потому коллизий не будет. Если только ты их специально не сделаешь.

Что значит не будет?

купи букварь, и узнай значение слов «НЕ БУДЕТ».

Есть факт возможности коллизий => нет однозначности => один и тот же мд5 соответствует куче файлов.

ты передёргиваешь. Есть некоторая разница между «не может быть» и «не бывает». Вот файлов с md5 как у моей пони НЕ БЫВАЕТ, кроме самой пони. И это не смотря на то, что их МОЖЕТ БЫТЬ ровно http://pastebin.com/k4f8mvCq Но их — нет.

Вот прислали тебе «мд5 архив» по почьте, он соответствует куче файлов в которые его можно разархивировать.

да. Но _реально_ есть только ОДИН такой файл. Остальные в альтернативной реальности.

Коллизии в мд5 на практике вполне себе находятся

достали школьники. СПЕЦИАЛЬНО ДЕЛАЮТСЯ КОЛЛИЗИИ. Осиль наконец букварь. НАЙТИ коллизию ещё ни у кого не получилось. Ты будешь первым, и первым получишь коллизию. Для моей лошади их ровно http://pastebin.com/k4f8mvCq но вот способ их нахождения пока не известен.

да. Но _реально_ есть только ОДИН такой файл. Остальные в альтернативной реальности.

Тебе прислали «мд5 архив», он может быть с равным успехом распакован в 50 000 абсолютно разных файлов.
Твои действия для выбора нужного тебе файла из этих 50 000?

Тебе прислали «мд5 архив», он может быть с равным успехом распакован в 50 000 абсолютно разных файлов.

блжад, НЕ МОЖЕТ!

Твои действия для выбора нужного тебе файла из этих 50 000?

не 50К, а намного больше. Для пони http://pastebin.com/k4f8mvCq (при условии, что размер точно известен и равен 100368бит). Но вот курящая поня там только одна, остальное бессмысленный мусор. Ты разве не в состоянии отличить мусор от пони?

Ты пойми такую вещь: если рассматривать ВСЁ множество файлов какой-то заданной длинны, то сжатие их НЕВОЗМОЖНО В ПРИНЦИПЕ. Но если множество ограничено, то сжатие возможно. В том числе и с помощью md5(на практике не получается только лишь потому, что нет достаточно быстрого распаковщика)

при условии, что размер точно известен

Нет такого условия

курящая поня там только одна

Предположим, что там бинарная программа.

на практике не получается только лишь потому, что нет достаточно быстрого распаковщика

На машине есть охренительная радужная таблица в которой собраны все соответствия мд5 в плоть до 100мб

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

Осталось 50 000 корректных бинарников. Как будешь искать нужный? Каждый бинарник запускать?

если рассматривать ВСЁ множество файлов какой-то заданной длинны, то сжатие их НЕВОЗМОЖНО В ПРИНЦИПЕ.

Любой алгоритм сжатия может обробатывать все множество файлов, просто не все сожмутся, но на работоспособность это ни как не повлияет.

при условии, что размер точно известен

Нет такого условия

тогда вариантов больше, но это ничего не меняет, т.к. на практике время всё равно бесконечное получается, а у нас его нет.

Предположим, что там бинарная программа.

нет, ТАМ пони. Нет там никакой «программы».

На машине есть охренительная радужная таблица в которой собраны все соответствия мд5 в плоть до 100мб

НЕТУ такой машины. Смирись с этим, её нет и быть не может, и причина проста: 2^128 БОЛЬШЕ, чем атомов во вселенной. Тебе просто негде будет это хранить. Говорю-же, только в альтернативной укуренной реальности.

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

отсыпь своей травы, у меня такой ядрёной нет. Твои предположения в принципе невозможны.

Осталось 50 000 корректных бинарников. Как будешь искать нужный? Каждый бинарник запускать?

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

нет, ТАМ пони. Нет там никакой «программы».

лол

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

отсыпь своей травы, у меня такой ядрёной нет. Твои предположения в принципе невозможны.

Невозможно проверить файл на соответствие какому нибудь бинарному формату, ELF например? Ну да, загадка века.

никак не буду.

слив засчитан.