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 (для которого мы предложили уточненную редакцию).

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


 

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

78693. ОЦЕНКА ЭФФЕКТИВНОСТИ ПРОЕКТОВ И ПРОГРАММ РЕНОВАЦИИ ЖИЛИЩНОГО ФОНДА 3.06 MB
  Целью диссертационного исследования является разработка методики оценки эффективности проектов реновации жилых зданий с учетом интересов субъектов инвестиционного процесса, и решение на этой основе вопросов экономического обоснования и формирования программ реновации жилищного фонда.
78694. «Северный край» - печатный орган оппозиции губерний Севера и Верхнего Поволжья конца XIX – начала XX веков 1.23 MB
  Конец XIX – начало XX в. для российской печати стали временем количественного и качественного роста. Данная тенденция в полной мере характерна и для столичной, и для провинциальной журналистики. Причин перехода отечественной прессы на новую ступень эволюции в это время несколько.
78695. Методические основы оценки конкурентной позиции предприятия на примере рынка водки г. Москвы 1.55 MB
  Между тем разработанные механизмы оценки взаимодействия конкCрентной и внутренней среды предприятия не позволяют определять эффе:тивность решений с точки зрения улучшения или укрепления конкурентной позиции предприятия относительно других производителей.
78696. МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ОЦЕНКИ АССОРТИМЕНТНОЙ ПОЛИТИКИ ПРЕДПРИЯТИЙ МЕБЕЛЬНОЙ ПРОМЫШЛЕННОСТИ 1.36 MB
  Практика реформирования экономики России наглядно продемонстрировала, что недооценка микроэкономических предпосылок роста реального сектора экономики может привести к негативному влиянию на экономическое развитие, к значительным потерям ресурсов и увеличению продолжительности реформ.
78697. Коррекция девиантного поведения подростков в условиях оздоровительно-образовательных центров 440.33 KB
  Рост девиантного поведения различных возрастных категорий населения несовершеннолетней молодежи обозначил актуальность проблемы организации профилактической работы с детьми и молодежью, но в связи с тем, что реализация профилактических технологий осуществляется с детьми...
78698. ПРАВОВЫЕ ОТНОШЕНИЯ В ИНФОРМАЦИОННОЙ СФЕРЕ 2.51 MB
  Сегодня все больше увеличивается значение информации в самых различных социальных процессах. Активное использование средств обработки и передачи информации развитие новых технологий вызывает существенные изменения в экономической политической и иных сферах общественной жизни.
78699. Ідея розвитку у працях Я. А. Коменського, М. Монтеня, Ж.-Ж. Руссо 69.5 KB
  Мета даного реферату - розкрита одну з головних проблем сучасної педагогіки, а саме проблему розвиваючого навчання. Можна із впевненістю сказати, що запровадження розвиваючого навчання в сучасну школу має величезне педагогічне значення.
78701. ЭРИКСОН ЭРИК 31 KB
  По Эриксону главной частью структуры личности является не бессознательное ИД как у Фрейда но сознаваемая часть Эго которая стремится в своем развитии к сохранению своей цельности и индивидуальности.