22235

Дифференциальный криптанализ

Лекция

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

Для DESподобных криптосистем различие выбирается как побитовая сумма по модулю два XOR значений двух текстов в модульной арифметике  разность пары текстов. Эта операция в дальнейшем для краткости будет обозначаться аббревиатурой из английских букв  XOR2. Данное фиксированное значение XOR входной пары правых полу блоков для F функции легко определяет свое XOR значение после расширения по формуле: EXEX = EXX. XOR с ключом не изменяет значение XOR в паре т.

Русский

2013-08-04

528 KB

0 чел.

Лекция 2

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

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

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

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

Определение 1. Независимый ключ является списком из n под ключей,, которые не обязательно сформированы алгоритмом разворачивания ключа..

Пример 1. В DES теоретически можно использовать 21648 = 2768 независимых ключей, из которых применяется только 256 (имеется в виду, что каждый ключ может быть рассмотрен как специальный тип независимого ключа).

В дальнейшем для упрощения вероятностного анализа атаки все подключи будут считаться независимыми. Атаки на DES с зависимыми под ключами также вполне реализуемы, но их теоретический анализ является значительно более трудным.

Рассмотрим, как ведет себя DES F функция при независимых ключах. Входами в F функцию (см. Рис. 2, Л-1) являются 32 бита правого полу блока каждого цикла и 48 битов под ключа. Входной 32-битный блок символов расширяется (E расширением) до 48 битов и суммируется по модулю 2 с ключом. Эта операция в дальнейшем для краткости будет обозначаться аббревиатурой из английских букв XOR2. Результат сложения поступает на S блоки, на выходах которых биты переставляются с помощью P перестановки.

Данное (фиксированное) значение XOR входной пары правых полу блоков для F функции легко определяет свое XOR значение после расширения по формуле:

E(X)E(X*) = E(XX*).

XOR с ключом не изменяет значение XOR в паре, т.е. значение XOR с учетом расширения остается неизменным и после сложения с ключом, что следует из формулы:

(XK)(X*K) = XX*.

Выходные биты S блоков перемешиваются P перестановкой и, таким образом, XOR пары 32-битных полу блоков после того, как P перестановка переставит значения S блоковых выходов, определяется по формуле:

P(X)P(X*) = P(XX*).

Выходной XOR F функции является линейным для XOR операции, формирующей циклы:

(XY)(X*Y*) = (XX*)(YY*).

XOR пары, таким образом, инвариантен к ключу и линейный для расширения E, перестановки P и XOR операции.

S блоки, как известно, являются нелинейными преобразованиями. Знание XOR входных пар не может гарантировать знание XOR выходных пар. Обычно для одного и того же входного XOR-а возможны различные выходные XOR-ы. Исключение составляет ситуация, когда оба входа равны. В этом случае оба выхода также получаются равными друг другу. Анализ результатов наблюдений также показывает, что для любого конкретного входного XOR-а возможны не все XOR выходы. Кроме того, возможные выходы появляются не равновероятно, т.е. некоторые XOR значения появляются более чаще, чем другие.

В DES любой S блок имеет 6464 возможных входных пары, и каждая из них имеет свой входной XOR и свой выходной XOR (см. Табл.1).

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

0

1

2

3

140

4

15

4

15

1

12

13

7

14

8

1

4

8

2

2

14

13

4

15

2

6

9

11

13

2

1

8

1

11

7

3

10

15

5

10

6

12

11

6

12

9

3

12

11

7

14

5

9

3

10

9

5

10

0

0

3

5

6

7

8

0

13

Таблица 1. Таблица S блока S1 с обозначениями входов.

Напомним здесь взаимосвязь между входными и выходными данными таблиц S блоков стандарта. Ее можно описать следующим образом. Пусть   6-ти битовый вектор, поступающий на вход некоторого S блока Sj. Образуем два десятичных числа  и , двоичная запись первого из которых есть , а второго  (например, применительно к вектору 000110 имеем , ). Тогда результатом работы S блока Sj, соответствующим входу  будет 4-х битовая запись десятичного числа, стоящего в j-той таблице (матрице) на пересечении -той строки и -того столбца (например, при поступлении упомянутого вектора 000110 на вход S блока S1 результатом будет 1 = 0001).

Есть только 6416 возможных кортежей (сочетаний) XOR выходов. Следовательно, каждый кортеж состоит в среднем из четырех пар. Однако, не все кортежи существуют как результат объединения пар, а существующие не имеют равномерного распределения. Для анализа свойств S блоков, характеризующих вероятности переходов различных входных разностей в выходные, разработчики дифференциального криптоанализа ввели в рассмотрение так называемые таблицы частных парных XOR распределений (Partial pairs XOR distribution tables) S блоков (мы их для краткости в дальнейшем будем называть таблицами распределения разностей).

При построении таблиц распределения разностей для каждого S блока просматриваются все возможные суммы по модулю 2 (XOR) различных пар входов (результат 6 битов) и соответствующих XOR пар выходов (результат 4 бита). Полученные числа являются индексами входов (по строкам и по столбцам) в ячейки таблиц распределения разностей S блоков. Размер каждой таблицы 6416. Сама таблица разностей получается заполнением ячеек числами, соответствующими количествам пар выходов рассматриваемого S блока, образующих заданные значения выходных разностей (индексов входов в ячейку таблицы по столбцам) для каждого значения входной разности (индекса входа в ячейки по строкам) при вариации по всему множеству пар входов S блока, формирующих заданную входную разность, т.е. каждая строка таблицы соответствует конкретному значению входного XOR-а, а каждый столбец соответствует конкретному значению выходного XOR-а, а значения соответствующих ячеек таблицы соответствуют количеству возможных пар с такими входным и выходным XOR-ами.

Авторы цитируемой работы вводят определение для таблиц распределения разностей S блоков в виде:

Определение 2. Таблица, которая показывает распределение XOR входов и XOR выходов всех возможных пар S блока, называется таблицей распределения разностей S блока (Partial pairs XOR distribution tables).

Пример 2. Таблица 2 является фрагментом таблицы разностей S блока S1. Сам S блок S1 описан в Таблице 1.

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

Входной

Выходной XOR

XOR

0x

1x

2x

3x

4x

5x

6x

7x

8x

9x

Ax

Bx

Cx

Dx

Ex

Fx

0x

64

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1x

0

0

0

6

0

2

4

4

0

10

12

4

10

6

2

4

2x

0

0

0

8

0

4

4

4

0

6

8

6

12

6

4

2

3x

14

4

2

2

10

10

4

2

6

4

4

0

2

2

2

0

4x

0

0

0

6

0

10

10

6

0

4

6

4

2

8

6

2

5x

4

8

6

2

2

4

4

2

0

4

4

0

12

2

4

6

6x

0

4

2

4

8

2

6

2

8

4

4

2

4

2

0

12

7x

1

4

10

4

0

4

8

4

2

4

8

2

2

2

4

4

8x

0

0

0

12

0

8

8

4

0

6

2

8

8

2

2

4

9x

10

2

4

0

2

4

6

0

2

2

8

0

10

0

2

12

Ax

0

8

6

2

2

8

6

0

6

4

6

0

4

0

2

10

Bx

2

4

0

10

2

2

4

0

2

6

2

6

6

4

2

12

Cx

0

0

0

8

0

6

6

0

0

6

6

4

6

6

14

2

Dx

6

6

4

8

4

8

2

6

0

6

4

6

0

2

0

2

Ex

0

4

8

8

6

6

4

0

6

6

4

0

0

4

0

8

Fx

2

0

2

4

4

6

4

2

4

8

2

2

2

6

8

8

30x

0

4

6

0

12

6

2

2

8

2

4

4

6

2

2

4

31x

4

8

2

10

2

2

2

2

6

0

0

2

2

4

10

8

32x

4

2

6

4

4

2

2

4

6

6

4

8

2

2

8

0

33x

4

4

6

2

10

8

4

2

4

0

2

2

4

6

2

4

34x

0

8

16

6

2

0

0

12

6

0

0

0

0

8

0

6

35x

2

2

4

0

8

0

0

0

14

4

6

8

0

2

14

0

36x

2

6

2

2

8

0

2

2

4

2

6

8

6

4

10

0

37x

2

2

12

4

2

4

4

10

4

4

2

6

0

2

2

4

38x

0

6

2

2

2

0

2

2

4

6

4

4

4

6

10

10

39x

6

2

2

4

12

6

4

8

4

0

2

4

2

4

4

0

3Ax

6

4

6

4

6

8

0

6

2

2

6

2

2

6

4

0

3Bx

2

6

4

0

0

2

4

6

4

6

8

6

4

4

6

2

3Cx

0

10

4

0

12

0

4

2

6

0

4

12

4

4

2

0

3Dx

0

8

6

2

2

6

0

8

4

4

0

4

0

12

4

4

3Ex

4

8

2

2

2

4

4

14

4

2

0

2

0

8

4

4

3Fx

4

8

4

2

4

0

2

4

4

2

4

8

8

6

2

2

Таблица 2. Таблица частных парных XOR распределений для S блока S1.

Очередное определение имеет дело с XOR-ами пар входов и выходов S блоков.

Определение 3. Пусть  будет шести битовая величина и  будет четырех битовая величина. Мы будем говорить, что  может вызвать  на S блоке, если есть пара в которой входной XOR S блока равен , а выходной XOR S блока равен . Если есть такая пара, мы ее будем записывать   , а если нет такой пары, мы будем говорить, что  не может вызвать  на S блоке и  записывать   .

Будем в дальнейшем обозначать реальные значения входов и выходов S блоков в шестнадцатеричном представлении. Так, запись  будет означать, что входная разность первого S блока приняла значение .

Пример 4. Рассмотрим входной XOR первого для S блока . Он имеет только восемь возможных выходных XOR-ов, в то время как другие восемь входов невозможны. Возможные выходные XOR-ы  есть 1x, 2x, 3x, 4x, 7x, 8x, Dx и Fx. Следовательно, входной XOR  может вызвать выходные XOR-ы  (34x 1x ), а также 34x  2x, 34x  3x, 34x  4x,
34
x  7x, 34x  8x, 34x  Dx и 34x   Fx. С другой стороны, 34x  0x,
34
x   9x и т.п.

Заметим далее, что пользуясь записями значений входов и выходов S блоков в шестнадцатеричной системе счисления и введенными обозначениями, для элементов таблиц парных разностей S блоков можно записать представление

,

где # обозначает кардинальность3 конечного множества, , ,  соответственно обозначение входа и выхода S блока в шестнадцатеричной системе счисления.

Примеры 3 и 4 демонстрируют, что для фиксированного входного XOR-а возможные выходные XOR-ы не имеют однородного (равномерного) распределения. Очередное определение распространяет предыдущее на вероятности переходов входных разностей в выходные разности S блоков.

Определение 4. Будем говорить, что  может вызвать  с вероятностью p на S блоке, если p есть доля всех пар, для которых входной XOR S блока равен , а выходной XOR равен , т.е. если .

Пример 5. Переход 34x   2x возникает в 16 случаях из 64 возможных пар входов S1 (), т.е., имеет вероятность 1/4 (34x может вызвать 2x с вероятностью 1/4). В то же время переход 34x  4x выполняется только для двух из 64 пар S1 (), т.е. имеет вероятность 1/32.

Другие входы Таблицы 2 имеют иные вероятности. В итоге для всей таблицы (всех входных XOR) возможно от 70% до 80% ненулевых выходов и от 20% до 30% переходов являются невозможными (они имеют вероятность равную нулю). Точный процент возможных (ненулевых) переходов для каждого S блока приведен в Таблице 3. В последующих расчетах процент возможных ненулевых переходов для всех S блоков будет аппроксимироваться значением 80%.

S блок

Проценты

S1

S2

S3

S4

S5

S6

S7

S8

79.4

78.6

79.6

68.5

76.5

80.4

77.2

77.1

Таблица 3. Процент возможных ненулевых переходов (входов, имеющих ненулевые выходы) в таблицах распределения разностей S блоков.

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

Пример 6. Рассмотрим переход 34x  4x для таблицы XOR распределения пар S блока S1. Так как переход 34x 4x имеет значение 2, то только две пары удовлетворяют этому XOR-у. Эти пары двойные. Если первая пара есть , то другая пара есть . Из Таблицы 1 мы видим что этими входами должны быть 13x и 27x, чьи выходы есть 6x и 2x соответственно.

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

Пример 7. Рассмотрим S1 и допустим, что входная пара есть ,  и что значение соответствующих шести ключевых бит есть  = 23x. Тогда фактические входы S1 (после XOR-рирования входных и ключевых битов) есть  = 22x,  = 16x и выходы есть  = 1x,  = Cx соответственно. Входной XOR есть , выходным XOR-ом является  = Dx. Возможные пары входов для других значений XOR выходов приведены в
Таблице 4.

Предположим мы знаем, что , ,  = Dx, и хотим найти ключевое значение , участвующее в формировании входов 1-го S блока. Входной XOR есть  независимо от фактического значения ключа . В соответствии c таблицей 2, предыдущей лекции, мы можем увидеть, что имеется восемь возможных сочетаний входов S блока, формирующих входную разность . Эти восемь пар определяют восемь возможных значений ключа  (=, здесь для краткости записи  обозначает


Выходной

XOR ()

Возможные пары входов

()

1

2

3

4

7

8

D

F

03 и 37, 0F и 3B, 1E и 2A, 1F, и 2B,

04 и 30, 05 и 31, 0E и 3A, 11 и 25, 12 и 26, 14 и 20, 1A и 2E, 1B и 2F

01 и 35, 02 и 36, 15 и 21

13 и 27

00 и 34, 08 и 3C, 0D и 39, 17 и 23,18 и 2C, 1D и 29

09 и 3D, 0C и 38, 19 и 2D

06 и 32 (03 и 29), 10 и 24 (08 и 22), 16 и 22 (0B и 21), 1C и 28 (0E и 24)

07 и 33, 0A и 3E, 0B и 3F

Таблица 4. Возможные входные значения пар входного XOR  для различных выходных XOR (в шестнадцатеричном исчислении). В скобках приведены значения входов в системе пользования таблицами S блоков.

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

S боксовые входы

Возможные ключи

06, 32  (03, 29)

10, 24  (08, 22)

16, 22  (0B, 21)

1C, 28  (0E, 24)

07,   33

11,   25

17,   23

1D,   29

Таблица 5. Возможные ключи для перехода 34x  Dx (1Ax  Dx, Dx = 1101) для S1 с входами 1x, 35x (в шестнадцатеричном обозначении)

Используя дополнительные пары мы можем получить дополнительных кандидатов для . Пусть, например, рассматривается входная пара ,  (с тем же  = 23x). Входы S блока есть , , а выходы есть , . Выходной XOR есть  = 3x. Возможные входы S блока для перехода 34x  3x и соответствующие возможные ключи представлены для этого случая в таблице 6.

S боксовые входы

Возможные ключи

01,   35

02,   36

15,   21

03,   37

00,   34

17,   23

Таблица 6. Возможные ключи для перехода 34x  3x S блока S1 с входами 21x, 15x (в шестнадцатеричном исчислении).

Правильный ключ должен встретиться в обоих таблицах. Общими ключевыми значениями в таблицах 1 и 2 являются только 17x и 23x. Эти два значения неразличимы для рассмотренных вариантов входных XOR-ов, так как
17
x 23x = 34x = . В то же время оставшихся два значения могут стать различимыми при использования пары с другим входным XOR значением ().

Следующий пример является расширением примера 7 на трех цикловую криптосистему рис. 1.

Пример 8. Предположим теперь, что мы имеем шифртекстовую пару, чей плайнтекстовый XOR известен и значения шести битов 33, ..., 38 (1, 2, 3, 4, 5 и 6-й биты правого полу блока) плайнтекстового XOR-а есть нули, следовательно, входной XOR первого цикла является нулем во всех битах, вводящих в S1 ( = 0) и, таким образом, выходной XOR S1 в первом цикле должен быть нулем ( = 0). Левая половина зашифрованного текста вычисляется как XOR значения левой половины открытого текста L, значения выхода первого цикла A и значения выхода третьего цикла C (l = LAC). Так как плайнтекстовый XOR и шифртекстовый XOR известны и выходной XOR S1 в первом цикле также известен, то выходной XOR S1 в третьем цикле может быть вычислен. Входная пара ,  в третьем цикле легко исключается из шифртекстовой пары.

Если входная пара S1 в третьем цикле есть  = 1x,  = 35x и выходной XOR есть  = Dx, то величина  может быть обнаружена как в примере 1 и она должна появиться в таблице 1. Используя дополнительные пары мы можем отвергнуть некоторые из возможных значений до того как мы получим уникальное значение . Так как  не константа, то оно не может быть любым неразличимым значением под ключа.

1 Материал этой и последующих лекций составлен по оригинальной работе авторов Eli Bicyam, Adi Shamir Differential Cryptanalysis of DES-like Cryptosystem., Journal of Cryptology,
Vol. 4, pp.3-72, (1991).

2 XOR   исключающее ИЛИ, сложение по модулю 2.

3 Кардинальность  мощность множества. В данном случае  это число элементов  таких, для которых выполняется условие  


 

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

15727. АТП на 150 автомобилей ВАЗ-2104 и 200 грузовых автомобилей ГАЗель 364.5 KB
  Расчетнопояснительная записка к курсовому проекту на тему: АТП на 150 автомобилей ВАЗ2104 и 200 грузовых автомобилей ГАЗель Введение Курсовое проектирование по кафедре Автомобильный транспорт имеет своей целью закрепление знаний по дисциплине Производственноте...
15728. Дизельные генераторы KDE12EA3 157.97 KB
  Дизельные генераторы KDE12EA3 Дизельные генераторы KIPOR KDE12EA3 имеют новый автоматический регулятор напряжения обеспечивающий высокую точность значения выходного напряжения и мощный дизельный двигатель KD2V86F. Генератор обладает номинальным напряжением 380 / 220В номинальной с
15729. ТЕХНИЧЕСКОЕ ОБСЛУЖИВАНИЕ СИСТЕМ ПИТАНИЯ АВТОМОБИЛЬНЫХ ДВИГАТЕЛЕЙ 116.9 KB
  Реферат на тему ТЕХНИЧЕСКОЕ ОБСЛУЖИВАНИЕ СИСТЕМ ПИТАНИЯ АВТОМОБИЛЬНЫХ ДВИГАТЕЛЕЙ Техническое обслуживание системы питания карбюраторного двигателя Неисправности системы питания заключаются в...
15730. Маркировка автомобильных шин 140.17 KB
  Маркировка автомобильных шин Автомобильные шины маркируются алфавитноцифровым кодом который обозначается на борту шины. Этот код определяет размеры шины и некоторые из ее ключевых характеристик типа индикаторов нагрузки и скорости. Иногда внутренний борт шины со
15731. Проект организации ТО и ремонта МТП в ЦРМ хозяйства с годовым объемом работ 33000 часов 151.16 KB
  КУРСОВАЯ РАБОТА Тема: Проект организации ТО и ремонта МТП в ЦРМ хозяйства с годовым объемом работ 33000 часов РЕФЕРАТ Пояснительная записка курсового проекта содержит 39 листов машиннопечатного текста формата А4 13 таблиц и два приложения список использованно
15732. МОДЕЛИРОВАНИЕ СОСТАВА МАШИННО-ТРАКТОРНОГО ПАРКА 369.5 KB
  Реферат по моделированию: МОДЕЛИРОВАНИЕ СОСТАВА МАШИННОТРАКТОРНОГО ПАРКА ВВЕДЕНИЕ За последние годы произошло значительное сокращение количества сельскохозяйственной техники в стране. Тяжелое финансовое положение предприятий нарушенный паритет цен на маши...
15733. ОСНОВНЫЕ ДАННЫЕ ДВИГАТЕЛЯ М-14П 422 KB
  КОНСТРУКЦИЯ ДВИГАТЕЛЯ М14П ОСНОВНЫЕ ДАННЫЕ ДВИГАТЕЛЯ М14П ОБЩИЕ СВЕДЕНИЯ Авиационный двигатель М14П поршневой четырехтактный бензиновый с воздушным охлаждением девятицилиндровый однорядный со звездообразным расположением цилиндров и с карб...
15734. Технология восстановления типовых деталей 92 KB
  Реферат по дисциплине Надежность и ремонт машин на тему: Технология восстановления типовых деталей Содержание 1 Номенклатура классов и групп деталей машин. 2 Характерные дефекты и способы их устранения у типовых деталей 2.1 Корпусные детали 2.2 ...
15735. Способы устранения дефектов деталей автомобиля 89.5 KB
  Способы устранения дефектов деталей автомобиля Виды и характеристика дефектов Наиболее распространенными дефектами деталей автомобилей и агрегатов поступающих на КР являются: изменение размеров рабочих поверхностей; механические повреждения; нарушение...