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.

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


 

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

82263. Язык социально-гуманитарных наук. Языковая картина мира и «языковые игры» 34.44 KB
  проблемы природы языка принципов и законов его функционирования начинают изучаться лингвистами логиками психологами и философами. Таким образом для языкознания важными вопросами становятся вопросы семантики а также проблемы взаимосвязи языка и мышления языка и предметного мира. Так швейцарский лингвист Фердинанд де Соссюр 1857–1913 указывает на то что предметом изучения лингвистики становится имманентная реальность языка. Также проблемы языка в первую очередь выдвигаются в логике.
82264. Интерпритация как придание смысла, значения высказываниям, текстам, явлениям, событиям 40.1 KB
  Это внешняя сторона интерпретации. Выделяя к качестве предмета изучения исторического познания текст мы не должны сводить процедуру интерпретации к набору грамматических языковых игр Л. Объективный план интерпретации как операции мышления представлен с одной стороны предметом исследования а с другой операциональным или формально логическим каркасом своего рода алгоритмом системой стандартных шагов правит принципов и приемов субъекта познания в ходе познавательной деятельности. Общепризнанным каноном процесса интерпретации в...
82265. Вера и знание, достоверность и сомнение. Диалектика веры и сомнения в процессе познания 32.72 KB
  В социальногуманитарных науках знание всегда сочетается с верой и сомнением так как вера ориентирована на преувеличение роли абсолютного момента в знании а сомнение – роли относительного – в нем. Вера присутствует в социальногуманитарных науках прежде всего в силу незавершенности познания социальных явлений как допущение возможности соответствия социальной реальности и его отражения в знании. Она также может присутствовать в социальногуманитарных науках: как вера ученогогуманитария в Бога ученый привносит в науку свою веру как его...
82266. Конструктивная роль веры как условия «бытия среди людей» (Л.Витгенштейн) Вера и верования 31.72 KB
  Витгенштейн Вера и верования. Вера возникает как необходимое следствие бытия среди людей утверждает Витгенштейн имеет социальнокоммуникативную природу. Вера – субъективная уверенность. Вера и знание имеют различные основания противоположно направленные.
82267. Вера и понимание в контексте коммуникаций. Вера и истина. Типы обоснования веры и знания. Соотношение веры и истины 36.66 KB
  Типы обоснования веры и знания. Одной из основных предпосылок философскометодологического анализа социальногуманитарного знания является рассмотрение научного познания в контексте культуры его связь с историческими особенностями и ценностными установками общества. Тема веры достоверности сомнения оказывается одной из фундаментальных в самых разных областях и на разных этапах научного познания. Соотношение различных духовноценностных установок веры и научного знания поразному влияло на развитие науки.
82268. Натуралистическая исследовательская программа 38.77 KB
  Сегодня вопрос об исследовательской программе или близком к ней понятии парадигмы в социальных науках сталкивается с двумя трудностями: 1 избрания масштаба исследования; 2 многообразия исследовательских программ господствующего сегодня в социальногуманитарных науках. Какие исследовательские программы парадигмы можно выделять 1 Классическая философия были ориентирована на природу и изучающие ее науки на следующую отсюда натуралистическую парадигму. Последователи натуралистической исследовательской программы полагают: либо предмет наук...
82269. Антинатуралистическая исследовательская программа и ее общенаучное значение 36.58 KB
  Природа остается в качестве предпосылки деятельности человека но культур центризмом не схватывается оставляя место натурализму Другой причиной жизненности натуралистической исследовательской программы является вызванное объективными социальными изменениями крушение классических рационалистических установок. Она по существу указала на границы натуралистической программы. Натуралистическая и антинатуралистическая программы направлены на изучение одного и того же объекта но в соответствии со своей методологией исследовательской программой...
82270. Применение натуралистической и антинатуралистической исследовательских программ ва социально –гуманитарных науках 33.52 KB
  В них присутствуют: натуралистическая парадигма общества основные варианты: механицизм физикализм биологизм географический детерминизм демографический детерминизм – общество понимается как жестко-детерминированная система обусловленная влиянием определенных природных факторов климата полезных ископаемых территории и т. оно рассматривается с редукционистских позиций; антинатуралистическая парадигма общества основные варианты: социологизм экономизм психологизм антипсихологизм – общество понимается как...
82271. Проблема разделения социальных и гуманитарных наук пол предмету, по методу, по предмету и методу одновременно, по исследовательским программам 34.01 KB
  В настоящее время считается что естественные науки и социально-гуманитарные науки имеют как общие так и различные характеристики. Естественные и социально-гуманитарные науки обладают всеми признаками науки как особого феномена познание нового наличие эмпирического и теоретического уровней оформленность в понятиях и т. Вместе с тем социально-гуманитарные науки отличаются от естественно-математических и технических наук по следующим основаниям: по объекту исследования – естественные науки изучают природную реальность т. то что существует...