22232

Дифференциальны криптоанализ полного 16-циклового DES

Лекция

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

Любая пара плайнтекстов дающая повышение промежуточных характерных XOR значений названа правильной парой. Предполагаемое изменение XOR соответствующих значений в течении шифрования правильной пары плайнтекстов в новой версии 16цикловой атаки проиллюстрировано на Рис.2 которое включает 15цикловую атаку в циклах со 2 до 16 с предшествующим новым 1ым циклом Наша цель сгенерировать без потери вероятности пары плайнтекстов чьи XOR выходы после первого цикла являются требуемыми XOR входов в 13цикловой характеристике в циклах со 2го по...

Русский

2013-08-04

279 KB

6 чел.

ЛЕКЦИЯ 8

Тема 4. Дифференциальны криптоанализ полного 16-циклового DES

На этой лекции мы рассмотрим первую известную атаку, способную взломать полный 16-цикловый DES со сложностью меньшей чем 255 (сложностью прямого перебора всех ключей), разработанную израильскими учеными Эли Биханом и Ади Шамиром1.

На предыдущей лекции было показано, что на момент создания стандарта разработчики обеспечили его защиту от 16-цикловых атак дифференциального криптоанализа. Но израильские ученые нашли возможность построить атаку на DES пользуясь 13- цикловой дифференциальной характеристикой, для которой запаса прочности, учтенной разработчиками стандарта оказалось недостаточно.

Ранняя версия их атаки на 15-цикловый вариант DES базировалась на двухцикловой итеративной характеристике обнуляющего типа представленной на Рис.1, в которой использована разность , при этом вероятность трехблочного цикла  получается близкой к .

Рис.1. Двухцикловая итеративная характеристика обнуляющего типа

!3-цикловая характеристика, являющаяся итеративным повторением этой характеристики шесть с половиной раз имеет вероятность около . Атака использует эту характеристику на циклах с 1-го по 13-ый с последующей 2R-атакой на 14-ом и 15-ом циклах. Любая пара плайнтекстов, дающая повышение промежуточных характерных XOR значений названа правильной парой. Атака испытывает много пар плайнтекстов и исключает любую пару, которая является явно неправильной для ожидаемых известных входных и выходных значений разностей. Однако, так как криптоаналитик не может определить действительные промежуточные значения, то процесс исключения получается несовершенным и оставляет после себя смесь правильных и неправильных пар.

В ранней версии дифференциального криптоанализа каждая оставшаяся пара поддерживает несколько значений для определенных битов ключа. Правильная пара всегда поддерживает истинное значение для этих ключевых бит (вместе с несколькими неправильными значениями). Когда проанализировано достаточно много правильных пар, правильное значение (сигнал) по сравнению со случайными значениями (шум) становится наиболее часто поддерживаемым. Действительный алгоритм содержит раздельные счетчики для подсчета числа появлений каждого из значений, которые поддерживаются. Это исследование требует огромной памяти (более  счетчиков для атаки на 15-цикловый DES), и имеет низкую вероятность успеха, когда число анализируемых пар оказывается ниже границы, определяемой отношением сигнал шум.

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

Ключом успеха в такой атаке является использование высоко вероятных характеристик, которые дают возможность рассматривать несколько неправильных пар прежде чем встретится правильная пара. Вероятность характеристики, которая используется в атаке на 15-цикловый вариант DES около . Очевидным путем расширения атаки на 16-ть циклов является использование приведенной выше итеративной характеристики еще один раз, но это уменьшает вероятность характеристики с 2-47.2 до 2-55.1, что делает атаку медленнее чем истощающее исследование. Новая версия атаки добавление дополнительного цикла без уменьшения вероятности вообще.

Предполагаемое изменение XOR соответствующих значений в течении шифрования правильной пары плайнтекстов в новой версии 16-цикловой атаки проиллюстрировано на Рис.2, которое включает 15-цикловую атаку в циклах со 2 до 16 с предшествующим новым 1-ым циклом



Наша цель сгенерировать без потери вероятности пары плайнтекстов, чьи XOR выходы после первого цикла являются требуемыми XOR входов  в 13-цикловой характеристике в циклах со 2-го по 14-ый. Пусть P будет произвольный 64-битный плайнтекст, и пусть , . . . ,  будет 212 32-битных констант, которые состоят из всех возможных значений 12-битных позиций, которые XOR-рируются с 12-ю выходными битами S1, S2, и S3 после первого цикла, и нулями на других позициях. Определим теперь структуру, которая состоит из 213 плайнтекстов

 для ,

.

Будем интересоваться плайнтекстовыми парами, в которых все пары ,  с . Всего существует 224 таких плайнтекстовых пар, и их XOR-ы всегда имеют форму , где каждое  встречается точно 212 раз. Так как при реальных преобразованиях левая половина P и левая половина P XOR-рированная с  в первом цикле при действительном ключе создает XOR значение после первого цикла, которое может быть не нулевым только на выходах S1, S2, и S3, то эти XOR значения могут быть только одним из . В результате, точно для 212 плайнтекстовых пар выходной XOR на выходе первой F функции точно сокращается XOR-рированием с левой половиной плайнтекстового XOR, и, таким образом, выходной XOR первого цикла (после обмена местами левых и правых половинок) является желаемым входным XOR  в итеративной характеристике. Следовательно, каждая структура имеет вероятность около  того что содержит правильную пару.

Основной проблемой этой исследования состоит в том, что мы не знаем действительного значения , которое содержится в выходном XOR первой F функции и, таким образом, мы не знаем на какой из 212 пар сосредоточиться. Можно перепробовать все 224 возможные пары, но это очень долго. Но мы можем использовать их кросс продуктовые структуры, для того чтобы выделить правильные пары среди них точно 212 раз. В любой правильной паре выходной XOR после 16-ти циклов должен быть нулевым для выходов пяти S блоков S4, . . . , S8 (т.е. на 20-ти битовых позициях). Мы можем таким образом сортировать (или смешать) две группы по 212 шифртекстов  и  на этих 20 позициях и определять всеслучаи повторяющихся значений среди 224 шифртекстовых пар около 212 раз. Любая пара плайнтекстов, которая не проходит эту проверку имеет ненулевые шифпртекстовые XOR-ы на этих 20 позициях, и, таким образом, не может быть правильной парой по определению. Так как одна из 224 возможных пар проходит эту проверку с вероятностью 2-20, мы ожидаем около 24 = 16 уцелевших пар. Проверкой дополнительных S блоков в первом, пятнадцатом и шестнадцатом циклах и исключением всех пар, чьи XOR значения фиксируются как невозможные в таблицах парных XOR распредеоений различных S блоков, мы можем отбросить около 92,55% таких уцелевших пар2 остается только 160,00745 = 1,19 пар по структуре как ожидаемые выходы данных на фазе сбора. Все эти дополнительные проверки могут быть внедрены в несколькими табличными операциями в маленьких предварительно вычисленных таблиц, и их временная сложность будет намного меньше, чем время, требуемое для преобразования чтобы выполнить одно тривиальное шифрование при истощающем исследовании. Заметим, что этот фильтрующий процесс удаляет только неправильные пары но не все из них и таким образом входные данные в фазе анализа являются по прежнему смесью правильных и неправильных пар.

Данные фазы анализа предыдущей версии дифференциальной криптоаналитической атаки использовали громадный массив свыше 242 счетчиков чтобы обнаружить самое популярные значения определенных ключевых бит. Новый вариант дифференциальной атаки, рассматриваемый здесь, использует только незначительное пространство. Мы хотим подсчитать все ключевые биты одновременно, но не можем позволить себе громадный массив из 256 счетчиков. Вместо этого мы немедленно пробуем каждое поддержанное значение ключа. Ключевое значение поддерживается, когда оно может быть создано как выходными XOR значениями последнего цикла так и ожидаемым выходными XOR первого цикла и пятнадцатым циклом для особых плайнтекстовых и шифртекстовых пар. В первом цикле и в пятнадцатом циклах выходные XORS4 и S5, . . . , S8 являются всегда нулями. Посредством ключевого планирующего алгоритма все 28 бит левого ключевого регистра используются как входы в блоки S1, S2 и S3 в первом и пятнадцатом циклах и S1, . . . , S4 в шестнадцатом цикле. Только 24 бита правого ключевого регистра используются в шестнадцатом цикле. Таким образом, 28 + 24 = 52 ключевых бита входят в эти S блоки.  отобранных 52 битовых значений остающихся после сравнения с выходным XOR последнего цикла с ожидаемым значением и исключением тех значений, которые невозможны, и  остающихся после сравнения с выходным XOR трех S блоков в первом цикле с ожидаемым значением. Простая дробь (доля) остающихся 52-битовых значений остается с помощью анализа трех S блоков в пятнадцатом цикле. Каждая анализируемая пара поддерживается около  = 0.84 значениями для 52 бит ключа, и каждая из них соответствует 16 значениям полного 56-битного ключа. Следовательно, каждая структура поддерживается около 1.190.8416 = 16 выборов для целого ключа. Снимая два дополнительных цикла мы можем проверить каждый такой ключ преобразованием около одного четверти DES шифрований (т.е. выполнение двух циклов для каждого одного из двух членов пары) разрешает толко около 212 выборов ключа. Эта фильтрация стоит около16 = 4 эквивалентным DES операциям. Каждый остающийся выбор 56 бит ключа проверяется пробным шифрованием одного из плайтекстов и сравнением результата с соответствующим шифртекстом. Если проверка успешная, то с высокой вероятностью этот ключ является правильным ключом. Заметим, что отношение сигнал-шум этой счетной схемы есть .

Эти данные анализа могут быть выполнены эффективно тщательным выбором порядка, в котором мы проверяем значения ключевых битов. Сначала мы перечисляем все возможные значения шести ключевых битов S4Kh, и исключаем любое значение, которое не позволяет достичь ожидаемого XOR для четырех выходных бит этого S блока. Это оставляет четыре из 64 возможностей в среднем. Таблица 1 показывает число общих бит входящих в зхадействованные S блоки на первом и шестнадцатом циклах. Символом X обозначены биты, которые не используются в характерных подключах. Мы видим, что три бита S4Kh распределяются (являются общими) с S3Ka. Мы пополняем (комплектуем) три отсутствующих бита S3Ka всеми возможными путями и уменьшаем среднее число возможностей до двух. Два бита S1Kh распределяются с S3Ka. Комплектуя четыре пропущенных бита S1Kh и затем двух пропущенных бита 23Ka мы можем уменьшить среднее число возможностей (около) наполовину. После комплектования 13 оставшихся бит левого ключевого регистра подобным путем, средне число значений поддерживаемых для этой половины ключей есть один.

Чтобы вычислить биты правого ключевого регистра, мы сначала исключаем (выделяем) действительные S блоковые биты из их предполагаемых XOR значений. В пятнадцатом цикле мы знаем входные XOR-ы и выходные XORS блоков S1, S2 и S3. Мы можем таким образом генерировать около 4-5 кандидатов входов для каждого из S блоков, и выводить соответствующие биты в g XOR-рируя с известными битами левого ключевого регистра. В простейшем случае мы можем вычислить (рассчитать0 выходы S блоков S1, S2, S3 и S4 в шестнадцатом цикле. XOR этих битов из H с известными битами левой половины шифртекста l и полученными 16-ю битами g, из которых два бита входят в S1, два бита входят в S2 и три бита входят в S3 в шестнадцатом цикле. Сравниая эти битовые значения с кандидатами входов в S блоки, мы в конце концов придем к около одному кандидату входа в S1, одному для S2 и только половина проб (проверок) будет давать результатом кандидата входа для S3. Мы можем теперь вывести все биты g, которые входят в эти три S блока и вывести соответствующие биты H посредством . Два из этих битов являются выходами S5, два бита есть выходы S6. Три есть выходы S7 и один есть выход S8. Для каждого из этих четырех S блоков мы знаем входные XOR-ы и выходные XOR-ы и можем вывести около 4-5 возможных входов. Так4 как мы знаем действительные значения выходных битов, то число возможных входов уменьшается до около одного для S5 и S6, двух для S8, но только половина проб может дать результатом кандидатов для S7. Мы можем вывести 24 из 28 битов правого ключевого регистра XOR-ированием 24 вычисленных битов со входами этих четырех S блоков с расширенными значениями известной правой половины шифртекста.

Мы можем теперь подитожить выполнение новой атаки следующим образом. Каждая структкра включает правильные пары с вероятностью 2-35.2. Данные собираемые в фазе шифрования включают в себя около 235 структур, которые включают около  выбранных плайнтекстов, из которых 2351.19 = 235.25 пар (236.25 шифртекстов). Остающихся как кандидаты входов для данных в фазе анализа. Вероятность,что по крайней мере одна из них будет правильной парой около 58% и анализ любой правильной пары гарантирует получение правильного ключа. Временная сложность этих данных в фазе анализа около 2354 = 237 эквивалентных DES операций.

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

Эта характеристика имеет ту же самую вероятность, что и первая. С этими метаструктурами мы можем получить в четыре раза больше пар из вдвое увеличенного числа плайнтекстов, и, таким образом, уменьшить число выбираемых плайнтекстовых шифрований для данных в фазе накапления от 248 до 247.

Общие выводы из новой атаки могут быть сводятся к следующему:

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

Число выбранных плайнтекстов может быть уменьшено до  использованием подходящих метаструктур и эффективная временная сложность может быть уменьшена коэффициентом f  1, если проверяемые ключи могут быть отброшены выполнением только части f-той части циклов. Следовательно, атаки с малой памятью могут быть предприняты всякий раз как только  и S/N > 1. Атаки с малой памятью требуют несколько выбранных плайтекстов по сравнению с соответствующими счетными схемами, но если отношение сигнал-шум является также низким, или если число ключевых бит для которых ведется счет мало, временная сложность данных в фазе анализа может оказаться намного больше чем соответствующая сложность счетной схемы.

В атаке, описанной Эли Биханом и Ади Шамиром, , k = 56,  и S/N = 216.8. Следовательно, число выборных плайнтекстов есть , которое может быть уменьшено до  использованием метаструктур. Сложность (данных) фазы анализа составляет 237.2 эквивалентных DES операций.

1 Материал этой лекции составлен по оригинальной работе авторов Eli Bicyam, Adi Shamir Differential Cryptanalysis of full 16-round DES., Technion - Computer Science - Techical Report CS0708 -1991.

2 Дробь близкая к  из этих пар остается и таким образом около 0,9255 из них отбрасывается. Входные XOR значения S блоков в первом и пятнадцатом циклах для правильных пар известны и фиксированы, и, таким образом, мы используем дроби ненулевых входов соответствующих строк в таблицах XOR распределений пар, чьи значения есть ,  и , быстрее чем часть ненулевых входов в целой таблице, которая аппроксимируется значением 0,8.


 

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

41986. ДОСЛІДЖЕННЯ СХЕМ ГЕНЕРАТОРІВ ЕЛЕКТРИЧНИХ СИГНАЛІВ (ПРЯМОКУТНИХ ІМПУЛЬСІВ) 215 KB
  Мультивібратор автоколивальний генератор прямокутних імпульсів. Тривалість імпульсів Порядок проведения экспериментов Результаты всех измерений и осциллограммы занести в соответствующий раздел Результаты экспериментов. б Вимірити амплітуду длительность і період следования імпульсів.
41988. ДОСЛІДЖЕННЯ СХЕМ ГЕНЕРАТОРІВ ГАРМОНІЙНИХ КОЛИВАНЬ І ПИЛКОПОДІБНОЇ НАПРУГИ 207.5 KB
  На рис.14.2 показано схема генератора синусоїдальних коливань на БТ з цепочкой R-параллель. Цепочка R-параллель являє собою коло R – C (три звена), обеспечивающая фазовый сдвиг 180о на рабочей частоте (цепь позитивного зворотного зв'язку). Резистори R1 и R2 создают необходимое смещение. Частота генерації примерно равна
41990. ИССЛЕДОВАНИЕ СХЕМ НА ОПЕРАЦИОННЫХ УСИЛИТЕЛЯХ 170 KB
  Интегратор на ОУ Недостатком этой схемы является дрейф выходного напряжения обусловленный напряжением смещения и входными токами ОУ. Выходное напряжение этой схемы при подаче на нее скачка входного напряжения амплитудной Uвх изменяется в соответствии с выражением: Uвых = Uвх[1 – exp ]. На начальном интервале переходного процесса при t R2С изменение выходного напряжения Uвых будет достаточно близко к линейному и скорость его изменения может быть вычислена из выражения: . Суммирование постоянного и переменного напряжения.
41991. ИССЛЕДОВАНИЕ ОПЕРАЦИОННЫХ УСИЛИТЕЛЕЙ (ОУ) 202 KB
  Идеальный усилитель имеет следующие свойства: бесконечный коэффициент усиления по напряжению А→ ∞; бесконечное полное входное сопротивление Zвх → ∞; нулевое полное выходное сопротивление Zвых → 0; равенство нулю выходного напряжения Uвых = 0 при равных напряжениях на входах U1 = U2; бесконечная ширина полосы пропускания ∆fпр= ∞. За входным каскадом следуют один или несколько промежуточных; они обеспечивают уменьшение напряжения сдвига на выходе усилителя до близкой к нулю величины и усиление по напряжению и по току....