On impossible truncated differentials of XSL ciphers.pdf Идея использовать невозможные разности, т. е. разности с нулевой вероятностью,для определения ключа шифрования была предложена Л. Р. Кнудсеном [1] при ана-лизе алгоритма блочного шифрования DEAL. Позже невозможные разности применя-лись для атак на алгоритмы блочного шифрования Skipjack [2], MISTY1 [3], AES [4],ARIA [5] и др.Пусть Xх = X\0; S(X) - множество всех подстановок на множестве X; V - мно-жество всех t-мерных векторов над GF(2); m = d q; s0,... ,sq - 1 Е S(Vd); Hd ЕЕ {Vd, GF(2d) j-; 0} , B3j) = {i Е {0,..., q - 1} : bj4 > 0} .В работе рассматриваются алгоритмы блочного шифрования с раундовой функ-цией ge : Vm - Vm, заданной как = (а ф в)sa для всех в, a Е Vm, и /3fcb ...,k j ) == gk1 ... gkj - j-раундовая функция зашифрования. Предполагается, что раундовыеключи k1,... , k выбираются случайно и равновероятно из Vm.Зафиксируем номера координат {j^,... , j c } С {0,... , q - 1} , j < ... < jc. ПоложимЛ(л,... , jc) = {а Е Hd : aj = 0, t = 1 , . . . , c } .Множество разностей ( A J 1 . . . , jc), А(^,... , it/)) называется невозможной усечён-ной разностью для преобразования v Е S (Vm), если для любых векторов а ЕЕ A ( j b ... , jc), в Е A ( i b . . . , it/) выполняется равенство (v) = 0, где(v) = 2 - m |{Л Е Vm : (Л ф a)v ф Av = в}| .В этом случае при v = /3k1,...,kj) будем использовать обозначениеЛ(Л, ...,Л'С) -j А(гх,... ).Покажем, что для большого класса XSL-алгоритмов блочного шифрования суще-ствуют 3-раундовые невозможные разности.Утверждение 1. Пусть a - такая произвольная обратимая (q х q)-матрица надполем GF(2) (GF(2d)), что по крайней мере один элемент в столбце af или bf равеннулю для некоторого t G { 0 , . . . , q - 1} . Тогда существует 3-раундовая невозможнаяусечённая разность Л^) Л(;)а для некоторых i, j G { 0 , . . . , q - 1} .Таким образом, для любой обратимой матрицы a над полем GF(2) в алгоритмешифрования XSL существует 3-раундовая усечённая невозможная разность, а значит,и просто 3-раундовая невозможная разность. Это следует из того, что если все эле-менты матрицы a равны единице, то она является необратимой. Приведём условия,при которых существуют 4-раундовые невозможные усечённые разности.Утверждение 2. Пусть i , j G {0, . . . , q - 1} . Пусть также для всех

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