22237

Введение в дифференциальный криптанализ. Итеративные характеристики

Лекция

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

Статистическое поведение большинства характеристик не позволяет нам искать пересечение всех ключей предложенных поддерживаемых различными парами как это мы делали в примере 6 Л2 так как пересечение обычно пустое: неправильные пары не обязательно указывают на правильный ключ как возможное значение. Однако мы знаем что правильное ключевое значение должно быть результатом всех правильных пар которые встречаются приблизительно с характеристической вероятностью с вероятностью характеристики. Все другие возможные ключевые значения...

Русский

2013-08-04

401.5 KB

0 чел.

ЛЕКЦИЯ 4

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

1. Итеративные характеристики

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

Определение 1. Характеристика  называется итеративной, если обмениваемое значение двух половин  равно .

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

Есть различные типы итеративных характеристик, но самые простые наиболее полезны. Эти характеристики базируются на ненулевом входном XOR-е в функцию F, которая может вызвать нулевой выходной XOR (т.е. два различных входа дают тот же самый выход). Это возможно в шифре DES, по крайней мере, для трех соседних S блоков. Структуру таких характеристик следует из примера, представленного на Рис.1 (характеристика под номером 2, Рис.5, Л-3)

Пример 1. Если входной XOR функции F есть , т.е. 0, то мы можем построить итеративную характеристику (см. Рис.1).

Рис.1. Итеративная двухцикловая характеристика.

Наилучшая такая характеристика имеет вероятность около 1/234. Пяти-цикловая характеристика, базирующаяся на этой итеративной характеристике, имеет вероятность около 1/55000.

Статистическое поведение большинства характеристик не позволяет нам искать пересечение всех ключей, предложенных (поддерживаемых) различными парами, как это мы делали в примере 6, Л-2, так как пересечение обычно пустое: неправильные пары не обязательно указывают на правильный ключ как возможное значение. Однако, мы знаем, что правильное ключевое значение должно быть результатом всех правильных пар, которые встречаются (приблизительно) с характеристической вероятностью (с вероятностью характеристики). Все другие возможные ключевые значения распределены достаточно произвольно: ожидаемое XOR значение (которое является обычно нереальным значением в паре) с известной парой зашифрованного текста может вызвать любое ключевое значение из всех возможных, и даже неправильные ключевые значения, предлагаемые правильными парами, совсем произвольны. Следовательно, правильный ключ появляется с характеристической вероятностью (с вероятностью характеристики) из правильных пар плюс другие произвольные случаи (неправильные пары). Чтобы найти ключ, мы должны просто считать количество случаев появления каждого из предложенных ключей. Правильным, вероятно, будет ключ, который встречается чаще всего.

Каждая характеристика позволяет искать конкретное количество битов в подключе последнего цикла (биты, которые входят в некоторые конкретные S блоки). Наиболее полезные характеристики те, которые имеют максимальную вероятность и максимальное число битов подключа, чьи случаи могут быть подсчитаны. Конечно, нет необходимости рассчитывать на все возможные биты подключа. Преимущество подсчетов всех возможных битов подключа хорошая идентификация правильного ключевого значения и небольшая сумма нужных данных. Тем не менее, счет количества случаев всех возможных значений для многих битов обычно требует огромную память, которая может сделать атаку непрактичной. Более практично подсчитывать меньшее число битов подключа, входящих в меньшее число S блоков, а все другие S блоки использовать только для того, чтобы идентифицировать и отвергать те неправильные пары, в которых входные XOR-ы S блоков не могут вызвать ожидаемые выходные XORы. Поскольку около 20% выходов таблиц распределения разностей S блоков невозможны (имеют вероятность равную нулю), то около 20% неправильных пар может быть отвергнуто каждым S блоком перед тем, как они действительно будут подсчитаны.

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

Определение 1. Отношение количества правильных пар к среднему результату счета счетной схемы называется отношением сигнал/шум этой счетной схемы и обозначается S/N.

Чтобы найти правильный ключ с помощью счетной схемы нам нужна высоко вероятная характеристика и достаточное количество шифртекстовых пар, которые гарантируют существование нескольких правильных пар. Это означает, что для характеристики с вероятностью 1/10000 нам нужно несколько десятков тысяч пар. Сколько пар необходимо зависит от вероятности самой характеристики, количества подсчитываемых ключевых битов и уровня идентификации неправильных пар, которые могут быть отвергнуты перед счетом. Если мы ищем k ключевых битов, то мы подсчитываем количество появлений 2k возможных ключевых значений в 2k счетчиках. Счетчики содержат среднее значение счета (итог)  подсчетов, где m  число просчитанных пар, среднее значение счета для подсчитываемой пары, а  отношение счета к общему числу всех пар (т.е. подсчитанных и отвергнутых).

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

Правильное ключевое значение подсчитывается около mp раз, используя правильные пары, где p является характеристической вероятностью (вероятностью характеристики), плюс случайные подсчеты, оцененные выше для всех возможных ключей. Отношение сигнал/шум счетной схемы, следовательно, есть:

.

Простой вывод из этой формулы состоит в том, что отношение сигнал/шум счетной схемы не зависит от количества пар использованных в схеме. Другой вывод состоит в том, что различные счетные схемы, базирующиеся на той же самой характеристике, но с различным числом битов подключа, имеют различные S/N.

Приведенные соотношения позволяют связать количество пар, которые необходимо для счетной схемы с количеством нужных правильных пар. Необходимое число правильных пар является функцией отношения сигнал/шум. Когда S/N достаточно высокое, то необходимо только несколько случаев обнаружения правильных пар, чтобы однозначно идентифицировать правильные значения битов подключа. Эксперименты показывают, что, когда S/N около 1-2, достаточно около 20-40 правильных пар. Когда S/N много выше обычно достаточно даже 3-4 правильных пар. Когда S/N много меньше, идентификация правильных значений битов подключа требует неразумно большое число пар.

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

Определение 2. Квартет является структурой из четырех зашифрованных текстов, которая одновременно содержит две пары зашифрованных текстов одной характеристики и две пары зашифрованных текстов второй характеристики. Октет является структурой из восьми зашифрованных текстов, которая одновременно содержит четыре пары зашифрованных текстов трех характеристик каждый.

Пример 2. Следующие четыре плайнтекста формируют квартет (где  и  плайнтекстовые XOR-ы характеристик):

1. Случайный плайнтекст P.

2. .

3. .

.

Две пары первой характеристики помечены (1, 2) и (3, 4), а две пары второй характеристики помечены (1, 3) и (2, 4).

Получение таких структур может быть достигнуто двумя путями. Когда атака использует n пар, для каждой из двух характеристик мы можем использовать n/2 квартетов, которые содержат ту же информацию как и каждые n пар каждой из характеристик. Таким образом, мы сохраняем половину данных. Используя три характеристики мы можем сохранить 2/3 данных. Другой метод можно использовать, когда в атаке одновременно используются две характеристики при подсчете тех же битов. Здесь мы можем разделить данные так, что одна половина пар базируются на первой характеристике, а вторая на другой. Когда используются квартеты, мы можем сохранить половину данных, а, когда могут быть использованы октеты, мы можем сохранить 2/3 данных.

2 Атака на DES уменьшенный до восьми циклов

Рассмотрим теперь детально саму технику добывания ключей. Начнем с более простого случая атаки на DES, уменьшенный до восьми циклов. Такой шифр, как показывают Эли Бихам и Ади Шамир, может быть взломан, используя около 25000 шифрованных пар, для которых XOR открытых текстов равняется P = 40 5C 00 00 04 00 00 00x. Метод определяет 30 битов K8. 18 дополнительных ключевых битов находятся, путем выполнения аналогичных манипуляций с парами. Оставшиеся восемь ключевых битов могут быть найдены, полным перебором.

В этой атаке используется характеристика, представленная на Рис. 2.

Рис. 2. Восьмицикловая характеристика.

Эта характеристика1 имеет вероятность 1/10485.76. Входная разность в шестом цикле для правильной пары равна

f = d E= b  A = L = 40 5C 00 00x.

Следовательно, для пяти S блоков  и .

Это значит, что в правильных парах пять S блоков S2, S5, …, S8 удовлетворяют условиям  и . В результате с помощью очевидного соотношения H = l  g = l e  F мы можем найти выходные разности, соответствующие S блокам восьмого цикла. Входные данные восьмого цикла известны из шифртекстов. Следовательно, мы можем воспользоваться счетным методом для нахождения 30 подключевых битов, входящих в пят ь S блоков восьмого цикла. Отношение сигнал-шум счетной схемы в этом случае равно  (в правильных парах, как уже было отмечено выше, пять S блоков S2, S5, …, S8 удовлетворяют условиям , , и тогда  средний итог подсчетов одного счетчика, а так как все пары правильные, то каждая пара будет фиксироваться всеми счетчиками и, следовательно, ).

Счет 30 подключевых битов требует огромной памяти из 230 счетчиков. Однако, как уже отмечалось выше, можно уменьшить объем памяти, если перейти к подсчету меньшего числа подключевых битов, входящих соответственно в меньшее число S блоков. Остальные S блоки могут быть использованы для определения некоторых неправильных пар, для которых . Около 20% выходов в таблицах распределения побитовых разностей невозможны, и, таким образом, каждый из оставшихся S блоков отбрасывает 20% неправильных пар. При подсчете 24 ключевых битов приходим к отношению сигнал-шум счетной схемы равному , а при подсчете 18 ключевых битов имеем соответствующее значение равным .

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

e = 04 00 00 00x  E = P(0W 00 00 00x) = X0 0Y Z0 00x

где W  {0x,1x,2x,3x,8x,9x,Ax,Bx}, X  {0x,4x}, Y  {0x,8x 10 x} и Z  {0x,4x} (в битовом представлении 6  P(5, 7, 8, исключая 6) 2, 13, 18, исключая 28-й бит). Поэтому на шестом цикле

f = X0 5V Z0 00x,

где V = Y  4. Единственная возможная комбинация в которой Z = 0 это переход 04 00 00 00x  40 08 00 00x, имеет вероятность 16/64
(NS
2(8x,Ax) = 16). Все другие комбинации (в которых Z = 4), имеют общую вероятность 20/64 (NS2(8x,1x) = 0, NS2(8x,3x) = 4, NS2(8x,9x) = 10, NS2(8x,Bx) = 6). Мы не можем считать подключевые биты пятого S блока, но очевидна целесообразность проверки возможных переходов  для пятого S блока, которая существует только у 80% пар. В результате вероятность перехода
e  E есть 16/64 + 0.820/64 = 32/64 = 1/2. Вероятность пятицикловой модифицированной характеристики равна . Отношение сигнал-шум счетной схемы, которая считает 24 подключевых бита, входящих в S2, S6, S7 и S8, равно . Это отношение сигнал-шум допускает (определяет) число правильных пар не менее пяти. Поэтому, здесь используется общий объем около 25000 пар. Отношение сигнал-шум счетной схемы, которая считает 18 подключевых битов, входящих в три S блока из S2, S6, S7 и S8 равно . Схема, которая считает 18 битов, требует 150000 пар и имеет в среднем около 24 просчетов для любого неправильного ключевого значения и около 53 просчетов для правильного ключевого значения
(53 = 24 + 150000/5243 = 24 +29).

Прорезюмируем кр иптоаналитический метод, использующий 218 ячеек памяти, в виде следующей последовательности операций, изложенной в работе Эли Бихана и Ади Шамира:

1. Установить массив из 218 счетчиков, которые инициализировать нулями (установить в ноль). Массив соответствует 218 значениям 18 ключевых битов K8, входящих в S6, S7 и S8.

2. Предварительно обработать возможные значения SI, которые удовлетворяют каждому  для восьми S блоков, и занести их в таблицу. Эта таблица используется для ускорения программы.

3. Для каждой шифртекстовой пары:

Принять h = r, H = l и h = r. Вычислить  и  для S2, S5,…, S8 с помощью h и H. Вычислить  для S6, S7 и S8 с помощью h.

(b) Для каждого из S блоков S2, S5, S6, S7 и S8 проверить условие . Если  для одного из S блоков, тогда отвергнуть пару как неправильную.

(с) Для каждого из S блоков S6, S7 и S8: выбрать из предварительно обработанной таблицы все значения , которые возможны для . Для каждого возможного значения вычислить SKh =   . Увеличить на единицу все счетчики, соответствующие комбинациям возможных значений S6Kh, S7Kh и S8Kh.

4. Найти вход в счетчик (массив счетчиков), который содержит максимальный результат счета. Индекс входа является наиболее вероятным действительным значением S6Kh, S7Kh и S8Kh, которые являются значением 18 битов 31, …, 48 ключа K8.

1 Есть дополнительная пятицикловая характеристика с вероятностью около 1/33000. Ее XOR открытого текста равен P = 04 04 07 80 00 20 20 00x. В этой характеристике только четыре S блока в шестом цикле удовлетворяют условию . Есть, конечно, и другие характеристики, но для них вероятности или число не изменившихся S блоков в шестом цикле меньше, и поэтому их использование менее полезно.


 

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

38011. ИССЛЕДОВАНИЕ АЛГОРИТМОВ НА ГРАФАХ 1.78 MB
  Краткая теория Представление графов Для представления графов чаще всего применяется матрица смежности это матрица [n n] где n число элементов а элементы [i j] могут быть равны значению 0 или x flse или 1 true в зависимости от того присутствует ли дуга из вершины i в вершину j рис.n] of integer то можно составить оператор L_SMEG_V который определяет множество смежных вершин для заданной вершины v и записывает их в вектор типа ms. function L_SMEG_Vv2 n1:integer; vr k1:integer:ms; {v2 это вершина для которой ищут все...
38012. ОПРЕДЕЛЕНИЕ ЭФФЕКТИВНОСТИ И СЛОЖНОСТИ ИССЛЕДУЕМЫХ АЛГОРИТМОВ 146.5 KB
  Краткая теория Теория сложности алгоритмов Сложность алгоритма характеристика алгоритма определяющая зависимость времени выполнения программы описывающей этот алгоритм от объёма обрабатываемых данных. Формально определяется как порядок функции выражающей время работы алгоритма. Эффективность алгоритма временная сложность в самом худшем случае Ofn или просто fn.
38013. ИЗУЧЕНИЕ БЕТА –АКТИВНОСТИ 145.5 KB
  10 ЛАБОРАТОРНАЯ РАБОТА № 95 ИЗУЧЕНИЕ БЕТА АКТИВНОСТИ Цель работы Изучение явления бета распада определение длины пробега частиц и максимальной энергии частиц радиоактивного источника. Например радиоактивный изотоп водорода испускает частицы с Еmx = 18 кэВ а изотоп азота с Еmx = 166 МэВ. Типичная кривая распределения частиц по энергиям изображена на рис.1 где dN dE число частиц имеющих полную энергию от Е до Е dЕ Еmx максимальная энергия частиц данного радиоактивного вещества.
38014. Изучение нормального закона распределения случайных величин (закон Гаусса) на основе опытных данных 190 KB
  Составить интервальную таблицу частот статистический интервальный ряд распределения: а Разбить весь диапазон случайных величин на k интервалов. Строки 13 Таблицы 3 называют статистическим интервальным рядом распределения. Интервальный ряд распределения изобразить графически в виде гистограммы.
38015. ФОТОМЕТРИЧЕСКОЕ ТИТРОВАНИЕ 115.5 KB
  Если измерение ведется на определенной длине волны а прибор снабжен монохроматором процесс титрования называют спектрофотометрическим титрованием. находят по резкому перегибу полученной в ходе титрования графической зависимости оптической плотности раствора поглощения пропускания от объема добавленного титранта. При СФтитровании достигается особая селективность что связано с возможностью перехода в ходе титрования многокомпонентных систем от одной длины волны к другой.
38016. ДИФФЕРЕНЦИАЛЬНАЯ ФОТОМЕТРИЯ 176.5 KB
  Сущность метода Точность спектрофотометрического анализа можно значительно повысить если измерять не абсолютную величину оптической плотности анализируемого раствора а ее относительную величину ΔD проводя измерения раствора с концентрацией Сx против эталона уже содержащего определяемый компонент в известной концентрации Со. Однако способы настройки существенно отличаются в разных вариантах фотометрического анализа: Способ настройки 1 2 3 4 5 Концентрация раствора в кювете во время настройки на Т = 100 0 С0 С0 или Сх 0 С 0 Концентрация...
38017. Запуск и настройка СУБД VFP 6.0 133 KB
  Вызывается Ctrl F2.0 специальные и функциональные клавиши Сочетание клавиш Пункт меню Комментарий CtrlN File New Создать новый файл CtrlO File Open Открыть существующий файл CtrlS File Sve Сохранить текущий файл CtrlP File Print Печать CtrlZ Edit Undo Отменить действие CtrlR Edit Redo Повторить действие CtrlX Edit Cut Вырезать CtrlC Edit Copy Копировать CtrlV Edit Pste Вставить Ctrl Edit Select ll Выделить все CtrlF Edit Find Найти в текущем файле CtrlG Edit Find gin Найти следующий CtrlL Edit Replce CtrlD Progrm Do CtrlM...
38018. ИЗУЧЕНИЕ И ПРИМЕНЕНИЕ ФИЗИЧЕСКОГО И МАТЕМАТИЧЕСКОГО МАЯТНИКОВ 98.63 KB
  Ознакомление с физическим и математическим маятниками изучение периодического движения маятников как примера колебаний в системах с одной степенью свободы. Измерение ускорения силы тяжести с помощью математического маятника. Измерение периода колебаний физического маятника и сравнение его с расчётным значением. Измерение момента инерции тела сложной формы с помощью физического маятника.
38019. Основы электрохимии 48.5 KB
  В пробирку налить 2 мл раствора йодида калия KJ добавить 2 3 капли раствора уксусной кислоты CH3COOH затем прилить 1 мл раствора перекиси водорода H2O2. В пробирку налить 2 мл раствора перманганата калия KMnO4 добавить 2 3 капли раствора серной кислоты H2SO4 затем прилить 1 мл раствора перекиси водорода H2O2. Собрать гальванический элемент из двух металлических электродов и растворов электролитов: зачистить наждачной бумагой две металлические пластинки промыть их дистиллированной водой просушить фильтровальной...