Способы криптоанализа симметричных шифров

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

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

Для ГОСТ 28147-89 была показана возможность раскрытия ключа и таблиц подстановок с помощью криптоанализа на основе формирования случайных аппаратных ошибок. DES, RC5 и другие шифры также являются уязвимыми по отношению к этому виду криптоанализа, поэтому при их использовании необходимо обеспечить защиту аппаратуры от навязывания сбоев.

4. Атаки по электромагнитному излучению

Выполнение  вычислительных операций на компьютере сопряжено с выделением электромагнитного излучения. Измеряя и анализируя это излучение, нарушитель может получить значительную информацию о выполняющихся вычислениях и используемых данных. Атаки по электромагнитному анализу могут быть также разделены на две большие категории: простые (SEMA) и дифференциальные (DEMA).

 

 

2. Практическая часть

Рассмотрим дифференциальный криптоанализ на примере алгоритма DES. Рассмотрим кратко алгоритм DES (рисунок 3).

Рисунок 3.

После начальной перестановки бит 16 раз  повторяется следующие процедуры:

• Получение раундового ключа J_i
• Применение функции f(L_i,J_i)
• XOR для R_i и f(L_i,J_i) – результат записывается в R_i+1
• Присвоение L_i+1 = R_i

После чего опять производится перестановка бит. Функция f выполняет следующие  преобразования (рисунок 4):

Рисунок 4.

• Расширяющая перестановка входных битов;
• Операция XOR ключа и расширенного входа;
• Разделение результата на 8 блоков по 6 бит и применение к ним S‐блоков, выходом которых являются блоки по 4 бита;
• Перестановка разрядов.

Долгое  время для криптоанализа алгоритма DES не было предложено ни одного метода, позволяющего уменьшить количество требуемых операций по сравнению с полным перебором более чем в 2 раза (эффект 50%‐го сокращения достигается, если имеется достаточное количество пар наборов открытый текст – шифротекст, в которых один открытый текст является побитовым отрицанием другого).

Были  найдены некоторые алгоритмы  для «урезанного» DES (т.е. при использовании меньшего количества раундов). Среди них можно выделить следующие:

• Встреча посередине (Шаум и Эвертс);
• Метод отыскания линейных зависимостей в битах ключа (Дейвиз).

Первым  методом, как говорилось ранее, позволяющим  ускорить криптоанализ полного DES, был дифференциальный метод, предложенный в 1991 году Бихамом (Biham) и Шамиром (Shamir).

Вначале этот метод также был предложен  для «урезанного» DES, но вскоре был  обобщен на полный 16‐раундовый алгоритм. Этот метод требует 247 открытых текстов, выбранных нападающим и обладает 237 сложностью. Природа метода статистическая, т.е. отыскиваются статистически наиболее вероятные ключи.

В данной курсовой будет рассмотрен алгоритм для трехраундового DES. Алгоритм для большего количества раундов является обобщением приведенного здесь алгоритма.

Метод дифференциального криптоанализа основан на влиянии особого вида разностей открытых текстов на разности шифротекстов (разностью будем называть побитовый XOR). Эти разности используются для отыскания статистических вероятностей ключей и отыскания наиболее вероятных из них.

Рассмотрим  фрагменты L_i на входе функции f на i‐ой итерации для двух различных открытых текстов. Пусть известна разность L_i для заданных текстов. Эта разность инвариантна относительно операции ХОR с раундовым ключом и линейна относительно операций расширения и перестановки битов. Но применение S‐блоков в функции f является нелинейной операцией. Поэтому для нахождения XOR результата действия функции f на пару входных аргументов недостаточно знать только разность аргументов, необходимы и сами значения аргументов. Однако каждому входному ХОR определенного S‐блока соответствует некоторое вероятностное распределение выходного XOR. На рисунке 5 показано вероятностное распределение выходного XOR при заданном входном для первого S‐блока (нормированное на 64 – т.е. сколько раз для заданного XOR входа возникает такой XOR выхода). Среднее значение вероятности равно 1/16, но видно, что

распределение не равномерно и многие выходные XOR невозможны или имеют малую вероятность.

Если  известны входы и разность (XOR) на выходе функции f, то, в силу линейности, известны и разности на входах и выходах всех S‐блоков. Далее, по этим разностям находим по таблице все возможные варианты входа S‐блока (а не разности входов) и вычисляем из них возможные варианты компонент раундового ключа (их – вариантов – столько же, сколько и возможных входов S‐блоков). Если подобную процедуру повторить для нескольких пар входных/выходных разностей, то можно отсеять наименее вероятные варианты раундового ключа.

Рисунок 5.

Далее рассмотри  алгоритм трехраундового DES (рисунок 6):

Рисунок 6.

Пусть (L, R) – открытый текст, (l, r) – шифротекст. Тогда l=L xor A xor C. Открытый текст будем выбирать следующим образом: L – случайно, R – равно нулю. Тогда XOR выхода первого F (для пары открытых текстов) равен нулю, т.к. входы одинаковы – равны нулю. Отсюда XOR(l) = XOR(L) xor XOR(C), или XOR(C) = XOR(l) xor XOR(L). Под обозначением XOR(i) понимается разность соответствующих блоков для разных открытых текстов.

Значение «с» (вход последней F) в явном виде присутствует в шифротектсе, отсюда получаем XOR входа F.

К найденным  значениям XOR входа и выхода функции F применяется описанный ранее алгоритм, и находятся возможные варианты ключа.

К примеру, рассмотрим случай, когда на вход XORа перед первым S‐блоком в третьем раунде были поданы значения S_E=1h и S_E* = 35h (эти значения легко вычисляются из шифротекста), а XOR выходов блока для этих входов равен S_О = Dh (вычисляется из открытого и шифротекстов). Тогда для полученной пары XOR входов/выходов S‐блока (1h/34h) находим все возможные варианты входных значений S_i на входе первого S‐блока, дающие эту пару XOR входов/выходов. А поскольку S_i =S_E^(*) xor S_K, где S_K – часть раундового ключа, то отсюда можно найти все возможные варианты S_K (рисунок 7).

Рисунок 7.

Левая часть таблицы на рисунке 7 показывает возможные пары (S_i S_i*), а правая – возможные ключи. Вариантов для ключа для каждой строки два, т.к. какое из чисел является S_i, а какое ‐ S_i*, не определено.

 

Заключение

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

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

 

Список использованных источников

1.	Алгоритм DES: [Электронный ресурс]. - Режим доступа: http://book.itep.ru/6/des_641.htm. Дата обращения: 15.11.2012.
2.	Винокуров А., Применко Э. Сравнение российского  стандарта шифрования, алгоритма ГОСТ 28147-89, и алгоритма Rijndael, выбранного в качестве нового стандарта шифрования США [Текст] // «Системы безопасности» - М., изд. «Гротэк», 2001, №№1,2.
3.	Горбенко И.Д. Криптографическая защита информации в информационных системах. Курс лекций. [Текст] / И.Д. Горбенко –  ХНУРЭ, 2002.
4.	Грушо А.А., Применко Э.А., Тимонина Е.Е. Анализ и синтез криптоалгоритмов. Курс лекций. [Текст] / А.А Грушо - М.: 2000.
5.	Жуков А.Е. Криптоанализ по побочным каналам (Side Channel Attacks). // Материалы конференции РусКрипто – 2006.
6.	Зубов А.Ю. Криптографические методы защиты информации. Совершенные шифры: Учебное пособие. [Текст] - М.: Гелиос АРВ, 2005.
7.	Ростовцев А.Г., Михайлова Н.В. Методы криптоанализа классических шифров [Текст] // 1998.
8.	Тульчинский  А. Взлом криптоалгоритмов: мифы и реалии // «Компьютерра» №12 от 19 мая 2003.

№ докум.

Лист

Изм.

Подп.

Дата

Пров.

Литера

Лист

Листов

Н.контр.

Утв.

Разраб.

КР.460300.090105.65.ПЗ

Подпись

Дата

№ докум.

Лист

Изм.

Лист

КР.460300.090105.65.ПЗ