Реализация уменьшеной версии бумернг атаки на уменьшеную модель шифра Риендаля

Следует назвать также  подход к классификации методов  криптоанализа блочных симметричных шифров, при котором  их делят на: силовые атаки, атаки на цикловую функцию, атаки на схемы выработки подключей и атаки на реализацию [7-8].

Другая классификация  атак на криптосистемы базируется на знании внутренних особенностей криптосистемы  и ее реализации. Здесь можно различать такие атаки [7-8]:

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

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

- Атаки через  побочный канал: и другие атаки, зависимые от реализации, базируются на синхронизации компьютерных операций, на измерении энергопотребления на устройствах, стойких к вмешательству, или электромагнитного излучения. Некоторые контрмеры для анализа мощности были представлены Борцом, Аккаром и Гиродом.

- Анализ отказов: базируется на симметричном инициировании отказов в отдельных аппаратных компонентах, используемых для защиты или хранения ключей или алгоритмов (Бихам и Шамир).

Также существует классификация  атак по доступным для криптоаналитика  данным, например:

1. Атака на основе шифротекста (Chiper-text only)

Допустим, криптоаналитик обладает некоторым числом шифротекстов, полученных в результате использования одного и того же алгоритма шифрования. В этом случае криптоаналитик может совершить только атаку на основе шифротекста. Целью криптографической атаки в этом случае является нахождение как можно большего числа открытых текстов, соответствующих имеющимся шифротекстам, или, что ещё лучше, нахождение используемого при шифровании ключа. Входные данные для подобного типа атак криптоаналитик может получить в результате простого перехвата зашифрованных сообщений. Если передача осуществляется по открытому каналу, то реализация задачи по сбору данных сравнительно легка и тривиальна. Атаки на основе шифротекста являются самыми слабыми и неудобными.

2. Атака на основе подобраного открытого текста (Сhosen plain text)

Атака на основе подобранного открытого текста – данный тип таки является улучшением метода основанного на открытых текстах. Здесь криптоаналитик так же имеет некоторое количество пар открытый/шифрованный текст, известных заранее. Но так же он может получить шифротексты соответствующие текстам заранее им выбранным. Метод получения таких шифртекстов например написать письмо с незашифрованным текстом изобразив из себя лицо от которого ждут шифрованное сообщение и при некоторых условиях можно получить ответ с цитатой данного текста, но уже в зашифрованном виде. Отличие данного метода от атаки на основе открытого текста в том что в данном методе криптоаналитик может сам выбрать какой текст он хочет зашифровать. А в методе, основанном только на открытом тексте все пары открытый / шифрованный текст известны заранее.

3. Атака на основе адаптивно подобранного открытого текста (Сhosen plain text and chiper text)

Атака на основе адаптивно  подобранного открытого текста –  данная атака является расширением  атаки на основе подобранного открытого  текста. Отличие заключается в том, что получив шифротекст соответствующий заданному открытому тексту, криптоаналитик сам принимает решение, какой текст он хочет зашифровать далее. Что как бы добавляет обратную связь в методе взлома. Для данного метода необходим непосредственный доступ к шифрующему устройству.

Существует большое  количество и других атак. Рассмотрим более подробно поставленную задачу на курсовую работу, а именно бумеранг-атаку на уменьшенную модель шифра Rijndael.

 

2 Бумеранг-атака

2.1 Описание атаки

Бумеранг атака по классификации принадлежит по первой классификации к ускоренным атакам, а по второй –  к атаке на основе адаптивно подобранного открытого текста.

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

Рассмотрим атаку более подробно.

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

      

Рис. 7 – Шифруем две пары входного текста Р и Р´

Рис. 8 – Получаем две пары шифротекста С и С´

 

 

 Затем к полученным  значениям шифротекстов необходимо прибавить некую константу дельта и расшифровать их.

Рис. 9 – Сдвигаем С и С´ (прибавляем дельту), получаем D и D´ и расшифровываем их

И получаем расшифрованные тексты Q и Q´. И проверяем, чтобы разница  между исходным Р и Р´ была такой же как и между Q и Q´. Если разница не совпадает, берем следующие пары Р и Р´ и снова находим Q и Q´, пока не найдем нужный квартет. В случае успеха, из этого квартета находим ключ шифрования.

Рис. 10 – Схема атаки бумеранг

 

2.2 Криптоанализ шифра

Рассмотрим криптоанализ бумеранг-атаки:

1. Необходимо подготовить 2³² наборов входящих текстов с значениями (*,0,0,0,0,*,0,0,0,0,*,0,0,0,0,*), где * – все возможные значения. После функции, которая сдвигает рядки, будут в одной и той же колонке.
2. Зашифровать эти наборы и получить  2³² шифротекстов.
3. Модифицировать шифротексты, путем прибавления дельты      где дельта – это фиксированное значение только с одним активным S-box.
4. Расшифровываем модифицированные криптотексты и получаем 2³² новых входящих (расшифрованных) текстов.
5.  Находим пары Q и Q´, которые имеют нулевую разницу на этих 8 байтах.

Рис. 11– Схема-описание для бумеранг-квартетов для шифра Rijndael

2.3 Сложность вычислений атаки для полного шифра Rijndael

 

1. Каждый набор 2³² текстов имеет 2⁶³ пар.
2. Из этих пар 2⁶³/2³²=2⁴¹ будут иметь один активный S-box после одного раунда.
3. Полная сложность вычислений будет: 2³⁸ выбранных пар и 2³⁸ соответствующих выбранных шифротекстов. 2³⁹ время (операций). И 2³⁷ байт памяти.

 

Рис. 12– Таблица сложности вычислений для некоторых атак

 

3 Выводы: Выполнив этот курсовой проект, я рассмотрел возможные атаки на данный шифр, и более подробно познакомился с бумеранг атакой. Также я реализовал упрощённый шифр Rijndael в программной среде Visual Studio 2010 на языке С++ и попытался сделать атаку бумеранг на упрощенный шифр. Результаты, которые были достигнуты, показаны на рис. 13, программа находит квартет пар Р и Р´, Q и Q´, у которых одинаковая разница. Для данной атаки процесс нахождения этого квартета является наиболее трудоемким процессом.

Рис. 13– Результат выполнения программы

 

Список литературы:

1. Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone “Handbook of Applied Cryptography”, CRC Press, October 1996, 816 p.

2 ГОСТ28147-89. Система обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. М. Госстандарт СССР.

3 FIPS 46, “Data Encryption Standard”, Federal Information Processing Standard (FIPS), Publication 46, National Bureau of Standards, U.S. Department of Commerce, Washington D. C.

4 X. Lai, J. L. Massey A proposal for a New Block Encryption Standard. Advances in Cryptology – EUROCRYPT-90 Proceedings, New York, NY: Springer-Verlag, pp. 389-404.

5 J. Daemen and V. Rijmen. AES Proposal: Rijndael. In First Advanced Encryption Standard(AES) Conference, Ventura, CA, 1998.

6 L. Knudsen, "DEAL - A 128-bit Block Cipher", in First Advanced Encryption Standard (AES) Conference, Ventura, CA, 1998.

7 Долгов В.И.,Лисицкая И.В., Головашич С.А, Олейников Р.В. Принципы защиты алгоритма DES от атак дифференциального криптоанализа Радиотехник .2001. Вып. 113. С. 157.

8 ДолговВ.И., ЛисицкаяИ.В., РуженцевВ.И. Обеспечение стойкости шифра  DES  к атакам дифференциального криптоанализа. Радиотехник. 2002 Вып. 124. С. 189.

 

  Приложение А:

 

#include "stdafx.h"

int gmul(int a, int b)

{

int p = 0;

int counter;

int hi_bit_set;

for(counter = 0; counter < 4; counter++)

{

if(b & 1)

p ^= a;

hi_bit_set = a & 0x8;

a <<= 1;

if(hi_bit_set)

a ^= 0x19;

b >>= 1;

}

return p;

}

void AddRoundKey(int** state,int key[2][2])

{

for(int i=0;i<2;i++)

for(int j=0;j<2;j++)

state[i][j]^=key[i][j];

}

void sub_bytes(int** state,int sub_e[16])

{

for(int i=0;i<2;i++)

for(int j=0;j<2;j++)

state[i][j]=sub_e[state[i][j]];

 

}

void shift_rows(int** state)

{

int temp(0);

temp=state[1][0];

state[1][0]=state[1][1];

state[1][1]=temp;

}

void MixColums(int** state,int mdr[2][2])

{

int copy[4][4];

for(int i=0;i<2;i++)

for(int j=0;j<2;j++)

copy[i][j]=state[i][j];

state[0][0]=gmul(copy[0][0],mdr[0][0])^gmul(copy[0][1],mdr[1][0]);

state[0][1]=gmul(copy[0][0],mdr[0][1])^gmul(copy[0][1],mdr[1][1]);

state[1][0]=gmul(copy[1][0],mdr[0][0])^gmul(copy[1][1],mdr[1][0]);

state[1][1]=gmul(copy[1][0],mdr[0][1])^gmul(copy[1][1],mdr[1][1]);

}

void encrypt_R(int** state,int key[2][2], int sub_e[16],int m_e[2][2])

{

AddRoundKey(state,key);

for(int i(0);i<5;i++)

{

sub_bytes(state,sub_e);

shift_rows(state);

    MixColums(state,m_e);

AddRoundKey(state,key);

}

 

}

void decrypt_R(int** state,int key[2][2], int sub_d[16],int m_d[2][2])

{

for(int i(0);i<5;i++)

{

AddRoundKey(state,key);

MixColums(state,m_d);

shift_rows(state);

sub_bytes(state,sub_d);

}

AddRoundKey(state,key);

}

void print(int** state)

{

for(int j=0;j<2;j++)

{

for(int i=0;i<2;i++)

{

printf("%x\t",state[j][i]);

}

printf("\n");

}

printf("\n");

}

 

int main()

{

int m_e[2][2]={{0x02,0x1},{0x01,0x02}};

int m_d[2][2]={{0x07,0x0f},{0x0f,0x07}};

int sub_e[16]={10,4,3,11,8,14,2,12,5,7,6,15,0,1,9,13};

int sub_d[16]={12,13,6,2,1,8,10,9,4,14,0,3,7,15,5,11};

int key[2][2]={{0x2,0x8},{0xa,0x9}};

int size=256,delta[2][2];

int*** P=new int**[size];

    for(int i=0;i<size;i++)P[i]=new int*[2];

for(int i=0;i<size;i++)

        for(int j=0;j<2;j++) P[i][j]=new int[2];

for(int i(0);i<size;i++)

for(int j(0);j<2;j++)

for(int z(0);z<2;z++)

P[ i ][ j ][ z ]=0;

int*** Q=new int**[size];

    for(int i=0;i<size;i++)Q[i]=new int*[2];

for(int i=0;i<size;i++)

        for(int j=0;j<2;j++) Q[i][j]=new int[2];

 

for(int i(0);i<size;i++)

{

P[i][0][0]=i%16;

P[i][1][1]=(i/16)%16;

}

 

for(int i(0);i<size;i++)

for(int j(0);j<2;j++)

for(int z(0);z<2;z++)

Q[i][j][z]=P[i][j][z];

for(int i(0);i<size;i++)

encrypt_R(Q[i],key,sub_e,m_e);

for(int i(0);i<2;i++)

for(int j(0);j<2;j++)

delta[i][j]=0;

delta[0][0]=11;

delta[1][1]=0;

printf("\n-------------------------------------------------------------\n");

printf("\ndelta2:\n");

for(int i(0);i<size;i++)

for(int x(0);x<2;x++)

for(int j(0);j<2;j++)

Q[i][x][j]^=delta[x][j];

for(int i(0);i<size;i++)

decrypt_R(Q[i],key,sub_d,m_d);

int r[2][2],r1[2][2],count;

for(int w(0);w<size;w++)

for(int i(1);i<size;i++)

{ 

if(w!=i)

{

count=0;

for(int z(0);z<2;z++)

for(int j(0);j<2;j++)

{

r[z][j]=P[w][z][j]^P[i][z][j];

r1[z][j]=Q[w][z][j]^Q[i][z][j];

if(r[z][j]==r1[z][j])

count++;

}

 

if(count==4)

{

printf("\n-------------------------------------------------------------\n");

printf("\ndelta2:\n");

for(int j=0;j<2;j++)

{

for(int i=0;i<2;i++)

printf("%x\t",delta[j][i]);

printf("\n");

}

printf("\nP1=\n");

print(P[w]);

printf("\nP2=\n");

print(P[i]);

printf("\nQ1=\n");

print(Q[w]);

printf("\nQ2=\n");

print(Q[i]);

printf("\nXOR=\n");

for(int j=0;j<2;j++)

{

for(int i=0;i<2;i++)

{

printf("%x\t",r[j][i]);

}

printf("\n");

}

printf("\n-------------------------------------------------------------\n");

break;

}

}

}

}