Появившиеся в последнее время сообщения о продвижении в области криптографического анализа алгоритма хеширования SHA-1, достигнутого специалистами Китая, США и других стран, ставят перед необходимостью ответить на ряд вопросов.

Где и как используется алгоритм SHA-1 в отечественных информационных системах? Насколько влияют последние результаты в решении проблемы коллизий алгоритма SHA-1 на легитимность электронных подписей и их аналогов в системах защиты информации, базирующихся на этом алгоритме? И наконец, насколько методы, применимые к SHA-1, можно перенести на российский стандарт функции хеширования ГОСТ Р 34.11-94?

Напомним основные криптографические требования, предъявляемые к хеш-функции:

  • однонаправленность — высокая алгоритмическая сложность построения прообраза по значению хеш-функции;
  • высокая алгоритмическая сложность нахождения коллизий — появление двух текстов с одинаковым значением хеш-функции.

Алгоритм SHA-1 разработан Агентством национальной безопасности США в 1995 году и включен Национальным институтом стандартов США в стандарт SHS. Хеш-функции используются в информационных технологиях в системах электронной подписи, системах контроля целостности программного кода и данных, а также для построения кодов аутентификации.

SHA-1 используется в подавляющей массе продуктов криптографической защиты, производимых и используемых в США, а также в других странах, которые поддерживают американские стандарты. Так, в операционных системах семейства Windows встроен ряд криптографических служб, использующих алгоритм SHA-1. Внедрение этого алгоритма в Windows настолько глубоко, что загрузка и использование операционных систем без обращения к нему из штатных криптографических сервисов невозможны. Стандарт SHS c алгоритмом SHA-1 используется совместно с другими криптографическими стандартами США в инфраструктуре открытых ключей, а также в других распространенных криптографических протоколах (SSL/TLS, IPSec, Kerberos и др.).

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

Построение и использование коллизий алгоритма хеширования распадается на две задачи:

  • криптографическая задача нахождения коллизии;
  • практическая задача использования найденной коллизии для атаки на защищаемую алгоритмом хеширования систему.

Поэтому, найденные подходы к построению коллизий являются значительным достижением в области криптографического анализа SHA-1. Вопрос о конкретном использовании получаемых коллизий для реальных атак остается открытым. Необходимо учитывать, что для успешного проведения целенаправленной атаки коллизии должны быть семантически допустимы. Поэтому угроза легитимности подписи на базе хеширования по алгоритму SHA-1 носит случайный характер и требует оценки вероятности достижения положительного результата. Атаки в системах аутентификации, основанные на построении коллизий алгоритма, невозможны из-за применения ключевого хеширования.

Хеш-функция реализует отображение множества хешируемых текстов на множество значений хеш-функции. Множество хешируемых тексов разбивается на классы эквивалентности по значениям хеш-функции. Сложность нахождения коллизий хеш-функции зависит от аналитической сложности этого отображения.

Математической моделью задачи об оценке сложности числа коллизий является задача, известная как «парадокс близнецов»: в множестве из элементов, каждый из которых характеризуется независимо от других одним из признаков при его случайном и равновероятном выборе, среднее число элементов с признаком, одинаковым для фиксированного элемента, равно n/m, среднее число пар элементов с одинаковым признаком равно n/m-2.

В применении к задаче о коллизиях среднее число коллизий в первом случае равно |B|/|H| во втором |B|/(|H|)-2. За теоретическую оценку сложности нахождения коллизий в криптографии принимается величина.

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

К возможности снижения криптографической сложности на три-четыре порядка привел ряд особенностей алгоритма SHA-1. Так, используемые математические операции (операция сложения, побитовые логические операции, операция сдвига) в своей совокупности не позволяют строить преобразования с хорошими перемешивающими свойствами. Кроме того, применяется последовательное хеширование текста блоками по 512 бит со сверткой блока до 160 бит. Используемый способ дополнения последнего неполного блока хешируемого текста до полного создает дополнительные возможности для поиска коллизий.

Указанные особенности характерны для алгоритмов MD4, MD5, SHA-256, SHA-512 и других с той же идеологией построения. Они позволяют применять к алгоритмам этого класса методы дифференциального анализа для построения коллизий.

Для алгоритма SHA-1 теоретическая стойкость равна, однако на практике стойкость снижается.

Алгоритм SHA-1 с его значением изначально не имел криптографического запаса и, видимо, был рассчитан на то, что оценку снизить не удастся.

В отличие от алгоритма SHA-1 алгоритм ГОСТ Р 34.11-94 характеризуется следующим свойствами:

  • преобразование блока информации при хешировании осуществляется использованием шифрующего преобразования по алгоритму ГОСТ 28147-89;
  • преобразование хешируемой информации производится блоками по 256 бит с размером преобразованного блока также 256 бит; теоретическая стойкость;
  • в алгоритме хеширования используются специальные меры, исключающие возможность упрощения задачи поиска коллизий при неполном последнем блоке.

В шифрующем преобразовании по алгоритму ГОСТ 28147-89 в дополнение к операциям, характерным для алгоритма SHA-1 и родственных ему, используется узел замен, выбором которых удается усложнить перемешивающее преобразование и существенно ограничить возможность применения к алгоритму ГОСТ Р 34.11-94 методов дифференциального анализа для решения задачи по поиску коллизий. До настоящего времени такие методы в процессе многолетних криптографических исследований алгоритма ГОСТ Р 34.11-94 не найдены. По нашему мнению, методы построения коллизий, найденные для алгоритма SHA-1, неприменимы к алгоритму ГОСТ Р 34.11-94.

Леонид Веденьев (wlt@cryptopro.ru) — инженер-аналитик, Владимир Попов (vpopov@cryptopro.ru), начальник отдела криптографического анализа и аттестационных испытаний компании «Крипто-Про» (Москва).