Можно ли усечь хэш SHA256 до 128 бит?

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

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

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


md5 sha256 hash sha
person Sunny Hirai    schedule 11.06.2010    source источник
comment
Я думал, что парадокс дня рождения даст меньше шансов, но Википедия согласна с вами: en.wikipedia .org / wiki / Birthday_paradox # Probability_table   -  person Mark Ransom    schedule 12.06.2010
comment
Связанный вопрос: stackoverflow.com/questions/2256423/   -  person Shadok    schedule 01.02.2012
comment
См. Также: security.stackexchange.com/questions/18385/   -  person Luc    schedule 10.04.2013
comment
Итак ... не делая еще одной расплывчатой ​​ссылки на статью в Википедии о парадоксе дня рождения, может ли кто-нибудь вкратце подвести итог, относительно нетехническим языком, почему можно обрезать вывод хеш-алгоритма? Если это такая хорошая идея, почему хеш-алгоритм просто не избавит вас от проблем и не усечет себя? Другими словами, алгоритм хеширования производит результат, который гарантированно в целом в пределах параметров алгоритма будет уникальным для каждого входа. Гарантирует ли сам алгоритм сам, что первые 128 символов будут уникальными?   -  person Craig    schedule 15.04.2013
comment
Можете ли вы действительно сделать вывод, что можно усечь вывод SHA-256 из статьи о парадоксе дня рождения, в которой обсуждается хеширование в целом, но нигде не упоминаются эффекты усечения выходных данных алгоритмов хеширования, не говоря уже об эффектах усечения выходных данных алгоритмов хеширования. какие-нибудь специфические алгоритмы хеширования? SHA-256 дает 256-битный результат, да? Он не выводит 128-битный результат. Где авторы алгоритма заявляют, что если вы произвольно отбрасываете 128 бит результата, вы в безопасности? Чем усеченный SHA-256 безопаснее, чем полный 160-битный SHA-1, если на то пошло?   -  person Craig    schedule 15.04.2013

Ответы (3)


arrow_upward
8
arrow_downward

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

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

person Joshua    schedule 11.06.2010
comment
Я не могу найти никакой ссылки, в которой говорится, что теоретически лучше выполнить XOR половинок вместе, и я скептически отношусь к этому. Интересная идея с унитаром. - person President James K. Polk; 12.06.2010
comment
GregS: некоторые из ранних атак на MD5 приводили к конфликтам на большей части хэша с одной или двумя разными ячейками. - person Joshua; 12.06.2010
comment
@Joshua Это похоже на то, что эмпирически (а не теоретически) лучше. Меня также интересует ссылка на то, почему XOR было бы лучше. - person Drux; 03.02.2015
comment
Вам не нужно выполнять XOR двух половин, официальный стандарт говорит, что вы можете просто взять крайние левые 128 бит (см. этот ответ < / а>). - person Eric Mutta; 19.04.2021

arrow_upward
3
arrow_downward

Но стоит ли оно того? Если у вас есть хэш для каждого файла, то у вас, по сути, есть накладные расходы для каждого файла. Предположим, что каждый файл должен занимать не менее 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 байт, вы действительно хотите хешировать каждый байт на диске?)

person Thanatos    schedule 11.06.2010
comment
На самом деле не отвечает на вопрос. Имеет ли это? - person ALOToverflow; 18.04.2013
comment
@ALOToverflow: Нет, это не так. Но это не значит, что это не актуально: иногда сомнение в посылке вопроса может привести к лучшему решению либо для автора, либо для широкой аудитории, читающей вопрос позже через Google, либо для того и другого: SO здесь, чтобы быть полезным, так что я считаю такие посты стоящими. Возможно, мне следовало сильнее подчеркнуть аспект безопасности: по моему опыту, в большинстве случаев, связанных с криптографией, если вы отклонитесь от проторенного пути, как правило, происходят странные (и обычно плохие) вещи. Стоит ли небольшая экономия на диске? (Может быть, но это зависит от варианта использования.) - person Thanatos; 19.04.2013

arrow_upward
0
arrow_downward

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

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

person BlueRaja - Danny Pflughoeft    schedule 11.06.2010
comment
SHA-256 (хеш, о котором говорит OP) - это SHA-2, а не SHA-1 - я думаю? И пока никаких коллизий для SHA-2 не обнаружено .. даже теоретически. - person user353297; 12.06.2010
comment
@ blueraja- не совсем так. проверьте: people.csail.mit.edu/yiqun/SHA1AttackProceedingVersion.pdf - person Yuval Adam; 12.06.2010
comment
@ mrl33t: Нет; SHA-1 имеет теоретические уязвимости, но SHA-256 (который является частью набора SHA-2) даже не имеет их. Учитывая, что размер хэшей SHA-256 в 2 ^ 128 раз БОЛЬШЕ, чем SHA-1, а SHA-2 считается теоретически более безопасным, маловероятно, что в ближайшее время возникнут конфликты SHA-256. - person BlueRaja - Danny Pflughoeft; 12.06.2010
comment
@Yuval: Да, это теоретическая уязвимость, о которой я упоминал (на самом деле, есть более свежая статья, которая еще больше сокращает пространство поиска). Тем не менее, то, что я сказал, было полностью правдой: до сих пор нет известных конфликтов для SHA-1. - person BlueRaja - Danny Pflughoeft; 12.06.2010
comment
В 2 ^ 128 раз больше? ВАУ! ;) Я думаю, вы могли бы проверить свою математику или свои формулировки ... - person Dan McGrath; 12.06.2010
comment
@Dan: упс, я имел в виду область поиска в 2 ^ 96 раз больше, извините (2 ^ 96 * 2 ^ 160 = 2 ^ 256) - person BlueRaja - Danny Pflughoeft; 12.06.2010
comment
Конфликт SHA-1 был обнаружен ранее в этом году: shattered.io - person Palec; 27.08.2017