11 окт 12:03Технологии
Коллизии в SHA-1 и их последствия
Хеш-функции ставят в соответствие произвольному входному сообщению (любой длины) некоторое число из множества значений функции, то есть, отображают всевозможные входные сообщения в конечное множество значений хеш-функции. Коллизия – это когда известны два различных сообщения, имеющих одно и то же значение хеш-функции, то есть, 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-сертификата (хотя он для неё не очень и подходит), то придётся ещё перехватывать соединение с сайтом. Неплохим вариантом применения оказывается подделка подписи на троянской программе, которая таким образом сможет легко проникать в операционные системы. Но, опять же, вопрос, что тут проще: подделать подпись через коллизию или украсть ключ?
Впрочем, нестойкая хеш-функция, естественно, не должна использоваться.
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-сертификата (хотя он для неё не очень и подходит), то придётся ещё перехватывать соединение с сайтом. Неплохим вариантом применения оказывается подделка подписи на троянской программе, которая таким образом сможет легко проникать в операционные системы. Но, опять же, вопрос, что тут проще: подделать подпись через коллизию или украсть ключ?
Впрочем, нестойкая хеш-функция, естественно, не должна использоваться.
Лента новостей
Популярные статьи