On a set of impossible differences of feistel ciphers with a non-bijective transform of a round function.pdf Метод невозможных разностей, независимо предложенный в работах [1, 2], является одним из наиболее распространённых подходов для оценки стойкости алгоритмов блочного шифрования. Он применялся, например, для анализа алгоритмов блочного шифрования Skipjack [1], DEAL [2], Present [3], CLEFIA, Simon, Camellia, Lblock [4] и AES [5], а также для анализа семейств XSL-алгоритмов [6], алгоритмов шифрования Фейстеля [7] и обобщений алгоритма Фейстеля [8]. Кроме того, невозможные разности применяются в атаках различения [8, 9], а также для отсеивания ложных ключей в атаках, основанных на методе невозможных разностей [4, 5]. Поиск таких разностей для наибольшего числа раундов - основная задача при анализе алгоритма шифрования относительно метода невозможных разностей. Пусть m G N, m > 2, Vm - m-мерное векторное пространство над полем GF(2) с «естественной» операцией + сложения векторов, S(X) -симметрическая группа на множестве X. Определение 1. Для l-раундовой функции зашифрования g(l): Vm х K Vm с множеством ключей шифрования K пара разностей (е, 5) G называется l-раундовой невозможной разностью, если для всех (a, k) G Vm х K справедливо условие gkl)(a + е) = gkl)(a) + 5 где gkl) (в) = g(l)(e, k) для всех (в, k) G Vm х K. Определение 2. Невозможной тривиальной разностью будем называть такую невозможную разность (е, 5) G Vm х Vm, что е = 0 или 5 = 0. Опишем рассматриваемое семейство сбалансированных алгоритмов Фейстеля с небиективной функцией усложнения. Пусть A - произвольная (m х те.)-матрица над полем GF(2), rank(A) = m - 1. Зафиксируем отображения f : Vm Vm, h(0) : Vm Vm, h(1) : Vm Vm, заданные для каждого a G Vm следующими условиями: a h(1)(h(0)(a)); (1) h(1) : a - aA. (2) Рассмотрим также отображение v : \\"m x Vm - \\"m с частичной функцией vk € S(Vm): Vk : (ai, ao) 1-- (ao + f (ai) + k, ai) для всех (ao, ai, k) € V^. (3) Ясно, что Vk - частичная раундовая функция сбалансированного алгоритма Фей-стеля. Отметим, что условию (3) удовлетворяет алгоритм блочного шифрования GRANULE [10]. В данной работе для семейства l-раундовых сбалансированных алгоритмов шифрования Фейстеля с функцией усложнения, удовлетворяющей условиям (1)-(3), предложен способ построения невозможных разностей для произвольного числа раундов, а также приведена аналитическая оценка числа таких разностей. Метод не зависит ни от биективных компонент функции усложнения, ни от алгоритма развёртывания ключа. Основой его является следующая теорема: Теорема 1. Пусть A - произвольная (mxm)-матрица над полем GF(2), rank(A) = = m-1, раундовая функция v : Vm2x Vm - Vm2 задана условием (3). Тогда для каждого натурального l > 3 у l-раундового алгоритма шифрования с раундовой функцией v существует не менее 3 x 22n-2 - 2n+1 невозможных l-раундовых нетривиальных разностей. Предложенный в [9] алгоритм поиска невозможных разностей не учитывает ключевую особенность алгоритма шифрования GRANULE, а именно необратимость функции усложнения. Произведена его модификация путём изменения способа зашифрования разностей на описанный в [11]. Это позволило улучшить результаты [9] относительно числа найденных 7-раундовых различителей, а также получить экспериментальное подтверждение справедливости теоремы 1.

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