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

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


 

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

22291. ПСИХОДИАГНОСТИКА РАЗВИТИЯ МЛАДЕНЦЕВ И ДОШКОЛЬНИКОВ 92.5 KB
  Рассмотрим некоторые шкалы развития младенцев. Гезелл и его коллеги подготовили таблицы развития охватывающие четыре основные сферы поведения: моторику язык адаптивное и личностносоциальное поведение. Они обеспечивают стандартизированную процедуру для наблюдения и оценки хода развития поведения ребенка в обыденной жизни.
22292. ПСИХОЛОГИЧЕСКАЯ ГОТОВНОСТЬ К ОБУЧЕНИЮ В ШКОЛЕ 85 KB
  Поэтому важно заранее еще до начала школьного обучения выяснить насколько психические возможности ребенка соответствуют требованиям школы. Показателями развития мышления до уровня готовности к школьному обучению является способность ребенка осуществлять мыслительные операции анализа синтеза сравнения обобщения в знакомом материале сформированность нагляднообразного мышления до уровня позволяющего выполнять учебные задания характерные для начального периода обучения. Личностная готовность предполагает зрелость мотивов учебной...
22293. СОЦИАЛЬНЫЕ И ЭТИЧЕСКИЕ АСПЕКТЫ ПСИХОЛОГИЧЕСКОЙ ДИАГНОСТИКИ. ЭТИЧЕСКИЙ КОДЕКС ПСИХОЛОГА-ДИАГНОСТА 69 KB
  Следует также заметить что студенты которые участвуют в учебном тестировании обычно не готовы к самостоятельному проведению диагностического обследования других людей и к интерпретации тестовых оценок. Неверные представления о характере и цели обследования а также неправильные интерпретации диагностических результатов лежат в основе многих распространенных ошибок и критических замечаний в адрес психологической диагностики. Полезный зарубежный опыт состоит также в том что для повышения профессиональных норм и улучшения качества...
22294. Психолого-педагогическая диагностика 38 KB
  Теоретические основы психодиагностики задаются соответствующими областями психологической науки общая дифференциальная возрастная медицинская психология и др. К методическим средствам психодиагностики относятся конкретные приемы изучения индивидуальнопсихологических особенностей способы обработки и интерпретации получаемых результатов. При этом направления теоретической и методической работы в области психодиагностики определяются главным образом запросами психологической практики.
22295. ИЗ ИСТОРИИ ПСИХОЛОГИЧЕСКОЙ ДИАГНОСТИКИ 140.5 KB
  Появление тестовых методов принято связывать с бихевиоризмом. Именно этим занимались первые психодиагносты разработавшие метод тестов термин введен Ф. В своей статье Интеллектуальные тесты и измерения 1890 год журнал Mind Мысль Кеттелл писал о том что применение серии тестов к большому числу индивидов позволит открыть закономерности психических процессов и тем самым приведет к преобразованию психологии в точную науку. Вместе с тем он высказал мысль о том что научная и практическая ценность тестов возрастет если условия...
22296. КЛАССИФИКАЦИЯ ПСИХОДИАГНОСТИЧЕСКИХ МЕТОДИК 125 KB
  К формализованным методикам относятся тесты опросники методики проективной техники и психофизиологические методики. Методики высокого уровня формализации Как уже говорилось выше они включают в себя четыре главных класса методик: тесты которые в свою очередь делятся на несколько подклассов опросники методики проективной техники и психофизиологические методики. Однако по своей психологической сущности тесты и например опросники очень несходны между собой. Тесты Тесты в переводе с английского испытание проверка проба ...
22297. ТРЕБОВАНИЯ К ПОСТРОЕНИЮ И ПРОВЕРКЕ МЕТОДИК 135.5 KB
  Обычно авторы методики в руководстве приводят точные и подробные указания по процедуре ее проведения. Формулирование таких указаний составляет основную часть стандартизации новой методики т. Другим наиболее важным этапом в стандартизации методики является выбор критерия по которому следует проводить сравнение результатов диагностических испытаний поскольку диагностические методики не имеют заранее определенных стандартов успешности или неудачи в их выполнении. В общих чертах стандартизация диагностической методики ориентированной на...
22298. Организация санитарно-противоэпидемических мероприятий в чрезвычайных ситуациях 181 KB
  Ознакомить студентов с организационной структурой и задачами санитарно-эпидемиологической службы, основами организации и порядком проведения противоэпидемических мероприятий в чрезвычайных ситуациях мирного и военного времени
22299. ОРГАНИЗАЦИЯ ОКАЗАНИЯ КВАЛИФИЦИРОВАННОЙ И СПЕЦИАЛИЗИРОВАННОЙ МЕДИЦИНСКОЙ ПОМОЩИ НАСЕЛЕНИЮ В ВОЕННОЕ ВРЕМЯ 160.5 KB
  Изучить организацию лечебно-эвакуационного обеспечения населения в очагах массовых санитарных потерь при применении противником ОМП. Рассмотреть организацию оказания квалифицированной и специализированной медицинской помощи пострадавшим. Изучить организацию работы второго этапа медицинской эвакуации