SHA-1: пришло время миграции

Берд Киви

Этого события в компьютерно-криптографическом мире ждали все, но мало кто ожидал, что оно наступит так быстро. Самый популярный и распространенный алгоритм хеширования SHA-1 не устоял перед атакой группы китайских исследователей (theory.csail.mit.edu/~yiqun/shanote.pdf) и «дал-таки слабину».

Китайцы, прославившиеся в минувшем году успешным штурмом другого популярного хеш-алгоритма MD5, существенно развили свою технику и теперь нашли метод для отыскания коллизий в SHA-1 за 2^69 шагов. Это примерно в две тысячи раз быстрее, чем при отыскании коллизий в лоб, методом тотального перебора всех возможных комбинаций (на что требуется 2^80 операций хеширования).

Прежде чем пояснить, почему это так важно и что все это означает на обычном человеческом языке, скажем несколько слов о SHA-1. Стандарт хеширования (или, как модно выражаться в научных кругах, криптографический примитив) SHA-1 на сегодняшний день реализован и работает чуть ли не во всех протоколах и программах защиты информации, применяемых в компьютерах и сетях, — от SSH, SSL и IPSec до VPN, S/MIME и PGP. В целом же можно уверенно утверждать, что алгоритмы хеширования оказались в криптографии гораздо более востребованными, нежели собственно шифрование информации.

Хеширование, напомним, это одностороннее (или однонаправленное) математическое преобразование. От шифрования оно принципиально отличается тем, что в одну сторону вычисляется легко и быстро, а вот в обратную — получить вход по выходу — не вычисляется никаким другим способом (в идеале), кроме тотального перебора всех возможных вариантов. Благодаря этому свойству, хеш-функции получили широчайшее применение в алгоритмах защиты информации: в криптографии с открытым ключом, в протоколах цифровой подписи, аутентификации, сертификации, проверки целостности сообщения и многих других приложениях. В 1990 году Рон Райвест (один из соавторов алгоритма RSA) изобрел весьма удачную хеш-функцию MD4, но когда стало ясно, что она все же не очень хороша, Райвест усовершенствовал ее, а в 1992 году создал другую, лучшую MD5. А в 1993 году Агентство национальной безопасности США опубликовало собственный вариант хеш-алгоритма, конструктивно весьма похожего на MD5 и получившего название SHA (Secure Hash Algorithm). Вскоре, однако, и с SHA произошла подобная история: в 1995 году АНБ обнаружило в предложенном алгоритме слабости и предложило новый, улучшенный алгоритм хеширования SHA-1, который стал не только национальным стандартом США, но и вообще наиболее популярной в мире хеш-функцией.

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

И вот именно это — эффективный алгоритм отыскания коллизий в SHA-1 — продемонстрировали ныне китайские исследователи из Шаньдунского университета, сократив 2^80 операций лобового перебора до 2^69 шагов. Сразу скажем, что никакой катастрофы не произошло, поскольку 2^69 операций хеширования — это все же чрезвычайно много, фактически на пределе возможностей нынешней суперкомпьютерной техники. Кроме того, эти вычислительные затраты понадобятся для отыскания лишь случайной пары-коллизии, об отыскании же другого прообраза конкретного хеш-значения (то есть реальной подделке документа) пока и речи не идет, поскольку на это (в теории) требуется неизмеримо больше операций тотального перебора — 2^160.

Но, как гласит популярное среди криптографов присловье, «со временем атаки никогда не становятся хуже — только лучше». Первые разговоры о недостаточной надежности SHA-1 пошли еще в прошлом году, а в комплекте национальных стандартов США уже имеются более длинные — и более стойкие к вскрытию — функции хеширования SHA-224, SHA-256, SHA-384, SHA-512. Но все же любопытно отметить, что буквально за неделю до объявления китайских криптографов. Национальный институт стандартов и технологий (НИСТ) США делал комментарии именно по этому поводу, в таких буквально словах: «SHA-1 не взломан, и нет никаких особых оснований полагать, что это вскоре произойдет»… Поэтому НИСТ порекомендовал готовить переход от SHA-1 к более сильным алгоритмам примерно на 2010 год. В свете последовавших событий можно предполагать, что массовый переход теперь начнется существенно раньше.