Обобщение границы Ниберг–Кнудсена для вероятностей тактовых дифференциалов DES-подобных блочных шифров

А. Н. Алексейчук, И. В. Васюков

Размещено на http://www.allbest.ru//

82

Размещено на http://www.allbest.ru//

Обобщение границы Ниберг-Кнудсена для вероятностей тактовых дифференциалов DES-подобных блочных шифров

А. Н. Алексейчук

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

Ключевые слова: криптографическая защита информации, блочный шифр, разностный криптоанализ.

блочный шифр ключ дифференциал тактовый

Введение

В современных автоматизированных системах управления и обработки данных для обеспечения конфиденциальности передаваемой и обрабатываемой информации, как правило, используются симметричные блочно-итерационные крип-тосистемы (шифры) [1, 2]. Реализуемые в этих шифрах криптографические преобразования представляют собой многократное выполнение относительно простых базовых преобразований, зависящих от ключа, называемых раундовыми или тактовыми преобразованиями. Наиболее известной общей схемой построения блочно-итерационных криптосистем является сеть Фейстеля [3], на основе которой построено большинство используемых в настоящее время блочных шифров, включая ГОСТ 28147-89 и ряд других [4]. К числу криптосистем Фейстеля относятся и так называемые DES-подобные блочно-итерационные шифры [2], исследованию криптографических свойств которых посвящено большое число публикаций [1, 2, 4].

При проектировании блочной криптосистемы наиболее важной задачей яв-ляется обеспечение ее стойкости к известным методам криптоанализа. Одним из таких методов, в значительной степени определяющих стойкость современных блочных шифров, является метод дифференциального (разностного) криптоанализа, впервые предложенный (применительно к DES-подобным шифрам) в [5]. Сущность разностностного криптоанализа заключается в исследовании степени влияния определенных отличий в открытых сообщениях шифра на соответствующие отличия в шифрованных текстах, получаемых в результате зашифрования данных открытых сообщений на одном и том же неизвестном ключе. Основным показателем стойкости блочного шифра к разностному криптоанализу является максимальная вероятность тактовых дифференциалов этого шифра (точные определения основных понятий разностного криптоанализа, используемых в данной статье, приведены ниже). Следует отметить, что оценка или обоснование стойкости конкретных шифров к разностным криптоаналитическим атакам, как правило, представляет собой сложную математическую задачу, полное решение которой удается получить лишь в исключительных случаях и при достаточно сильных (зачастую, эвристических) упрощающих предположениях, в определенном смысле идеализирующих исследуемую криптосистему. Общие практически значимые оценки стойкости к разностному криптоанализу могут быть получены для класса DES-подобных блочно-итерационных шифров с независимыми в совокупности и равновероятными тактовыми ключами [5, 6]. В основе указанных оценок лежит граница Ниберг-Кнудсена [7] (см. неравенство (6)), устанавливающая не зависящую от количества раундов шифрования равномерную верхнюю оценку вероятностей ненулевых тактовых дифференциалов данного DES-подобного шифра.

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

Основные понятия разностного криптоанализа DES-подобных блочно-итерационных шифров

Пусть даны конечная абелева группа G порядка q 2, непустое конечное множество K и семейство (fk: Gn Gn, k K) взаимно однозначных преобразований множества Gn = {(g1, …, gn): gi G, }.

Согласно определению [2, 6], r-раундовый блочно-итерационный шифр c множеством открытых (шифрованных) сообщений Gn, множеством ключей Kr и функцией шифрования F: Gn Kr Gn представляет собой систему (Gn, Kr, F) такую, что для любых x Gn, = (k(1), …, k(r)) Kr выполняется равенство F(x, ) = fk(r) … fk(1)(x), где fk(r) … fk(1) есть произведение (последовательное выполнение) указанных преобразований. Элементы k(1), …, k(r) называются тактовыми ключами, а отображения fk(1), …, fk(r) -- тактовыми шифрующими преобразованиями шифра в раундах шифрования с номерами 1, …, r соответственно.

Блочно-итерационный шифр = (Gn, Kr, F) называется DES-подобным [2, 7, 8], если n = 2m -- четное число, K = Gl, где l m, и существуют вектор b Gl, мономорфизм групп E: Gm Gl и отображение : Gl Gm такие, что для любого тактового ключа k K шифрующее преобразование fk в каждом из r раундов имеет вид fk(x1, x2) = (x2, x1 + k(x2)), где k(x2) = (E(x2) + b + k), x1, x2 Gm. Отображения E и называются функцией расширения и раундовой функцией шифра соответственно.

С целью оценки стойкости данного блочно-итерационного шифра к методу разностного криптоанализа, определим (в предположении независимости и равновероятности тактовых ключей k(1), …, k(r) и открытых сообщений X, X шифра ) матрицу Pi = ||p(i)(, )|| вероятностей i-тактовых дифференциалов этого шифра, полагая [6]

p(i)(, ) = , , Gn, (1)

где Y(i) = Y (i) - Y(i), Х = X - X, Y(i) и Y (i) -- случайные сообщения, вырабатываемые в i-м раунде шифрования по открытым текстам X и X соответственно, .

Согласно [5, 6], базовая атака по методу разностного криптоанализа на шифр проводится при выбираемом открытом тексте и имеет своей целью восстановление неизвестного тактового ключа в последнем раунде шифрования. Как показано в [6], эффективность такой атаки определяется максимальным значением вероятностей ненулевых (r - 1)-тактовых дифференциалов (Х = , Y(r - 1) = ) шифра :

= max{p(r-1)(, ): Gn \ 0, Gn}. (2)

Обозначим через Wr() число упорядоченных пар (Х, Х) выбираемых открытых сообщений, необходимых в среднем для успешного восстановления ключа k(r) по методу разностного криптоанализа. Тогда, согласно [2, 6], при выполнении гипотез о «стохастической эквивалентности» и «различимости ключей», принимаемых обычно в разностном криптоанализе, имеет место неравенство

Wr() (- (qn - 1)-1)-1, (3)

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

Неравенство (3) сводит задачу оценки или обоснования стойкости шифра относительно разностного криптоанализа к построению верхних границ вероятностей тактовых дифференциалов этого шифра. Известно [2, 6], что матрица вероятностей i-тактовых дифференциалов DES-подобного шифра является i-й степенью матрицы вероятностей 1-тактовых дифференциалов:

Pi = (P1)i, . (4)

При этом непосредственно из равенства (1) нетрудно получить явные выражения чисел p(1)(, ) [2, 8]:

p(1)(, ) = =

= , (5)

где = (1, 2), = (1, 2), 1, 2, 1, 2 Gm, (2, 1) -- символ Кронекера, и запись #M обозначает мощность произвольного конечного множества M.

В работе К. Ниберг и Л. Кнудсена [7] (см. также [8]) показано, что при i 4 для любых Gn \0, Gn вероятность i-тактового дифференциала (, ) произвольного DES-подобного шифра удовлетворяет неравенству

p(i)(, ) , (6)

где

= max{p(1)(, ): , Gn, 1 0}. (7)

Верхняя граница (6) имеет важное практическое значение для оценки и обоснования стойкости DES-подобных шифров к разностным криптоаналитическим атакам. В частности, при r 5 для обоснования стойкости шифра к разностному криптоанализу в соответствии с соотношениями (3), (5) и (6) достаточно показать, что раундовая функция данного шифра удовлетворяет условиям, гарантирующим требуемое (достаточно малое) отклонение вероятности , определяемой по формуле (7), от q-m. Конкретные применения указанного подхода к построению «разностно-устойчивых» DES-подобных шифров можно найти в [1, 7-9] и ряде других работ.

Новые верхние границы вероятностей тактовых дифференциалов

Пусть A -- произвольное непустое подмножество группы Gn. Назовем множество A полусимметричным, если выполняется следующее условие: для любого вектора 1 Gm соотношение (1, 0) A влечет соотношение (0, 1) A.

Положим

= max{p(1)(, ): A, Gn, 1 0}. (8)

Отметим, что при A = Gn параметр совпадает со значением , определенным в соответствии с равенством (7). Далее для любого вектора z Gn будем обозначать через z1 и z2 соответственно левую и правую части (длины m) этого вектора.

Основным результатом настоящей статьи является следующая теорема, обобщающая неравенство (6) и позволяющая устанавливать более точные верхние оценки вероятностей отдельных тактовых дифференциалов DES-подобных блочных шифров.

Теорема. Пусть = (Gn, Kr, F) -- r-раундовый DES-подобный блочный шифр, r 4 и A Gn -- полусимметричное множество. Тогда для любых A\0, Gn выполняется неравенство

p(r)(, ) 2. (9)

Доказательство. Вначале получим ряд вспомогательных соотношений. Из равенства (4) следует, что для любых r 2, , Gn

p(r)(, ) = , (10)

p(r)(, ) = . (11)

Принимая во внимание соотношение (5), запишем равенства (10), (11) в виде

p(r)(, ) = (12)

p(r)(, ) = (13)

Непосредственно из равенств (5), (12), (13) получим, что

= , 1 Gm\0, (14)

= , 2 Gm\0. (15)

Наконец, полагая в формуле (12) r = 2, получим равенство

= . (16)

Из формулы (16) и определения чисел , следует, что для любых A\0, Gn таких, что 2 0 и 1 0, выполняется неравенство

p(2)(, ) . (17)

Перейдем к доказательству неравенства (9). Из соотношений (5), (10) вытекает, что p(r)(, 0) = 0 для любых Gn \0, r 1. Поэтому далее будем считать, что A\0, Gn \0. Заметим, что в силу равенства (11)

p(r)(, ) =

и, следовательно,

, r 2. (18)

Таким образом, на основании неравенства (18) для доказательства неравенства (9) достаточно показать, что для любых A\0, Gn \0 выполняется условие

p(4)(, ) 2. (19)

Для доказательства неравенства (19) рассмотрим три возможных случая: 1 -- 2 = 0, 1 0; 2 -- 2 = 0, 1 = 0; 3 -- 2 0.

Случай 1. Прежде всего, заметим, что 1 0, так как A\0. На основании соотношений (13), (14) получим, что

p(4)(, ) = ==

= +

+. (20)

Поскольку 1 0, 1 0, то на основании оценки (17), условия = (1, 0) A и полусимметричности множества A выполняется неравенство

. (21)

Аналогично, в силу равенства (15), условий 1 0, 1 0 и полусимметричности множества A справедливы соотношения

=

= . (22)

На основании соотношений (20)-(22) имеем

p(4)(, ) + 2,

что и требовалось доказать.

Случай 2. Так как 1 0, 2 0, то на основании равенств (14), (15) получим

p(4)(, ) === ,

где последнее неравенство следует из оценки (17) и условия полусимметричности множества A.

Случай 3. Согласно равенству (4),

p(4)(, ) = =

= + (23)

+ .

Оценим второе слагаемое в правой части равенства (23). Поскольку (1, 2) A, 2 0, с1 0, то на основании неравенства (17)

. (24)

Для оценки первого слагаемого в выражении (23) заметим, что

= , (25)

так как (1, 2) A, 2 0 и с2 0. Кроме того, в соответствии с равенством (16)

=

? . (26)

Следовательно, в силу соотношений (25), (26) выполняются неравенства

. (27)

Окончательно на основании оценок (23), (24) и (27) получим неравенство (19). Теорема доказана.

В качестве следствия полученной теоремы отметим такой результат, непосредственно вытекающий из соотношений (5), (8), (9). Введем обозначение

= , a Gm \0. (28)

Следствие. В условиях теоремы для любых = (1, 2) Gn \0, Gn имеют место неравенства

p(r)(, ) 2, если 2 0;

p(r)(, ) 2 -- в противном случае. (29)

Действительно, полагая в формуле (9) A = {(1, 2)}, где 2 0, получим первое неравенство (29); второе неравенство получится, если положить в (9) A = {(1, 0), (0, 1)}.

Рассмотрим следующий простой пример, иллюстрирующий применение соотношений (29) к построению верхних оценок вероятностей тактовых дифференциалов DES-подобных блочных шифров.

Пусть G = (GF(2), +), m = l = 4 (n = 2m = 8), E -- тождественное отображение множества Gm = {0, 1, …, 15}, и функция : Gm Gm является подстановкой следующего вида:

. (30)

Отметим, что, согласно информации, приведенной в [2], совпадает с одним из S-блоков, используемых Центральным банком Российской Федерации в алгоритме шифрования ГОСТ 28147-89.

Исходя из равенства (28), нетрудно вычислить значения для всех a Gm \0, соответствующие подстановке (30):

= , если a {1, 8}; = , если a = 6;

= - в остальных случаях.

Отсюда = и, согласно формулам (29), при r 4 для любых = (1, 2) Gn \0, Gn выполняются следующие неравенства:

p(r)(, ) , если 2 {1, 8} или {(1, 0), (8, 0)};

p(r)(, ) , если 2 = 6 или = (6, 0); p(r)(, ) -- в остальных случаях.

Для сравнения отметим, что формула (6) позволяет установить лишь равномерную верхнюю границу: p(r)(, ) для всех Gn \0, Gn.

Полученные выше аналитические соотношения (9), (29) могут быть использованы, прежде всего, на этапе предварительного анализа стойкости данного DES-подобного шифра к разностным криптоаналитическим атакам, в частности, при определении высоковероятных разностных характеристик [5, 6] или оценке вероятностей отдельных тактовых дифференциалов этого шифра. Другим возможным применением доказанной теоремы является синтез рандомизированных блочно-итерационных шифров, имеющих обоснованную стойкость к разностному криптоанализу [10]. В этом случае границы (9), (29) могут быть положены в основу алгоритмов конструктивного построения эффективных (с точки зрения практической стойкости к разностным атакам и скорости шифрования информации) рандомизаций данных DES-подобных блочных шифров.

Литература

Молдовян А.А., Молдовян Н.А., Гуц Н.Д., Изотов Б.В. Криптография: скоростные шифры. -- С-Пб.: БХВ-Петербург, 2002. -- 496 с.

Харин Ю.С., Берник В.И., Матвеев Г.В. Математические основы криптологии. -- Минск.: Изд-во БГУ, 1999. -- 319 с.

Feistel H. Cryptography and computer privacy // Scintific American. -- 1973. -- Vol. 228, № 5. -- P. 15-23.

Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. -- М.: Триумф, 2002. -- 816 с.

Biham E, Shamir A. Differential cryptanalysis of DES-like cryptosystems // J. Cryptology. -- 1991. -- Vol. 4, № 1. -- P. 3-72.

Lai X., Massey J.L., Murphy S. Markov chiphers and differential cryptanalysis // Advances in Cryptology - EUROCRYPT' 91, Proceedings. -- Springer Verlag, 1991. -- P. 17-38.

Nyberg K., Knudsen L. Provable security against differential cryptanalysis // Advances in Cryptology - CRYPTO' 92, Proceedings. -- Springer Verlag, 1993. -- P. 566-574.

Nyberg K. Differentially uniform mappings for cryptography // Advances in Cryptology - EUROCRYPT' 93, Proceedings. -- Springer Verlag, 1994. -- P. 55-64.

Chabaud F., Vaudenay S. Links between differential and linear cryptanalysis // Advances in Cryptology - EUROCRYPT' 94, Proceedings. -- Springer Verlag, 1995. -- P. 356-365.

Алексейчук А.Н., Васюков И.В., Корнейко А.В. Обоснование стойкости вероятностных моделей рандомизированных блочных шифров к методу разностного криптоанализа // Электрон. моделирование. -- 2004. -- № 2 (в печати).

Размещено на Allbest.ru