Можно ли обрезать хэш SHA256 до 128 бит?

MD5 и SHA-1 хэши имеют слабые стороны от столкновений. SHA256 не только выводит 256 бит. Можно ли безопасно взять первый или последний 128 бит и использовать это как хэш? Я знаю, что он будет слабее (потому что у него меньше бит), но в противном случае он будет работать?

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

То, с чем я не могу жить, - это если кто-то может легко, намеренно вставить новый файл с тем же хэшем и теми же начальными символами файла. Я верю в MD5 и SHA1, это возможно.

Ответ 1

Да, это сработает. Теоретически лучше XOR две половины вместе, но даже усеченный SHA256 сильнее, чем MD5. Вы все равно должны считать результат 128-битным хешем, а не 256-битным хэшем.

Моя особая рекомендация в этом конкретном случае заключается в том, чтобы хранить и ссылаться с помощью HASH + uniquifier, где uniquifier - это счет количества различных файлов, которые вы видели с этим хешем раньше. Таким образом, вы абсолютно не упадете, если кто-то попытается сохранить будущие обнаруженные векторы столкновений для SHA256.

Ответ 2

Но стоит ли это? Если у вас есть хэш для каждого файла, у вас по существу есть накладные расходы для каждого файла. Скажем, что каждый файл должен занимать не менее 512 байт (типичный сектор диска) и что вы храните эти хэши достаточно компактно, чтобы не иметь каждого хэша, занимающего гораздо больше, чем размер хэша.

Итак, даже если все ваши файлы имеют 512 байт, самый маленький, вы говорите либо 16 / 512 = 3.1%, либо 32 / 512 = 6.3%. На самом деле, я бы поставил, что ваш средний размер файла выше (если все ваши файлы не являются 1 сектором...), поэтому накладные расходы будут меньше.

Теперь объем пространства, необходимый для хешей, линейно зависит от количества файлов, которые у вас есть. Разве это лишнее пространство стоит того? Даже если у вас были упомянутые триллионы файлов - это 1 000 000 000 000 * 16 = ~29 TiB, что много места, но имейте в виду: ваши данные будут 1 000 000 000 000 * 512 = 465 TiB. На самом деле эти цифры бесполезны, поскольку они все еще 3% или 6% накладные расходы. Но на этом уровне, где у вас есть половина петабайта памяти, имеет значение 15 терабайт? На любом уровне экономия 3% означает что-нибудь? И помните, если они больше, вы экономите меньше. (Который, вероятно, это: удача, получающая размер сектора 512 байт при этом размере жесткого диска.)

Итак, стоит ли это 3% или меньше дисковой экономии, что потенциально опасно для безопасности. (Который я оставлю без ответа, так как это не моя чашка чая.)

В качестве альтернативы вы могли бы, скажем, группировать файлы вместе логически, чтобы у вас было меньше файлов? (Я имею в виду, если у вас есть триллионы 512-байтных файлов, действительно ли вы хотите хэш каждый байт на диске?)

Ответ 3

Да, это сработает.

Для записи есть известные атаки на столкновение с использованием MD5, но атаки SHA-1 на данный момент полностью теоретические (никакого столкновения SHA-1 никогда не было найдено).