22239

Введение в дифференциальный криптанализ

Лекция

Информатика, кибернетика и программирование

Анализ требований к отбору S блоков разработчиков стандарта. В этом разделе мы хотим высказать свою версию обоснования требований к отбору S блоков выдвинутых разработчиками стандарта. Критерии отбора S блоков: 1. Если два входа S блока отличаются своими первыми двумя битами и имеют совпадающими 2 последних бита то выходные биты не должны быть теми же самыми  для любых e и f; Для любых ненулевых 6ти битовых различий между входами не более чем 8 из 32 пар входов могут показывать одни и те же выходные различия; Критерий подобный...

Русский

2013-08-04

626 KB

2 чел.

ЛЕКЦИЯ 5

Тема 2. Введение в дифференциальный криптанализ

1. Анализ требований к отбору S блоков разработчиков стандарта.

В этом разделе мы хотим высказать свою версию обоснования требований к отбору S блоков, выдвинутых разработчиками стандарта. Полезно их будет сразу напомнить в одной из известных редакций1.

Критерии отбора S блоков:

1. Каждый S блок имеет 6 входных и 4 выходных бита;

2. Нет выходного бита S блока, который может быть связан функцией близкой к линейной с входными битами;

3. Если зафиксированы самый левый и самый правый входные биты S блока и изменяются четыре его средних бита, то каждый из возможных 4-х битовых выходов получается точно один раз (  для любых a, b, c и d, );

4. Если два входа S блока отличаются точно одним битом, то выходы должны отличаться не менее чем в двух битах;

5. Если два входа S блока отличаются точно в двух средних битах, то выходные биты должны отличаться не менее чем двумя битами ( и  отличаются не мене чем двумя битами);

6. Если два входа S блока отличаются своими первыми двумя битами и имеют совпадающими 2 последних бита, то выходные биты не должны быть теми же самыми (  для любых e и f);

Для любых ненулевых 6-ти битовых различий между входами не более чем 8 из 32 пар входов могут показывать одни и те же выходные различия;

Критерий, подобный седьмому, должен выполняться и в случае трех активных S блоков.

Следует сразу отметить, что эти требования долгое время были неизвестными. Да и сегодня, имеющиеся сведения не позволяют считать, что требования опубликованы в полном объеме. Тем не менее мы покажем, что большинство из них (6 из 8-ми) направлены именно на защиту от атак дифференциального криптоанализа, т.е. разработчики стандарта тогда уже владели соответствующими методами. Однако, при разработке требований к отбору S блоков они, по-видимому, еще не знали о возможности использования атаки на укороченный до 13 циклов шифр DES и ориентировались на обеспечение его защищенности от 16-ти цикловых атак. Мы покажем, что если исходить из этих позиций, то им удалось перекрыть все практически возможные атаки дифференциального криптоанализа на него.

Как было отмечено ранее (см. Л-4), наиболее эффективными следует считать характеристики с максимально возможным числом тривиальных циклов. К ним относятся, прежде всего, итеративные характеристики, строящиеся с помощью обнуляющего разностного преобразования. Так мы назвали выполнение одноциклового преобразования, при котором ненулевая разность на входе цикловой функции F преобразуется в нулевую разность на ее выходе.. Если обозначить разность на входе цикла , то речь идет о характеристиках, для которых входная разность  с некоторой вероятностью  преобразуется в выходную разность . В сочетании с тривиальным циклом (в котором входная и выходная разности равны нулю) такое преобразование позволяет реализовать итеративную двухцикловую характеристику вида   , представленную на Рис. 1. Здесь  и  обозначены соответственно значения разностей на входе и выходе двухцикловой характеристики, а (x, y) конкатенация соответствующих разностей для левого и правого полублоков данных на входе и выходе характеристики.

Рис.1. Двухцикловая итеративная характеристика обнуляющего типа

Приведенная характеристика позволяет осуществить свое циклическое повторение необходимое количество раз. Именно в этом случае при проведении атаки удается построить характеристики с максимально возможным числом тривиальных циклов (с максимальной вероятностью). И среди них потенциально наиболее опасной является характеристика с одним активным S блоком в нетривиальном цикле. Именно с нее мы и начнем изучение условий перекрытия атак на шифр DES, учтенных разработчиками стандарта.

1.1. Одноблочные характеристики.

Рассмотрим некоторый произвольно взятый (один) S блок. Пусть   разность на входе этого S блока, а ,   отдельные биты этой разности. Нас будет интересовать в свете изложенного одноблочные переходы указанной входной разности в нулевую выходную разность S блока, т.е. переходы . Покажем, что требования к отбору S блоков, выдвинутые разработчиками стандарта, полностью исключают подобные характеристики.

Действительно, в соответствии с таблицей расширения E первый, второй, пятый и шестой биты входов каждого из S блоков становятся входными битами и соседних S блоков, и их ненулевые значения всегда активизируют соседние S блоки (входы соседних S блоков: (1, 0, 0, 0, 0, 0) 20x, (0, 1, 0, 0, 0, 0) 10x и (1, 1, 0, 0, 0, 0) 30x), (0, 0, 0, 0, 1, 0) 2x, (0, 0, 0, 0, 0, 1) 1x и
(0, 0, 0, 0, 1, 1)
2x)),. Так как мы строим цикловую функцию с одним активным S блоком, то этому условию удовлетворяют только нулевые значения общих с соседними S блоками входных битов. Это значит, что одноблочная характеристика в рассматриваемом случае может строиться лишь для значений входных разностей (6 -битных входов S блоков) вида (0, 0, x, y, 0, 0). В соответствии с правилами пользования таблицами стандарта (см. Л-2) эти разности определяются парами входов в таблицы S блоков из одной и той же строки каждой таблицы подстановок (см. табл. 1, Л-2). Легко убедиться, что требование 3 разработчиков стандарта как раз направлено на то, чтобы обеспечить полное перекрытие этих характеристик (если зафиксированы самый левый и самый правый входные биты S блока и изменяются четыре его средних бита, то каждый из возможных 4-х битовых выходов получается точно один раз. В соответствии с этим условием в качестве строк таблицы подстановок взяты перестановки (размещения без повторения элементов). Для строки в виде перестановки все 64 возможные пары входов, формирующих входную разность  для одного S блока (три нетривиальных варианта входных различий: (0, 0, 0, 1, 0, 0),
(0, 0, 1, 0, 0, 0) и (0, 0, 1, 1, 0, 0)), будут всегда давать несовпадающие выходы, и поэтому вероятности этих переходов для любого
S блока оказываются равными нулю (в табл.2, Л-2 для входных разностей 4x, 8x, Cx число возможных нулевых выходных разностей равно 0). Следовательно, обнуляющую характеристику  с одним активным S блоком и ненулевой вероятностью выхода для таблиц S блоков разработчиков стандарта построить нельзя. Их просто для этих таблиц не существует.

Отметим также следствие из приведенного обсуждения: многоблочные характеристики, использующие обнуляющее разностное преобразование, можно пытаться строить только из смежных или групп смежных S блоков.

Рассмотрим теперь возможность построения атаки для одноблочных характеристик не обнуляющего типа, т.е. при . Опять нас должны интересовать входные разности S блоков вида (0, 0, x, y, 0, 0). В этом случае снова разрешаются только три ненулевых значения входов (опять это 4x, 8x, Cx). Очевидно, что для построения характеристик в этом случае допустимыми являются только однобитные переходы через S блоки, так как из-за завершающей цикловую функцию P перестановки два и более битов на выходе любого S блока будут активизировать на следующем цикле сразу несколько S блоков. Но тогда для запрещения одноблочных характеристик с  достаточно таблицы S блоков строить без однобитных переходов. Это ограничение учтено требованием 4 разработчиков стандарта, и поэтому можно подвести общий итог: одноблочные характеристики для шифра DES просто нереализуемы.

Зафиксируем также важное для дальнейшего следствие последнего результата.

Следствие 1. При выполнении требований разработчиков стандарта к отбору S блоков дифференциальные характеристики шифра DES не содержат одноблочных переходов.

1.2. Двухблочные характеристики.

Перейдем теперь к изучению условий перекрытия двухблочных характеристик. Опять рассмотрим сначала характеристики, строящиеся с помощью обнуляющего разностного преобразования. Их, как уже отмечено выше, можно пытаться строить только для смежных S блоков. Для характеристики с двумя активными S блоками необходимо уже рассматривать 10-битные входные разности

.

Здесь опять из условия сохранения на каждом цикле именно двух активных S блоков необходимо рассматривать входные разности, удовлетворяющие условию: . Далее необходимо исключить характеристики, в которых  и (или)  = 1, так как при одном из ненулевых значений этих битов вероятность дифференциальной обнуляющей характеристики одного из S блоков равна нулю (для таблиц дифференциальных разностей S блоков с перестановками вероятности переходов всех входов от 1x до 10x в выходную разность 0x в соответствии с требованием 3 равны нулю). Тогда для получения двухблочной характеристики можно использовать только входные разности вида (0, 0, x, y, 1, 1, z, t, 0, 0). Это будет 16 вариантов сочетаний входов (входных разностей), представленных в табл.1.

Таблица 1

Входные разности

первого S блока

Входные разности

второго S блока

(0, 0, 0, 0, 1, 1) 3x

(1, 1, 0, 0, 0, 0) 30x

(0, 0, 0, 1, 1, 1) 7x

(1, 1, 0, 1, 0, 0) 34x

(0, 0, 1, 0, 1, 1) 11x

(1, 1, 1, 0, 0, 0) 38x

(0, 0, 1, 1, 1, 1) 15x

(1, 1, 1, 1, 0, 0) 3Cx

Из табл.1 легко видно, что для полного запрещения двухблочных характеристик, строящихся с помощью обнуляющего разностного преобразования, достаточно таблицы строить таким образом, чтобы или для входных разностей 3x, 7x, 11x, 15x или для входных разностей 30x, 34x, 38x, 3Cx были запрещены нулевые выходные разности. Легко убедится, что этому служит требование 6 разработчиков стандарта (если два входа S блока отличаются своими первыми двумя битами и имеют совпадающими 2 последних бита, то выходные биты не должны быть теми же самыми). Поэтому двухблочных обнуляющих характеристик здесь также запрещены.

Рассмотрим теперь процесс образования двухблочных характеристик с переходами . Воспользуемся для этого случая достаточно очевидным утверждением.

Утверждение. Пусть при построении дифференциальной характеристики на текущем цикле активизируется некоторое заданное число S блоков. Тогда для сохранения этого же числа активных S блоков на следующем цикле побитовая сумма по модулю два выходов S блоков текущего цикла со входами S блоков предыдущего цикла должна формировать вход в цикл, активизирующий это же число S блоков.

Действительно, выходом цикловой функции шифра DES является сумма по модулю два результата шифрования на текущем цикле правого входного полублока (результата его сложения с ключом и последующего прохождения через S блоки и P перестановку) с левым полублоком, являющимся входом цикловой функции предыдущего цикла. Но это же правило будет справедливо и для разностей (побитовых сумм по модулю два) входных и выходных блоков цикловой функции (при этом исключается явная зависимость от битов ключа).

Из этого утверждения приходим к следствию: Если на текущем цикле активизируется некоторое заданное число S блоков, то для того, чтобы на следующем цикле дифференциальной характеристики получить тождественное преобразование, выходы активизированных S блоков текущего цикла должны совпадать со входами активизированных S блоков предыдущего цикла.

Пользуясь приведенными правилами, легко убедиться в том, что принципиально можно пытаться строить двухблочные дифференциальные характеристики двух типов:

- с использованием тривиальных тождественных переходов (переходов с вероятностью единица);

- без использования тривиальных тождественных переходов.

Рассмотрим процесс построения произвольной характеристики с двумя активными S блоками. Пусть для конкретности это будут S блоки S1 и S2, как это показано на рис. 2.

Потенциально в активизации этих двух S блоков могут участвовать 2, 3, 4, 5, 6 и 7-ой биты 32-битной разности правых полублоков, участвующих в шифровании. На выходе этих S блоков (S1 и S2) в принципе могут быть задействованными 2, 9, 13, 17, 18, 23, 28, 31 биты (один или два, в зависимости от того, сколько S блоков следующего цикла активизирует каждый из них). В соответствии с правилами P и E преобразований DES из этих битов могут активизировать именно два первых S блока (если стремиться прийти к тождественному преобразованию) только вполне определенные биты (9, 17, 18, 23, 28, 31).

Пусть для конкретности используются ненулевые выходы S блоков S1 и S2, формирующие 18 и 23 биты (на промежуточном цикле активизируются S блоки S5 и S6). В соответствии с приведенным утверждением ненулевое значение  в данном случае может включать в себя либо биты, подтверждающие входы S блоков S5 и S6 (19, 20, 21 и 22 биты), либо биты, компенсирующие один из двух битов 18 или 23, или оба сразу и вводящие вместо них новые биты, активизирующих иную пару S блоков (например, 5, 6, 18, 23).

 

Вероятность 16-цикловой характеристики

,

если  и

,

если .

Для

имеем

..

Рис. 2. Построение произвольной двухблочной характеристики (обозначает левый полублок, в скобках приводится вариант активизации на промежуточном цикле S блоков S7 и S8).

В первом случае на очередном цикле снова активизируются S блоки S1 и S2, и естественно получается подтверждение (или компенсация) входных битов предыдущих циклов. Во втором,  активизируется новая пара S блоков (в рассмотренном примере S блоки S7 и S8). Видно также, что приведенная на рис. 2 характеристика во всех случаях допускает итеративное продолжение.

Формированию тождественного перехода в рассматриваемом примере соответствуют условия: либо  и тогда мы приходим к 6-цикловой итеративной характеристике с двумя тождественными циклами (две различные 3-цикловые характеристики, каждая содержащая тождественный цикл), либо для много битного входа  мы приходим к 8-цикловой итеративной характеристике с двумя тождественными циклами (две 4-цикловых характеристики, содержащие тождественный цикл каждая). Для входа  вторым можно получить тождественный цикл, при этом вход следующего за тождественным циклом будет  и далее ситуация сводится к рассмотренному выше случаю. Точнее, если правый полублок, поступающий на вход цикловой функции, содержит более двух битов, инициирующих заданную пару S блоков, то, как следует из рис.2, имеется возможность построить итеративную двухблочную характеристику с двумя тождественными циклами.

Формирование тождественного цикла при  (биты левого полублока являются нулями) констатирует приведенное выше следствие. Действительно, таблица P перестановки шифра DES разрешает в этом случае для входа в различные S блоки следующего цикла использовать только по одному выходному биту каждого из S блоков текущего цикла или два выходных бита одного из S блоков текущего цикла (каждый бит на выходе любого S блока попадает на входы различных S блоков следующего цикла). В результате на выходе двух S блоков можно использовать либо один бит (если он после E перестановки оказывается общим для входов сразу двух S блоков), либо два бита (если каждый их битов инициирует свой S блок). Условию подтверждения исходных входов S блоков S1 и S2 (входов предыдущего цикла) на выходе текущего цикла в рассматриваемом случае удовлетворяют только 18 и 23 биты (S блоки S5 и S6) и никакие другие биты этому условию не удовлетворяют. В результате формируется вход в S блоки очередного цикла равный нулю, т.е. мы приходим на очередном цикле к использованию тождественного преобразования тривиального типа .

Как показывает анализ, главной особенностью характеристик первого типа является непременное использование при их построении циклов, у которых входы в пары активизируемых S блоков содержат не более двух отличающихся битов (иначе не получится эффект компенсации битов при получении тривиального цикла). При этом возможны две ситуации. Либо различия с однобитными переходами используются уже на первом (начальном) цикле (у каждого из активизированных S блоков начального цикла используется однобитное выходное различие). Либо на первом цикле у одного из S блоков используется переход в ноль, а у второго двухбитное выходное различие. В последнем случае эти два бита поступают всегда на входы различных S блоков очередного цикла, а у тех в свою очередь активизируются однобитные выходы (выходные различия). В итоге можно сделать вывод, что во всех случаях при построении двухблочных характеристик с тождественными переходами используются циклы с однобитными переходами (переходами однобитных различий в однобитные).

Становится теперь понятным, что нужно сделать для того, чтобы характеристики с двумя активными S блоками сделать не реализуемыми. Для запрещения характеристик, использующих однобитные выходы сразу двух активных S блоков, в таблицах побитовых разностей должны быть запрещены все однобитные переходы. Для запрещения же характеристик, использующих один или два бита только одного из активных S блоков необходимо, чтобы были запрещены нулевые выходные разности для второго S блока. Таким образом, необходимо потребовать в первом случае, чтобы значения таблиц побитовых разностей для входов 1x, 2x, 4x, 8x, 10x, 20x по строкам и входов 1x, 2x, 4x, 8x по столбцам были нулевыми (требование 3 разработчиков стандарта), а во втором  запретить кроме указанных выше однобитных переходов и переход двухбитного входа 6x в ноль. Последнее условие учтено разработчиками стандарта требованием 5 (если два входа S блока отличаются точно в двух средних битах, то выходные биты должны отличаться не менее чем двумя битами). Заметим, также, что в случае использования однобитных выходов каждого из S блоков однобитные переходы используются на промежуточном цикле и при двухбитном входе .

1 Schneier B. Applied Cryptography. Second Edition^ protocols, algorithms, and Source code in C. Published by John Wiley & SonS, Inc, New york^ ChicheSter BriSbane Toronto Singapore, 1996. P 294.


 

А также другие работы, которые могут Вас заинтересовать

12802. ИЗУЧЕНИЕ СЛОЖНЫХ ЛОГИЧЕСКИХ ВЫСКАЗЫВАНИЙ 409.5 KB
  Лабораторная работа № 3 ИЗУЧЕНИЕ СЛОЖНЫХ ЛОГИЧЕСКИХ ВЫСКАЗЫВАНИЙ Цель работы: Изучить основы алгебры логики и составления сложных логических выражений. Краткие теоретические сведения Как и фундаментальные операции И ИЛИ и НЕ более сложные функции также мо...
12803. Реконструкция сиропного отделения при приготовлении помадных конфет производительностью 27 т/сут 1.78 MB
  Кондитерские изделия по своим вкусовым достоинствам, питательной ценности и усвояемости являются высококачественными продуктами питания, пользующиеся большим спросом у населения. Эта продукция широко представлена в торговле и общественном питании во всех населенных пунктах страны, но спрос на нее все не ослабевает
12804. ИССЛЕДОВАНИЕ ОДНОРАЗРЯДНЫХ СУММАТОРОВ И СИНТЕЗ МНОГОРАЗРЯДНЫХ СУММАТОРОВ 529.5 KB
  Лабораторная работа № 5 ИССЛЕДОВАНИЕ ОДНОРАЗРЯДНЫХ СУММАТОРОВ И СИНТЕЗ МНОГОРАЗРЯДНЫХ СУММАТОРОВ Цель работы: Изучить принципы работы одноразрядного сумматора и принципы построения многоразрядных сумматоров. Краткие теоретические сведения Сумматором
12805. ИЗУЧЕНИЕ РАБОТЫ ПОСЛЕДОВАТЕЛЬНЫХ И НАКАПЛИВАЮЩИХ СУММАТОРОВ 603 KB
  Лабораторная работа № 6 ИЗУЧЕНИЕ РАБОТЫ ПОСЛЕДОВАТЕЛЬНЫХ И НАКАПЛИВАЮЩИХ СУММАТОРОВ Цель работы: Изучить принципы построения последовательных и накапливающих сумматоров. Краткие теоретические сведения Последовательное суммирование многоразрядных чисел ...
12806. ИЗУЧЕНИЕ РАБОТЫ ЦИФРОВОГО ДВОИЧНО-ДЕСЯТИЧНОГО КОМБИНАЦИОННОГО СУММАТОРА 924 KB
  Лабораторная работа № 7 ИЗУЧЕНИЕ РАБОТЫ ЦИФРОВОГО ДВОИЧНОДЕСЯТИЧНОГО КОМБИНАЦИОННОГО СУММАТОРА Цель работы: Изучить принципы построения двоичнодесятичных комбинационных сумматоров. Краткие теоретические сведения Для построения двоичнодесятичного с
12807. ИЗУЧЕНИЕ РАБОТЫ УНИВЕРСАЛЬНОГО РЕГИСТРА 160.5 KB
  Лабораторная работа № 8 ИЗУЧЕНИЕ РАБОТЫ УНИВЕРСАЛЬНОГО РЕГИСТРА Цель работы: Изучить принцип работы 4разрядного универсального регистра и возможности его применения для записи и преобразования информации. Краткие теоретические сведения Вообще регистро
12808. ИЗУЧЕНИЕ РАБОТЫ ЛОГИЧЕСКИХ УСТРОЙСТВ 532.5 KB
  Лабораторная работа № 9 ИЗУЧЕНИЕ РАБОТЫ ЛОГИЧЕСКИХ УСТРОЙСТВ Цель работы: Изучить работу мультиплексоров демультиплексоров. Краткие теоретические сведения Мультиплексором называется логическое устройство которое позволяет выбирать только один из наб
12809. Исследование однофазного трансформатора малой мощности 753.5 KB
  Лабораторная работа №1 €œИсследование однофазного трансформатора малой мощности€ 1. Цель работы Целью работы является изучение принципа действия и устройства однофазного трансформатора малой мощности путём определения его основных параметров. Для изучен...
12810. Иccледование трёхфазного трансформатора 1.74 MB
  Лабораторная работа № 2 Иccледование трёхфазного трансформатора 1. Цель работы Цель работы заключается в изучении особенностей устройства и работы трёхфазного трансформатора освоении методов разметки фаз трёхфазного трансформатора определения начала и конца ...