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

14 чел.

ЛЕКЦИЯ 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-битный ключ.

(  для ),

( ).


 

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

35129. БЕЛАРУСКАЯ МОВА. ПРАФЕСІЙНАЯ ЛЕКСІКА 1.48 MB
  Лічылася што мова закладзена ў самой біялагічнай сутнасці чалавека і перадаецца ў спадчыну. На самой справе мова – зява біялагічная і псіхічная але ў тым сэнсе што ў чалавеку генетычна закладзена здольнасць авалодаць мовай г. Кожны чалавек валодае не мовай увогуле а канкрэтнай мовай ці мовамі што належыць пэўнаму народу. Сацыяльная прырода мовы заключаецца найперш у тым што яна аснова і форма грамадскай свядомасці і разам з тым унікальны і універсальны сродак зносін людзей феномен духоўнай культуры чалавецтва [7].
35130. Расчёт пространственного одноэтажного промышленного здания, оборудованного мостовым краном 414.33 KB
  Список литературы Исходные данные Количество пролетов – 3; Длина пролета – l1 = 18 м; Длина здания – l = 168 м; Несущая конструкция покрытия – балка; Шаг колонн – 6 м; Высота до верха рельса – 84 м; Грузоподъемность крана – 15 т; Расчетное сопротивление грунта – Rгр =019 МПа; Место строительства – г. Расчет крайней колонны Данные для расчета сечений: бетон тяжелый класса B15 подвергнутый тепловой обработке при атмосферном давлении Rb = 85 МПа; Rbt = 075 МПа; Eb = 20500 МПа. Арматура класса АIII d 10 мм RS = RSC =...
35131. Форматирование результатов запроса 82 KB
  Например можно применить следующую команду чтобы увидеть определенные поля таблицы Slespeople упорядоченные по убыванию поля commission comm: SELECT snme comm FROM Slespeople ORDER BY 2 DESC; Мы рассматриваем это свойство ORDER BY для того чтобы продемонстрировать возможность его использования со столбцами выходных данных; эта процедура аналогична применению ORDER BY со столбцами таблицы. Например чтобы подсчитать заявки orders для каждого продавца slespeople и вывести результаты в убывающем порядке: SELECT snum COUNT DISTINCT...
35132. Создание таблиц 90 KB
  Команда CRETE TBLE Таблицы определяются с помощью команды CRETE TBLE создающей пустую таблицу таблицу не имеющую строк. Команда CRETE TBLE определяет имя таблицы и множество поименованных столбцов в указанном порядке. Синтаксис команды CRETE TBLE: CRETE TBLE имя таблицы имя столбца тип данных [ размер ] имя столбца тип данных [ размер ]. Поскольку пробелы используются для разделения отдельных частей команд в SQL их нельзя использовать как часть имени таблицы.
35133. Основные понятия SQL 152.5 KB
  Он используется для связи с такими системами управления базами данных как Orcle INGRES Informix Sybse SQLbse Microsoft SQL Server DB2 СУБД самой IBM продуктами SQL DC Prdox ccess pproch и многими другими. Обычно продукт базы данных включает не только СУБД. Собственно СУБД иногда ее называют исполнительной системой или исполнительным механизмом базы данных является рабочей лошадкой продукта. Она хранит данные осуществляет поиск и выборку данных а также записывает данные посредством исполнения операторов SQL В вычислительной...
35134. Альтернативная программная реализация выборки и модификации данных в базе данных Interbase 34.5 KB
  Конфигурируется ODBCисточник реализующий доступ к БД Interbse. В DBE dministrtor настраивается псевдоним БД доступной через BDE и представляющей собой в данном случае ODBCисточник. В отличие от 3го способа являющегося усовершенствованным подходом BDE 1й способ является более универсальным и более ресурсоемким в первую очередь по критерию времени поскольку представляет собой использование промежуточного уровня BDE и промежуточного уровня ODBC а 2й – менее универсальным и менее ресурсоемким поскольку предполагает использование...
35135. Пример реализации трехзвенной архитектуры 39.5 KB
  Два разрабатываемых при этом программных компонента – это сервер приложений и клиент взаимодействующие по протоколу DCOM. Разработка сервера приложений Основные шаги создания сервера приложений: Создание удаленного модуля данных Remote Dt Module. Однократный запуск программы с целью регистрации сервера приложений в реестре Windows. Для распределенного использования разработанных клиентского и серверного приложений требуется установка некоторых дополнительных программных компонент.
35136. Пример реализации обмена данными с Microsoft Excel 45.5 KB
  Создание новой книги Vrint MSBooks; MSBooks = MSExcel. Создание нового листа книги. Сохранение книги. Создание нового листа книги.
35137. Изучение формата баз данных Visual FoxPro 549.5 KB
  После заголовка таблицы следует цепочка 32байтовых описаний полей таблица 4.fmp Fp 01 1 YY Год последнего обновления таблицы Все 02 1 MM Месяц последнего обновления таблицы Все 03 1 DD День последнего обновления таблицы Все 04 4 RecordsCount Количество записей в таблице Все 08 2 HederSize Размер заголовка в байтах Все 10 2 RecordSize Размер записи в байтах Все 12 2 0x000x00 Зарезервировано Все 14 1 0x01 Начало транзакции D4 D5 0x00 Конец транзакции D4 D5 0x00 Игнорируется FS D3 Fb Fp CL 15 1 0x01 Закодировано D4 D5 0x00 Нормальная...