Сокращение вдвое каждого SHA224 от 2 байтов до 1 байта для уменьшения вдвое длины хэша повышает риск коллизии?

Допустим, у меня есть строки, которые не должны быть обратимыми, и допустим, я использую SHA224 для их хеширования.

Хэш hello world равен 2f05477fc24bb4faefd86517156dafdecec45b8ad3cf2522a563582b и его длина составляет 56 байт.

Что, если я преобразую каждые два символа в их числовое представление и сделаю из них один байт?

В Python я бы сделал что-то вроде этого:

shalist = list("2f05477fc24bb4faefd86517156dafdecec45b8ad3cf2522a563582b")
for first_byte,next_byte in zip(shalist[0::2],shalist[1::2]):
    chr(ord(first_byte)+ord(next_byte))

Результат будет \x98ek\x9d\x95\x96\x96\xc7\xcb\x9ckhf\x9a\xc7\xc9\xc8\x97\x97\x99\x97\xc9gd\x96im\x94. 28 байт. Эффективно уменьшил ввод вдвое.

Теперь, есть ли более высокий риск столкновения хэшей при этом?


hash hash-collision sha2
person Alper Turan    schedule 24.04.2015    source источник
comment
Я почти уверен, что преобразование каждых двух символов, а затем создание из них одного байта - это инъективная функция. Если это так, у него не должно быть более высокого риска столкновения хэшей.   -  person M. Shaw    schedule 25.04.2015

Ответы (1)


arrow_upward
1
arrow_downward

Простой ответ довольно очевиден: да, это увеличивает вероятность столкновения на столько степеней двойки, сколько отсутствующих битов. Для 56 байтов, уменьшенных вдвое до 28 байт, вы получаете увеличение вероятности коллизии 2 ^ (28 * 8). Это все еще оставляет шанс столкновения в 1: 2 ^ (28 * 8).

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

«Идеальный» хэш должен сохранять пропорциональное количество «эффективных» битов, если вы его усекаете. Например, 32-битный результат SHA256 должен иметь ту же «силу», что и 32-битный CRC, хотя могут быть некоторые особые свойства CRC, которые делают его более подходящим для одних целей, в то время как усеченный SHA может быть лучше для других.

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

Давайте уменьшим размер, чтобы понять смысл, и используем 2-байтовый хеш вместо 56. Исходный хеш будет иметь 65536 возможных значений, поэтому, если вы хэшируете больше, чем это количество строк, вы наверняка получите коллизию. Половина этого до 1 байта, и вы получите коллизию после хеширования не более 256 строк, независимо от того, берете ли вы первый или второй байт. Таким образом, ваш шанс столкновения на 256 больше (2 ^ (1 байт * 8 бит)) и составляет 1: 256.

Длинные хэши используются для того, чтобы сделать их перебор непрактичным даже после долгих лет криптоанализа. Когда MD5 был представлен в 1991 году, он считался достаточно безопасным для использования для подписи сертификатов, в 2008 году он считался «сломанным» и не подходящим для использования в целях безопасности. Могут быть разработаны различные методы криптоанализа для снижения «эффективной» стойкости алгоритмов хеширования и шифрования, поэтому чем больше запасных битов (в другом сильном алгоритме), тем более эффективные биты должны оставаться для обеспечения безопасности хэша для всех практических целей.

person Sten Petrov    schedule 24.04.2015