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

Похоже, вы хотите сравнить поведение при столкновении:

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]; }

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

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

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

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

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

Отредактируйте, чтобы добавить пояснение, потому что он слишком длинный для комментария:

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

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

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