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


 

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

38535. Разграничение изнасилования и насильственных действий сексуального характера от иных преступлений, посягающих на половую неприкосновенность и половую свободу 322 KB
  Уголовноправовой анализ насильственных действий сексуального характера. Разграничение изнасилования и насильственных действий сексуального характера от иных преступлений посягающих на половую неприкосновенность и половую свободу. Актуальность выбранной темы дипломной работы обусловлена тем что в нынешнее время нравственные устои в сфере половых отношений в российском обществе существенно расшатаны путем легализации однополых связей агрессивностью показа в средствах массовой информации и коммуникации технологии секса безбрежным...
38536. Назначение и характеристика парка обслуживания пассажирских вагонов в прямых поездах и поездах своего формирования 1019.5 KB
  Назначение и характеристика парка обслуживания пассажирских вагонов в прямых поездах и поездах своего формирования 3. Технология обслуживания ходовой части вагонов 4. Время ремонта вагонов на ПТО 5. Перечень инструментов приспособлений и оборудования применяемого при обслуживании вагонов 6.
38537. Электрофизические свойства ультра-тонких плёнок кремния на изоляторе, сформированных методом ионной имплантации и водородного переноса 787.5 KB
  «Кремний на изоляторе» (КНИ) — технология изготовления полупроводниковых приборов, основанная на использовании трёхслойной подложки со структурой кремний-диэлектрик-кремний вместо обычно применяемых монокристаллических кремниевых пластин. В качестве диэлектрика обычно выступает диоксид кремния SiO2
38539. Социальная защита детей-сирот и детей, оставшихся без попечения родителей: история вопроса и современное состояние 91.5 KB
  Исторические предпосылки возникновения социальной защиты детей сирот и детей оставшихся без попечения родителей 1. Зачатки социальной защиты детей – сирот и детей оставшихся без попечения родителей Во все времена были дети которым выпадала горькая участь расти без родителей. Первые учреждения для детей оставшихся без родителей были приютами для младенцев.
38540. Разработка компактного, надежного современного датчика алкогольных паров 1.06 MB
  Ширина печатного проводника рассчитывается по формуле:1 1 где I протекающий по проводнику ток А; J плотность тока А мм h толщина фольги мм; Для односторонней печатной платы изготовленной химическим способом методом сеткографии для бытовой аппаратуры плотность тока J= 30 ммпо справочнику. Сопротивление...
38542. ОПЫТНО-ЭКСПЕРИМЕНТАЛЬНАЯ РАБОТА ПО ФОРМИРОВАНИЮ ЭКОЛОГИЧЕСКОЙ КУЛЬТУРЫ МЛАДШИХ ШКОЛЬНИКОВ ПОСРЕДСТВОМ ДИДАКТИЧЕСКИХ ИГР 720 KB
  Формирования экологической культуры посредством дидактической игры . Эффективным методом формирования экологической культуры являются дидактические игры. В процессе использования дидактической игры у детей формируется умение действовать в какойлибо ситуации в соответствии с определенными нормами. Фицула в учебнике по педагогике отмечает что целью формирования экологической культуры в учебновоспитательном процессе используют экологопсихологическую терминологию групповые и ролевые игры мозговой штурм что направлены на...
38543. Управление маркетингом на предприятие на примере торговой компании ТОО «DOM COMPANI» 755.5 KB
  Организационная структура предприятия ТОО DOM COMPNI. Используя в управлении теорию маркетинга предприятия и фирма должны строить свою деятельность в соответствии с ее ключевым принципом: производить то что продается а не продавать то что производится. Методически этот процесс должен предшествовать разработке любых тактических и тем более стратегических линий поведения предприятия поскольку он на многоальтернативной основе позволяет высшему звену управления остановить свой выбор на наиболее перспективных для предприятия рынках....