SHA1 мёртв, похороны в мае

Статьи, хлынувшие на страницы посвящённых информационной безопасности изданий 23 февраля, напоминали по структуре некрологи. Родился в 1993 году, трудился на благо до 2012, несмотря на сомнения в здоровье, высказанные в 2005 году и укреплявшиеся до 2015 года. Ну а сейчас аналитики говорят о последнем гвозде в гроб покойного. Для человека такой трудовой стаж совершенно обычен, но вот для криптографического алгоритма это срок солидный. Итак, сегодня мы начинаем церемонию предварительного прощания с алгоритмом хеширования SHA1.

Алгоритм, как и полагается алгоритму хеширования, превращал любой набор данных в 160-битное число. Таким образом, его стойкость к вычислениям коллизий (то есть двух файлов, при обработке которых получится одинаковый результат) оценивалась как 2^80 вычислений, что представляет собой очень большое число даже для современных компьютеров. В течение многих лет эта оценка улучшалась, и в какой-то момент снизилась до 2^63, что по-прежнему очень много.

Потом, в 2015 году, случился прорыв. Тогда удалось построить так называемые freestart collisions для алгоритма SHA1. Поменяв входные параметры алгоритма, удалось подобрать пару сообщений, хеш от которых совпадает. Тогда же была дана оценка стоимости нахождения полноценной коллизии для алгоритма — примерно 100 тысяч долларов. С этого момента закат некогда распространённого алгоритма ускорился. С начала 2017 года браузеры перестали доверять сертификатам, подписанным с помощью SHA1 (Firefox сделал это уже после появления публикации о найденных коллизиях). Так, сейчас в Рунете по данным проекта Statdom осталось меньше 200 таких сертификатов (полтора года назад их было примерно 2600). В частности, за выпуск сертификатов с использованием SHA1 после установленного переходного периода пострадали удостоверяющие центры WoSign и StartCom.

Сейчас мы сталкиваемся уже с полноценной коллизией — два pdf-файла, которые дают одинаковые хеш-суммы. Их можно скачать, например, со специально созданного сайта SHAttered.io, название которого содержит буквы SHA и переводится как «разрушенный». Для получения коллизии потребовалось вычислить 9 223 372 036 854 775 808 значений хеш-функции, что примерно равно 6500 годам вычислений на современном процессоре. На GPU — специализированном процессоре видеокарт — эти вычисления занимают 110 лет, и, разумеется, в обоих случаях не требуется выполнять их последовательно — они могут выполняться параллельно, что займёт гораздо меньше времени. Оценка времени, необходимого для осуществления атаки методами полного перебора, составляет 12 миллионов лет GPU — улучшение, как мы видим, более чем в 100 тысяч раз. У статьи с некоторыми техническими подробностями 5 авторов: Марк Стивенс, Эли Вурштейн, Пьер Карпман, Анжи Альбертини и Ярик Марков(Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov). Трое представляют Google, двое — институт CWI, Амстердам. Цена вопроса — примерно 110 тысяч долларов по ценам Amazon. Атака пока не столь богата возможностями, как аналогичные результаты исследования MD5, но для приговора SHA1 этого достаточно. Доступен на сайте и инструмент, проверяющий, пригоден ли тот или иной файл для организации коллизии.

После SHA1 было разработано целое семейство алгоритмов SHA2, длиной от 224 до 512 бит. Сейчас это единственный широко распространённый алгоритм хеширования. Фактически мы имеем дело с монокультурой, которая вызывает опасения у криптографов. Был проведён и следующий конкурс, результатом которого стали алгоритмы семейства SHA3. Они ещё не получили ни широкого распространения в реализациях, ни поддержки в протоколах, и криптографы призывают начать их внедрение уже сейчас. Ведь если семейство SHA2 окажется нестойким по отношению к новым методам криптоанализа, очень важно, чтобы наготове была замена.

Несмотря на то, что алгоритм SHA1 в течение многих последних лет убирали отовсюду и заменяли на более новые, остался целый ряд программ, до сих пор полагающихся на теперь уже окончательно скомпрометированный алгоритм. В том числе там имеется программа, которая критична для IT-индустрии в целом. Это созданная Линусом Торвальдсом для разработки ядра Linux распределённая система контроля версий Git. SHA1 используется в продукте для контроля идентичности файлов и идентификации отдельных ревизий. Мало что мешает воспользоваться более новыми алгоритмами, но огромное количество старых репозиториев, ссылающихся на значения, вычисленные по текущей схеме, порождают вопрос, что же делать с ними. Сам Торвальдс заявил, что, по его мнению, есть ещё некоторое время для того, чтобы принять контрмеры.

Как ни странно, первые неприятности уже начались. Сразу после публикации, 24 февраля, кто-то с помощью демонстрационных файлов проверил репозиторий браузерного движка WebKit. Система контроля версий SVN, используемая в проекте, тоже использовала SHA1 для дедупликации файлов, и была на несколько дней приведена в неработоспособное состояние. Уже 25 февраля, впрочем, был выпущен специальный инструмент для предотвращения жестокого обращения с репозиторием. По состоянию на 27 февраля репозиторий так и не был починен, хотя залитые туда файлы были уже удалены. Жертвами подобной атаки могут стать и другие репозитории.

В Google отложили публикацию исходного кода, используемого для организации атаки, на 90 дней — стандартный срок так называемого «ответственного объявления об уязвимостях», за который разработчики ПО должны успеть исправить всё то, что нашли исследователи. Так что полностью насладиться красотой решения мы сможем только в мае 2017 года.


Автор:  Дмитрий Белявский (ТЦИ)

Возврат к списку