Comments 25
теоретически это возможно для любой комбинации любых хэш-функций (Если, конечно, область значения каждой — конечное множество). Перемножаем размеры этих множеств, прибавляем 1, берем столько различных файлов. Хотя бы у двух все эти функции совпадут.
По крайней мере пока это так. и интуиция подсказывает что это будет так очень долго.Интуиция в таких делах — плохой помощник. «Прямая» атака на SHA1 — это 2⁸⁰, «прямая» атака на MD5 — 2⁶⁴, атака на их комбинацию — это 2⁶⁴+2⁸⁰ что почти неотличимо от 2⁸⁰.
Понятно что в данном случае всё не так плохо и потребует дополнительных исследований, но прогноз — скорее нет. MD5+SHA1 почти наверняка мало отличаются от просто SHA1.
Нужно скорее переходить на SHA2 или SHA3…
атака на их комбинацию — это 2⁶⁴+2⁸⁰
А не 264+80 ли?
А можете объяснить на пальцах, почему так? Я вижу вот как:
Раз мы делаем брутфорс, чтобы найти оригинал сообщения для одного лишь SHA1 в среднем нужно будет перебрать 2⁸⁰ сообщений. Когда мы найдем хоть одно совпадение, мы можем проверить, удовлетворяет ли это сообщение хэшу MD5. Вероятность, что совпадет, будет 1/2⁶⁴. Т.е. нам надо будет проверить в среднем 2⁶⁴ сообщений, уже подошедших для SHA1, т.е. уже являющимися в среднем одним из 2⁸⁰ оригинальных сообщений. Т.е. в среднем лишь одно из 2⁸⁰×2⁶⁴ сообщений будет удовлетворять обоим хэшам.
Раз мы делаем брутфорс, чтобы найти оригинал сообщения для одного лишь SHA1 в среднем нужно будет перебрать 2⁸⁰ сообщений.Уже неверно. Вы бы хоть чуть-чуть подумали, а? Откуда там 64 и 80, если MD5 имеет 128 бит, SHA1 — 160? Для того, чтобы проделать то, что вы описали вам нужно будет 2¹⁶⁰ операций для SHA1 и 2¹²⁸ для MD5. Атаку нахождения прообраза пока даже на MD5 проводить не умеют, куда там SHA1 или MD5!
А чём же тогда сыр-бор? О совсем другой атаке — атаке «дней рождения» связанной с парадоксом дней рождения. Грубо говоря — подобрать пару документов с одинаковой хеш-суммой гораздо проще, чем подобрать документ с заданной хеш-суммой. А в статье, на которую я дал ссылку, объясняется, что создать не два, а много документов с одной хеш-суммой тоже можно — и не сильно сложнее, чем создать два!
Дальше понятно — создаём кучу документов и выбираем пару с одинаковыми MD5+SHA1…
Звучит примерно как — возьмем 10^100 документов и выбираем пару с одинаковыми MD5+SHA1… что то мне подсказывает что множества совпадающие хэши MD5 и совпадающие хэши SHA1 очень сильно не захотят пересекаться. И парадокс дней рождения тут совсем негодная аналогия.
Звучит примерно как — возьмем 10^100 документов и выбираем пару с одинаковыми MD5+SHA1…Вам статью совсем прочитать влом или как? Создаём 2⁶⁴ документов, имеющих одну и ту же SHA1-сумму. Дальше — с приличной вероятностью там будет MD5-коллизия тоже. И нет, для этого не требуется в 2⁶⁴ раз больше работы, чем для создания коллизии всего двух документов.
И парадокс дней рождения тут совсем негодная аналогия.Всё эти атаки построены вокруг него, уж извините.
что то мне подсказывает что множества совпадающие хэши MD5 и совпадающие хэши SHA1 очень сильно не захотят пересекаться.Если делать «в лоб» — то не захотят. Но используя «парадокс дней рождения» много раз их можно заставить это сделать с приличной вероятностью.
угу, а для SHA-1 и SHA-256 придётся «всего-то» создать 2^128 документов и посчитать для каждого из них хэш SHA-256…Не 2¹²⁸, а 2⁸⁰. Брать нужно всегда меньший из хешей. И, что удивительно, для этого потребуется работы всего лишь в 128 раз больше, чем для порождения пары документов, то есть не 2⁸⁰, а 128*2⁸⁰! На фоне того, что вам потребуется 2¹²⁸ операций чтобы просто породить одну коллизию SHA-256 — это «копейки».
Тут тоже хотите сказать, что второй хэш бесполезен и это будет менее затратно, чем проведённая атака?Да, практически бесполезен. Добавляет к сложности атаки на SHA-256 доли процентов.
А если добавить третий пока ещё не сломанный хэш и тем самым ещё увеличить сложность на 2^128Получите существенный проигрыш к памяти и мизерное увеличение сложности взлома. Гораздо, гораздо лучше взять просто SHA-384. В триллионы триллионов раз лучше!
это всё продолжение в том числе к моему комментариюВаш комментарий как был чушью, так и остался. Прочитайте же, наконец, статью!
В случае с «хорошими» хешами (без специальных уязвимостей) одновременное применение хешей разной «мощности» смысла не имеет. И даже хуже: вместо 10 разных 128-битных хешей гораздо, гораздо надёжнее использовать один 160-битный. А вместо 10 разных 160-битных — один 192-битный. И так далее.
Так что возможность перехода от одного хеша к другому — да, полезна. Возможноть использовать одновременно несколько хешей — категорически нет. Как бы парадоксально это ни звучало…
2 хэша, безусловно, не хуже чем один.
Если у вас (например) SHA1 и SHA256… и, вдруг, взломают SHA1… второй хэш позволят сидеть спокойно.
НО! при этом, речь совсем о другом. Предположим что хэши не взломаны вообще. В таком случае, сложность находки коллизии в
— MD5: 2^64
— SHA1: 2^80
— SHA256: 2^128
— MD5 + SHA1: 2^80… а не 2^144! (как большинство думает)
— MD5 + SHA256: 2^128… а не 2^208
— MD5 + SHA1 + SHA256: 2^128… а не 2^272
Так что да, в какой-то степени ваш MD5 + SHA1 + SHA256 бесполезен.
Сложность находки коллизии в MD5 + SHA1 + SHA256 почти не отличить от сложности SHA256.
Этот каскад интересен только если (очень неожиданно) взломают SHA256 и снизят сложность находки коллизии до менее чем 2^79. В таком случае, сложность SHA1 в 2^80 позволит сидеть спокойно.
Дело в том что такие «неожиданные взломы» вряд ли будут. Математики находят теоретическую брешь за долго до того как её начинают эксплуатировать на практике.
В SHA1 уже лет 10 известно что есть проблема, но только сейчас нашли коллизию.
Стоит ли «MD5 + SHA1 + SHA256 » того что ваш сервер будет тратить в 2.5 больше времени на расчет? Вам решать. Я лично для себя решил… что нет.
Насколько это затрудняет «улучшенную» атаку пока неясно, но даже если это сделает её в 10 раз более сложной — это всё равно «копейки».
Как правило, в реальной ситуации, злоумышленнику не нужно два каких-то случайных совпадения, ему нужно добиться того же хэша, что и хэш конкретного документа или блока данных.Это, блин, какой-то разговор слепого с глухим.
f15: Злоумышленники добрались до Гренландии, теперь все живущие на островах уязвимы!
smind: Фигня вопрос, до Австралии не допрывут.
khim: Доплывут. Немного лодку доработают и доплывут
smind: Да нет же, не доплывут. Далеко очень.
khim: Далеко, да, но главное — научиться корабли строить.
istem: Да, но на самом-то деле злоумышленникам нужно на Альфа-Центавра лететь!
Вы приводите в пример парадокс дней рождения, но, и по-моему тоже, в данном случае он бессмысленен.У меня слов нет, одни междометия. Как вы думаете для каких из этих трех хешей то, о чём вы говорите (по научному это называется атака нахождения прообраза) возможно:
SHA1 — только что «сломан»
А если ещё и учесть, что этот документ или блок данных не случайный набор байт, а упорядоченная структура, то задача усложняется во много раз.А вот это — как раз неважно, как ни странно. Все атаки требуют не так много бит. Даже в текстовом документе за счёт всяких ZWNJ не так сложно упрятать «немножко мусора». Заметьте, что практическая атака на SHA1 таки порождает для валидных PDF-документа, а не просто какой-то мусор.
P.S. Первое правило криптографии: если «здравый смысл» вам что-то говорит об уязвимости того или иного алгоритма, то вы, почти наверняка, неправы. Даже если вы криптограф. Мир криптографии — увлекателен, но очень, очень странен. Вещи, которые кажутся, на первый взгляд, мелочами — на самом деле могут быть разницей между «фигня вопрос» и «нет, этого мы не сможем сделать никогда», а вещи, которые кажутся важными — могут оказаться ерундой. Вы умудрились наступить в вашем коротком тексте на оба вида граблей одновременно.
Security Week 08: SHA-1 точно всё, уязвимости в роутерах TP-Link, кроссплатформенный ботнет с кодом Mirai