Есть ли коллизии в SHA-1 для сообщения меньше размера хеша (20 байтов)?
Сабж. Является ли SHA-1 обратимой функцией, т.е. x1 != x2 => sha1(x1) != sha1(x2), если длина x1 и x2 <= 20 байтов (размер хеша и внутреннего состояния)?
Если да, для каких еще функций это верно?
Ссылки
[link1] https://en.wikipedia.org/wiki/One-way_compression_function
[link2] https://en.wikipedia.org/wiki/One-way_compression_function#Davies.E2.80.93Meyer
[link3] https://en.wikipedia.org/wiki/One-way_compression_function#Matyas.E2.80.93Meyer.E2.80.93Oseas
[link4] https://en.wikipedia.org/wiki/One-way_compression_function#Miyaguchi.E2.80.93Preneel
[link5] https://en.wikipedia.org/wiki/One-way_compression_function#Hirose
[link6] https://www.pgpru.com/faq/kriptografijaobschievoprosy#h37247-9
[link7] https://ru.wikipedia.org/wiki/Автоморфизм
Во всех (даже идеальных) функциях могут (и по определённой статистической зависимости должны быть) быть коллизии при любом размере сообщения. Вопрос в вероятности их возникновения и отсутствии возможности находить их быстрее простого перебора.
Если использовать в качестве хеш-функции блочный шифр – в нем не будет коллизий, разве не так?
ТС наверно на mtgox смотрит, хотя там sha-2
В нём-то коллизий не будет. А в ней (построенной на его основе хэш-функции) — будут, также как и в любой другой.
В ней тоже не будет, если длина хешируемого сообщения не больше размера блока. hash(x) -> encrypt(const, key=x)
ТС не знает, что это такое.
Так, как вы представляете конструирование хэшей из блочных шифров, так делать нельзя. Неинвертируемость для любого размера сообщения — одно из фундаментальных требований к стойкости.
А как по-вашему в старом ГОСТе из 64-битного шифра получался 256-битный хэш? Там сообщение размазывается линейными функциями с разными константами по 4 блочным шифрованиям ГОСТа.
Тоже касается Whirlpool, Skein.
Можете зайти в вики, в статье One-way compression function[link1] смотреть картинки: Davies–Meyer[link2], Matyas–Meyer–Oseas[link3], Miyaguchi–Preneel[link4], Hirose[link5].
Сообщение используется в качестве ключа.
Из определения идеального блочного шифра следует, что разные ключи могут давать одинаковые пары "открытый текст" — "шифртекст". С заведомо крайне малой, но ненулевой вероятностью. Что и означает коллизии.
В других схемах специально для неинвертируемости (и возможности получения коллизий) в функции сжатия исходное сообщение хотя и не является ключом, а скорее открытым текстом, но ксорится после шифрования со своим исходным значением (до шифрования).
Уберите XOR из представленных конструкций и вы легко получите коллизию к сообщению любой длины. Именно за счёт того, что вы хотите сконструировать функцию вообще без коллизий в пределах блока на основе блочного шифра, вы и получите тривиальное нахождение по-крайней мере одной коллизии за счёт обратного расшифрования всех блоков по цепочке для сообщения любой длины. Т.е. абсолютно дефектный алгоритм хэширования.
Нет.
Для таких, которые можно считать дефектными, нестойкими или неграмотно сконструированными и которые нельзя применять для серьёзных задач.
Функция, вероятность коллизий в которой строго равна нулю даже для сообщений, меньших размера блока, именно к таким и относится. Не говоря уже о том, что это открывает путь к взлому всей конструкции и для больших сообщений.
А я как сказал?
Сообщение x используется в качестве ключа, а вместо открытого текста берется константа или соль, которая добавляется к хешу в открытом виде.
А я как ответил?
Два (или более) разных ключа могут зашифровать одну и ту же константу (открытый текcт) в один и тот же шифртекст. В блочном шифре, да. Что такое модель идеального шифра?[link6].
Следовательно, при такой схеме применения блочного шифра редкие коллизии есть, полной обратимости нет. Всё как положено.
То есть инвертируемость гарантируется для постоянного ключа, но не для постоянного открытого текста? Я помнил про доказательство корректности шифров, но оно относится только к с = f§?
* c = f ( p ) и k=const?
Идеальный блочный шифр — это зависящая от ключа псевдослучайная перестановка (PRP) всех возможных вариантов открытого текста во все возможные варианты шифртекста в пределах блока.
При смене ключа PRP-таблица заполняется заново безо всякой связи с предыдушей, так что могут быть совпадения.
Представим, что размер блока — 4 бита, тогда таблица будет маленькой и например для ключа k1 выпадет такой расклад:
а для ключа k2 — такой:
Если повторения никогда не случаются, значит шифр неидеальный, дефектный и подверженный взлому. Так, на его основе нельзя будет построить переход к псевдослучайной функции PRP → PRF, например в конструкции Дамгарда-Меркла, такой как в SHA-1/SHA-2 — она тоже будет дефектной.
У меня это в голове не помещается, почему хеш функция f: M -> M (входное и выходное множества одинаковы, надеюсь, правильно записал), будет плохой, если она не будет иметь коллизий? Как это противоречит случайному оракулу?
Не надо пытаться сделать конструкцию случайнее, чем случайный оракул и идеальнее, чем идеал :) Не должно быть различителей между идеальной PRF, в которой могут выпадать совпадения, как положено по статистике.
Это просто фундаментальные вещи, нарушение которых рушит всё доказательство стойкости. Возможно, отсутствие коллизий в изначальной конструкции (предусмотренных естественной статистикой) приведёт к тому, что искать сообщение-ключ станет станет быстрее, чем простой перебор n / 2 вариантов (как было бы по парадоксу дней рождения). И тогда, на самом деле, число коллизий будет не строго равно нулю, а недопустимо близко к нулю. И они отыщутся быстрее. Это как невозможные (никогда не выпадающие) дифференциалы в криптоанализе — метод, обратный (или комплементарный) дифференциальному криптоанализу. Ну или совсем художественный пример — помните Шерлока Холмса с методом дедукции? Если мы знаем то, чего не может быть, что можно исключить, значит мы тоже сокращаем искомое множество, оно становится статистически неравномерным.
В SHA-1/SHA-2 есть ряд тонких различителей от RO, которые, казалось бы безобидны, но не позволяют использовать их в качестве потокового шифра, например.
Поэтому все новые алгоритмы проектируются как можно строже по условию RO-неразличимости.
Я бы ещё так пояснил мысль unknown'а:
Если отображение абсолютно случайное, то коллизии в нём будут. Если их нет, между входом и выходом есть взаимно-однозначное соответствие (биекция). Множество всех отображений, переводящих множество само в себя (автоморфмизмы[link7]?), меньше множества всех случайных отображений (которые, в общем случае, небиективны), поэтому и поиск, ограниченный только на автоморфизмы, провести быстрее, чем поиск среди всех случайных отображений. Так понятней?
А это вы не поняли. Для любой хэш-функции множество выходов много меньше множества входов, или лучше так: множество выходов конечно, множество входов бесконечно, поэтому при таком раскладе коллизии будут всегда. Период появления коллизий будет равен мощности множества выходов.
Гость (03/03/2013 14:57), топикстартер спрашивает не про хэш-функции вообще, а про свои конкретные конструкции.
…т.е. его то как раз интересует частный случай, где {множество входов} ≤ {множество выходов}. И он почему-то решил, что там коллизий не должно быть.
Он так считает, потому что полагает функцию сжатия типа SHA алгебраической функцией с аналитически доказанным биективным отображением входов в выходы, а на самом то деле функции типа SHA и т.д. просто другие функции – т.н. случайные, со своими свойствами. Ы?
В основе функции может лежать и такой примитив, например, как кто-то здесь упомянул, блочный шифр. Но режим использования внутри самой функции сжатия (смена ключа) или ряд небольших добавок (простейший XOR входа с выходом) специально делают конструкцию гарантировано небиективной.
https://www.pgpru.com/comment61514
Кажется, понял – если хеш-функция f: M -> N биективная, то выходные значения будут выбираться не из N, а из N – (уже встретившиеся значения), т.е. не будут случайными из N.
где-то тут должно быть M? Или в смысле (N – x), т.е. "минус" встретившиеся значения?
Да.