22236

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

Лекция

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

Будем говорить что X может вызвать Y с вероятностью p для F функции если p есть доля всех возможных входных пар зашифрованных всеми возможными значениями подключа в которых входной XOR F функции равен X а выходной XOR равен Y. Если в DES X  Y X переходит в Y с вероятностью p для F функции то каждая фиксированная входная пара Z Z с Z = ZZ= X образует выходной XOR F функции равный Y с той же самой долей p возможных значений подключа. Очевидно что для каждого входного XOR имеем = независимо от ключа KS. Если имеется k входных пар...

Русский

2013-08-04

741 KB

1 чел.

Лекция 3

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

Следующее определение является расширением определений 3 и 4 предыдущей лекции на случай использования F функции:

Определение 1. Пусть X и Y будут 32 битовыми величинами. Будем говорить, что X может вызвать Y с вероятностью p для F функции, если p есть доля всех возможных входных пар, зашифрованных всеми возможными значениями подключа, в которых входной XOR F функции равен X, а выходной XOR равен Y. Если p > 0 мы обозначим эту возможность как X Y.

Лемма 1. Если в DES X Y (X переходит в Y) с вероятностью p для F функции, то каждая фиксированная входная пара Z, Z* с Z = ZZ*= X образует выходной XOR F функции, равный Y с той же самой долей p возможных значений подключа.

Д о к а з а т е л ь с т в о. Для того, чтобы доказать лемму достаточно показать, что указанное в лемме свойство выполняется для каждого S блока. Очевидно, что для каждого входного XOR  имеем  =  независимо от ключа KS. Если имеется k входных пар S блока с входным XOR-ом, который может вызвать данный выходной XOR, то мы можем выбрать точно k ключевых значений K =   , каждое из которых соответствует фиксированной входной паре ,  и, следовательно одной из возможных входных пар ,  S блока и, таким образом, вызывает данный выходной XOR. Поэтому дробь p содержит константу для всех входных пар, и, следовательно, равняется среднему значению над всеми входными парами.

В других итеративных криптосистемах эта лемма выполняется не обязательно. Тем не менее, мы допускаем что дробь очень близка к p, что является обычным (типичным) случаем.

Вывод 1. Вероятность p (перехода) XY для функции F есть произведение pi в котором XiYi для S блоков Si , где X1X2X3X4X5X6X7X8 = E(X) и Y1Y2Y3Y4Y5Y6Y7Y8 = .

Приведенные соображения по обнаружению ключевых битов, входящих в S блоки, могут быть расширены, для того чтобы находить подключи, входящие в функцию F. Эли Бихам и Ади Шамир предлагают для этого следующий порядок действий (метод):

Выберите подходящий XOR открытых текстов.

Присвойте соответствующие номера плайнтекстовым парам с выбранным XOR-ом открытых текстов, зашифруйте их и запомните только результирующие шифртекстовые пары.

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

Для каждой возможного ключевого значения подсчитайте количество пар, которые дают результатом ожидаемый выходной XOR, используя это ключевое значение на последнем цикле.

Правильным является (надо надеяться уникальным) ключевое значение, предложенное всеми парами.

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

Определение 2. (неформальное) Свяжем с любой парой шифрования, имеющей XOR значение ее (двух) открытых текстов, XOR ее зашифрованных текстов, XOR-ы входов и XOR-ы выходов каждого цикла в двух вариантах. Эти XOR значения формируют n-цикловую характеристику. Характеристика имеет вероятность, которая является вероятностью того, что произвольно взятая пара с выбранным плайнтекстовым XOR-ом имеет цикловые и шифртекстовые
XOR-ы, определенные характеристикой.

Обозначим XOR открытых текстов для характеристики , а XOR зашифрованных текстов .

Пример 1. На Рис. 1 приведена одноцикловая характеристика с вероятностью 1 (существует для любого ):

Рис. 1. Одноцикловая характеристика с вероятностью 1.

Это единственная одноцикловая характеристика с вероятностью большей чем 1/4. Она очень полезна и существует в любой DES-подобной криптосистеме. Характеристику этого типа мы будем называть тождественной или тривиальной. Следующий пример описывает одноцикловую характеристику с вероятностью 14/64.

Пример 2. В этой одноцикловой характеристике все S блоковые XOR-входы за исключением одного являются нулевыми. Один S блоковый XOR не ноль, и выбирается так, чтобы максимизировать вероятность, с которой входной XOR может вызвать выходной XOR. Так как здесь имеется несколько входных битов, которые расширением E активизируют два соседних S блока, то мы должны гарантировать, чтобы XOR-ы этих битов были нулями. Есть только два отдельных (внутренних) бита входа в каждый (один) S блок. Эти биты могут иметь ненулевые XOR значения. Наилучшее значение такой вероятности для S блока S1 равно 14/64 (т.е., есть существует выходная разность, которая образуется 14-ю парами входов таких, среди которых нет ненулевых битов входов в соседние S блоки S2 или S8). В результате легко получить одноцикловую характеристику с вероятностью 14/64, которая есть:

S1: 0Cx  Ex вероятностью 14/64;

S2, . . . , S8: 00x 0x всегда.

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

Рис. 2. Одноцикловая характеристика с вероятностью 1/4.

Одно цикловая характеристика с вероятностью 1/4 может быть построена для ненулевых входных XOR-ов в S блоки S2 или S6.

Пример 3. Двухцикловая характеристика с вероятностью 14/64 приведена на Рис.3.

Рис. 3. Двухцикловая характеристика.

Теперь мы можем дать точное определение характеристики:

Определение 3. n-цикловая дифференциальная характеристика есть форма вида , где  и  являются m-битными числами, а   список из n последовательных элементов , каждый из которых является парой формы , i = 2, . . . , n1 где    функционально связанные m/2 битовые числа (для DES это полублоки XOR входов и выходов циклового F преобразования), а m блочный размер криптосистемы. Характеристика удовлетворяет следующим требованиям:

 правой половине ;

 левой половине ;

 правой половине ;

 левой половине ,

и для каждого i такого, что  имеем

).

Таким образом, дифференциальная характеристика Фестель-подобного шифра, каким является шифр DES, удовлетворяет условию:

. (1)

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

Определение 4. Конкатенацией (объединением) n-цикловой характеристики  с m-цикловой характеристикой , где  равно переставленным значениям двух половин , есть характеристика , где   конкатенация списков из  и .

Следующие определения, лемма, вывод и теорема имеют дело с вероятностями характеристик:

Определение 5. Цикл i характеристики  имеет вероятность , если с помощью F функции осуществляется переход    с вероятностью .

Определение 6. n-цикловая характеристика , имеет вероятность если  есть произведение вероятностей ее n циклов:

.

Заметим, что по определениям 5 и 7 вероятность характеристики , которая является конкатенацией характеристики  с характеристикой , является произведением их вероятностей:  = . В результате, каждая n-цикловая характеристика может быть описана как конкатенация n одно-цикловых характеристик с вероятностью, которая является произведением вероятностей одноцикловых характеристик.

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

Д о к а з а т е л ь с т в о. Вероятность для любой фиксированной пары открытых текстов, удовлетворяющих условию , быть правильной парой является вероятностью того, что на всех циклах i: . Вероятность в каждом цикле является независимой от своего точного входа (как доказано в лемме 1) и независима от действия предшествующих циклов (с тех пор как независимые ключи полностью перемешивают входы в каждый S блок, сохраняя только фиксированное значение XOR-ов). Следовательно, вероятность пары быть правильной парой является произведением вероятностей , которая была определена выше как вероятность характеристики.

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

Определение 7. Правильной парой, удовлетворяющей n-цикловой характеристике  с независимым ключом K, называется пара, для которой , и для первых n циклов шифрования пары, использующей независимый ключ K, входной XOR i-того цикла равен , а выходной XOR F функции равен . Каждая пара которая не является правильной парой, удовлетворяющей характеристике и независимому ключу называется неправильной парой, удовлетворяющей характеристике и независимому ключу. В дальнейшем для краткости мы будем называть их правильной парой и неправильной парой.

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

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

Рис. 4. Трехцикловая характеристика.

Мы видим, что, когда открытые тексты (левые полублоки) отличаются в пяти определенных битовых позициях, то с вероятностью около 0,05 имеется различие только трех битов на входе четвертого цикла. После битового расширения (для входа 60 00 00 00x  это 9, 17 и 23-ий биты правого полублока на входе четвертого цикла), пять S блоков (S2, S3, S4, S5, S6) имеют ненулевые входные XOR-ы а три (S1, S7, S8) имеют нулевые входные XOR-ы, а, следовательно, и нулевые выходные XOR-ы. В этом случае можно определять 12 битов, для которых  (для пяти циклов) (по  и ).

Рассмотренная выше трехцикловая структура из трех циклов с нулевым входным XOR-ом в среднем цикле является очень полезной и формирует наилучшую возможную вероятность для трехцикловой характеристики1. Аналогичная структура может использоваться в пятицикловых характеристиках. Средний цикл имеет нулевой входной и выходной XOR и есть симметрия относительно этого тождественного цикла (см. Рис.6).

Рис. 6. Пятицикловая характеристика.

Здесь в шестом цикле имеем . Существование строки  гарантирует существование пяти цикловой характеристики. Вероятность такой пяти цикловой характеристики имеет совсем низкий уровень, поскольку три S блоковых входа должны отличаться в двух циклах из трех  и  и шесть в целой пяти цикловой характеристике. Наилучшая вероятность для S блока равна 16/64 = 1/4. Это ограничивает вероятность пяти цикловой характеристики (Рис.6) уровнем ниже или равным = 1/4096. Фактически, наилучшая известная пятицикловая характеристика имеет вероятность около 1/10486.

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

1

1-цикловая

характеристика

2

  Г

2-х цикловая итеративная характеристика

3

Ф Г

Ф Г

4-х цикловая итеративная характеристика

4

Ф Г,

4-х цикловая итеративная характеристика

5

,

,

,

6-ти цикловая итеративная характеристика 6

,

,

6-ти цикловая

итеративная

характеристика

7

8-ми цикловая итеративная характеристика

8

,

.

8-ми цикловая итеративная характеристика

 

9

,

,

,

,

,

,

,

,

,

10-ти цикловая итеративная характеристика

10

,

,

,

,

,

,

10-ти цикловая итеративная характеристика

Рис. 5. Дифференциальные характеристики шифра DES.

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


 

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

38542. ОПЫТНО-ЭКСПЕРИМЕНТАЛЬНАЯ РАБОТА ПО ФОРМИРОВАНИЮ ЭКОЛОГИЧЕСКОЙ КУЛЬТУРЫ МЛАДШИХ ШКОЛЬНИКОВ ПОСРЕДСТВОМ ДИДАКТИЧЕСКИХ ИГР 720 KB
  Формирования экологической культуры посредством дидактической игры . Эффективным методом формирования экологической культуры являются дидактические игры. В процессе использования дидактической игры у детей формируется умение действовать в какойлибо ситуации в соответствии с определенными нормами. Фицула в учебнике по педагогике отмечает что целью формирования экологической культуры в учебновоспитательном процессе используют экологопсихологическую терминологию групповые и ролевые игры мозговой штурм что направлены на...
38543. Управление маркетингом на предприятие на примере торговой компании ТОО «DOM COMPANI» 755.5 KB
  Организационная структура предприятия ТОО DOM COMPNI. Используя в управлении теорию маркетинга предприятия и фирма должны строить свою деятельность в соответствии с ее ключевым принципом: производить то что продается а не продавать то что производится. Методически этот процесс должен предшествовать разработке любых тактических и тем более стратегических линий поведения предприятия поскольку он на многоальтернативной основе позволяет высшему звену управления остановить свой выбор на наиболее перспективных для предприятия рынках....
38544. Управление прибылью и рентабельностью предприятия (на примере ООО «Моравия Авто Плюс») 1 MB
  кафедрой _________________________ __ ____________20___г Дипломный проект Студента 6 курса заочного отделения Сухобока Александра Владимировича зачетная книжка №1008 на тему: Управление прибылью и рентабельностью предприятия на примере ООО Моравия Авто Плюс Специальность: 080507. Аннотация Дипломный проект на тему: Управление прибылью и рентабельностью предприятия на примере ООО Моравия Авто Плюс. При написании работы ставятся следующие задачи: изучить теоретически основы анализа ликвидности и платежеспособности;...
38545. Исследования динамики воображения при использовании эвристических методов обучения у студентов специальности Связи с общественностью ЧГПУ им. И.Я. Яковлева 222 KB
  Донесение и работа с информацией, влияние на определенные слои общества, а также проталкивание, лоббирование некоторых своих, личных интересов, как раз и составляет основу деятельности PR. Именно поэтому на сегодняшний день актуально изучение эвристических методы в работе PR - специалиста.
38546. Технология возделывания картофеля в условиях СПК “Старый Лепель” Лепельского района 545 KB
  Технология возделывания картофеля в условиях СПК â€œСтарый Лепель†Лепельского района24 5. Мучнистая рассыпчатая консистенция отварного картофеля приготовленного в домашних условиях – критерий отбора при покупке. Поэтому нужно ориентироваться на производство типичного картофеля не пытаясь подменять продукцию немецких голландских польских картофелеводов. Сбыт качественного картофеля не вызывает серьезных затруднений.
38547. Решение задач организации правильного монтажа, технического обслуживания и ремонта электротехнических изделий 72.5 KB
  Развитие производства базируется на современных технологиях, широко использующих электрическую энергию. В связи с этим возрастают требования к качеству электрической энергии, ее экономному использованию и рациональному расходованию материальных ресурсов при сооружении систем электроснабжения. Отсюда – повышение роли инженеров-электриков.
38548. Анализ деятельности продюсера в современной отечественной музыкальной индустрии 49 KB
  Стремительное развитие в России в последнее пятнадцатилетие рыночных отношений глобальное реформирование всех сфер жизни общества в том числе сферы культуры и массовых коммуникаций привели к появлению новых видов профессиональной деятельности. Формирование рыночных механизмов на отечественной сцене тесно связано со становлением особого вида предпринимательской деятельности телевизионным продюсированием играющим ключевую роль в развитии российской аудиовизуальной индустрии. Поэтому у института продюсерской деятельности с одной стороны...
38549. Унификация и типизация технологических процессов (ТП) 60.5 KB
  Эффективное применение ГАП и ИПК в единичном и серийном производствах зависит главным образом от устойчивости (стабильности) производственного процесса. Продукция машиностроительных и приборостроительных заводов характеризуется сменой изделий
38550. Разработка и реализация управленческих решений на примере Межрайонной ИФНС России по крупнейшим налогоплательщикам по Республике Башкортостан 333.5 KB
  2 Анализ управленческих решений как составная часть процесса принятия решения Межрайонной ИФНС России по крупнейшим налогоплательщикам по РБ 2.3 Механизм и методы принятия решения Межрайонной ИФНС России по крупнейшим налогоплательщикам по РБ Глава 3 Совершенствование системы принятия решений и оценка ее эффективности 3. В решениях фиксируется вся совокупность отношений возникающих в процессе трудовой деятельности и управления организацией. Лица наделенные правом принимать решения или организовывать их реализацию называются субъектами...