Коллизия — это когда два разных объекта имеют один хеш. Если алгоритм SHA-1 используется для идентификации объекта, то появляется возможность «подсунуть» иной объект так, что «по документам» он будет идентичен оригиналу. И речь идет даже не о взломе шифрованной переписки, хотя SHA-1 по-прежнему довольно активно используется в криптографии. «Объекты» могут быть документами, сертификатами для идентификации определенного сервера: подмена в данном случае открывает широкий простор для кибератак.
Но этот простор — теоретический: подтвердить уязвимость на практике стоит дорого. На этой неделе команда исследователей из Google и голландского CWI Institute сообщили, что они, таки да, смогли (новость, минисайт проекта).
Результатом практической атаки на SHA-1 стало создание двух разных документов в формате PDF, у которых полностью совпадает хеш (пруф — 1,2). Создание документа потребовало огромного объема вычислений — более 9 квинтиллионов операций или 6500 лет процессорного времени (если этот сферический процессор будет трудиться в одиночку, конечно).
Алгоритм поиска коллизий исследователи не раскрывают. Интересно, что в Google решили относиться к этой проблеме, как к любой другой уязвимости: через 90 дней обещают выложить исходный код атаки. Воспользоваться кодом на практике, понятное дело, смогут только очень состоятельные джентльмены. Хотя уже сейчас известно, что примененный метод в 100 тысяч раз быстрее брутфорс-атаки, повторный подход к снаряду обойдется, по мнению диванных аналитиков, в полмиллиона долларов в ценах Амазона. Если потерпеть и использовать только непиковую процессорную мощность, доступную со скидкой, получится около 110 тысяч долларов — в целом похоже на предсказанные полтора года назад $75k.
Реальная атака с использованием коллизий известна в единственном экземпляре: Кибершпионская кампания Flame использовала данный прием для перенаправления жертвы на поддельный сайт при запросе службы Windows Update. Но в том случае речь шла об алгоритме MD5, который «ломается» за секунды на любом оборудовании (но практическая атака все равно требует немало вычислительной мощности). С SHA-1 все несколько сложнее, но после практической реализации ничего интересного уже не произойдет. В ближайшем будущем обнаружат атаку, которая таки использует SHA-1 как один из многих способов взлома; это ненадолго привлечет внимание СМИ и сообщества. А еще лет через пять настанут трудовые будни админов, оставшихся один на один с устаревшей инфраструктурой, которую и выкинуть жалко, и использовать опасно, и заменить не на что.
Google на странице проекта не забывает напомнить, что браузер Chrome помечает соединения с использованием SHA-1 как небезопасные. Это, конечно, здорово, но проблемы если и возникнут, то скорее всего не в браузере.
Ждем
Новость. Подробности в гитхабе исследователя.
Исследователь из Кот-д'Ивуара (!) Пьер Ким сообщил о множественных уязвимостях в роутерах TP-Link C2 и C20i (продаются в том числе и у нас), среди них — серьезная дыра в веб-интерфейсе, позволяющая выполнить на роутере произвольный код. Эксплуатируется уязвимость RCE достаточно просто: нужно залогиниться в веб-интерфейс, зайти на страницу диагностики и выполнить там любую команду, в том числе можно, например, запустить telnetd. Управлять роутером через telnet в дальнейшем можно вообще без авторизации.
Как обычно, в этой истории интереснее не уязвимости (они не так чтобы ужасные — все же требуется логин для веб-интерфейса, но это преодолимо), а процесс починки вендором. К чести TP-Link, патч для уязвимостей вот-вот должен выйти. Но изначально исследователю сообщили в техподдержке, что контакта для информации о дырах в софте у них просто нет. Весь процесс, от обнаружения до (надеемся) патча занял у исследователя полгода.
Исследователи «Лаборатории» обнаружили Windows-ботнет, атакующий IoT-устройства кодом Mirai
Новость. Исследование.
Ну как обнаружили. Ботнет, организованный кем-то, говорящим на китайском, существует уже довольно давно, но относительно недавно он начал использовать печально известный код атаки Mirai на уязвимые Linux-устройства. При этом сам ботнет построен из зараженных Windows-систем. В исследовании экспертов «Лаборатории» приводятся живописные примеры сбора вредоносной кампании, что называется, с миру по нитке. Атакующие слепили ботнет из того, что было: используются методы атаки на серверы MS SQL, вредоносный код подписывается украденными у ряда китайских компаний сертификатами, на пораженные системы внедряются кейлоггеры, все это построено чуть ли не на батниках.
В общем это такой антипод опасных, но красивых, черт возьми, атак, который доказывает, что техника взлома чужих систем не обязана быть совершенной, чтобы быть эффективной. И так сойдет. Стать жертвой угрозы
Древности
«Adolf-475»
Резидентный опасный вирус, стандартно записывается в COM- и OVL-файлы при их загрузке в память. Свою резидентную копию помещает в таблицу векторов прерываний по адресу 0000:0020. Содержит текст: «Adolf Hitler». С вероятностью 1/8 блокирует удаление файлов. Перехватывает int 21h.
Цитата по книге «Компьютерные вирусы в MS-DOS» Евгения Касперского. 1992 год. Страницa 58.
Disclaimer: Данная колонка отражает лишь частное мнение ее автора. Оно может совпадать с позицией компании «Лаборатория Касперского», а может и не совпадать. Тут уж как повезет.
Комментарии (25)
khim
25.02.2017 20:11+2А про cloudflare, раздававший всему Интернету «явки и пароли» ничего… Ну и кто вы после этого?
smind
25.02.2017 22:39Вы забыли упоминуть что сделать коллизию для хэшей md5 и sha-1 одновременно — нереально, т.е. либо тот либо другой станет невалидным. По крайней мере пока это так. и интуиция подсказывает что это будет так очень долго.
MikailBag
25.02.2017 23:03+1теоретически это возможно для любой комбинации любых хэш-функций (Если, конечно, область значения каждой — конечное множество). Перемножаем размеры этих множеств, прибавляем 1, берем столько различных файлов. Хотя бы у двух все эти функции совпадут.
khim
26.02.2017 00:49По крайней мере пока это так. и интуиция подсказывает что это будет так очень долго.
Интуиция в таких делах — плохой помощник. «Прямая» атака на SHA1 — это 2??, «прямая» атака на MD5 — 2??, атака на их комбинацию — это 2??+2?? что почти неотличимо от 2??.
Понятно что в данном случае всё не так плохо и потребует дополнительных исследований, но прогноз — скорее нет. MD5+SHA1 почти наверняка мало отличаются от просто SHA1.
Нужно скорее переходить на SHA2 или SHA3…
homm
26.02.2017 02:16атака на их комбинацию — это 2??+2??
А не 264+80 ли?
khim
26.02.2017 02:24Нет. Почитайте на досуге. Там рассматриваются только «тупой» брутфорс, правда. Теоретически может оказаться что атаку на MD5+SHA1 гораздо сложнее сделать, чем просто SHA1 — но маловероятно…
homm
26.02.2017 14:24А можете объяснить на пальцах, почему так? Я вижу вот как:
Раз мы делаем брутфорс, чтобы найти оригинал сообщения для одного лишь SHA1 в среднем нужно будет перебрать 2?? сообщений. Когда мы найдем хоть одно совпадение, мы можем проверить, удовлетворяет ли это сообщение хэшу MD5. Вероятность, что совпадет, будет 1/2??. Т.е. нам надо будет проверить в среднем 2?? сообщений, уже подошедших для SHA1, т.е. уже являющимися в среднем одним из 2?? оригинальных сообщений. Т.е. в среднем лишь одно из 2???2?? сообщений будет удовлетворять обоим хэшам.khim
26.02.2017 17:52-1Раз мы делаем брутфорс, чтобы найти оригинал сообщения для одного лишь SHA1 в среднем нужно будет перебрать 2?? сообщений.
Уже неверно. Вы бы хоть чуть-чуть подумали, а? Откуда там 64 и 80, если MD5 имеет 128 бит, SHA1 — 160? Для того, чтобы проделать то, что вы описали вам нужно будет 2??? операций для SHA1 и 2??? для MD5. Атаку нахождения прообраза пока даже на MD5 проводить не умеют, куда там SHA1 или MD5!
А чём же тогда сыр-бор? О совсем другой атаке — атаке «дней рождения» связанной с парадоксом дней рождения. Грубо говоря — подобрать пару документов с одинаковой хеш-суммой гораздо проще, чем подобрать документ с заданной хеш-суммой. А в статье, на которую я дал ссылку, объясняется, что создать не два, а много документов с одной хеш-суммой тоже можно — и не сильно сложнее, чем создать два!
Дальше понятно — создаём кучу документов и выбираем пару с одинаковыми MD5+SHA1…smind
27.02.2017 23:58>Дальше понятно — создаём кучу документов и выбираем пару с одинаковыми MD5+SHA1…
Звучит примерно как — возьмем 10^100 документов и выбираем пару с одинаковыми MD5+SHA1… что то мне подсказывает что множества совпадающие хэши MD5 и совпадающие хэши SHA1 очень сильно не захотят пересекаться. И парадокс дней рождения тут совсем негодная аналогия.khim
28.02.2017 00:12Звучит примерно как — возьмем 10^100 документов и выбираем пару с одинаковыми MD5+SHA1…
Вам статью совсем прочитать влом или как? Создаём 2?? документов, имеющих одну и ту же SHA1-сумму. Дальше — с приличной вероятностью там будет MD5-коллизия тоже. И нет, для этого не требуется в 2?? раз больше работы, чем для создания коллизии всего двух документов.
И парадокс дней рождения тут совсем негодная аналогия.
Всё эти атаки построены вокруг него, уж извините.
что то мне подсказывает что множества совпадающие хэши MD5 и совпадающие хэши SHA1 очень сильно не захотят пересекаться.
Если делать «в лоб» — то не захотят. Но используя «парадокс дней рождения» много раз их можно заставить это сделать с приличной вероятностью.
Germanets
28.02.2017 23:38угу, а для SHA-1 и SHA-256 придётся «всего-то» создать 2^128 документов и посчитать для каждого из них хэш SHA-256… Тут тоже хотите сказать, что второй хэш бесполезен и это будет менее затратно, чем проведённая атака?) А если добавить третий пока ещё не сломанный хэш и тем самым ещё увеличить сложность на 2^128?(это всё продолжение в том числе к моему комментарию)
khim
28.02.2017 23:54-1угу, а для 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-битный. И так далее.
Так что возможность перехода от одного хеша к другому — да, полезна. Возможноть использовать одновременно несколько хешей — категорически нет. Как бы парадоксально это ни звучало…
At0mik
02.03.2017 10:26+1Ну так об этом и речь.
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 больше времени на расчет? Вам решать. Я лично для себя решил… что нет.
Germanets
26.02.2017 11:10Судя по всему настало время, когда пользоваться только одним хэшем — небезопасно, нужно использовать 2 или 3, а в логику работы приложения добавить возможность замены очередного «слабого звена» с минимальными на то усилиями…
khim
26.02.2017 18:56Использовать 2 или 3 бессмысленно, как я уже объяснял выше, а вот добавить возможность замены — завсегда полезно.
smind
27.02.2017 23:592-3 хэша не последовательноже а к одному исходному тексту.
khim
28.02.2017 00:18Так точно. Сложность «грубой» атаки возрастёт с 2?? до 160*2??+2?? (был неправ, когда написал 2??+2??, извиняйте), то есть улучшение на 0.3%. Прочитайте же, чёрт побери, статью, если вам это интересно — она достаточно понятным языком написана.
Насколько это затрудняет «улучшенную» атаку пока неясно, но даже если это сделает её в 10 раз более сложной — это всё равно «копейки».
istem
28.02.2017 13:06Вы приводите в пример парадокс дней рождения, но, и по-моему тоже, в данном случае он бессмысленен. Как правило, в реальной ситуации, злоумышленнику не нужно два каких-то случайных совпадения, ему нужно добиться того же хэша, что и хэш конкретного документа или блока данных. А если ещё и учесть, что этот документ или блок данных не случайный набор байт, а упорядоченная структура, то задача усложняется во много раз.
khim
28.02.2017 15:28-1Как правило, в реальной ситуации, злоумышленнику не нужно два каких-то случайных совпадения, ему нужно добиться того же хэша, что и хэш конкретного документа или блока данных.
Это, блин, какой-то разговор слепого с глухим.
f15: Злоумышленники добрались до Гренландии, теперь все живущие на островах уязвимы!
smind: Фигня вопрос, до Австралии не допрывут.
khim: Доплывут. Немного лодку доработают и доплывут
smind: Да нет же, не доплывут. Далеко очень.
khim: Далеко, да, но главное — научиться корабли строить.
istem: Да, но на самом-то деле злоумышленникам нужно на Альфа-Центавра лететь!
Вы приводите в пример парадокс дней рождения, но, и по-моему тоже, в данном случае он бессмысленен.
У меня слов нет, одни междометия. Как вы думаете для каких из этих трех хешей то, о чём вы говорите (по научному это называется атака нахождения прообраза) возможно:
SHA1 — только что «сломан»Правильный ответВы издеватесь? Конечно же нет!
BalinTomsk
На каком-то крипто-форуме видел что для SHA-3 пройдено 11 раундов и собирают деньги на вычислительные мощности и обещают поломать за 3 месяца расчетов.
Greendq
Если они ещё и SHA3 поломают — то вообще будет вешалка, его де только относительно недавно утвердили.
dmitrmax
и тут такой выходит ГОСТ и говорит: «Добрый день» )
Greendq
Я не думаю, что ГОСТ вот прям такой вот растакой. Вполне возможно, что сейчас он на положении «Неуловимого Джо» — так как им пользуются в основном в РФ — то он не так интересен, как другие алгоритмы.