Есть ли коллизии в SHA-1 для сообщения меньше размера хеша (20 байтов)?
Сабж. Является ли SHA-1 обратимой функцией, т.е. x1 != x2 => sha1(x1) != sha1(x2), если длина x1 и x2 <= 20 байтов (размер хеша и внутреннего состояния)?
Если да, для каких еще функций это верно?
комментариев: 9796 документов: 488 редакций: 5664
Во всех (даже идеальных) функциях могут (и по определённой статистической зависимости должны быть) быть коллизии при любом размере сообщения. Вопрос в вероятности их возникновения и отсутствии возможности находить их быстрее простого перебора.
комментариев: 9796 документов: 488 редакций: 5664
В нём-то коллизий не будет. А в ней (построенной на его основе хэш-функции) — будут, также как и в любой другой.
ТС не знает, что это такое.
комментариев: 9796 документов: 488 редакций: 5664
Так, как вы представляете конструирование хэшей из блочных шифров, так делать нельзя. Неинвертируемость для любого размера сообщения — одно из фундаментальных требований к стойкости.
А как по-вашему в старом ГОСТе из 64-битного шифра получался 256-битный хэш? Там сообщение размазывается линейными функциями с разными константами по 4 блочным шифрованиям ГОСТа.
Тоже касается Whirlpool, Skein.
Можете зайти в вики, в статье One-way compression function смотреть картинки: Davies–Meyer, Matyas–Meyer–Oseas, Miyaguchi–Preneel, Hirose.
Сообщение используется в качестве ключа.
Из определения идеального блочного шифра следует, что разные ключи могут давать одинаковые пары "открытый текст" — "шифртекст". С заведомо крайне малой, но ненулевой вероятностью. Что и означает коллизии.
В других схемах специально для неинвертируемости (и возможности получения коллизий) в функции сжатия исходное сообщение хотя и не является ключом, а скорее открытым текстом, но ксорится после шифрования со своим исходным значением (до шифрования).
Уберите XOR из представленных конструкций и вы легко получите коллизию к сообщению любой длины. Именно за счёт того, что вы хотите сконструировать функцию вообще без коллизий в пределах блока на основе блочного шифра, вы и получите тривиальное нахождение по-крайней мере одной коллизии за счёт обратного расшифрования всех блоков по цепочке для сообщения любой длины. Т.е. абсолютно дефектный алгоритм хэширования.
Нет.
Для таких, которые можно считать дефектными, нестойкими или неграмотно сконструированными и которые нельзя применять для серьёзных задач.
Функция, вероятность коллизий в которой строго равна нулю даже для сообщений, меньших размера блока, именно к таким и относится. Не говоря уже о том, что это открывает путь к взлому всей конструкции и для больших сообщений.
А я как сказал?
Сообщение x используется в качестве ключа, а вместо открытого текста берется константа или соль, которая добавляется к хешу в открытом виде.
комментариев: 9796 документов: 488 редакций: 5664
А я как ответил?
Два (или более) разных ключа могут зашифровать одну и ту же константу (открытый текcт) в один и тот же шифртекст. В блочном шифре, да. Что такое модель идеального шифра?.
Следовательно, при такой схеме применения блочного шифра редкие коллизии есть, полной обратимости нет. Всё как положено.
комментариев: 9796 документов: 488 редакций: 5664
При смене ключа PRP-таблица заполняется заново безо всякой связи с предыдушей, так что могут быть совпадения.
Представим, что размер блока — 4 бита, тогда таблица будет маленькой и например для ключа k1 выпадет такой расклад:
а для ключа k2 — такой:
Если повторения никогда не случаются, значит шифр неидеальный, дефектный и подверженный взлому. Так, на его основе нельзя будет построить переход к псевдослучайной функции PRP → PRF, например в конструкции Дамгарда-Меркла, такой как в SHA-1/SHA-2 — она тоже будет дефектной.
комментариев: 9796 документов: 488 редакций: 5664
Это просто фундаментальные вещи, нарушение которых рушит всё доказательство стойкости. Возможно, отсутствие коллизий в изначальной конструкции (предусмотренных естественной статистикой) приведёт к тому, что искать сообщение-ключ станет станет быстрее, чем простой перебор n / 2 вариантов (как было бы по парадоксу дней рождения). И тогда, на самом деле, число коллизий будет не строго равно нулю, а недопустимо близко к нулю. И они отыщутся быстрее. Это как невозможные (никогда не выпадающие) дифференциалы в криптоанализе — метод, обратный (или комплементарный) дифференциальному криптоанализу. Ну или совсем художественный пример — помните Шерлока Холмса с методом дедукции? Если мы знаем то, чего не может быть, что можно исключить, значит мы тоже сокращаем искомое множество, оно становится статистически неравномерным.
В SHA-1/SHA-2 есть ряд тонких различителей от RO, которые, казалось бы безобидны, но не позволяют использовать их в качестве потокового шифра, например.
Поэтому все новые алгоритмы проектируются как можно строже по условию RO-неразличимости.
Если отображение абсолютно случайное, то коллизии в нём будут. Если их нет, между входом и выходом есть взаимно-однозначное соответствие (биекция). Множество всех отображений, переводящих множество само в себя (автоморфмизмы?), меньше множества всех случайных отображений (которые, в общем случае, небиективны), поэтому и поиск, ограниченный только на автоморфизмы, провести быстрее, чем поиск среди всех случайных отображений. Так понятней?