Критерии марковости алгоритмов блочного шифрования | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/3

Критерии марковости алгоритмов блочного шифрования

Изучаются вероятностные модели блочных шифрсистем, в которых случайные раундовые ключи независимы и одинаково распределены. Они называются марковскими шифрами, если последовательность раундовых разностей образует простую однородную цепь Маркова. Уточнены и обобщены критерий и достаточное условие марковости моделей шифрсистем. Расширен класс марковских шифров, построенный в диссертации швейцарского учёного X. Lai. Получены достаточные условия, при которых формула для матриц вероятностей переходов разностей расширенного класса содержит тензорное произведение матриц вероятностей переходов S-блоков.

Criteria for Markov block ciphers.pdf Введение Пусть на алфавите X входных и выходных блоков задана групповая операция ©, e £ X - нейтральный элемент, X-1 -обратный к элементу X группы (X, ©). Как принято в дифференциальном (разностном) анализе, величины вида X1 © X-1 будем называть разностями блоков X1,X2. Через X' = X \ {e} обозначим множество «ненулевых» разностей, M = |X| - 1 -его мощность. Через S(X) обозначим множество всех подстановок на множестве X. Рассматривается итеративный r-раундовый алгоритм блочного шифрования (3), в котором раундовые ключи принимают значения из некоторого множества Г, каждый набор раундовых ключей 7 £ Гг задает шифрующую подстановку gY £ S(X). Шифруется двублочный текст (X, X*). Будем работать в вероятностной модели такого случайного выбора текста и набора раундовых ключей, что открытый текст (X, X*) и набор 7 = (71,... , Yr) независимы; (1) ключи 71,... , Yr независимы и одинаково распределены. (2) Тогда, как известно из курса теории вероятностей, случайные последовательности промежуточных блоков X = X(0), X(1) = g7l(X(0)),... ,X(r) = glr(X(r - 1)) = Y, (3) X* = X*(0), X*(1) = g7i(X(0)),... ,X*(r) = g7r(X*(r - 1)) = Y*, последовательность их пар (X, X *), (X (1), X *(1)),..., (X (r), X *(r)) = (Y,Y *) (4) и последовательность промежуточных подстановок g(7i.....7t) = gYi ...да, 1 ^ t ^r, являются простыми (далее рассматриваем только такие) однородными цепями Маркова. Но не всякая функция от последовательности состояний цепи Маркова (и, в частности, разность компонент пар) образует цепь Маркова. Поэтому содержательно следующее определение. Определение 1. При условиях (1) и (2) будем говорить, что итеративный алгоритм шифрования (3) является марковским шифром (относительно операции © при заданных распределениях входной пары (X, X*) и раундового ключа 71), если последовательность случайных раундовых разностей AX = X*X-1, AX(1) = X*(1)X(1)-1, ..., AX(r) = X*(r)X(r)-1 (5) образует однородную цепь Маркова. В (5) (и далее там, где это удобно) знак операции © опущен для краткости. 1. Критерии марковости последовательности раундовых разностей Обозначим для краткости g = gYl; распределение этой случайной подстановки совпадает с распределением остальных раундовых подстановок согласно (2). В следующей теореме доказан критерий (7), близкий к условиям [1, 2], и новые критерии (8), (9), которые можно назвать условиями инвариантности распределения разностей подстановки g относительно фиксации входного блока и/или входной разности. Пункт 1 доказательства основан на идее [2] использования теоремы [3] об укрупнении состояний цепей Маркова. Теорема 1. Пусть выполнены условия (1) и (2), P = ||pa,b||a,bex' -фиксированная стохастическая матрица. Тогда эквивалентны следующие четыре условия: последовательность (5) образует однородную цепь Маркова (6) с матрицей вероятностей переходов P при любом распределении (X, X*); для всех a Е X' распределение g(ax)g(x)-1 не зависит от выбора x Е X; (7) Va Е X',x Е X (g(ax)g(x)-1 ~ g(aX)g(X)-1) при любом распределении X; (8) Vx Е X (g(AX x)g(x)-1 ~ g(AXX)g(X)-1) при любом распределении (X, AX). (9) При этом матрица P является дважды стохастической, pa,b = P{g(ax)g(x)-1 = b}, a, b Е X'. Доказательство. 1. Докажем эквивалентность условий (6) и (7). Условие (6) означает, что цепь Маркова (4) допускает такое укрупнение состояний, при котором все пары (x, x*) с одинаковой разностью a Е X' объединяются в одно состояние a' = {(x,ax) : x Е X}, состоящее из |X| пар. Заметим, что a' является смежным классом группы (X х X, ©) (являющейся прямым произведением двух групп) по её «диагональной» подгруппе X1 = {(x,x) : x Е X}, поскольку a' = (e,a) © X1. По теореме 6.3.2 [3, с. 160] такое укрупнение возможно при любом начальном распределении исходной цепи и даёт цепь Маркова с матрицей переходных вероятностей P тогда и только тогда, когда при любых фиксированных a, b Е X' вероятности P(x,x*),b' = Е P{X(1) = y, X*(1) = y* | X = x, X* = x*} (y,y*)& одинаковы для всех пар (x, x*) Е a' и равны pa,b. Но для таких пар x* = ax-1 и можно преобразовать P(x,x*),b' = Е P{g(X) = y, g(AX)g(X)-1 = b | X = x, AX = a} = P{g(ax)g(x)-1 = b}, yex где в последнем переходе использовано условие независимости (1). Итак, цепь Маркова (4) допускает укрупнение состояний при любом распределении (X, X* ) тогда и только тогда, когда правые части последнего равенства одинаковы и равны pa,b для всех x Е X, т. е. выполнено условие (7). 2. Справедливо следующее утверждение: если случайная величина £ является функцией от случайного вектора п и, возможно, некоторых других случайных величин, то условие инвариантности условных распределений (£ | п = с) относительно всех возможных фиксаций вектора п эквивалентно тому, что распределение £ одинаково при любом распределении п. Действительно, необходимость условия инвариантности относительно фиксаций очевидна, а достаточность легко вытекает из формулы полной вероятности P{£ = b} = Е P{n = с} P{£ = b| п = с} = P{£ = b| п = со} c для любого фиксированного со из множества значений п. Применяя это утверждение к случайной величине £ = g(aX)g(X)-1 при п = X, получаем равносильность (7) и (8). Применяя это утверждение к случайной величине £ = g(AXX)g(X)-1 при п = AX, получаем равносильность (7) и (9). 3. Полагая x = e в (7), получаем формулу pa,b = P (g(a)g(e)-1 = b} . (10) Из неё легко вытекает дважды стохастичность матрицы P: E?a,b = Е P{bg(e) = g(a)} = P {bg(e) e X \ {g(e)}} , что равно 1, поскольку bg(e) = g(e). Теорема 1 доказана. ■ Рассмотрим класс шифров, у которых раундовый ключ может быть разделён на две независимые части y = (5, е), первая из которых равномерно распределена на X и накладывается на шифруемый блок в соответствии с групповой операцией, а вторая определяет применяемую случайную подстановку f: Y = (5, е), (x) = f£(x © 5), 5 ~ U(X) и е независимы. (11) Схема шифрования пар блоков такими раундовыми подстановками иллюстрируется рис. 1. AY © -► f © -► f ... -l- AX 5(1) е(1)' 5(2) е(2) © -► f © -► f ... -=-*> Рис. 1. Схема шифрования [4], обеспечивающая марковость алгоритма Заметим, что схемы шифрования, использующие раундовые подстановки вида (11), близки к так называемым «key-alternating» шифрам, активно изучаемым в настоящее время. Следствие 1. Пусть выполнены условия (1) и (2). Тогда условие (11) является достаточным для каждого из условий (6)-(9). Доказательство. Согласно теореме 1, достаточно доказать, что условие (11) обеспечивает условие (7) инвариантности распределения разностей относительно фиксации входных блока и разности. Действительно, так как при любом x e X случайная величина y = x5 также имеет равномерное распределение на X и не зависит от случайной подстановки f£, то распределение #7 (ax)g7 (x)-1 = fe(ax5)fe(x5)-1 = fe(ay)fe(y)-1 определяется распределением f и значением a. ■ Заметим, что кроме случайных подстановок вида (11) условию (8) удовлетворяет равномерно распределённая подстановка а ~ U(S(X)), поскольку для неё распределение разности также не зависит от x e X и даже от a e X': P{a(ax)a(x) 1 = b} = Е P{^(ax)a(x) 1 = b, a(x) = y} = yex = E P{^(x) = y,a(ax) = by} = (M + 1),,, * ,, = -1. 1 (m + 1)M m Обсудим возможную практическую пользу от формулы (10). Начнем с автономной вероятностной модели: пусть K - множество всех ключей шифрования произвольной блочной шифрсистемы с некоторым заданным на нём вероятностным распределением. Это распределение при заданном алгоритме развёртывания ключа (АРК) индуцирует некоторое распределение на множестве Гг всех раундовых ключей, что с учётом распределения входной пары блоков позволяет найти матрицу P(r) вероятностей переходов разностей (5) за r раундов. Для реализации разностной атаки различения с фиксированной входной разностью a требуется знание строки Временная сложность метода вычисления Pir) путём перебора ключей шифрования и вычисления переходов за r раундов всех пар блоков с фиксированной разностью a близка к сложности |K|(M + 1) © 2r (12) операций вычисления значений раундовых подстановок. Эта величина превосходит сложность тотального опробования, и в ряде работ по разностному анализу (в основном начиная с [5, 6]) рассматриваются неавтономные вероятностные модели шифрсистем, где АРК отсутствует, и раундовые ключи считаются независимыми одинаково распределёнными случайными величинами, т. е. выполняется условие (2). Марковские шифры удобны тем, что для них = Pr и сложность вычисления P(r) близка к сложности вычисления P, которая, согласно (13), меньше (12) примерно в 2r|K|/|Г| раз. В следующей за [6] пионерской работе [1] перед теоремой 3 приведена («The (i, j) entry in П is P {AY(1) = aj | AX = a^}») фактически формула (в наших обозначениях) pab = P {g(aX)g(X)-1 = b} для элементов P. Вычисление по ней фиксированной строки Pa может быть осуществлено перебором всех x Е X, y Е Г и добавлением произведений P{X = x} P{y1 = Y} к счётчику, соответствующему элементу pa,b, b = (x)-1gY(xa). Для этого надо (M + 1)|Г| (13) раз произвести две операции вычисления значения раундовой подстановки, две групповые операции и одну операцию вычисления обратного элемента в группе (X, ©). Осталось заметить, что для вычисления Pa по формуле (10) аналогичным способом достаточно |Г| операций вычисления значения раундовой подстановки и операций ©, что примерно в 2M раз меньше сложности вычисления по формуле [1]. 2. Шифрование параллельным набором S-боксов и подстановкой Рассмотрим практически важный подкласс класса (11) марковских шифров, шифрование в перемешивающем слое которого осуществляется параллельным набором S-боксов, а затем действует подстановка п: g7(x) = П (/Ml (x1 ©1 £1), . . . , /m,£m (xm ©m £m)) , Y = (£,£), £ = (£1, . . . ,£m), £ = (^1, . . .,£m), (14) x = (x1,... ,xm) Е X = X1 x ... x Xm, где i-й S-бокс действует на множестве Xi, 1 ^ i ^ m, и выбирается случайно (в общем случае) из некоторого фиксированного набора функций (fi,j : Xi ^ Xi,j G Ji), Ji - некоторое множество индексов. В этом случае (X, ©) -прямое произведение групп (Xl, ©l),..., (Xm, ©m). Здесь в следующей формуле для матрицы вероятностей переходов разностей возникает тензорное произведение матриц вероятностей переходов разностей меньшей размерности. Теорема 2. Пусть при условиях (1), (2) в каждом раунде (14) компоненты 8^...,8m, el,...,em раундового ключа y независимы, 8i ~ U(Xi), 1 ^ i ^ m, подстановка п является гомоморфизмом группы (X, ©). Тогда при любом распределении (X, X*) последовательность (5) образует однородную цепь Маркова с множеством состояний X и дважды стохастической матрицей P = (Pl 0 ... 0 Pm)n, Pi = Iba?ja,bex, 1 ^ i ^ m, где П - матрица подстановки п; вероятности p^b = P{fi,ei(a ©i x)fi,£i(x)-l©i = b} вычислены в предположении независимости x ~ U (Xi) от ei. Доказательство. Положим fY(x) = п (fl,£1 (xl),..., fm,£m(xm)). Тогда (x) = = fY(x©8) и выполнено условие (11), поскольку, согласно условию теоремы, случайные векторы 8 ~ U(X) и е независимы. Поэтому из следствия 1 и теоремы 1 получаем, что последовательность разностей образует однородную цепь Маркова с дважды стохастической матрицей переходных вероятностей и множеством состояний X \ {e}, e = (el,... , em), ei - нейтральные элементы групп Xi. Нейтральный элемент e образует одноэлементный класс существенных состояний, и добавление его в множество состояний приводит к появлению соответствующего блока единичного размера на диагонали P, не влияя на дважды стоха-стичность матрицы. Найдём переходные вероятности. Для a = (al,... , am) G X и b' = (bl,... , bm) = = п-1(Ь) G X - прообраза блока b относительно действия п - имеем с учётом гомо-морфности п #7(ax)g-l(x) = п (fY(ax8)) п (fY(x8))-1 = п (f7(ax8)fY(x8)-) . Отсюда с учётом независимости случайных векторов (8i,ei), 1 ^ i ^ m, получаем Pa,b = P {f7(ax8)f7(x8)-1 = b'} = = П P {fi,ei (ai ©i xi ©i 8i)fi,ei (xi ©i 8i)- = bi} = p^b! ...pamm)bm. l^i^m Теорема 2 доказана. ■ Рассмотрим случай, когда все компонентные группы одинаковы, т. е. (X, ©) - прямое произведение m групп (Xl, ©), S-боксы выбираются из набора (fj : Xl ^ Xl, j G J): g7 (x) = п (fei (8l © xl),...,f£m (8m © xm)) , x =(xl,...,xm) GX = X^. (15) Если при этом индексы выбора одинаково распределены, то очевидно, что тензорное произведение матриц становится тензорной степенью одной матрицы. Следствие 2. Пусть при условиях (1) и (2) в каждом раунде (15) раундовый ключ y состоит из независимых в совокупности случайных величин ..., е1, ..., £m, где ^ ~ U(X1), а одинаково распределены. Пусть также подстановка п с матрицей П является гомоморфизмом группы (X, ©). Тогда при любом распределении (X, X*) последовательность (5) образует однородную цепь Маркова с дважды стохастической матрицей P = Р1т]П, P1 = | Pf faxf(x)-1 = 6|a,bexi, где вероятности вычисляются в предположении независимости x ~ U (X1) и е1. Отметим, что если в (15) операция © - сложение по модулю 2, то п является гомоморфизмом как в SP-сети, где п выбирается из группы перестановок координат векторов, так и в XSL-сети, где п выбирается из группы невырожденных линейных преобразований двоичных векторов. Прокомментируем теорему 2. Известно [6, следствие 1], что при шифровании набором параллельных S-боксов и покоординатном аддитивном наложении раундового ключа вероятность перехода разности равна произведению вероятностей переходов её составных частей. Другими словами, матрица вероятностей перехода разностей при таком шифровании является тензорным произведением соответствующих матриц переходов частей разностей, соответствующих S-боксам [2; 7, с. 11]. Но при этом были сформулированы не все вероятностные условия (в частности, не было условия (1)), при которых такая матрица является матрицей вероятностей переходов разностной цепи Маркова; в теореме 2 этот недочёт устранён. С другой стороны, часть ключа, управляющая выбором индексов S-боксов, либо отсутствовала [7] (и тогда этот набор постоянен в раунде), либо считалась равномерно распределённой [4]. Теорема 2 показывает, что условие равномерной распределённости необязательно. 3. Обсуждение результатов 3.1. Об определениях марковского шифра В [1] шифр называется марковским, если для всех а, b £ X' при равномерном распределении y г -1 ч (16) P {(AXX)gY(X) = b | AX = а, X = xj не зависит от выбора x £ X. Заметим, что при условии (1) независимости входных блоков и раундовых ключей вторая строка условия (16) становится условием (7). Доказано [1, теорема 2], что из (16) при условии (2) следует марковость последовательности разностей (5). Но в формулировке и в доказательстве теоремы имеются некоторые изъяны. В формулировке нет условия (1), без которого в общем случае даже последовательность пар блоков (4) не является цепью Маркова. В доказательстве показана марковость лишь отрезка из первых трёх разностей, не обоснована возможность исключения условия AX = а при переходе от строки 3 к строке 4 в цепочке равенств. В тезисах [8] указан ещё один некорректный переход в доказательстве теоремы 2 [1]. В работе [2] выбран другой подход к доказательству марковости, основанный на теореме 6.3.2 [3] о возможности укрупнения состояний цепи Маркова, что позволило фактически доказать необходимость и достаточность условия (16) для марковости (5). В теореме 1 данной работы установлено, что доказательство [2] может быть проведено в условиях, когда раундовые ключи могут выбираться не обязательно равновероятно. Но для получения критерия условие марковости последовательности разностей должно быть усилено требованием его выполнения при любом распределении входной пары блоков, иначе остаётся потенциальная возможность слабого укрупнения состояний [3, с. 169]. Доказанная дважды стохастичность P равносильна установленной в теореме 2 [1] стационарности равномерного распределения разностей. Заметим, что в нашей работе в качестве определения марковского шифра выбрано условие марковости (5) как более естественное по сравнению с близким к нему условием (16). Достаточное условие (11) нашей работы является ослаблением условия [4, теорема 6], поскольку не требует равномерности распределения второй части раундового ключа. При этом доказательство его достаточности значительно проще доказательства теоремы 6 [4, с. 44]. До работы [4] марковость моделей шифрсистем доказывалась лишь в частных случаях для DES [6, лемма 1, теорема 1], PES [1, лемма 1], а также для шифрсистемы IPES, позже названной IDEA [4, с. 57]. Заметим, что условие (11) позволяет рассматривать другие вероятностные модели IDEA, в которых часть (Z^l), Z^l)) [4, с. 65] раундового ключа не обязательно равномерно распределена, что может способствовать построению атак на слабые части ключа. 3.2. О к р и т и к е м а р к о в с к о й м о д е л и Марковская модель блочных шифрсистем активно используется в англоязычной литературе с начала 1990-х гг. Примерно с 2006 г. интерес к ней стали проявлять украинские авторы [9-11], а в последние годы и российские. Вместе с тем имеются и критики этой модели, поскольку она, естественно, далека от совершенства. Они обычно выдвигают следующий аргумент: «в реальности ключ всегда один и фиксирован, а не случаен». (17) Приведём контраргументы. 1. Существует ряд ситуаций, в которых наблюдаются несколько шифртекстов, выработанных на разных ключах шифрования, например: а) ключи получены из одного долговременного и различных разовых ключей; б) ключи получены из фиксированного ключа и различных известных инициализирующих векторов (tweakable ciphers); в) связанные ключи. 2. При некоторых алгоритмах развертывания ключа раундовые ключи, полученные на первых раундах, слабо зависимы, т. е. они близки к случайным независимым равновероятным векторам при случайном равновероятном выборе ключа шифрования. Модель случайного выбора ключа позволяет привлекать аппарат теории вероятностей для изучения характеристик «типичной» случайной подстановки, реализуемой блочной шифрсистемой, а также для изучения распределения вероятностей отклонений от таких характеристик. 3. Очевидно, аргумент (17) относится не к марковским шифрам как таковым, а вообще к неавтономным вероятностным моделям блочных шифрсистем. Но, например, в теории поточных шифрсистем давно используется и не вызывает возражений аналогичная модель для фильтрующего генератора, когда линейная рекуррентная последовательность, определяемая ключевым начальным заполнением, заменяется на последовательность независимых равновероятных битов. Для блочных шифрсистем увеличивается только размерность задачи и последовательность раундовых ключей, определяемая ключом шифрования, заменяется на последовательность независимых равновероятных двоичных векторов. Теория марковских шифров, как уже сказано выше, всего лишь изучает условия, при которых пары шифруемых блоков могут быть укрупнены в их разности с сохранением марковского свойства, которое даёт затем удобное равенство Колмогорова - Чепмена P(r) = Pr для матрицы переходных вероятностей за r тактов. Подводя итог, перечислим достоинства (+) неавтономных моделей и некоторые их недостатки (-) как естественные продолжения достоинств: (+) возможность исследования вероятностей переходов блоков и пар блоков за r раундов методами цепей Маркова, простое вычисление P(r) = Pr; (-) возникновение вопроса об адекватности модели; (+) результаты анализа устойчивы к модификации АРК; (-) теряется информация о возможной связи между раундовыми ключами; (+) в марковских алгоритмах шифрования: возможность сокращения в два раза размерности состояния при переходе в неавтономной модели от пар блоков к их разностям. Автор выражает признательность Б. А. Погорелову за постановку задачи и внимание к работе и Ф. М. Малышеву, чьи замечания способствовали существенному упрощению формулировок и доказательств результатов.

Ключевые слова

марковские шифры, случайные подстановки, вероятности переходов разностей, Markov ciphers, random permutations, transition probabilities of differentials

Авторы

ФИООрганизацияДополнительноE-mail
Денисов Олег ВикторовичООО «Инновационные телекоммуникационные технологии»кандидат физико-математических наук, доцентdenisovOleg@yandex.ru
Всего: 1

Ссылки

Lai X., Massey J., and Murphy S. Markov ciphers and differential cryptanalysis // Eurocrypt-1991. LNCS. 1991. V. 547. P. 17-38.
Погорелов Б. А., Пудовкина М. А. Разбиения на биграммах и марковость алгоритмов блочного шифрования // Математические вопросы криптографии. 2017. Т. 8. Вып. 1. С. 107-142.
Кемени Дж., Снелл Дж. Конечные цепи Маркова. M.: Hayra, 1970. 271c.
Lai X. On the Design and Security of Block Ciphers: dissertation for the degree of Doctor of Technical Sciences. Swiss Federal Institute of Technology, Zurich, 1992. 118 p.
Biham E. and Shamir A. Differential cryptanalysis of DES-like cryptosystems // CRYPTO-1990. LNCS. 1991. V. 537. P. 2-21.
Biham E. and Shamir A. Differential cryptanalysis of DES-like cryptosystems // J. Cryptology. 1991. V.4. No. 1. P. 3-72.
Глухов М. М. О рассеивающих линейных преобразованиях для блочных шифрсистем // Математические вопросы криптографии. 2011. Т. 2. Вып. 2. C. 5-40.
Дрелихов В. О., Никифоров М. С. О марковских свойствах усредненных разностных характеристик итеративных блочных шифров // Тез. докл. на конф. РУСКРИПТО, 2017. www.ruscrypto.ru/accociation/archive/rc2017.html
Алексейчук А. Н. Верхние границы параметров, характеризующих стойкость немарковских блочных шифров относительно методов разностного и линейного криптоанализа // Науково-техшчний журнал «Захист шформацп». 2006. Вып.3. С. 20-28.
Ковальчук Л. В. Обобщенные марковские шифры: построение оценок практической стойкости к дифференциальным атакам // Сб. материалов 2-й Междунар. научн. конф. по проблемам безопасности и противодействия терроризму, 25-26 октября 2006 г. М.: МЦ-НМО, 2006.
Лисицкая И. В., Долгов В. И. Блочные симметричные шифры и марковские процессы // Прикладная радиоэлектроника. 2012. Т. 11. Вып. 2. С. 137-143.
 Критерии марковости алгоритмов блочного шифрования | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/3

Критерии марковости алгоритмов блочного шифрования | ПДМ. 2018. № 41. DOI: 10.17223/20710410/41/3