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.

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


 

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

38113. Психологічні особливості адаптації 126 KB
  “Загальні психологопедагогічні особливості процесу адаптаціїâ€. Заняття № 1: “Психологічні особливості адаптації â€. Розглянути питання щодо адаптації у військовому колективі. 1 2 ВСТУПНА ЧАСТИНА ОСНОВНА ЧАСТИНА Сутність адаптації.
38114. Составление программ разветвляющейся структуры 91.5 KB
  Решить задание в соответствии с вариантом задания. Исходные данные должны вводиться в режиме диалога и сопровождаться комментариями. Результат вывести на экран, сопровождая вывод комментариями. Изучить правила записи операторов ветвления. Разработать алгоритм решения задачи. Составить программу решения задачи.
38116. ЭКОНОМИКО-СТАТИСТИЧЕСКИЙ АНАЛИЗ ОСНОВНЫХ ПОКАЗАЗАТЕЛЕЙ ДЕЯТЕЛЬНОСТИ ВОДОХОЗЯЙСТВЕННОЙ СТРОИТЕЛЬНОЙ ОРГАНИЗАЦИИ 569 KB
  Целью экономической статистики является получение информации для принятия решений органами государственного управления в вопросах регулирования экономики и разработки экономической политики.
38117. ФИРМА В РАЗЛИЧНЫХ МОДЕЛЯХ РЫНКА 231.5 KB
  Издержки производства, их структура. Экономическая и бухгалтерская прибыль. Закон убывающей предельной производительности (отдачи). Совершенноконкурентный производитель: определение цены и объема производства. Фирма в условиях несовершенной конкуренции: определение цены и объема производства.
38118. Соціально-психологічні риси військового колективу 80 KB
  Військовий підрозділ як мала соціальна група Заняття №4: Соціальнопсихологічні риси військового колективу Час: 2 год. Мета заняття: З’ясувати загальна характеристика військового навчання. Усвідомити закономірності та принципи військового навчання.
38119. Основні методи вивчення психології військового колективу 210.5 KB
  Письмове або усне опитування курсантів: 1 варіант: соціометрія як метод дослідження; особливості методу спостереження; 2 варіант: експеримент як метод дослідження; особливості психологічної бесіди анкетного методу та опитування. Обговорення третього питання: Спостереження та експеримент. Практичне проведення спостереження. Вирішують проблемне питання Відповідають на запитання Приймають участь у дискусії Проводять спостереження 6.
38120. Характеристика військового колективу 138.5 KB
  Характеристика військового колективу Час: 2 години Мета заняття: 1. РОЗПОДІЛ ЧАСУ №зп СТРУКТУРА ЗАНЯТТЯ Час хв. Перевірка готовності курсантів до заняття. Підведення підсумків і закінчення практичного заняття оголошення завдання на самостійну підготовку.
38121. Морально-психологічний вплив на війська в ході наступальних і оборонних дій 135.5 KB
  Мета заняття: ознайомити курсантів із психологічною стійкістю колективу в бою; – надати курсантам знання щодо стану страху та шляхів його подолання. Обговорення другого питання: Стан страху шляхи його подолання 40 хв. Мета заняття: ознайомити курсантів із психологічною стійкістю колективу в бою; – надати курсантам знання щодо стану страху та шляхів його подолання. Основна частина 80 Психологічна стійкість колективу в бою 40 Стан страху шляхи його подолання 40 3.