Уменьшение размера хэша

Question

Если у меня есть некоторые данные, которые я хэширования с SHA256, как это: - хэш = SHA256 (данные)

А затем скопировать только первые 8 байт хэша вместо целых 32 байта, как легко найти хэш-столкновение с разными данными? Это 2^64 или 2^32?

Если мне нужно уменьшить хэш некоторых данных до меньшего размера (n бит), есть ли способ обеспечить пространство поиска 2^n?

Answer 1

Я думаю, вы действительно заинтересованы в трех вещах.

Первое, что вам нужно понять, это распределение энтропии хэша. Если выход хеш-функции равен n -биты длинны, то максимальная энтропия равна n бит. Обратите внимание, что я говорю максимум; вам никогда не будет гарантировано n бит энтропии. Аналогичным образом, если вы усекаете хэш-вывод до n/4 битов, у вас не гарантируется наличие 2 ^n/4 бит энтропии в результате. SHA-256 - это довольно uniformly distributed, что частично означает, что у вас вряд ли будет больше энтропии в высоких битах, чем у младших бит (или наоборот).

Однако информация об этом разрежена, поскольку функция хэша предназначена для использования со всем ее хэш-выходом. Если вам нужен только 8-байтовый хэш-вывод, тогда вам может не понадобиться криптографическая хеш-функция и может рассмотреть other algorithms. (Дело в том, что если вам нужна криптографическая хеш-функция, тогда вам нужно столько битов, сколько она может вам дать, так как укорачивание вывода ослабляет безопасность функции.)

Во-вторых, поисковое пространство: это вообще не зависящий от хэш-функции. Поиск ввода, который создает заданный вывод хеш-функции, более известен как Brute-Force attack. Количество входов, которые нужно будет искать, не зависит от самой функции хэша; как он мог? Каждый вывод функции хэш-функции одинаков: каждый выход SHA-256 имеет 256 бит. Если вам просто нужно столкнуться, вы можете найти один конкретный вход, который сгенерировал каждый возможный выход из 256 бит. К сожалению, это займет минимальное пространство хранения 256 * 2 ≈ 3 * 10 только для самих значений хэша (т. Е. Не считая входов, необходимых для их создания), что значительно затмевает entire hard drive capacity of the entire world.

Следовательно, пространство поиска зависит от сложности и длины ввода хеш-функции. Если ваши данные представляют собой 8-символьные длинные строки ASCII, то вы, как правило, гарантированно никогда не сталкиваетесь с столкновением, BUT пространство поиска для этих значений хэша только 2 ^{7 * 8} ≈ 7.2 * 10 , которые, возможно, могут быть найдены на вашем компьютере через несколько минут. В конце концов, вам не нужно искать столкновение, если вы можете сами найти исходный вход. Вот почему salts важны для криптографии.

В-третьих, вам интересно знать сопротивление столкновению. Как GregS 'linked article points out, сопротивление столкновения пространства намного ограничено, чем входное пространство поиска из-за pigeonhole principle.

Каждая хеш-функция с большим количеством входов, чем выходы, обязательно будет иметь коллизии.Рассмотрим хеш-функцию, такую ​​как SHA-256, которая выдает 256 бит вывода из произвольно большого ввода. Так как он должен генерировать один из двух выходов для каждого члена гораздо большего набора входов, принцип pigeonhole гарантирует, что некоторые входы будут хешировать на одном выходе. Сопротивление столкновению не означает, что никаких столкновений не существует; просто их трудно найти.

«День рождения парадокс» устанавливает верхнюю границу на сопротивление столкновения: если хэш-функция производит N битов выходных данных, злоумышленник, который вычисляет «только» 2 ^N/2 (или SQRT (2 ^Н)) хэш-операции на случайном входе, вероятно, найдут два совпадающих выхода. Если есть более простой способ, чем эта атака грубой силы, это обычно считается недостатком хеш-функции.

Так подумайте, что произойдет, если вы изучите и сохраните только первые 8 байт (одна четверть) вашего вывода. Сопротивление столкновению снизилось с 2 ^256/2 = 2 до 2 ^64/2 = 2 . Насколько меньше 2 than 2 ? Это, как выясняется, намного меньше, примерно 0,0000000000000000000000000001% от размера в лучшем случае.