Узлы замены ГОСТ 28147-89

Базовым элементом блочных криптосистем являются узлы замены – заданные таблично преобразования двоичных слов малой длины. Узлы замены называют также S-блоками или даже S-боксами. (Последнее название – калька с английского S-box – в совокупности с раундами шифрования кажется нам боксерским перебором.) Узлы замены отвечают за установление сложных нелинейных зависимостей между символами открытых текстов, шифртекстов и ключей. Их использование в криптосистемах реализует принцип усложнения (confusion) К. Шеннона.

В блочной криптосистеме из советского стандарта ГОСТ 28147-89, поныне действующего на постсоветском пространстве, используется набор из 8 узлов замены. Каждый узел задает преобразование тетрад (4-битовых слов).

ГОСТ 28147 весьма скупо характеризует свои узлы. Говорится лишь о том, что они являются дополнительным секретным элементом (наряду с обычным ключом – двоичным словом) и «поставляются в установленном порядке». Больше ничего. Нет даже требования биективности, которое соответствует устоявшимся принципам проектирования блочных криптосистем и защищает от некоторых атак.

С момента принятия ГОСТ 28147 научно-техническая неопределенность, связанная с выбором узлов замены, заполнялась слухами и домыслами. Ходили разговоры о секретных критериях, известных только разработчикам ГОСТ. Естественно, что эта неопределенность снижала доверие к криптосистеме, затрудняла применение ГОСТ на практике.

Все это происходило одновременно с открытием принципов выбора S-блоков DES. Блочная криптосистема DES была разработана компанией IBM и принята в качестве стандарта шифрования США в 1977 году. При разработке специалисты IBM открыли разностные атаки на блочные криптосистемы и выбрали S-блоки так, чтобы защитить DES от этих атак. Критерии выбора, также первоначально секретные, были оглашены только после переоткрытия разностных атак Э. Байхэмом и А. Шамиром в 1991 году.

В приложении к более позднему стандарту ГОСТ Р 34.11-94 были указаны узлы замены, необходимые для объяснения проверочного примера хэширования. На протяжении долгого времени эти проверочные узлы, вроде бы как выбранные самими разработчиками ГОСТ 28147, были весьма распространены. Известный специалист Б. Шнайер написал в своей книге «Прикладная криптография», что проверочные узлы используются в Центробанке РФ. Впоследствии исследователь Н. Куртуа объявил об использовании этих узлов другими российскими банками и даже утверждал, что, по мнению большинства криптографов, ГОСТ с проверочными узлами – это и есть собственно ГОСТ.

В 2011–2012 годах Н. Куртуа опубликовал несколько статей, содержащих ряд спорных положений относительно стойкости ГОСТ. Технический комитет РФ по стандартизации в области криптографии, который в это же время занимался продвижением ГОСТ как части международного стандарта, сообщил в своем пресс-релизе, что «набор узлов замены, рассматриваемый в работе Куртуа, полностью отличается от набора узлов замены, определенного в 1-м рабочем проекте Дополнения 1 к стандарту ISO/IEC 18033-3. Это означает, что последняя работа Куртуа – не о российском блочном шифре ГОСТ, предложенном для стандартизации в ISO». Российский специалист В.И. Рудской объяснил, что результаты Куртуа «неприменимы при оптимальном выборе узлов замены». К сожалению, принципы оптимального выбора снова не были оглашены.

По нашим оценкам проверочные узлы действительно не являются оптимальными относительно общих критериев выбора (высокая нелинейность, малые разностные характеристики, максимальные степени координатных функций и их линейных комбинаций и др.). Интересная деталь – у всех проверочных узлов отсутствуют неподвижные точки. Соответствующие подстановки в комбинаторике называют беспорядками. Вероятность того, что случайная подстановка окажется беспорядком, близка к e^-1 ≈ 0.367. Соответственно все 8 случайных биективных узлов окажутся беспорядками с весьма малой вероятностью, близкой к e^-8 ≈ 0.00034. Поэтому критерий беспорядков скорее всего учитывался при выборе проверочных узлов. Следует, впрочем, отметить, что отсутствие неподвижных точек вряд ли обеспечивает защиту от каких-либо атак. Выбор узлов-беспорядков больше похож на «водяной знак» производителя.

Кроме проверочных нам известны следующие стандартизированные наборы узлов замены ГОСТ:

• 4 набора, выбранных российской компанией КриптоПро и зафиксированных в RFC 4357.
• 10 наборов, выбранных Государственной службы специальной связи и защиты информации Украины и зафиксированных в Инструкции о порядке использования ключей ГОСТ.

Критерии выбора опять не объяснены.

Стандартный набор узлов замены ГОСТ выбран и в нашей стране. Этот набор определен в предварительном стандарте СТБ П 34.101.50-2012, который вступил в действие 1 августа текущего года. Набор имеет следующий вид:

  2  6  3 14 12 15  7  5 11 13  8  9 10  0  4  1
  8 12  9  6 10  7 13  1  3 11 14 15  2  4  0  5
  1  5  4 13  3  8  0 14 12  6  7  2  9 15 11 10
  4  0  5 10  2 11  1  9 15  3  6  7 14 12  8 13
  7  9  6 11 15 10  8 12  4 14  1  0  5  3 13  2
 14  8 15  2  6  3  9 13  5  7  0  1  4 10 12 11
  9 13  8  5 11  4 12  2  0 10 15 14  1  7  3  6
 11 15 10  8  1 14  3  6  9  0  4  5 13  2  7 12

Здесь i-ая строка представляет собой образы i-го узла для прообразов 0, 1,..., 15 (тетрады представляются числами от 0 до 15).

Следуя традиции, ни слова больше ни о строках, ни о столбцах.