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.

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


 

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

41157. Пошук інформації в системі 121.5 KB
  Перегляд тексту документа.Друк тексту документа. Підведення підсумків уроку Яку роботу можна проводити з документами Що таке закладка Що таке інформаційна панель Що таке експорт документів Що таке структура документа Відповіді студентів 2 хв. Перегляд тексту документа.
41158. Влияние отдельных факторов на интенсивность теплоотдачи при пленочной конденсации пара 431.5 KB
  Влияние отдельных факторов на интенсивность теплоотдачи при пленочной конденсации пара. Влияние перегрева пара Конденсация перегретого пара будет иметь место если температура поверхности стенки меньше температуры насыщения. При этом в случае конденсации перегретого пара его температура у стенки постоянно снижается и конденсируется по существу насыщенный пар. В случае конденсации одного килограмма перегретого пара к стенке отводится теплота равная 1337...
41159. Логические функции и логические элементы 754.5 KB
  Физическими аналогами логических переменных 0 и 1 служат сигналы способные принимать два хорошо различимых состояния например потенциал низкого и высокого уровней разомкнутое и замкнутое состояние контакта реле и т. Триггеры Триггер это устройство имеющее два устойчивых состояния способное под воздействием управляющего сигнала скачком переходить из одного состояния в другое и хранить это состояние сколь угодно долго. Способность хранить состояние сколь угодно долго и определяет память триггера. состояние триггера не меняется.
41160. Морфологические и синтаксические нормы русского литературного языка 79 KB
  Морфологические ошибки связаны с нарушением грамматических форм слов незнанием склонений с неправильным употреблением окончаний с неправильным ударением если это влияет на форму слова. Морфологостилистические ошибки связаны с использованием сложных конструкций характерных для официально делового и научного стиля в разговорном стиле.Синтаксические ошибки синтаксическим ошибкам относятся следующие: Нарушения в управлении.
41161. Методы преобразования комплексного чертежа (эпюра Монжа) 286 KB
  Сущность этого метода заключается в следующем: положение точек линий плоских фигур поверхностей в пространстве не изменяется а система П1 П2 заменяется дополняется плоскостями образующими с П1 или П2 или между собой системы двух взаимно перпендикулярных плоскостей принимаемых за плоскости проекций. Если введение одной плоскости П4 или П5 не позволяет решить задачу то прибегают к последовательному дополнению основной системы плоскостей проекций новыми П6 П7 и т. показано преобразование проекций точки А из системы П2 П1 в систему П4...
41162. История лазерных принтеров 1.9 MB
  На поверхности фоторецептора создается электростатическое а затем видимое изображение копируемого оригинала с последующим переносом этого изображения на бумагу или специальный материал. Формирование изображения На этапе формирования изображения на поверхности фоторецептора создается оптическое изображение оригинала. Полученное оптическое изображение должно: а обладать требуемыми геометрическими параметрами б иметь распределение освещенностей соответствующее оптическим плотностям оригинала. Проявление На этапе проявления на участки...
41163. Метод узловых напряжений 192.5 KB
  Метод узловых напряжений. Метод узловых напряжений заключается в определении на основании первого закона Кирхгофа потенциалов в узлах электрической цепи относительного некоторого базисного узла. Положительное напряжение узловых напряжений указывается стрелкой от рассматриваемого узла к базисному. Иллюстрация к методу узловых напряжений.
41164. Власть, влияние, лидерство 198 KB
  Они делают это посредством допущения подчиненных к выработке управленческих решений развитию лидерства в рабочих командах инициативы обучения и т. Лидерство Вопросы лидерства вызывали интерес людей с древних времен. Природа лидерства может быть лучше понята если сравнить лидерство с управлением. Теория лидерских качеств Это один из наиболее ранних подходов к изучению и объяснению лидерства.
41165. Человек в организации. Функция мотивации 242.5 KB
  Системно поведение человека в организации может быть представлено с двух позиций: 1 с позиции взаимодействия человека с организационным окружением в этом случае человек находится в центре модели и 2 с позиции организации включающей в себя индивидов в этом случае организация как целое является исходной точкой рассмотрения. Второе что он сделал для организационного окружения для организации в ответ на стимулирующие воздействия которые организация применила по отношению к человеку. Нас будут интересовать ответы на вопросы: как...