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

Question

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

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

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

Answer 1

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

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

Answer 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 байт, вы действительно хотите хешировать каждый байт на диске?)

Answer 3

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

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