Коллизии в SHA-1 и их последствия

SignХеш-функции ставят в соответствие произвольному входному сообщению (любой длины) некоторое число из множества значений функции, то есть, отображают всевозможные входные сообщения в конечное множество значений хеш-функции. Коллизия – это когда известны два различных сообщения, имеющих одно и то же значение хеш-функции, то есть, H(M) = H(M’). Очевидно, коллизии обязательно существуют для хеш-функции, за редким исключением (потому что на практике сообщений, грубо говоря, больше, чем значений функции). Коллизии бывают различных типов, и это различные типы обладают разными свойствами. Криптографически стойкие хеш-функции отличаются тем, что для них обнаружить коллизии должно быть вычислительно сложно.

SHA-1 – одна из самых распространённых криптографических хеш-функций. Сейчас она считается устаревшей, поэтому есть активное движение по вытеснению этой функции из практики. На днях опубликована работа, в которой найдены коллизии в полной функции сжатия SHA-1. Это весьма важное достижение. Сразу отмечу: функция сжатия – ключевой элемент алгоритма SHA-1, но обнаружение коллизий в функции сжатия не означает, что коллизии удалось обнаружить и для самой SHA-1: эффективных алгоритмов, позволяющих построить коллизии для SHA-1 из коллизий функции сжатия, не известно – ну или, как принято писать, “в открытой печати не опубликовано”. То есть, подделать электронную подпись, используя коллизию в функции сжатия, пока не получится.

С разными существенными ограничениями коллизии в SHA-1 обнаруживали и ранее, примерно с 2005 года. Новая работа – существенный шаг вперёд. Тем не менее, практически применимых коллизий никто пока не опубликовал. В упомянутой работе есть небольшой экскурс в историю: например, с MD5 тоже всё время улучшались результаты, уже было очевидно, что функция полностью утратила криптографическую стойкость, но все ждали пока опубликуют практическую демонстрацию – такой демонстрацией явился выпуск группой исследователей поддельного сертификата удостоверяющего центра.

А что вообще даёт возможность обнаружения коллизий в SHA-1? Предположим, у нас есть эффективный алгоритм, позволяющий находить самые “простые” коллизии (коллизии второго рода), а именно – два сообщения, для которых значения хеш-функции равны. Это позволяет получить два, – вообще говоря, случайных, – текста, для которых будет одинаковым значение электронной подписи, использующей SHA-1 для генерирования дайджеста сообщения. Смысла в этом не так много. Гораздо полезнее алгоритм, позволяющий найти коллизию первого рода: сообщение M’, для которого значение SHA-1 будет равно значению для заданного сообщения M. Тогда, например, можно будет взять SSL-сертификат (M), использующий SHA-1 в составе криптосистемы электронной подписи, и построить второе сообщение (M’), соответствующее данной электронной подписи. Хорошо? Хорошо. Но есть проблема: нигде не сказано, что это сообщение будет хоть как-то похоже на SSL-сертификат. То есть, подделать SSL-сертификат таким образом не выйдет – скорее всего пара из коллизии будет представлять собой случайный набор байтов, и хоть подписи совпадают, но подменить-то сертификат можно только файлом, соответствующим этому сертификату по структуре. Примерно то же относится и к ключам RSA – не факт, что обнаруженную коллизию удастся использовать в качестве открытого ключа. (Тут, впрочем, есть интересные оговорки, связанные с особенностями RSA – дело в том, что открытый ключ RSA – это не структура данных, а всего лишь целое число заданной разрядности; но это другая история.)

То есть, для того, чтобы коллизии в SHA-1 хорошо заработали на практике, нужен алгоритм, позволяющий обнаруживать коллизию для заданного сообщения, которая обладает некоторыми свойствами этого сообщения. Например, для заданного SSL-сертификата нужно иметь возможность построить сообщение, которое тоже является SSL-сертификатом, содержит другой открытый ключ, но при этом имеет то же значение хеш-функции. Это чрезвычайно сложно. Особенно если в качестве цели выбрать не произвольный сертификат, а вполне конкретное множество сертификатов, как того требует атака на ту или иную выбранную цель. В случае с MD5 и подделкой сертификатов, использовался алгоритм коллизии с выбранным префиксом: в составе сертификата выделили поля, одно из которых могло иметь произвольное значение, а другие – легко предсказуемое (в том числе, серийный номер), под эти параметры и была подобрана коллизия. Для SHA-1, применительно к инфраструктуре SSL, потребуется что-то подобное, вот только сертификаты сейчас чуть лучше защищены – формат лишили требуемой гибкости (addon: хотя, как мне подсказали, гибкости всё равно достаточно – можно ввести собственные расширения, либо использовать в качестве носителя переменного значения поля типа SAN и др., где формат позволяет вписывать самые разные данные).

В упомянутой работе также уточняют примерную стоимость нахождения полезной коллизии в SHA-1 – это около $170 тыс., потраченных на аренду мощностей Amazon EC2. С одной стороны, не такая большая сумма. С другой – целей для атак, которые заслуживают подобной траты, не так много. Если пытаться применить данный инструмент для подмены SSL-сертификата (хотя он для неё не очень и подходит), то придётся ещё перехватывать соединение с сайтом. Неплохим вариантом применения оказывается подделка подписи на троянской программе, которая таким образом сможет легко проникать в операционные системы. Но, опять же, вопрос, что тут проще: подделать подпись через коллизию или украсть ключ?

Впрочем, нестойкая хеш-функция, естественно, не должна использоваться.

Адрес записки: https://dxdt.ru/2015/10/09/7696/

Похожие записки:



Далее - мнения и дискуссии

(Сообщения ниже добавляются читателями сайта, через форму, расположенную в конце страницы.)

Комментарии читателей блога: 4

  • 1. 9th October 2015, 18:00 // Читатель sarin написал:

    с коллизиями второго рода можно было бы осуществить такую атаку. при условии, что есть возможность для заданных M и M’ вычислить дополнения A и A’ такие, что H(M|A) == H(M’|A’).
    тогда атакующая сторона может подготовить, например, два текста договора один из которых будет выгоден атакуемому, другой нет. атакуемый подпишет выгодный ему договор. после этого атакующий через регулятора взыщет по невыгодному.
    тут есть нюансы, конечно. дополнения должны содержать байты только определённых значений, надо учитывать особенности формата данных и всё такое. но самое главное – очень своеобразная модель угроз.

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

    цена за амазон не имеет особого значения. если у атакующего ферма, то он платит, в основном, только за электричество. если ботнет – не платит даже за электричество.

  • 2. 9th October 2015, 23:10 // Александр Венедюхин:

    У схемы с договорами есть один недостаток: атакуемая сторона может показать, что оба договора имеют одинаковую подпись, подтвердив таким образом несостоятельность алгоритма и злой умысел атакующего.

  • 3. 10th October 2015, 00:23 // Читатель sarin написал:

    да, если успеет

    приведённый пример очень схематичен. примерно как сказки про Алису с Бобом. на практике такая атака сомнительно что может быть проведена без серьёзной агентурной работы и/или разных мошеннических схем. например нечистый на руку нотариус может подделать завещание с помощью такой атаки. правда ему придётся модифицировать и исходный текст тоже.

  • 4. 10th October 2015, 15:53 // Читатель Antonio написал:

    Амазону повезло, у него купили мощностей на 170к$ :-)