22231

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

Лекция

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

Введение в дифференциальный криптанализ Анализ требований к отбору S блоков разработчиков стандарта. Построение произвольной двухблочной характеристики обозначает левый полублок в скобках приводится вариант активизации на промежуточном цикле S блоков S7 и S8. Для того чтобы уйти от однобитного перехода на втором цикле можно взять левый полублок с битами попадающими на те же входы S блоков S блоки S5 и S6 что и использованные ранее входы  18 и 23 биты должна сохраниться идея активизации на каждом цикле не более двух S блоков. Для...

Русский

2013-08-04

291 KB

3 чел.

ЛЕКЦИЯ 7

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

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

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

 

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

,

если  и

,

если .

Для

имеем

..

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

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

В рамках рассматриваемого примера (см. рис.1) на первом цикле уже используется многобитный вход. Для того чтобы уйти от однобитного перехода на втором цикле можно взять левый полублок с битами, попадающими на те же входы S блоков (S блоки S5 и S6), что и использованные ранее входы  18 и 23 биты (должна сохраниться идея активизации на каждом цикле не более двух S блоков). Это могут быть 19, 20, 21, 22 биты. В итоге можно сформировать 3-цикловую характеристику с двумя активными S блоками  P = 19,20,21,22, 2,3,4,5,6,7   T = 19,20,21,22, 2,5,6,7, которая также допускает итеративное продолжение (3, 4 и 18, 23 биты попарно то компенсируются, то возникают снова). Можно использовать и не итеративные продолжения рассматриваемой характеристики (например, взять  = 18, 23, 28, 31 и т.д. , а точнее рассматривать итеративные характеристики с большим чем 4-е числом циклов).

Разработчики стандарта ясно представляли опасность двухблочных характеристик второго типа и для защиты шифра от атак, использующих эти характеристики, наложили ограничение на максимально возможное значение выходов таблиц побитовых разностей. Этому служит требование 7, в соответствии с которым допустимое значение выходов таблиц побитовых разностей ограничено значением 16 (не более 8 из 32-х пар 6-битных входов могут показывать одни и те же выходные различия). Действительно, если вести расчеты, ориентируясь на реализацию двухблочной 16-ти цикловой характеристики, то для самого благоприятного с точки зрения криптоаналитика (и практически невероятного) случая, когда в каждом цикле удается использовать характеристику с максимальной вероятностью равной , для шифра DES можно прийти к оценке

.

Для 16-ти цикловой атаки с отмеченными максимально допустимыми значениями таблиц парных разностей S блоков уязвимыми могут оказаться характеристики смешанного типа, когда на одном цикле активизируется два S блока, а на очередном только один. Так, например, расчет вероятности 16-ти цикловой характеристики типа 2+1+2+1 и т.д., приводит к результату

.

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

. (1)

где  и   полублоки на входе и выходе F функции DES на i-том цикле. Это значит, что три соседних цикла дифференциальной характеристики жестко связаны между собой свойством цикличности, которое проявляется в том, что выходные биты промежуточного цикла должны подтверждать инициализацию входов (входные биты) окаймляющих циклов (должны содержать входные биты S блоков (по крайней мере одного из S блоков) окаймляющих циклов.

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

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

1

  23  1

23, 31  2, 3 1

  31 1

2

 23, 31 2

23  2, 3 1

 31 1

3

 23, 31 2

31  2, 3 1

 23 1

3

17 2

17, 31  2, 3 1

 31 1

4

 23, 17 3

23  2, 3 1

 17 2

5

 31, 17 3

31  2, 3 1

 17 2

6

 9 2

23, 9  2, 3 1

 23 1

7

 23, 9 3

9  2, 3 1

  23 2

8

 23, 9 3

23  2, 3 1

 9 2

Рис. 1. Примеры распределений выходных битов одноблочного цикла по входам примыкающих к нему циклов для S блока S1.

Здесь приведены только композиции, включающие не более двух битов выходов одноблочного цикла. Выходы с большим числом битов будут всегда приводить к характеристикам, выходящим за интересующие нас пределы (нас интересуют характеристики двухблочного типа). 

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

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

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

Примеры 3 и 6 ввиду того, что однобитные переходы в ноль, как уже было показано выше, запрещены, также приводят к инициализации на очередном цикле более четырех S блоков.

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

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

Более того, приведенные рассуждения можно обобщить и на случай, когда к одноблочному циклу примыкающим является цикл с большим чем два числом S блоков (примеры 4,5,7,8, и могут быть построены многие другие варианты, в том числе при использовании большего чем два битов выходов одноблочного цикла). Опять это будут S блоки с однобитными входами (за исключением случая, когда входы S блоков примыкающих циклов совпадают). Поэтому можно убедиться в справедливости более общего утверждения.

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

3. Трехблочные характеристики.

Напомним, что характеристики обнуляющего типа могут строиться только из связанных (смежных) S блоков. Здесь должны уже рассматриваться 14-битные входы цикловой функции вида (0, 0, x, y, z, 1, t, p, 1, q, l, m, 0, 0), причем биты z и q не могут быть одновременно равными нулю (т.к. переход в 0 для входной разности вида (0, x1, x2, x3, x4, 0) невозможен). В табл. 1 представлены все возможные варианты входов в таблицы разностей S блоков, которые могут участвовать в формировании трехблочных характеристик (характеристик с тремя активными S блоками в одном из циклов).

Таблица 1

Участие S блоков в формировании входной разности при трехблочной характеристике (0, 0, x, y, z, 1, t, p, 1, q, l, m, 0, 0)

z

Входы первого

S блока

z

q

Входы второго

S блока

q

Входы третьего

S блока

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

(0, 1, 0, 0, 1, 1) 13x

(1, 0, 0, 0, 0, 0) 20x

0

(0, 0, 0, 1, 0, 1) 5x

0

(0, 1, 0, 1, 1, 1) 17x

(1, 0, 0, 1, 0, 0) 24x

(0, 0, 1, 0, 0, 1) 9x

1

(0, 1, 1, 0, 1, 1) 1Bx

0

(1, 0, 1, 0, 0, 0) 28x

(0, 0, 1, 1, 0, 1)  Dx

(0, 1, 1, 1, 1, 1) 1Fx

(1, 0, 1, 1, 0, 0) 2Cx

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

(1, 1, 0, 0, 1, 0) 32x

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

1

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

1

(1, 1, 0, 1, 1, 0) 36x

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

(0, 0, 1, 0, 1, 1)  Bx

0

(1, 1, 1, 0, 1, 0) 3Ax

1

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

(0, 0, 1, 1, 1, 1)  Fx

(1, 1, 1, 1, 1, 0) 2Ex

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

(1, 1, 0, 0, 1, 1) 33x

1

(1, 1, 1, 0, 1, 1) 3Bx

1

(1, 1, 0, 1, 1, 1) 37x

(1, 1, 1, 1, 1, 1) 3Fx

Всего получается  вариантов входов для каждой тройки таблиц, а для шифра в целом  вариантов.

Для DES  в соответствии с ранее оговоренными ограничениями (требования 3 и 4) входы 30x, 34x, 38x, 3Cx, 1x и 30x во всех таблицах разностей выбраны с нулевыми вероятностями переходов разностей в нуль. Поэтому остается 48 вариантов входов для каждой тройки смежных таблиц.

Расчеты показывают, что необходимо перекрыть все трехблочные обнуляющие характеристики, так как при  вероятность 16-цикловой характеристики, составленной из 2-цикловых характеристик обнуляющего типа (см. рис. 1, Л-5), получается равной .

Анализ показывает, что основная масса трехблочных обнуляющих характеристик оказалась перекрытой за счет требования 6 (если два входа S блока отличаются своими первыми двумя битами и имеют совпадающими 2 последних бита, то выходные биты не должны быть теми же самыми (  для любых e и f). В соответствии с этим требованием входы 30x, 34x, 38x, 3Cx во всех таблицах парных разностей выбраны с нулевыми вероятностями переходов в выходную разность ноль). Кроме того, по требованию 4 отсутствуют переходы в ноль для входов 1x и 30x. В результате из 192 вариантов остается перекрыть 48 возможных характеристик для каждой тройки смежных таблиц.

Решению задачи перекрытия оставшихся 48 вариантов, на наш взгляд, и должно было служить требование 8, ограничивающее число одинаковых выходных разностей для трех активных S блоков в одном цикле. Конечно это требование уже нужно относить не к 6-битным парам входов одного S блока, а к 14-битным парам входов сразу трех активных S блоков. Оно эквивалентно ограничению на максимально допустимое значение вероятностей хотя бы для одной из одноблочных характеристик, участвующих в формировании трехблочной 3-цикловой характеристики рис.1, Л-5. Однако в представленной редакции это требование остается трудно понимаемым. Если ориентироваться на его буквальный смысл, то оно для таблиц стандарта не выполнено (допустимое значение числа пар входов одного S блока, имеющих совпадающие выходы, ограничено значением 16). Зато, как показывает анализ таблиц побитовых разностей S блоков стандарта, выполнено другое требование, в соответствии с которым вероятность хотя бы одной из одноблочных одноцикловых характеристик, участвующих в формировании трехблочной характеристики ограничена значением . При этом значении для вероятности трехблочной 16-цикловой характеристики обнуляющего типа (опять для самого благоприятного с точки зрения криптоаналитика случая, когда в каждом цикле удается использовать характеристику с максимальной вероятностью), приходим к результату

,

что сложнее прямого перебора ключей.

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

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

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

, .

Анализ показывает, что с учетом приведенных оценок и следствия 2 речь может идти о трехблочных характеристиках смешанного типа, когда удается сформировать итеративную 3-цикловую характеристику, включающую один цикл с тремя активными S блоками, второй цикл с двумя активными S блоками и третий цикл тождественного типа (3+2+0). Расчет вероятности такой 15-цикловой характеристики приводит к оценочному результату

,

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

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

 

Г Г

Г Г

0 0

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

Это единственная итеративная характеристика с нечетным числом циклов. В приведенном примере при построении характеристики используются три первых S блока S1S2S3. Анализ завершающей цикловую функцию P подстановки показывает, что среди входных и выходных битов для этих трех S блоков имеется три совпадающих (повторяющихся) бита: это 2-ой, 6-ой и 9-ый, т.е. действительно можно построить характеристику, которая входную разность 40 40 80 00 преобразует в ту же самую выходную разность 40 40 80 00. Как следует из рис. 2, в этом случае двухкратное применение нетривиального тождественного преобразования в сочетании с тривиальным циклом позволяет получить трехцикловую характеристику итеративного типа. Аналогичные характеристики можно построить на основе других троек S блоков. Легко убедиться, что во всех возможных вариантах применяется два S блока с однобитными входами и один S блок (средний) с двухбитным входом, а на выходе каждого S блока используется только по одному биту. Но для таблиц S блоков стандарта однобитные переходы запрещены и, следовательно, для DES с таблицами, предложенными разработчиками, приведенные характеристики также не реализуемы.

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

Таким образом, нам удалось объяснить практически все требования, использованные разработчиками при построении таблиц стандарта (имеющие отношение к дифференциальному криптоанализу), за исключением требования 8 (для которого мы предложили уточненную редакцию).

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


 

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

55391. ПРОЕКТНА ДІЯЛЬНІСТЬ УЧНІВ НА УРОКАХ УКРАЇНСЬКОЇ МОВИ ТА ЛІТЕРАТУРИ 140 KB
  Метод проектів особливо на уроках української мови та літератури передбачає не тільки наявність субєктивно чи соціально значущої для учня проблеми не просто її дослідження пошук шляхів вирішення а й практичне впровадження отриманих результатів у тому чи іншому продукті діяльності.
55392. Проектная деятельность на уроке технологии 86 KB
  Обобщить знания о пищевом рационе режиме питания условиях приёма пищи и сформулировать правила рационального питания. Воспитывать бережное отношение к здоровью и продуктам питания.
55393. Метод проектов на уроках истории и во внеклассной деятельности 396 KB
  Материально-техническое обеспечение проекта: аудио видео стенд. Для подготовки учеников к настоящим проектам необходимо начать их знакомство с данной технологией на уровне второй ступени обучения.
55394. Використання проектної технології як засіб активізації пізнавальної діяльності учнів на уроках інформатики 339.5 KB
  Мій досвід роботи в школі показав що в розвитку зацікавленості до предмета не можна покладатися тільки на зміст виучуваного матеріалу уникаючи залучення учня до активної діяльності.
55395. Творчі проекти у початковій школі 44 KB
  Творчий проект Казка про народнопоетичні символи України Я і Україна 4 клас Мета проекту. Поглибити знання школярів про народнопоетичні символи України; розвивати творчу уяву звязне мовлення школярів; виховувати любов до Батьківщини. Учні ознайомлюються з народнопоетичними символами України; виконують завдання у групах Казкарі та Художники. Завдання Групі казкарів: скласти казки про рослинні та тваринні народнопоетичні символи України: вербу калину тополю соняшник соловейка лелеку та ін.
55396. У пошуках майбутньої професії 63 KB
  Мета: познайомити учнів з деякими професіями, стимулювати стійкий інтерес до здобуття професійних знань;розвивати ерудицію, кмітливість, винахідливість , артистизм, навики ділової гри; формувати свідоме ставлення до вибору професії.
55397. Проект по профориентации 467.5 KB
  С этого момента начинается работа над проектами. Каждый ребёнок получил задание в результате выполнения которого он должен прийти к выводу почему именно эта профессия ему нравится.
55398. МИР ПРОФЕССИЙ 241.5 KB
  Познакомить обучающихся с престижными редкими и новыми профессиями охарактеризовать предмет труда каждой профессии. Воспитывать житейское отношение к выбору профессии.
55399. Вибір майбутньої професії 145 KB
  У цьому випадку людина вивчає власні можливості інтереси здібності переглядає багато професій і свідомо обирає ту яка підходить саме для неї з урахуванням сучасних проблем суспільства та особливостей ринку праці.