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 блоков в шестом цикле меньше, и поэтому их использование менее полезно.


 

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

28249. Гуманистический (К.Роджерс, А. Маслоу), экзистенциальный (В.Франкл, Р.Мэй, И. Ялом) и гештальт (Ф. Перлз, К.Левин) подходы к исследованию личности и психотерапия 68 KB
  Основные положения гуманистической психологии: 1человек должен изучаться в его целостности; 2каждый человек уникален поэтому анализ отдельных случаев не менее оправдан чем статистические обобщения; 3переживания человеком мира и себя в мире являются главной психологической реальностью; 4человеческая жизнь единый процесс становления и бытия человека; 5человек открыт к непрерывному развитию и самореализации которые являются частью его природы; 6человек обладает определенной степенью свободы от внешней детерминации благодаря смыслам и...
28250. Культурно-историческая психология (Выготский Л.С., Леонтьев А.Н.) 49 KB
  В основе теории лежат 2 гипотезы: об опосредованном характере психической деятельности о происхождении внутренних психических процессов из деятельности первоначально внешней и €œинтерпсихической€ Выготский выдвигает предположение что в психике человека существует особенность соответствующая той роли которую играют труд употребление и создание орудий в его производственной деятельности. Эта особенность – в опосредованном характере психической деятельности людей основа исторического подхода к изучению человека. Психическая деятельность...
28251. Гуманистическая психология (А.Маслоу, К.Роджерс и др.) 48 KB
  Бихевиоризм фактически сводит жизнедеятельность к манипуляциям и тем самым низводит человека до уровня стимульнореактивного механизма. Основные положения гуманистической психологии: человек должен изучаться в его целостности; каждый человек уникален поэтому анализ отдельных случаев не менее оправдан чем статистические обобщения; переживания человеком мира и себя в мире являются главной психологической реальностью; человеческая жизнь единый процесс становления и бытия человека; человек открыт к непрерывному развитию и самореализации...
28252. Когнитивная психология (Дж.Миллер, У.Найссер и др.) 40 KB
  КОГНИТИВНАЯ ПСИХОЛОГИЯ одно из ведущих направлений современной зарубежной психологии. Хотя ощущение и восприятие механическая а позже логическая память мышление и речь как психические функции действия или процессы были первыми объектами исследований в ранней экспериментальной психологии но все же первыми научными направлениями завоевавшими психологическое пространство в начале нашего века были бихевиоризм психоанализ и гештальтпсихология в меньшей степени интересовавшиеся указанными процессами как таковыми. Лишь к 60м годам...
28253. Виды ощущений (по Б.Г.Ананьеву) 39 KB
  Так тактильные вибрационные мышечные вестибулярные ощущения отражают определенные моменты и свойства механического движения различных тел в том числе и тела человека. Интерорецепция вкусовые болевые температурные ощущения специфически связаны с основными явлениями жизнедеятельности биологической формой движения материи. механические формы движения тактильные вибрационные мышечные вестибулярные молекулярные формы движения зрительные слуховые вибрационные температурные химические формы движения обонятельные...
28254. Эволюция и психологичсское значение дистантных ощущений. Отражение пространства при парной работе дистантных анализаторов 47 KB
  1 базальные ощущения тактилънокинестетическое осязание 2 ведущие зрение слух от них идет максимальная информация 3 сквозные ощущения кинестетические движение. Дистанционные ощущения в процессе эволюции развились позже контактных: вибро и хеморецепция обоняние слух зрение как повышение адапгивных возможностей организма ОТРАЖЕНИЕ ПРОСТРАНСТВА функция парных анализаторов напр. Бинокулярное зрение При раздражении несоответствующих диспарантных точек бинокулярное зрение или дизассоциируется раздваевается или...
28255. Особая роль осязания в структуре сенсорной организации человека и его значение в процессах познания и труда (Ананьев, Веккер, Ломов, Ярмоленко) 27 KB
  Осязание в процессах познания и труда которая в 1961 году была удостоена премии К. Осязание органически связано со всей структурой чувственной репрезентации человека. Осязание способность животных и человека воспринимать действие факторов внешней среды с помощью рецепторов кожи опорнодвигательного аппарата мышц сухожилий суставов и др. Осязание существенно расширяет представления организма об окружающем мире играет важную роль в его жизнедеятельности.