Optimal linear approximations for Feistel networks. Estimation for the resistance of the cipher SMS4 to linear cryptanal.pdf Для применения линейного криптоанализа к итеративному блочному шифру тре-буется найти линейное приближение для конкретного числа раундов. Если известнолучшее приближение, то можно определить минимальную трудоёмкость линейногокриптоанализа шифра, то есть оценить его криптографическую стойкость. Таким об-разом, задача оценки криптографической стойкости сводится к поиску линейных при-ближений и нахождению среди них лучшего. В связи с этим возникает ряд проблем,так как, помимо того, что нужно исследовать раундовую функцию, необходимо пра-вильно согласовывать приближения раундов. Как правило, при проведении линейногокриптоанализа выбирается некоторое найденное линейное приближение без доказа-тельства того, что оно является лучшим.Для поиска лучшего приближения можно перебирать всевозможные линейные со-отношения, но на это может потребоваться больше времени, чем на составление сло-варя, поэтому необходимо придумывать другие способы. Предлагается подход к на-хождению линейных приближений сети Фейстеля и поиску оптимального.Определение 1. Раундовая функция - функция вида F : (Zm)n ^ Z^. ПустьF ( X 1 , X 2 , . . . , X n ) = Y, где Y,Xj e Z ™ i = 1, 2 , . . . , n .Как правило, раундовая функция сети Фейстеля удовлетворяет некоторым ограни-чениям, например, является простой (применяется в SMS4) или псевдо-простой (DES,TEA). Функция F называется простой, если F(X1 , X 2 , . . . , X n ) = G ( X 1 0 X 2 0 . . . 0 X n )для некоторой функции G : Z^ ^ Z^. Функция F называется псевдопростой, ес-ли F ( X 1 , X 2 , . . . , X n ) = G(L1(X1 ) 0 L2(X2 ) 0 . . . 0 Ln(Xn ) ) для некоторых функцииG : Z^ ^ Z^ и набора функций L 1 , . . . , Ln, где Lj : Z^ ^ Z™Определение 2. Линейным приближением функции F называется соотношениеbi Xi 0 62 X2 0 . . . 0 bn Xn = a F ( X i , . . . , Xn), (1)выполняющееся с вероятностью 1/2 + e, где |e| ^ 1/2, a, bj E Z^, i = 1, 2 , . . . , n.Величину e назовём линейным преобладанием соотношения или просто пре-обладанием. Вектор bi назовём маской для вектора Xi. Определим функциюRF : (Zm)n+1 ^ R, действующую на масках b1 , . . . , , a следующим образом:RF(bi,... ,bn,a) = 2 + е.Функция RF на масках b1 , . . . , b n , a принимает значение вероятности, с которойвыполняется соответствующее линейное приближение (1).Утверждение 1. Если F является простой и RF ( b 1 , . . . , bn, a) = 1/2 + е, где|е| > 0, то выполняется b1 = b2 = . . . = bn.Следствие 1. Пусть F является псевдопростой и RF ( b 1 , . . . , bn, a) = 1/2 + е, где|е| > 0. Тогда для некоторого набора функций / 1 , . . . ,/га выполняется /1(b1) = /2(b2) == . . . = /n(bn). При этом если одна из масок bi является нулевой, то b1 = . . . = bn = 0.Следствие 2. Если F является псевдопростой и хотя бы одна из масок b1, b2, . . .,bn, a является нулевой, тоRF(bi in,a) = ( 1 ' если = b2 = - = bn = a 11/2 иначе. = °'Открытый текст обозначим через X 0 , промежуточный шифртекст после i-го раун-да- через X1 , где Xг Е (Z^-)"", i = 0 , 1 , . . . На i-м раунде используется ключ K Е Zmm.Определение 3. Линейным приближением раунда r называется соотношениеa r - i X r - i 0 ar X r 0 a r = dr K rвыполняющееся с вероятностью 1/2 + er , где er > 0, ar Е Z2 , a r - i , ar Е (Zm)n, dr Е Zmm.Линейное приближение раунда строится на основе линейного приближения раун-довой функции F. Путём последовательного приближения раундов получаем прибли-жение нескольких раундов шифра.Определение 4. Линейным приближением p раундов шифра называется соотно-шениеa0 X 0 0 ap X p 0 а = d1 К 1 0 . . . 0 dP Kp , (2)выполняющееся с вероятностью 1/2 + е, е > 0.Если a0 совпадает с ap, то линейное приближение (2) называется замкнутым иимеет следующий вид:a0 X 0 0 a0 X p 0 а = d1 K 1 0 . . . 0 dP K p .Лучшим линейным приближением шифра считается то, преобладание которогомаксимально. Как правило, число раундов сети Фейстеля довольно большое, а ли-нейное приближение получается последовательным применением некоторого замкну-того линейного приближения и, если требуется, анализом ещё нескольких раундов.В данной работе для нахождения лучшего линейного приближения шифра предлага-ется найти лучшее замкнутое линейное приближение, а для этого нужно научитьсяих сравнивать. Для сравнения замкнутых линейных приближений с использованиемpiling-up леммы [1] вводится раундовое преобладание.Определение 5. Раундовым преобладанием линейного приближения p раундовназовём величинуе = (е 2 1 - p ) Р,где е является преобладанием линейного приближения p раундов.С помощью раундового преобладания можно сравнивать замкнутые линейные при-ближения различного количества раундов и определять оптимальное. Оптимальнымлинейным приближением раундов назовём замкнутое линейное приближение, такое,что его раундовое преобладание максимально. Оптимальное линейное приближениенаходится среди линейных приближений различного числа раундов.Проведена оценка стойкости шифра SMS4 (стандарт блочного шифр КНР для за-щиты беспроводных сетей WLAN [2]) к линейному криптоанализу.Теорема 1. Замкнутое линейное приближение пяти раундов SMS4а X 0 0 а X 5 = Y K 4 0 Y K 5 ,где а, X 0 , X 5 G (Z32)4, Y , K 4 , K 5 G Z32 и маска а имеет вид (0, 0, 0,Y), Y = 0x0011ffba,является оптимальным.Теорема 2. Минимальная трудоёмкость линейного криптоанализа девяти раун-дов блочного шифра SMS4 достигается при объёме статистики 284 и составляет 2115 за-шифрований.

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