The additive differential probability of k successive exclusive-or.pdf Существуют различные подходы для разработки алгоритмов симметричной криптографии. Один из них - ARX. Во всех примитивах этой архитектуры используются только три операции: сложение по модулю 2n (Ш), циклический сдвиг битов и побитовое сложение по модулю 2 (ф, XOR). ARX-шифры могут быть различных назначений, например блочные шифры FEAL [1], Threefish [2], поточные шифры Salsa20 [3] и его модификация ChaCha [4], хэш-функции BLAKE [5] и Skein [2]. Разностный криптоанализ - один из современных методов криптоанализа, предложенный в [6]. Для проведения разностного криптоанализа ARX-шифров при выборе в качестве разности сложения по модулю 2n необходима разностная характеристика adp®: adp®(a,e Y) = 4П |{x,y 6 Zn : (x Ш а) Ф (у Ш в) = (x Ф у) Ш Y}|- Здесь и далее с вектором х 6 Zn ассоциируется целое число xn + xn-1216 + ... + х12п-1. Многие свойства adp® изучены в работах [7, 8]. Однако в некоторых ARX-шифрах присутствует применение композиции побитовых XOR. Так, например, в хэш-функции EDON-R [9] используется XOR трёх векторов. В этом случае использование характеристики adp® может привести к неверным оценкам. Более точные оценки можно получить при прямом использовании аналогичной характеристики для XOR нескольких векторов, которая определяется как 1 k М1 Шф x16}^ i=1 adp®(a\\... ,ак ак+) = - |{x\\... ,xk 6 : ф^ Ш ai) = а' 2 kn i =1 Здесь и далее k 2. Многие свойства adpk® и adp® схожи. Так, в частности, симметрии аргументов adpk® аналогичны симметриям adp®, описанным в [8, разд. 4]. Однако случай замены аргументов на обратные относительно сложения по модулю 2n в случае нечётного k отличается от чётного k. В нечётном случае на обратный можно заменить только пару элементов одновременно. Теорема 1. Для любого набора аргументов характеристика adpk® обладает следующими свойствами: 1) adp® - симметрическая функция, то есть её значение не изменится при перестановке аргументов. Например, для любых а1,... , a4 G Zn справедливо adp® (а1, а2, а3 - а4) = adp® (а2, а1, а3 - а4). 2) Значение adpk® не изменится, если к любым двум аргументам прибавить 2n-1 по модулю 2n. Например, для любых а1 , . . . , а4 G Z2n справедливо adp® (а1, а2, а3 - а4) = adp® (а1 ffi 2n-1, а2 ffi 2n-1, а3 - а4). 3) Значение adpk® не изменится, если два аргумента одновременно заменить на обратные относительно сложения по модулю 2n. Например, для любых а1, . . . , а4 G Z2n справедливо adp®(а1, а2, а3, - а4) = adp®(-а1, -а2, а3, - а4). 4) При чётном k значение adpk® не изменится, если любой из аргументов заменить на обратный относительно сложения по модулю 2n. Например, для любых а1, . . . , а5 G Z2n справедливо adp® (а1, а2, а3, а4 - а5) = adp® (-а1 Для вектора а G Zn обозначим через а|| 1 и а||0 векторы (а1,... ап, 1) и (а1,... ап, 0) n из Zn+1 соответственно; вес Хэмминга wt(tt) = У® а^. Запись b а обозначает, что для i=1 векторов a, b G Z^1 выполнено bi С ai, i = 1,... , k +1. Тогда для adp® можно доказать рекуррентные формулы, аналогичные [8, теорема 3] и позволяющие получить значение adpk® от аргументов размерности n+1 при помощи набора значений adpk® от аргументов размерности n. Теорема 2. Для любого набора векторов а1,..., ак+1 G Zn и вектора a G Z2k+1, составленного из младших бит аргументов, выполняются следующие равенства: 1) если wt(a) нечётный, то adp®^®^,... ак||ак - ак+1||ак+1) = 0; 2) если k нечётное и a = (1, . . . , 1), то adp® (а11| 1,... ак || 1 - ак+1|| 1) = = Е adp®(а1 ffi Ь1,...,ак ffi bk - ак+1 ffi bk+1); 2к b^a, wt(b)-четн. 3) во всех остальных случаях adp®^®^,... ак||ак - ак+1||ак+1) = 1 Е adp®^1 ffi b1,..., ак ffi Ьк - ак+1 ffi Ьк+1). b^a Так, например, для любых а1, . . . , а4 G Z2n, согласно п. 1, справедливо adp® (а^О, а21|0, а31| 1 - а41|0) = 0. Согласно п. 3, справедливо adp®^1^, а21|0, а3||1-а41| 1) = -adp®(а1, а2, а3-а4)+-adp®(а1, а2, а3 ffi 1-а4 ffi 1) + +-adp®(a1, а2, а3 ffi 1 - а4) + iadp®^1, а2, а3 - а4 ffi 1). Заметим, что ранее известные формулы для adp® описываются пп. 1 и 3. Для вектора a € Zn обозначим через a вектор (a1 ф 1,... ,anф 1). Тогда симметрии из теоремы 1 позволяют в некоторых случаях записать рекуррентные формулы при помощи операции инверсии, анализировать которую проще, чем сложение по модулю. Например, adp3®(a||1, 3 1 a|| 1, a|| 1 - a|| 1) = -adp®(a, a, a - a) + -adp®(a,a,a - a)+ 4 3 8 3 + -adp® (a, a, a - a). 83 Рекуррентные формулы позволяют также найти максимум adpk® при чётном k аналогичный максимуму при k = 2, доказанному в [8, теорема 2]. Теорема 3. Для любого y € Zn и любого чётного k выполняется max adp®(a1,...,ak - y) = adp®(0,..., 0, y - Y)• a1,...,ak Однако при нечётном k данное утверждение неверно и аналогичный максимум adpk® выглядит иначе. Мы предполагаем, что он выглядит так: Гипотеза 1. Для любого y € Z2n и любого нечётного k выполняется max adpk®(a1, . . . , ak - y) = adpk®(y, . . . , y - y). a1,...,ak£Zn Гипотеза подтверждается вычислительными экспериментами и разбором некоторых частных случаев. В случае k = 3 для этого полезны следующие неравенства: Теорема 4. Для любого y € Z2n выполняется adP®(y> Y,Y - Y) < adP®(y> Y, Y - Y) < 3 adP®(y> Y,Y - Y). Отметим, что для разностного криптоанализа важно различать наборы аргументов, на которых adp® равно нулю. Теорема 5. При любом k и любом наборе аргументов a1, . . . , ak+1 € Z2n значение adp®(a1, . . . , ak - ak+1) = 0 тогда и только тогда, когда существует позиция i, такая, что вектор (a1,... , ak+1) = (0,... , 0), а для любой позиции j, n Y j > i верно (aj1, . . . , ajk+1) = (0, . . . , 0), и выполняется одно из следующих условий: 1) вектор (ai1, . . . , aik+1) имеет нечётный вес; 2) k нечётное, i > 1, вектор (ai1, . . . , aik+1) равен (1, . . . , 1) и вектор битов на разряд выше (ai1 1, . . . , aik+11) имеет нечётный вес. Заметим, что нули функции в случае чётного k выглядят аналогично нулям для adp®. Случай 2 появляется только при нечётном k и порождает дополнительное множество нулей характеристики.

Скачать электронную версию публикации