512-битный хэш против 4-х 128-битного

Question

Интересно, что я не нашел достаточно информации относительно какого-либо теста или эксперимента вероятности столкновения одиночного 512-битного хэша, такого как гидромассаж, против конкатенации 4-х 128-битных хэшей, как md5, sha1 и т. Д.

Возможность появления четырех 128-битных хэшей выглядит менее вероятной, чем одиночная 512-битная, когда данные, для которых выполняется хеширование, имеют небольшой размер, в среднем всего 100 символов.

Но это только кажущаяся догадка без основания, потому что я не выполнил никакого теста. Что вы думаете об этом?

Редактировать это как 512-битный хэш против 128-битного. 128-битный хэш. 128-битный хэш. 128-битный хеш (4 128-битных сцепленных)

Edit2 Я хочу использовать хэш для этого индекса на URL или хэширования с учетом оперативной памяти и цель состоит в том, чтобы свести к минимуму возможность коллизий, потому что я хочу установить столбец хеш-функции как уникальный вместо столбца URL.

Edit3 Обратите внимание, что цель этого вопроса - найти способ минимизировать вероятность столкновения. Сказав это, почему я должен сосредоточиться больше на минимизации возможности столкновения? Вот мое описание Edit2, которое приводит к поиску решения использовать меньше оперативной памяти. Таким образом, интересы сводятся к минимизации коллизий и снижению использования оперативной памяти. Но основное внимание в этом вопросе уделяется снижению вероятности столкновения.

Answer 1

Звучит так, как будто вы хотите сравнить поведение столкновения:

hash512(x)

с поведением столкновения:

hash128_a(x) . hash128_b(x) . hash128_c(x) . hash128_d(x)

, где "." обозначает конкатенацию, а hash128_a, hash128_b и т. Д. - четыре различных 128-битных алгоритма хеширования.

Ответ: это полностью зависит от свойств отдельных хэшей.

Предположим, например, что 128-битные хеш-функции могут быть реализованы как:

uint128_t hash128_a(T x)   { return hash512(x)[  0:127]; }
uint128_t hash128_b(T x)   { return hash512(x)[128:255]; }
uint128_t hash128_c(T x)   { return hash512(x)[256:383]; }
uint128_t hash128_d(T x)   { return hash512(x)[384:511]; }

В этом случае производительность будет идентичной.

Answer 2

Классическая статья для чтения по этому вопросу написана Хохом и Шамиром . Он основан на предыдущих открытиях, особенно Жу. Суть в следующем: если вы берете четыре хеш-функции с 128-битным выходом, а четыре хеш-функции используют конструкцию Merkle-Damgård , то поиск коллизии для всего 512-битного выхода не сложнее, чем найти коллизию для одной из хеш-функций. MD5, SHA-1 ... использовать конструкцию MD.

С другой стороны, если некоторые из ваших хеш-функций используют отличную структуру, в частности с более широким рабочим состоянием, конкатенация может дать более сильную функцию. См. Пример из @Oli: если все четыре функции - SHA-512 с некоторой операцией на выходе, то сцепленная хеш-функция может быть простой SHA-512.

Единственная надежная вещь в отношении конкатенации четырех хеш-функций заключается в том, что результат будет не менее устойчивым к коллизиям, чем самая сильная из четырех хеш-функций. Это использовалось в SSL / TLS , который, до версии 1.1, внутренне использует одновременно и MD5, и SHA-1, пытаясь противостоять разрывам на любом из них.

Answer 3

512 бит - это 512 бит.Разница лишь в недостатках хэшей.Наилучшим общим хэшем будет 512 с использованием лучшего доступного алгоритма.

Изменить, чтобы добавить пояснение, потому что это слишком долго для комментария:

Идеальный контент хеш-картравномерно на х бит.Если у вас есть 4 (полностью независимых) х-битных хэша, это позволяет равномерно отобразить файл на 4х бит;4-битный хэш все равно отображает один и тот же файл на 4-битные.4х бит - это 4х бит;до тех пор, пока он абсолютно однороден, не имеет значения, исходит ли оно от одной (4x) хеш-функции или 4 (x).Однако ни один хэш не может быть абсолютно идеальным, поэтому вы хотите получить наиболее равномерное распределение, и если вы используете 4 разных функции, только 1 может быть ближайшей к оптимальной, поэтому у вас есть x оптимальных битов и 3x неоптимальных, тогда как один алгоритм может охватыватьвсе 4x пространства с наиболее оптимальным распределением.

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

Answer 4

Если вы сравниваете объединение четырех разных «идеальных» 128-битных алгоритмов хеширования с одним идеальным 512-битным алгоритмом хеширования, то да, оба метода предоставят вам одинаковую вероятность коллизии.Использование md5 облегчит взлом хэша.Если злоумышленник, например, знает, что вы выполняете md5 + md5 с солью + md5 с другой солью ... тогда это будет гораздо проще взломать, как и столкновение md5. Смотрите здесь для получения дополнительной информации о хэш-функциях, которые совершали атаки.