Шифр NSUPresent: устойчивость к линейному и дифференциальному криптоанализам | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/22

Шифр NSUPresent: устойчивость к линейному и дифференциальному криптоанализам

Рассмотрен шифр NSUPresent - модификация известного легковесного блочного шифра Present. Исследуется криптографическая стойкость данного шифра к линейному и дифференциальному криптоанализам. Получены теоретические оценки на дифференциальную и линейную характеристики шифра. Показано, что достаточно пяти раундов шифра NSUPresent, чтобы обеспечить устойчивость шифра к линейному и дифференциальному криптоанализам.

NSUPresent cipher: resistance to linear and differential cryptanalysis.pdf Пусть Fn - множество всех двоичных векторов длины n. Весом Хэмминга wt(x) двоичного вектора x G Fn называется количество единиц, содержащихся в x. Векторной булевой функцией называется функция вида F : Fn ^ F^. Функцию F также записывают как F = (/ь ..., /m), где /i,..., /m - координатные булевы функции от n переменных, а функции (b, F) = bi/i ф b2/2 ф ... ф bm/m называются компонентными, где b G Fm. Спектром Уолша - Адамара векторной функции F называется набор коэффициентов W(b,F}(y) = £ (-Функцию F : Fn ^ Fn можно рассматривать как функцию над конечным полем F2n и однозначно представлять в виде 2n-i полинома степени не выше 2n - 1: F(x) = £ tf*x*, где tf* G F2n. i=0 SP-сеть (подстановочно-перестановочная сеть) - одна из моделей построения итеративных блочных шифров - состоит из S-блоков, замещающих набор входных битов на соответствующий набор выходных битов, и P-блоков, перемешивающих биты. S-блок размера n - это отображение F : Fn ^ Fn (как правило, взаимно однозначное). Рассмотрим модификацию легковесного блочного шифра Present [1], в основе которого лежит SP-сеть (длина блока 64 бит, 31 раунд, слой S-блоков состоит из 16 одинаковых S-блоков размера 4). В отличие от Present, слой S-блоков NSUPresent состоит из четырёх S-блоков размера 16. Будем использовать перемешивающий слой шифра Present. Цель данной работы - найти минимальное количество раундов шифра NSUPresent, необходимое для криптографической стойкости шифра к линейному и дифференциальному криптоанализам. Введем для вектора а = (а1,..., an) G Fn следующие множества: gr/(а) = {[(i - 1)/4] + 1 : а* = 1}, gro(а) = {i mod 4 : а* = 1}. Если а - входной вектор S-блока, то множество gr/(а) задаёт активные входные группы S-блока, если выходной, то множество grO (а) задаёт активные выходные группы S-блока. Структура P-слоя такова, что каждая выходная группа S-блока связана ровно с одной входной группой S-блока следующего раунда. Будем использовать S-блок F : F^ ^ F26 с дополнительными условиями: 1) для любой ненулевой входной разности tf1 G F^ и любой ненулевой выходной разности G Fi6 выполняется |{x G F26 : F(x) ф F(x ф tf1) = }| ^ 4; 2) для любой ненулевой входной разности 81 G F1,6, такой, что |gr/(81)| = 1, выходная разность 8° = F(x) ф F(x ф 81) такова, что |gr°(8°)| ^ 2; 3) для любого a G F26 и всех ненулевых b G F26 выполняется |W(b,F)(a)| ^ 29; 4) для всех a G F26 и всех b G F26, таких, что |gr/(a)| = 1 и |gr°(b)| = 1, выполняется |WV)(a)| ^ 28. Первое и второе условия определяют дифференциальную характеристику S-блока и позволяют увеличить количество активных S-блоков при проведении дифференциального криптоанализа; третье и четвёртое определяют линейную характеристику S-блока. Отметим, что функция, удовлетворяющая данным условиям, существует, например функция обращения элемента в поле, используемая в шифре AES. Утверждение 1. Существуют коэффициенты a,b G F2i6, такие, что функция обращения F(x) = ax-1 + b удовлетворяет условиям 1-4. Основа линейного криптоанализа [2] -поиск линейного приближения, которое содержит биты открытого текста и шифртекста и имеет наибольшую вероятность выполнения. Линейная характеристика шифра - вероятность выполнения найденного линейного приближения. Теорема 1. Линейная характеристика для пяти раундов шифра NSUPresent р._35 меньше чем 2 35. В основе дифференциального криптоанализа [3] лежит анализ пар открытых текстов (P, P') и соответствующих им пар шифртекстов (C, С), между которыми существуют определённые разности, или дифференциалы а = P ф P', в = C ф С. Дифференциальная характеристика шифра - максимальная вероятность выполнения пары (а0,в0) из всевозможных пар (а, в). Теорема 2. Дифференциальная характеристика для пяти раундов шифра NSUPresent меньше чем 2-84. Для теорем 1 и 2 получены аналитические доказательства, в которых использованы свойства функции обращения и условия, накладываемые на S-блок. Следствие 1. Для проведения успешной атаки с помощью линейного криптоанализа потребуется более 270 пар открытых текстов / шифртекстов, а для дифференциального криптоанализа - более 284 пар текстов. Так как на вход шифра подаются блоки длины 64, то максимально возможное количество пар открытый текст / шифртекст равно 264. Следовательно, для проведения данных атак таких пар недостаточно.

Ключевые слова

differential crypt-analysis, SP-network, linear cryptanalysis, дифференциальный криптоанализ, lightweight block cipher, SP-сеть, линейный криптоанализ, легковесный блочный шифр

Авторы

ФИООрганизацияДополнительноE-mail
Манылов Егор АлександровичНовосибирский государственный университетстудентegormanylov@gmail.com
Всего: 1

Ссылки

Matsui M. Linear cryptanalysis method for DES cipher // Advances in Cryptology - EUROCRYPT'93. Berlin: Springer, 1994. P. 386-397.
Biham E. and Shamir A. Differential cryptanalysis of DES-like cryptosystems //J. Cryptology. 1991. V.4. No. 1. P. 3-72.
Bogdanov A., Knudsen L.R., Leander G., et al. PRESENT: An ultra-lightweight block cipher // CHES 2007. LNCS. 2007. V.4727. P. 450-466.
 Шифр NSUPresent: устойчивость к линейному и дифференциальному криптоанализам | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/22

Шифр NSUPresent: устойчивость к линейному и дифференциальному криптоанализам | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/22