Алгоритм SHA-1 — национальный американский стандарт, однако его злоключения могут оказать влияние и на отечественные компании. Computerworld Россия попросил прокомментировать сообщение о коллизиях в этом алгоритме российских криптографов — Анатолия Лебедева, генерального директора компании «ЛАН Крипто», и Сергея Леонтьева, технического директора «КриптоПро».

Как развивались события по поиску коллизий для алгоритма SHA-1?

Анатолий Лебедев (АЛ): В августе 2004 года на конференции Crypto 2004 в Санта-Барбаре (США) с докладом по методам построения так называемых коллизий для известных хеш-функций, то есть двух разных файлов или строк данных, результаты хеширования которых одинаковы, выступал профессор Эли Бихэм из Хайфы (Израиль). Он доложил о своих новых результатах, которые были опубликованы в трудах конференции и вызвали большой интерес, поскольку впервые показали, что многие распространенные в мире алгоритмы хеширования, в частности американский национальный стандарт SHA-1, не так надежны, как это казалось ранее. Замечания китайских исследователей, которые прозвучали в ходе его доклада, показали, что в данном направлении они уже имеют более сильные результаты. Эта дискуссия вызвала большой резонанс в кругах криптографов. Стало очевидно, что следует ожидать публикаций новых результатов.

И вот такая публикация анонсирована. Пока окончательного ее текста мы не видели, но имя Джикун Лизы Юин хорошо известно специалистам: она живет и работает в США более 25 лет, что дает основания судить о серьезности ее заявлений и претензии на важный результат.

В каких приложениях используется хеш-функция SHA-1?

Сергей Леонтьев (СЛ): Иногда SHA-1 используется при выработке электронных подписей для документов или сертификатов, например в продуктах компаний Thawte или VeriSign. Эта функция применяется для контроля целостности программного обеспечения, в частности в Microsoft Windows и Java. Еще чаще SHA-1 используется в составе импортных реализаций протокола SSL для контроля аутентичности сторон соединения, а также в основанных на IPSec реализациях VPN-сред для тех же самых целей; в последнем случае это касается не только импортных, но и некоторых отечественных реализаций.

Реально ли построить коллизию для SHA-1?

АЛ: По данным криптографов «ЛАН Крипто», в анонсированной работе заявлен алгоритм построения коллизий для SHA-1 со сложностью 269, то есть примерно 500 000 000 000 000 000 000 элементарных операций. Такое количество операций может быть реально проделано примерно за 1 год непрерывной работы компьютерной системы из тысячи 1,5-гигагерцевых процессоров. Реальность построения такой системы в настоящее время определяется чисто финансовыми соображениями; технически это вполне возможно.

К сожалению, пока не опубликована полная версия статьи, нельзя с уверенностью утверждать, что заявленный результат не содержит ошибок. Подобный печальный опыт наши криптографы уже получали во время европейского конкурса криптографических алгоритмов в 2001 году. Тогда также группа китайских исследователей — среди них, правда, не было известных криптографов — анонсировала результаты анализа алгоритма НАШ, которые послужили для комиссии основанием для решения о снятии его со второго этапа конкурса. Позднее комиссия признала, что анонсированный результат содержал ошибки.

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

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

СЛ: Если рассматривать легитимность как юридическое понятие, то, с одной стороны, хеш-функция SHA-1 в России не была легитимной, поскольку соответствующие органы, в общем-то, никогда и не признавали ее стойкость достаточной. С другой стороны, в случае, когда стороны предварительно в договоре указали, что они доверяют SHA-1, до пересмотра этого договора данная хеш-функция применима. Таким образом, грубо говоря, в отношении легитимности ничего не изменится: с точки зрения применения закона «Об ЭЦП» ее как не было, так и нет, а при использовании двусторонних договоров она как была, так и осталась.

Можно ли предложенный китайскими исследователями метод поиска коллизий использовать и для российских хеш-функций?

АЛ: Что касается алгоритма ГОСТ Р 34.11-94, то он не вызывает сомнений. Криптографами нашей компании ведутся исследования по разработке собственных алгоритмов хеширования. Результаты показывают, что алгоритм хеширования ОСТ 51-09-98 «Информационная технология. Защита информации. Хеширование», являющийся отраслевым стандартом газовой промышленности, не вызывает беспокойства.

СЛ: Есть несколько способов построения хэш-функции. Так, семейство хэш-функций MD4/MD5/RIPE-MD/SHA/SHA-1/SHA-256/SHA-512 имеет один принцип построения. Но есть еще несколько иных способов создания хеш-функций, в частности на основе блочных симметричных алгоритмов шифрования. Хеш-функция ГОСТ Р 34.11-94 построена на основе блочного шифра ГОСТ 28147-89. Можно утверждать, что возможность применения обнаруженных коллизий и методов их получения непосредственно для криптоанализа ГОСТ Р 34.11-94 маловероятна.