хеш функции
Здравствуйте. :D
К примеру хеш функция имеет разрядность 256 бит, иначе говоря это число ограничено в любом случае, оно вычисляется для текста любой длины, хоть для 1 слова, хоть для 100 страниц. Длинные тексты имеет гораздо большую разрядность, если выразить ее в битах, т.е., как я понимаю, результат хеш функции не может «уместить в себе», даже во всех своих возможных значениях все возможные результаты комбинаций текстов большой длины. Означает ли это, что для любых хеш функций существует обязательное множество коллизий и вопрос открытия методов их определения является делом времени?
комментариев: 9796 документов: 488 редакций: 5664
Рады приветствовать.
Вообще все ваши рассуждения абсолютно правильны, кроме вывода.
Давайте по порядку.
Совершенно верно.
Разумеется. Но это число не должно отличаться от того, как если бы коллизии были случайными совпадениями.
"Естественные коллизии" – они не угрожают стокости хэшей.
По теории вероятности: 1/2^128 для двух произвольно сгенерированных или выбранных текстов. (Парадокс дней рождения).
Один шанс из 340282366920938463463374607431768211456.
И 1/2^256 для подгонки одного текста к другому (или к примеру чужого ключа подписи к своему):
Один шанс из 115792089237316195423570985008687907853269984665640564039457584007913129639936.
Нет не означает. Если вы можете взломать 128-битный шифр быстрее, чем за 2^128 операций, значит он нестойкий.
Если вы можете найти произвольную коллизию хэша быстрее, чем за 2^128 бит операций для 256-битной хэш-функции,
значит она нестойкая (что и произошло c md5 и SHA-1). Но это не значит, что все функции заведомо нестойкие.
Вероятность нахождения коллизии должна быть такой же случайной (Один шанс из 340282366920938463463374607431768211456.) для любых, даже специально побитово подобранных текстов,
как и вероятность случайного нахождения ключа шифра (перебор грубой силой, brute force).
Согласитесь, это пренебрежимо малая вероятность.
Из ваших абсолютно верных рассуждений следует только то, что любой хэш (от себя добавлю: так же как и симметричный шифр) можно "сбрутфорсить", перебирая неограниченно большие массивы данных.
Если есть более короткий способ, то это уже из области криптоанализа, но он строится на других принципах
(дифференциальные свойства функции сжатия к примеру), т.е. не на общих предположениях, что "коллизии есть, их не может не быть". Вот поэтому выход функции сжатия (а тем более хэша в целом) должен выглядеть максимально детерминированно-случайным и непредсказуемым.
Еще раз повторю, наличие "естественных", "неотличимых от случайных" коллизий, не означает, что их автоматически можно найти быстрее, чем нереально долгим перебором.
комментариев: 510 документов: 110 редакций: 75
комментариев: 9796 документов: 488 редакций: 5664
Вы мыслите в правильном направлении, а знания – это вопрос времени и интереса к теме.
комментариев: 9796 документов: 488 редакций: 5664
И во всех работах коллизии были найдены в первом же блоке. Только недавно (вн ачале апреля (2 дня назад на этот момент) были опубликованы данные о нахождении коллизии во втором блоке сообщения: http://eprint.iacr.org/2005/102.
Так что получение естественных коллизий при сворачивании больших текстов в маленькую строку пока вообще не используется в криптоанализе хэшей. Проще изучить работу функции сжатия с маленьким блоком.
Не знаете как в этом вопросе (поиск коллизий) обстоят дела с новыми функциями, примененными в 9-й версии PGP и последних версиях GnuPG: sha-256, sha-384, sha-512, а так же ripemd-160 (последняя по моему не новая)?
комментариев: 9796 документов: 488 редакций: 5664
От функций типа md5-sha-ripemd рано или поздно придется уходить. Пока они должны дать запас практической стойкости на длительное время.
Реальная альтернатива только whirlpool, но она не прошла испытание временем и может иметь нестойкости иного рода. В распространенных утилитах ее нет.
Кроме того, она очень медленная.
Я о статье, этой китайских учёных где написано что найти коллизию в МД5 по их методу можно от 15 до 60 минут компьтерного времени.
комментариев: 9796 документов: 488 редакций: 5664
Мы это уже целый год обсуждаем.
http://www.pgpru.com/forum/viewtopic.php?t=564
И свою позицию по этому вопросу я излагал: функции типа md5-sha-ripemd, это имеется ввиду одно семейство функций. Они все структурно очень похожи. И SHA512 – не решит всех проблем.
Нужно изобретать принципиально новый вид хэшей на неизвестных ранее принципах. Единственная достойная попытка – Whirlpool.
Были еще проекты от Ади Шамира на дискретных логаритмах, но я даже их названия не помню.
А whirlpool прошла хотя бы европейский конкурс cryptoNESSI.
у когонить есть пример как допустим abc превращается в md5 хеш??
комментариев: 510 документов: 110 редакций: 75
Во первых разрешите поприветсвовать вернувшегося в форум unknown, все Вам рады!
Не ясно, так и превращается по моему. Берется хеш от abc и все. Что Вы имели в виду? Если нужна программа, то можете найти в разделе софт. Для данных целей очень удобной является программа HashCalc.
комментариев: 11558 документов: 1036 редакций: 4118
MD5 (abc) = 900150983cd24fb0d6963f7d28e17f72
комментариев: 9796 документов: 488 редакций: 5664
И я Вам всем тоже!
Про счет md5:
у меня прямо как в кино с брюками получилось с третьей попытки, пока не забыл убрать символ "перевода каретки" в конце строки.
Еще бывают замороки с кодировкой ASCI или UTF
есть описание на руском но там общее описание "берется строка потом добавляется стока-то нулей..... итд.. итп.."
я про описание на конкретном примере
комментариев: 11558 документов: 1036 редакций: 4118
комментариев: 9796 документов: 488 редакций: 5664
http://eprint.iacr.org/2005/248