On the choice of slid pairs for the correlation cryptanalysis of KeeLoq.pdf KeeLoq - блочный шифр, широко используемый в системах бесключевого удалён-ного доступа. Шифр был разработан профессором Г. Каном и запатентован Южно-Африканской компанией «Nanoteq» в середине 80-х. В 1995 г. фирма «MICROCHIP»приобрела KeeLoq у фирмы «Nanoteq» вместе с лицензионными правами.Алгоритм KeeLoq [1] имеет 64-битный ключ и осуществляет шифрование 32-битныхблоков открытого текста. В нём используются два регистра сдвига: один - длины 64без функции обратной связи (для выработки подключа), другой - регистр сдвига дли-ны 32 с нелинейной функцией обратной связи NLF от пяти переменных (непосред-ственно для шифрования). Блок открытого текста помещается в текстовый регистр.Шифртекстом является состояние регистра после 528 циклов с использованием реги-стра ключа. Пусть Vn = GFn - множество всех n-битных слов; Y= (y^,... , У0*>) .Е V32 и K= ( к 6 з ,... , Уо^) . V63 - соответственно состояния текстового регистра ирегистра ключа после i тактов. Каждый цикл шифрования может быть описан следу-ющим образом:- вычисление очередного бита: ^ = NLF(y31, y2g>, y20, y(i), y(i>) ф y(6 ф y(i) ф ;- сдвиг состояния текстового регистра: Я(г+1) = (^,y3\),... , У1*>);- сдвиг состояния регистра ключа: K(г+1) = (k^, & 6 з , . . . , k(i)).Первый криптоанализ KeeLoq был опубликован только в феврале 2007 г. А. Богда-новым [1]. Эта атака основана на слайдовой технике и линейном приближении нели-нейной булевой функции, использующейся в KeeLoq. Криптоанализ имеет временнуюсложность 252 и требует 16 Гбайт памяти. Позднее Богданов обновил свой метод, ис-пользуя алгебраический криптоанализ для нахождения первых 16 битов ключа [2].Улучшение привело к уменьшению временной сложности до 250'6.В работе [1] Богданов описывает следующие шаги. Для каждого подключа K' == (k15,... , k0) и случайного 32-битного входа /0 G V32 с помощью парадокса дней рож-дения угадывается промежуточный шифртекст O0 G V32 после 64 циклов шифрования.Такая пара (/0,O0) называется слайдовой парой. Используя периодическую структу-ру ключа, в KeeLoq генерируются другие пары (/j, Oj) G (V32)2, i = 1,... , N - 1. Дляуспешной атаки их число должно быть около 28. Для каждого такого набора пар полу-чаются линейные соотношения для неизвестных битов ключа с высокой вероятностьюв связи с тем, что нелинейная функция обратной связи, использующаяся в KeeLoq, неявляется 2-устойчивой. Таким образом, можно определить (k47,..., k16) бит за битом.После этого решается треугольная система линейных уравнений для оставшихся битовключа (k63,..., k48).Отметим, что в методе А. Богданова для каждого подключа K' = (k15,... , k0) посути происходит полный перебор всевозможных пар (кандидатов на первую слайдовуюпару (/0, O0)) из случайного подмножества мощности 216 множества всех двоичныхвекторов длины 32 и для каждой такой пары (/0,O0) выполняется корреляционныйкриптоанализ.В данной работе предлагается на каждом шаге корреляционной атаки использо-вать найденные биты ключа для отсеивания неподходящих пар, а именно можно най-ти вероятностное соотношение между битами из правильной слайдовой пары и би-тами ключа, проверка которого позволяет для части неправильных пар остановитьвыполнение корреляционного криптоанализа уже на этом шаге. В этом соотношениииспользуется линейное приближение нелинейной функции NLF, выполняющееся с ве-роятностью 5/8.Например, связь бита y064) с битами на 16-м раунде выражается так:y064) = y3313) = NLF(y312), y2362), y202), y932), y 1 3 2 ) ) е yg2) е y032) е k* == y132) е y(32) е уГ е y032) е k32 = y(76) е y(56) е y317) е y(66) е k32 =у(76) е y256) е (NLF(y316),y266),У206),y(16),y(16)) е y(66) е y016) е Ы е y(66) е ^Таким образом, после того как будут найдены k16 и k32 на первом шаге корреляци-онной атаки, для отсеивания неправильных слайдовых пар используются биты ключа(&16, &15, ... , М и ^32.На каждом шаге корреляционной атаки используется дополнительное соотношениедля битов входного и выходного текста, что позволяет останавливать криптоанализс вероятностью 5/8 для каждой пары, которая не удовлетворяет полученным соотно-шениям. Следующая таблица иллюстрирует этот процесс.Шаг 0 1 2 15 16Количество слайдовых пар 232 231 2 3 0 217 216Найденные биты ключа &15, . . . , ^0 k16, k32 k17, k33 ^30, ^464731Во второй строке указано количество пар, для которых будет выполняться сле-дующий шаг корреляционного анализа. Например, изначально понадобится перебор232 пар. Затем находятся биты ключа k16 и k32 на первом шаге корреляционной атаки,которые используются в соотношении между y064) и битами шифртекста после 16 цик-лов. Значит, можно не рассматривать пары, не удовлетворяющие этому соотношению.Следовательно, число пар, для которых будет выполняться следующий шаг крипто-анализа, сократится до 231, и т.д.При выборе другого приближения нелинейной функции NLF можно добиться по-вышения вероятности нахождения правильной слайдовой пары.В дальнейшем необходимо определить параметры улучшенного метода криптоана-лиза: временную сложность, требуемую память и т. д.

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