Как стать автором
Обновить

Security Week 08: SHA-1 точно всё, уязвимости в роутерах TP-Link, кроссплатформенный ботнет с кодом Mirai

Время на прочтение 4 мин
Количество просмотров 17K
Всего голосов 26: ↑25 и ↓1 +24
Комментарии 25

Комментарии 25

На каком-то крипто-форуме видел что для SHA-3 пройдено 11 раундов и собирают деньги на вычислительные мощности и обещают поломать за 3 месяца расчетов.
Если они ещё и SHA3 поломают — то вообще будет вешалка, его де только относительно недавно утвердили.
и тут такой выходит ГОСТ и говорит: «Добрый день» )
Я не думаю, что ГОСТ вот прям такой вот растакой. Вполне возможно, что сейчас он на положении «Неуловимого Джо» — так как им пользуются в основном в РФ — то он не так интересен, как другие алгоритмы.
Вы забыли упоминуть что сделать коллизию для хэшей md5 и sha-1 одновременно — нереально, т.е. либо тот либо другой станет невалидным. По крайней мере пока это так. и интуиция подсказывает что это будет так очень долго.

теоретически это возможно для любой комбинации любых хэш-функций (Если, конечно, область значения каждой — конечное множество). Перемножаем размеры этих множеств, прибавляем 1, берем столько различных файлов. Хотя бы у двух все эти функции совпадут.

По крайней мере пока это так. и интуиция подсказывает что это будет так очень долго.
Интуиция в таких делах — плохой помощник. «Прямая» атака на SHA1 — это 2⁸⁰, «прямая» атака на MD5 — 2⁶⁴, атака на их комбинацию — это 2⁶⁴+2⁸⁰ что почти неотличимо от 2⁸⁰.

Понятно что в данном случае всё не так плохо и потребует дополнительных исследований, но прогноз — скорее нет. MD5+SHA1 почти наверняка мало отличаются от просто SHA1.

Нужно скорее переходить на SHA2 или SHA3…
атака на их комбинацию — это 2⁶⁴+2⁸⁰

А не 264+80 ли?

Нет. Почитайте на досуге. Там рассматриваются только «тупой» брутфорс, правда. Теоретически может оказаться что атаку на MD5+SHA1 гораздо сложнее сделать, чем просто SHA1 — но маловероятно…

А можете объяснить на пальцах, почему так? Я вижу вот как:
Раз мы делаем брутфорс, чтобы найти оригинал сообщения для одного лишь 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…
>Дальше понятно — создаём кучу документов и выбираем пару с одинаковыми 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^128?(это всё продолжение в том числе к моему комментарию)
угу, а для 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 больше времени на расчет? Вам решать. Я лично для себя решил… что нет.
SHA-256, безопасней?
Пока считается, что да.
Судя по всему настало время, когда пользоваться только одним хэшем — небезопасно, нужно использовать 2 или 3, а в логику работы приложения добавить возможность замены очередного «слабого звена» с минимальными на то усилиями…
Использовать 2 или 3 бессмысленно, как я уже объяснял выше, а вот добавить возможность замены — завсегда полезно.
2-3 хэша не последовательноже а к одному исходному тексту.
Так точно. Сложность «грубой» атаки возрастёт с 2⁸⁰ до 160*2⁶⁴+2⁸⁰ (был неправ, когда написал 2⁶⁴+2⁸⁰, извиняйте), то есть улучшение на 0.3%. Прочитайте же, чёрт побери, статью, если вам это интересно — она достаточно понятным языком написана.

Насколько это затрудняет «улучшенную» атаку пока неясно, но даже если это сделает её в 10 раз более сложной — это всё равно «копейки».
Вы приводите в пример парадокс дней рождения, но, и по-моему тоже, в данном случае он бессмысленен. Как правило, в реальной ситуации, злоумышленнику не нужно два каких-то случайных совпадения, ему нужно добиться того же хэша, что и хэш конкретного документа или блока данных. А если ещё и учесть, что этот документ или блок данных не случайный набор байт, а упорядоченная структура, то задача усложняется во много раз.
Как правило, в реальной ситуации, злоумышленнику не нужно два каких-то случайных совпадения, ему нужно добиться того же хэша, что и хэш конкретного документа или блока данных.
Это, блин, какой-то разговор слепого с глухим.

f15: Злоумышленники добрались до Гренландии, теперь все живущие на островах уязвимы!
smind: Фигня вопрос, до Австралии не допрывут.
khim: Доплывут. Немного лодку доработают и доплывут
smind: Да нет же, не доплывут. Далеко очень.
khim: Далеко, да, но главное — научиться корабли строить.
istem: Да, но на самом-то деле злоумышленникам нужно на Альфа-Центавра лететь!

Вы приводите в пример парадокс дней рождения, но, и по-моему тоже, в данном случае он бессмысленен.
У меня слов нет, одни междометия. Как вы думаете для каких из этих трех хешей то, о чём вы говорите (по научному это называется атака нахождения прообраза) возможно:

SHA1 — только что «сломан»
Правильный ответ
Вы издеватесь? Конечно же нет!
MD5 — «сломан» давным-давно и заменён на SHA1
Правильный ответ
Нет, нет и нет. Лучшая атака — 2¹²³. Неосуществимо на практике, даже если задействовать все компьютеры Земли.
MD4 — «катастрофически сломан» так давно, что о нём уже все забыли.
Правильный ответ
И всё равно — нет! Лучшая атака требует перебора 2¹⁰², что, конечно, не 2¹²⁸, но только теоретически. На практике никакой возможности провести атаку нахождения прообраза даже на MD4 — невозможно.


А если ещё и учесть, что этот документ или блок данных не случайный набор байт, а упорядоченная структура, то задача усложняется во много раз.
А вот это — как раз неважно, как ни странно. Все атаки требуют не так много бит. Даже в текстовом документе за счёт всяких ZWNJ не так сложно упрятать «немножко мусора». Заметьте, что практическая атака на SHA1 таки порождает для валидных PDF-документа, а не просто какой-то мусор.

P.S. Первое правило криптографии: если «здравый смысл» вам что-то говорит об уязвимости того или иного алгоритма, то вы, почти наверняка, неправы. Даже если вы криптограф. Мир криптографии — увлекателен, но очень, очень странен. Вещи, которые кажутся, на первый взгляд, мелочами — на самом деле могут быть разницей между «фигня вопрос» и «нет, этого мы не сможем сделать никогда», а вещи, которые кажутся важными — могут оказаться ерундой. Вы умудрились наступить в вашем коротком тексте на оба вида граблей одновременно.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий