хеш функции
Здравствуйте. :D
К примеру хеш функция имеет разрядность 256 бит, иначе говоря это число ограничено в любом случае, оно вычисляется для текста любой длины, хоть для 1 слова, хоть для 100 страниц. Длинные тексты имеет гораздо большую разрядность, если выразить ее в битах, т.е., как я понимаю, результат хеш функции не может «уместить в себе», даже во всех своих возможных значениях все возможные результаты комбинаций текстов большой длины. Означает ли это, что для любых хеш функций существует обязательное множество коллизий и вопрос открытия методов их определения является делом времени?
Рады приветствовать.
Вообще все ваши рассуждения абсолютно правильны, кроме вывода.
Давайте по порядку.
Совершенно верно.
Разумеется. Но это число не должно отличаться от того, как если бы коллизии были случайными совпадениями.
"Естественные коллизии" – они не угрожают стокости хэшей.
По теории вероятности: 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 минут компьтерного времени.
Мы это уже целый год обсуждаем.
http://www.pgpru.com/forum/viewtopic.php?t=564
И свою позицию по этому вопросу я излагал: функции типа md5-sha-ripemd, это имеется ввиду одно семейство функций. Они все структурно очень похожи. И SHA512 – не решит всех проблем.
Нужно изобретать принципиально новый вид хэшей на неизвестных ранее принципах. Единственная достойная попытка – Whirlpool.
Были еще проекты от Ади Шамира на дискретных логаритмах, но я даже их названия не помню.
А whirlpool прошла хотя бы европейский конкурс cryptoNESSI.
не много не по теме
у когонить есть пример как допустим abc превращается в md5 хеш??
Добрый день! :D
Во первых разрешите поприветсвовать вернувшегося в форум unknown, все Вам рады!
Не ясно, так и превращается по моему. Берется хеш от abc и все. Что Вы имели в виду? Если нужна программа, то можете найти в разделе софт[link1]. Для данных целей очень удобной является программа HashCalc.
"Брюки превращаются... брюки превращаются..." :)
MD5 (abc) = 900150983cd24fb0d6963f7d28e17f72
И я Вам всем тоже!
Про счет md5:
у меня прямо как в кино с брюками получилось с третьей попытки, пока не забыл убрать символ "перевода каретки" в конце строки.
Еще бывают замороки с кодировкой ASCI или UTF
вы не поняли
есть описание на руском но там общее описание "берется строка потом добавляется стока-то нулей..... итд.. итп.."
я про описание на конкретном примере
Просто запишите свои "abc" в шестнадцатеричной форме или в битовом представлении (смотря в каком виде приведены константы в описании), а затем замените получившейся строкой это общее "берётся строка" в описании алгоритма. Это для Вас же будет проще и понятней, чем если нам здесь пытаться "на пальцах" без диаграмм и схем описать этого монстра.
Кстати, md5 и sha1 еще пытаются спасти от коллизий в практических приложениях:
http://eprint.iacr.org/2005/248
А с другой стороны хэш-функции типа SHA-512 возможно уже нельзя обрезать:
http://www.mail-archive.com/cr.....wd.com/msg04468.html[link2]
1. 2 SATtva а что мд5 такой монстр??
2. по поводу взломов мд5 и прочих если кто не видел:
http://www.insidepro.com/gb/rus/index.shtml?page=6
смотрите темы #195 #196
Функция сжатия раунда. Но все шаги надо рассматривать в комплексе.
так это что получается md5 sha у них у всех принцип один блоками
тока у sha подлиннее
или я неправ???
Ну естественно их делали похожими на блочные шифры – блок, раунд, функция раунда.
Входной блок у них у всех одинаковый – 512 бит. Выходной соотвественно разный.
Отличие sha в незначительном усложнении фунции сжатия.