22233

Дифференциальный криптоанализ DES Атака на полный 16-цикловый DES со сложностью 219

Лекция

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

В таблице 1 представлен фрагмент таблицы разностей для второго S блока Таблица 1 Входной Выходной XOR XOR 0x 1x 2x 3x 4x 5x 6x 7x 8x 9x Ax Bx Cx Dx Ex Fx 4x 0 0 0 0 0 6 0 14 0 6 10 4 10 6 4 4 8x 0 0 0 4 0 4 0 8 0 10 16 6 6 0 6 4 Рассмотрим ситуацию когда на входе второго S блока одной 16цикловой характеристики имеется входная разность 4x а на входе второго S блока другой 16цикловой характеристики имеется входная разность 8x. Убедимся прежде всего что и в этом случае используя известные входные пары и выходные XORы для пары S блоков...

Русский

2013-08-04

551.5 KB

13 чел.

ЛЕКЦИЯ 9

Тема 4. Дифференциальный криптоанализ DES

Атака на полный 16-цикловый DES со сложностью 219

В соответствии с изложенными принципами выполнения атак дифферегнциального криптоанализа основной смысл таких атак сводится к нахождению и использованию высоковероятных дифференциальных характеристик.

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

Будем исходить из уже имеющихся таблиц распределения парных разностей S блоков, использованных в дифференциальном криптоанализе Эли Бихана и Ади Шамира.

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

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

Пусть это будут входы (в таблицы парных разностей) 4x 8x. В таблице 1 представлен фрагмент таблицы разностей для второго S блока

Таблица 1

Входной

Выходной XOR

XOR

0x

1x

2x

3x

4x

5x

6x

7x

8x

9x

Ax

Bx

Cx

Dx

Ex

Fx

4x

0

0

0

0

0

6

0

14

0

6

10

4

10

6

4

4

8x

0

0

0

4

0

4

0

8

0

10

16

6

6

0

6

4

Рассмотрим ситуацию, когда на входе второго S блока одной 16-цикловой характеристики имеется входная разность 4x, а на входе второго S блока другой 16-цикловой характеристики имеется входная разность 8x. Будем интересоваться событием, заключающимся в том. что при одновременной подаче на входы вторых S блоков указанных характеристик оговоренных разностей на выходах из первых цикллв образуется одна и та же выходная разность.

В соответствии с приведенной таблицей одинаковые значения выходных разностей могут быть равными 5x, 7x, 9x, Ax, Bx, Cx, Ex и Fx всего 8 вариантов значений. Любое из приведенных значений образуется с вероятностью равной произведению вероятностей, образующих его событий. Поэтому, для результирующей вероятности образования совпадающих выходных разностей на выходе первого (одноблочного) цикла для рассматриваемого случая можем получить результат

.

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

Рис.1. Двухцикловая итеративная характеристика обнуляющего типа

Эта характеристика может быть итеративно продолжена необходимое число раз. Так, при восьмикратном ее повторе приходим к вероятности 16-цикловой характеристики

.

Для 13-цикловой характеристики такого типа соответственно получим результат

.

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

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

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

Предположим теперь, что мы знаем значения , , , , при которых  (), , и мы хотим найти ключевое значение , участвующее в формировании входов S блоков каждой из характеристик, участвующих в образовании , . Входные XOR-ы есть  для первой характеристики и  для второй () независимо от фактического значения ключа . В соответствии c таблицей 1, мы видим, что имеется 480 возможных сочетаний входов S блоков S2, формирующих одну и ту же выходную разность. В Таблице 2 приведены все варианты ненулевых XOR выходов S блока S2 для двух интересующих нас значений входной разности  и , из которых могут формироваться указанные 480 вариантов совпадающих выходов. Нас должны интересовать только те двойные пары входов в S блок S2 которые дают (при совпадающих XOR выходах) при сложении (по модулю 2) с соответствующим известными значениями входов в S блок S2: , , ,  одно и то же значение претендента на ключевое значение . Анализ показывает, что этому требованию удовлетворяет только четверка входов: пара , , образующая выходную разность  = 7x и пара  1x,  5x, образующая эту же выходную разность  = 7x.

Таблица 2.

XOR выхода 

Варианты пар входов ,

для XOR входа

XOR выхода

Варианты пар входов ,

для XOR входа

3x-

(27x, 2Fx), (33x, 3Bx)

5x

(10x, 18x), (37x, 3Fx)

5x

(8x, Cx), (22x, 26x), (2Ax, 2E x)

7x

(12x, 1Ax), (14x, 1Cx), (18x, 1Ex), (23x, 2Bx)

7x

(1x, 5x), (4x, 0x), (9x, Dx), (20x, 24x), (21x, 25x), (28x, 2Cx), (29x, 2Dx)

9x

(0x, 8x), (13x, 1Bx), (7x, Fx), 
(35
x, 3Dx), (36x, 3Ex)

9x

(18x, 1Cx), (23x, 27x), (30x, 34x)

Ax

(2x, Ax), (6x, Ex), (11x, 19x), 
(15
x, 1Dx), (20x, 28x), (22x, 2Ax), (26x, 2Ex), 

Ax

(3x, 7x), (12x, 16x), (13x, 17x), (1Ax,1Ex), (33x, 37x)

Bx

(4x, Cx), (31x, 39x), (32x, 3Ax)

Bx

(10x, 14x), (38x, 3Cx)

Cx

(1x, 9x), (5x, Dx), (30x, 38x)

Cx

(Bx, Fx), (3Ax,3Ex), (3Bx,3Ex), (1Bx,1Fx), (31x, 35x)

Dx

0

Dx

(11x, 15x), (19x, 1Dx), (2Bx, 2Fx)

Ex

(21x, 29x), (25x, 2Dx), (34x, 3Cx)

Ex

(32x, 36x), (39x, 3Dx)

Fx

(17x, 1Fx), (24x, 2Cx), (3x, Bx),

Fx

(2x, 6x), (Ax, Ex)

В этом случае получаем

,

,

,

.

Это обозначает, что в качестве действительного значения ключа  следует взять значение .

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

Что касается построения самой атаки на шифр DES с использованием вторых разностей, то на наш взгляд здесь могут быть применены практически все приемы, использованные Эли Биханом и Ади Шамиром в работе [] при атаке на шифр с использованием первых разностей. Только теперь необходимо работать не с парами открытых и соответствующих им шифрованных текстов, а с их четверками. Тогда атака на 16-цикловый DES будет выглядеть следующим образом.

Как и в известной атаке, сначала решается задача генерации без уменьшения вероятности пар плайнтекстов, чьи XOR выходы после первого цикла являются требуемыми XOR входов  в 13-цикловой характеристике в циклах со 2-го по 14-ый. Пусть P будет произвольный 64-битный плайнтекст, и пусть , . . . ,  и , . . . ,   два набора из 24 32-битных констант, состоящих из всех возможных значений 4-битных позиций, которые XOR-рируются в каждой из характеристик с 4-мя выходными битами блока S2 после первого цикла, и нулями на всех других позициях. Определим теперь структуру, которая состоит из 2 наборов по 25 плайнтекстов и стольких же шифртекстов

 для ,

 для ,

,

,

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

В атаке Эли Бихама и Ади Шамира вероятность получения правильных пар оказалась чрезвычайно малой (), и им пришлось разрабатывать специальную дополнительную процедуру отбраковки неправильных пар.

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

Будем сразу ориентируясь на новый вариант дифференциальной атаки Эли Бихама и Ади Шамира, рассмотренный на предыдущей лекции, который ориентирован на использование незначительное объема памяти. Будем стремиться подсчитать все ключевые биты одновременно, не используя громадный массив из 256 счетчиков.

Для этого нам нужно, прежде всего, суметь сформировать предполагаемого кандидата на полный 56-битный ключ.

(  для ),

( ).


 

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

62864. Изготовление изделий из проволоки 2.19 MB
  Формировать умения работать с инструментами предназначенными для гибки тонколистового металла и проволоки. Оборудование: молоток слесарные тиски оправки плоскогубцы заготовки металла и проволоки.