id: Гость   вход   регистрация
текущее время 01:21 31/07/2021
Автор темы: Гость, тема открыта 28/02/2013 20:56 Печать
Категории: разное, сообщество
https://www.pgpru.com/Форум/Криптография/ЕстьЛиКоллизииВSHA-1ДляСообщенияМеньшеРазмераХеша20Байтов
создать
просмотр
ссылки

Есть ли коллизии в SHA-1 для сообщения меньше размера хеша (20 байтов)?


Сабж. Является ли SHA-1 обратимой функцией, т.е. x1 != x2 => sha1(x1) != sha1(x2), если длина x1 и x2 <= 20 байтов (размер хеша и внутреннего состояния)?


Если да, для каких еще функций это верно?


 
На страницу: 1, 2 След.
Комментарии
— unknown (01/03/2013 10:02, исправлен 01/03/2013 11:08)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

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

— Гость (01/03/2013 12:56)   <#>
Если использовать в качестве хеш-функции блочный шифр – в нем не будет коллизий, разве не так?
— Гость (01/03/2013 13:48)   <#>
ТС наверно на mtgox смотрит, хотя там sha-2
— unknown (01/03/2013 14:11, исправлен 01/03/2013 14:12)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

В нём-то коллизий не будет. А в ней (построенной на его основе хэш-функции) — будут, также как и в любой другой.

— Гость (01/03/2013 15:11)   <#>
В ней тоже не будет, если длина хешируемого сообщения не больше размера блока. hash(x) -> encrypt(const, key=x)

ТС не знает, что это такое.
— unknown (01/03/2013 15:56, исправлен 01/03/2013 17:18)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Так, как вы представляете конструирование хэшей из блочных шифров, так делать нельзя. Неинвертируемость для любого размера сообщения — одно из фундаментальных требований к стойкости.


А как по-вашему в старом ГОСТе из 64-битного шифра получался 256-битный хэш? Там сообщение размазывается линейными функциями с разными константами по 4 блочным шифрованиям ГОСТа.


Тоже касается Whirlpool, Skein.


Можете зайти в вики, в статье One-way compression function смотреть картинки: Davies–Meyer, Matyas–Meyer–Oseas, Miyaguchi–Preneel, Hirose.


The Davies–Meyer single-block-length one-way compression function feeds each block of the message (mi) as the key to a block cipher.

Most widely used hash functions, including MD5, SHA-1 and SHA-2 use this construction.

Сообщение используется в качестве ключа.
Из определения идеального блочного шифра следует, что разные ключи могут давать одинаковые пары "открытый текст" — "шифртекст". С заведомо крайне малой, но ненулевой вероятностью. Что и означает коллизии.


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


Уберите XOR из представленных конструкций и вы легко получите коллизию к сообщению любой длины. Именно за счёт того, что вы хотите сконструировать функцию вообще без коллизий в пределах блока на основе блочного шифра, вы и получите тривиальное нахождение по-крайней мере одной коллизии за счёт обратного расшифрования всех блоков по цепочке для сообщения любой длины. Т.е. абсолютно дефектный алгоритм хэширования.



Нет.



Для таких, которые можно считать дефектными, нестойкими или неграмотно сконструированными и которые нельзя применять для серьёзных задач.


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

— топикстартер (01/03/2013 18:22)   <#>

А я как сказал?

Сообщение x используется в качестве ключа, а вместо открытого текста берется константа или соль, которая добавляется к хешу в открытом виде.
— unknown (01/03/2013 20:35, исправлен 01/03/2013 20:45)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

А я как ответил?


Два (или более) разных ключа могут зашифровать одну и ту же константу (открытый текcт) в один и тот же шифртекст. В блочном шифре, да. Что такое модель идеального шифра?.


Следовательно, при такой схеме применения блочного шифра редкие коллизии есть, полной обратимости нет. Всё как положено.

— Гость (02/03/2013 02:38)   <#>
То есть инвертируемость гарантируется для постоянного ключа, но не для постоянного открытого текста? Я помнил про доказательство корректности шифров, но оно относится только к с = f§?
— Гость (02/03/2013 02:39)   <#>
* c = f ( p ) и k=const?
— unknown (02/03/2013 18:51)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Идеальный блочный шифр — это зависящая от ключа псевдослучайная перестановка (PRP) всех возможных вариантов открытого текста во все возможные варианты шифртекста в пределах блока.

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

Представим, что размер блока — 4 бита, тогда таблица будет маленькой и например для ключа k1 выпадет такой расклад:
0123456789ABCDEF
F2A0B8491C53D6E7


а для ключа k2 — такой:
0123456789ABCDEF
2B1E08F975C63AD4

Если повторения никогда не случаются, значит шифр неидеальный, дефектный и подверженный взлому. Так, на его основе нельзя будет построить переход к псевдослучайной функции PRP → PRF, например в конструкции Дамгарда-Меркла, такой как в SHA-1/SHA-2 — она тоже будет дефектной.
— Гость (02/03/2013 19:27)   <#>
У меня это в голове не помещается, почему хеш функция f: M -> M (входное и выходное множества одинаковы, надеюсь, правильно записал), будет плохой, если она не будет иметь коллизий? Как это противоречит случайному оракулу?
— unknown (02/03/2013 19:53)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Не надо пытаться сделать конструкцию случайнее, чем случайный оракул и идеальнее, чем идеал :) Не должно быть различителей между идеальной PRF, в которой могут выпадать совпадения, как положено по статистике.

Это просто фундаментальные вещи, нарушение которых рушит всё доказательство стойкости. Возможно, отсутствие коллизий в изначальной конструкции (предусмотренных естественной статистикой) приведёт к тому, что искать сообщение-ключ станет станет быстрее, чем простой перебор n / 2 вариантов (как было бы по парадоксу дней рождения). И тогда, на самом деле, число коллизий будет не строго равно нулю, а недопустимо близко к нулю. И они отыщутся быстрее. Это как невозможные (никогда не выпадающие) дифференциалы в криптоанализе — метод, обратный (или комплементарный) дифференциальному криптоанализу. Ну или совсем художественный пример — помните Шерлока Холмса с методом дедукции? Если мы знаем то, чего не может быть, что можно исключить, значит мы тоже сокращаем искомое множество, оно становится статистически неравномерным.

В SHA-1/SHA-2 есть ряд тонких различителей от RO, которые, казалось бы безобидны, но не позволяют использовать их в качестве потокового шифра, например.

Поэтому все новые алгоритмы проектируются как можно строже по условию RO-неразличимости.
— antiunknown (02/03/2013 20:38)   <#>
Я бы ещё так пояснил мысль unknown'а:


Если отображение абсолютно случайное, то коллизии в нём будут. Если их нет, между входом и выходом есть взаимно-однозначное соответствие (биекция). Множество всех отображений, переводящих множество само в себя (автоморфмизмы?), меньше множества всех случайных отображений (которые, в общем случае, небиективны), поэтому и поиск, ограниченный только на автоморфизмы, провести быстрее, чем поиск среди всех случайных отображений. Так понятней?
— Гость (03/03/2013 14:57)   <#>
Если отображение абсолютно случайное, то коллизии в нём будут. Если их нет, между входом и выходом есть взаимно-однозначное соответствие (биекция).
А это вы не поняли. Для любой хэш-функции множество выходов много меньше множества входов, или лучше так: множество выходов конечно, множество входов бесконечно, поэтому при таком раскладе коллизии будут всегда. Период появления коллизий будет равен мощности множества выходов.
На страницу: 1, 2 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3