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


 

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

64289. ДОСЛІДЖЕННЯ МЕТОДІВ МАРШРУТИЗАЦІЇ З КОНВЕРСІЄЮ ДОВЖИНИ ХВИЛІ 850.5 KB
  Проте методи маршрутизації в повністю оптичних мережах з використанням конверсії довжини хвилі а також методи оптимального розташування конвертерів для мінімізації їх числа не зважаючи на величезне число робіт в даний час відсутні.
64290. ПСИХОЛОГІЧНІ ЧИННИКИ ДИНАМІКИ СУБ’ЄКТНОСТІ МАЙБУТНЬОГО ВЧИТЕЛЯ У ПРОЦЕСІ НАВЧАЛЬНОЇ ДІЯЛЬНОСТІ 188 KB
  Розвиток людини як суб'єкта діяльності стає метою сучасної освіти та важливою проблемою психології. Категорія суб'єкт має давню історію у вітчизняній психології.
64291. ДОГОВІР ПРО НАДАННЯ ПОСЛУГ У МЕРЕЖІ ІНТЕРНЕТ 146.5 KB
  Актуальність теми дослідження зумовлена стрімким поширенням новітніх комунікаційних та інформаційних технологій та потребою віднайти адекватні правові форми для регулювання відносин щодо набуття зміни та припинення цивільних прав...
64292. БЕЗКОНФЛІКТНЕ УПРАВЛІННЯ ЕКОНОМІЧНИМИ ВЗАЄМОДІЯМИ НА ПРОМИСЛОВОМУ ПІДПРИЄМСТВІ 514 KB
  Відомо, що машинобудівний комплекс є сполучною ланкою між металургійною, гірничою, хімічною та багатьма іншими галузями промисловості і визначає рівень загального розвитку економіки країни.
64293. ЗАХИСТ ПРАВА ЛЮДИНИ НА ОСОБИСТУ СВОБОДУ В КОНТЕКСТІ ПРОТИДІЇ ТОРГІВЛІ ЛЮДЬМИ: ФІЛОСОФСЬКО-ПРАВОВІ ЗАСАДИ 136.5 KB
  Можна відзначити що сутність цього соціального феномену полягає в запереченні свободи людини у звязку з чим головною засадою протидії таким порушенням слід вважати відповідний захист свободи.
64294. РОЗВИТОК Я-КОНЦЕПЦІЇ ОСОБИСТОСТІ МАЙБУТНЬОГО СОЦІАЛЬНОГО ПРАЦІВНИКА У ВИЩОМУ НАВЧАЛЬНОМУ ЗАКЛАДІ 231.5 KB
  Забезпечення ефективності вирішення складного комплексу цих проблем вимагає повноцінних теоретичних концепцій соціальної роботи як професійної діяльності насамперед розвитку адекватної і гармонійної Я-концепції самого працівника соціальної сфери наявність...
64295. СПЕКТРАЛЬНІ ПРОЯВИ ВЗАЄМОДІЇ ІЗОХІНОЛІНОВИХ АЛКАЛОЇДІВ З ДНК 249.5 KB
  Взаємодія низькомолекулярних лігандів з ДНК має широкий спектр застосувань: медичні препарати зокрема протипухлинні та імуномодулюючі флуоресцентні зонди тощо.
64296. МЕТОДИКА ВИРОБНИЧОГО НАВЧАННЯ МАЙБУТНІХ КРАВЦІВ У ПТНЗ ЗАСОБАМИ ІНТЕГРОВАНИХ МІКРОМОДУЛІВ 269.5 KB
  Основи створення методичних систем виробничого навчання та підвищення ефективності професійної підготовки кваліфікованих робітників розроблено в працях В. Перспективним напрямком інтеграції при створенні методичних систем навчання є використання модульного та мікромодульного...
64297. ВУГЛЕПЛАСТИКИ ТРИБОТЕХНІЧНОГО ПРИЗНАЧЕННЯ НА ОСНОВІ ФТОРОПЛАСТУ-4 ТА МОДИФІКОВАНОГО ВУГЛЕЦЕВОВОЛОКНИСТОГО НАПОВНЮВАЧА 197.5 KB
  Сучасна тенденція розвитку полімерного матеріалознавства полягає у пошуку раціональних шляхів використання відомих матеріалів шляхом модифікування їх властивостей.