хеш функции

Здравствуйте.

Рады приветствовать.
Вообще все ваши рассуждения абсолютно правильны, кроме вывода.
Давайте по порядку.

результат хеш функции не может «уместить в себе», даже во всех своих возможных значениях все возможные результаты комбинаций текстов большой длины.

Совершенно верно.

Означает ли это, что для любых хеш функций существует обязательное множество коллизий

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

По теории вероятности: 1/2^128 для двух произвольно сгенерированных или выбранных текстов. (Парадокс дней рождения).
Один шанс из 340282366920938463463374607431768211456.

И 1/2^256 для подгонки одного текста к другому (или к примеру чужого ключа подписи к своему):
Один шанс из 115792089237316195423570985008687907853269984665640564039457584007913129639936.

и вопрос открытия методов их определения является делом времени?

Нет не означает. Если вы можете взломать 128-битный шифр быстрее, чем за 2^128 операций, значит он нестойкий.

Если вы можете найти произвольную коллизию хэша быстрее, чем за 2^128 бит операций для 256-битной хэш-функции,
значит она нестойкая (что и произошло c md5 и SHA-1). Но это не значит, что все функции заведомо нестойкие.

Вероятность нахождения коллизии должна быть такой же случайной (Один шанс из 340282366920938463463374607431768211456.) для любых, даже специально побитово подобранных текстов,
как и вероятность случайного нахождения ключа шифра (перебор грубой силой, brute force).

Согласитесь, это пренебрежимо малая вероятность.

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

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

Еще раз повторю, наличие "естественных", "неотличимых от случайных" коллизий, не означает, что их автоматически можно найти быстрее, чем нереально долгим перебором.

Unknown, еще раз спасибо за информацию, набраться бы Ваших знаний.

Не за что, всегда рады.

Вы мыслите в правильном направлении, а знания – это вопрос времени и интереса к теме.

Кстати, вот еще что. Размер блока выхода MD5 -128 бит, SHA1-160, но обе функции обрабатывают входные данные блоками по 512 бит.
И во всех работах коллизии были найдены в первом же блоке. Только недавно (вн ачале апреля (2 дня назад на этот момент) были опубликованы данные о нахождении коллизии во втором блоке сообщения: http://eprint.iacr.org/2005/102.

Так что получение естественных коллизий при сворачивании больших текстов в маленькую строку пока вообще не используется в криптоанализе хэшей. Проще изучить работу функции сжатия с маленьким блоком.

Unknown, здравствуйте!
Не знаете как в этом вопросе (поиск коллизий) обстоят дела с новыми функциями, примененными в 9-й версии PGP и последних версиях GnuPG: sha-256, sha-384, sha-512, а так же ripemd-160 (последняя по моему не новая)?

Практически лучше, но теоретически тоже не очень хорошо.

От функций типа md5-sha-ripemd рано или поздно придется уходить. Пока они должны дать запас практической стойкости на длительное время.

Реальная альтернатива только whirlpool, но она не прошла испытание временем и может иметь нестойкости иного рода. В распространенных утилитах ее нет.
Кроме того, она очень медленная.

Помоему md5 уже исчирпала свой запас прочности.
Я о статье, этой китайских учёных где написано что найти коллизию в МД5 по их методу можно от 15 до 60 минут компьтерного времени.

Помоему md5 уже исчирпала свой запас прочности.
Я о статье, этой китайских учёных где написано что найти коллизию в МД5 по их методу можно от 15 до 60 минут компьтерного времени.

Мы это уже целый год обсуждаем.
http://www.pgpru.com/forum/viewtopic.php?t=564

И свою позицию по этому вопросу я излагал: функции типа md5-sha-ripemd, это имеется ввиду одно семейство функций. Они все структурно очень похожи. И SHA512 – не решит всех проблем.

Нужно изобретать принципиально новый вид хэшей на неизвестных ранее принципах. Единственная достойная попытка – Whirlpool.

Были еще проекты от Ади Шамира на дискретных логаритмах, но я даже их названия не помню.

А whirlpool прошла хотя бы европейский конкурс cryptoNESSI.

не много не по теме
у когонить есть пример как допустим abc превращается в md5 хеш??

Добрый день! :D
Во первых разрешите поприветсвовать вернувшегося в форум unknown, все Вам рады!

не много не по теме
у когонить есть пример как допустим abc превращается в md5 хеш??

Не ясно, так и превращается по моему. Берется хеш от abc и все. Что Вы имели в виду? Если нужна программа, то можете найти в разделе софт. Для данных целей очень удобной является программа HashCalc.

"Брюки превращаются... брюки превращаются..." :)

MD5 (abc) = 900150983cd24fb0d6963f7d28e17f72

Во первых разрешите поприветсвовать вернувшегося в форум unknown, все Вам рады!

И я Вам всем тоже!

Про счет md5:

у меня прямо как в кино с брюками получилось с третьей попытки, пока не забыл убрать символ "перевода каретки" в конце строки.

localhost:/home/unknown$ echo "abc" | md5sum 0bee89b07a248e27c83fc3d5951213c1 - localhost:/home/unknown$ echo "(abc)" | md5sum 29836381da49c35ceebdaf8e638b86fc - localhost:/home/unknown$ echo "abc" | openssl md5 0bee89b07a248e27c83fc3d5951213c1 localhost:/home/unknown$ echo -n "abc" | openssl md5 900150983cd24fb0d6963f7d28e17f72 localhost:/home/unknown$ echo -n "abc" | md5sum 900150983cd24fb0d6963f7d28e17f72 - localhost:/home/unknown$


Еще бывают замороки с кодировкой ASCI или UTF

вы не поняли
есть описание на руском но там общее описание "берется строка потом добавляется стока-то нулей..... итд.. итп.."
я про описание на конкретном примере

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

Кстати, md5 и sha1 еще пытаются спасти от коллизий в практических приложениях:

http://eprint.iacr.org/2005/248

Collision-Resistant usage of MD5 and SHA-1 via Message Preprocessing

Michael Szydlo and Yiqun Lisa Yin