Дипломная работа на тему "Интегральная атака против блочного симметричного шифра Crypton"

ГлавнаяИнформатика → Интегральная атака против блочного симметричного шифра Crypton




Не нашли то, что вам нужно?
Посмотрите вашу тему в базе готовых дипломных и курсовых работ:

(Результаты откроются в новом окне)

Текст дипломной работы "Интегральная атака против блочного симметричного шифра Crypton":


ВВЕДЕНИЕ

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

Именно поэтому ужесточаются требования к информационной безопасности. Под ней понимается защищенность информации и поддерживающей инфраструктуры от случайных и преднамеренных воздействий, которые могут нанести ущерб владельцам или пользователям информации. Обеспечение безопасности информационной системы является одной из важнейших задач при эксплуатации данной системы, так как от сохранения конфиденциальности, целостности и доступности информационных ресурсов во многом зависит быстрота принятия решений, эффективность и надежность работы . Разработка и анализ блочных шифров, является очень актуальной и необходимой задачей, которая должна быть реализована на государственном уровне, поскольку от этого зависит государственная безопасность Украины. Украине необходимо иметь свой БСШ.

Одним из основополагающих элементов в общем комплексе средств и методов обеспечения информационной безопасности являются криптографические методы защиты информации[2]. На данном этапе развития применяется как симметричные, так и несимметричные криптографические методы защиты. Это обуславливается тем, что первые способны обеспечить высокую скорость шифрования, а вторые – модель взаимного недоверия и защиты, т.е. ситуацию, когда пользователи информационных систем не хотят никому доверять свои личные ключи и параметры, но при этом хотят иметь гарантию компенсации потерь, если их обманут.

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

Одним из наиболее эффективных, на сегодняшний день, является интегральный метод криптоанализа.

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

Для достижения этой цели необходимо решить следующие задачи:

- Изучить методику применения интегральной атаки против блочного симметричного шифра Crypton.

- Адаптировать методику применения интегральной атаки для использования против усеченного варианта блочного симметричного шифра Crypton.

- Выполнить программную реализацию интегральной атаки против усеченного варианта блочного симметричного шифра Crypton.

В данной дипломной работе рассчитывается экономическая эффективность разработки методики определения стойкости блочного симметричного шифра Сrypton против интегральной атаки.

В разделе "Безопасность жизнедеятельности" дипломного проекта необходимо разработать вопросы БЖД при выполнении работ по разработке интегральной атаки на шифр Crypton, которые выполняются в научно-исследовательской лаборатории (НИЛ). В разделе следует выполнить анализ условий труда, разработать вопросы техники безопасности, производственной санитарии и гигиены труда, пожарной профилактики.


1. БЛОЧНЫЕ СИММЕТРИЧНЫЕ ШИФРЫ И ИХ МЕСТО В СОВРЕМЕННЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ

1.1 Основные требования к БСШ как к механизму обеспечивающему конфиденциальность

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

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

Z=EnCrypt(X,Key) и X=DeCrypt(Z,Key)[3]

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

Блочные шифры являются основой, на которой реализованы практически все криптосистемы[4]. Методика создания цепочек из зашифрованных блочными алгоритмами байт позволяет шифровать ими пакеты информации неограниченной длины. Такое свойство блочных шифров, как быстрота работы, используется асимметричными криптоалгоритмами, медлительными по своей природе. Отсутствие статистической корреляции между битами выходного потока блочного шифра используется для вычисления контрольных сумм пакетов данных и в хешировании паролей.

Стойкость криптоалгоритмов описана в [5], [6]. Криптоалгоритм именуется идеально стойким, если прочесть зашифрованный блок данных можно только перебрав все возможные ключи, до тех пор, пока сообщение не окажется осмысленным. Так как по теории вероятности искомый ключ будет найден с вероятностью 1/2 после перебора половины всех ключей, то на взлом идеально стойкого криптоалгоритма с ключом длины N потребуется в среднем 2N-1 проверок. Таким образом, в общем случае стойкость блочного шифра зависит только от длины ключа и возрастает экспоненциально с ее ростом. Даже предположив, что перебор ключей производится на специально созданной многопроцессорной системе, в которой благодаря диагональному параллелизму на проверку 1 ключа уходит только 1 такт, то на взлом 128 битного ключа современной технике потребуется не менее 1021 лет. Естественно, все сказанное относится только к идеально стойким шифрам, которыми, например, с большой долей уверенности являются приведенные в таблице выше алгоритмы.

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

Таким образом, на функцию стойкого блочного шифра Z=EnCrypt(X,Key) накладываются следующие условия:

- функция EnCrypt должна быть обратимой.

- не должно существовать иных методов прочтения сообщения X по известному блоку Z, кроме как полным перебором ключей Key.

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

Давайте рассмотрим методы, с помощью которых разработчики блочных криптоалгоритмов добиваются одновременного выполнения этих трех условий с очень большой долей достоверности. Все действия, производимые над данными блочным криптоалгоритмом, основаны на том факте, что преобразуемый блок может быть представлен в виде целого неотрицательного числа из диапазона, соответствующего его разрядности. Так, например, 32-битный блок данных можно интерпретировать как число из диапазона 0..4'294'967'295. Кроме того, блок, разрядность которого обычно является "степенью двойки", можно трактовать как несколько независимых неотрицательных чисел из меньшего диапазона (рассмотренный выше 32-битный блок можно также представить в виде 2 независимых чисел из диапазона 0..65535 или в виде 4 независимых чисел из диапазона 0..255). Над этими числами блочным криптоалгоритмом и производятся по определенной схеме показаной на Таб 1.1 (слева даны условные обозначения этих операций на графических схемах алгоритмов):

В качестве параметра V для любого из этих преобразований может использоваться:

- фиксированное число (например, X'=X+125)

- число, получаемое из ключа (например, X'=X+F(Key))

- число, получаемое из независимой части блока (например, X2'=X2+F(X1))


Рисунок убран из работы и доступен только в оригинальном файле.

Таблица 1.1 Условные обозначения операций на графических схемах алгоритмов.

Последний вариант используется в схеме, названной по имени ее создателя сетью Фейстеля (нем. Feistel).

Последовательность выполняемых над блоком операций, комбинации перечисленных выше вариантов V и сами функции F и составляют "ноу-хау" каждого конкретного блочного криптоалгоритма. Размер блоков и длина ключа современных (1999 год) алгоритмов были нами рассмотрены ранее. Один-два раза в год исследовательские центры мира публикуют очередной блочный шифр, который под яростной атакой криптоаналитиков либо приобретает за несколько лет статус стойкого криптоалгоритма, либо (что происходит неизмеримо чаще) бесславно уходит в историю криптографии.

Характерным признаком блочных алгоритмов является многократное и косвенное использование материала ключа. Это диктуется в первую очередь требованием невозможности обратного декодирования в отношении ключа при известных исходном и зашифрованном текстах. Для решения этой задачи в приведенных выше преобразованиях чаще всего используется не само значение ключа или его части, а некоторая, иногда необратимая (небиективная) функция от материала ключа. Более того, в подобных преобразованиях один и тот же блок или элемент ключа используется многократно. Это позволяет при выполнении условия обратимости функции относительно величины X сделать функцию необратимой относительно ключа Key.

Поскольку операция зашифровки или расшифровки отдельного блока в процессе кодирования пакета информации выполняется многократно (иногда до сотен тысяч раз), а значение ключа и, следовательно, функций Vi(Key) остается неизменным, то иногда становится целесообразно заранее однократно вычислить данные значения и хранить их в оперативной памяти совместно с ключом. Поскольку эти значения зависят только от ключа, то оин в криптографии называются материалом ключа. Необходимо отметить, что данная операция никоим образом не изменяет ни длину ключа, ни криптостойкость алгоритма в целом. Здесь происходит лишь оптимизация скорости вычислений путем кеширования (англ. caching) промежуточных результатов. Описанные действия встречаются практически во многих блочных криптоалгоритмах и носят название расширение ключа (англ. key scheduling)


1.2 Обзор известных БСШ

1.2.1 Анализ симметричного блочного шифра Rijndael

Шифр реализует совершенно нетрадиционную криптографическую парадигму, полностью отказавшись от сети Фейстела[7],[8]. К достоинствам алгоритма относят: очень хорошее быстродействие на всех платформах от 8-битных до 64-битных, самый высокий потенциальный параллелизм среди претендентов, минимальные требования к ресурсам оперативной и постоянной памяти в реализации без кеширования некоторых операций, устойчивость к подавляющему большинству атак по времени исполнения и потребляемой мощности, структура шифра позволяет использовать любые комбинации размеров блока и длин ключа, кратные 32 бит (при достижении размером блока определенных границ требуется только увеличение числа раундов). При этом процедуры шифрования/дешифрования и операции расширения ключей различаются между собой достаточно сильно по сравнению с простым изменением порядка ключей либо операцией наложения, характерных для сети Фейстела, что увеличивает суммарный объем кода алгоритма.

Как показали предварительные исследования [9],[10], Rijndael может быть очень эффективно реализован на самых разных процессорах и чрезвычайно успешно противостоит известным криптоаналитическим атакам.

Rijndael представляет собой итеративный блочный шифр, имеющий переменную длину блоков и различные длины ключей. Длина ключа и длина блока могут быть независимо друг от друга 128, 192 или 256 бит.

Разнообразные преобразования работают с промежуточным результатом, называемым Состоянием (State).

Состояние можно представить в виде прямоугольного массива байтов. Этот массив имеет 4 строки, а число столбцов обозначено как Nb и равно длине блока, деленной на 32.

Ключ шифрования также представлен в виде прямоугольного массива с четырьмя строками. Число столбцов обозначено как Nk и равно длине ключа, деленной на 32. Это показано на рисунке 1.4.

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок 1.4. Пример представления Состояния (Nb=6) и Ключа шифрования (Nk=4).

В некоторых случаях ключ шифрования показан как линейный массив 4-байтовых слов. Слова состоят из 4 байтов, которые находятся в одном столбце (при представлении в виде прямоугольного массива) как показано на рисунке 1.4 взятый с [11].

Входные данные для шифра ("открытый текст", если используется режим шифрования ECB) обозначаются как байты состояния в порядке a0,0, a1,0, a3,0, a0,1, a1,1, a3,1 ,a4,1 ... После завершения действия шифра выходные данные получаются из байтов состояния в том же порядке.

Число циклов обозначено как Nr и зависит от значений Nb и Nk. Оно приведено в Таблице 1.2

Рисунок убран из работы и доступен только в оригинальном файле.

Таблица 1.2 Число циклов (Nr) как функция от длины ключа и длины блока.


Цикловое преобразование состоит из четырех различных преобразований. На псевдо-Си это выглядит следующим образом:

Round (State, RoundKey)

{

ByteSub(State); // замена байт

ShiftRow(State); // сдвиг строк

MixColumn(State); // замешивание столбцов

AddRoundKey(State, RoundKey); // добавление циклового ключа

}

Последний цикл шифра немного отличается. Вот как он выглядит:

FinalRound(State, RoundKey)

{

ByteSub(State); // замена байт

ShiftRow(State); // сдвиг строк

AddRoundKey(State, RoundKey); // добавление циклового ключа

}

В приведенной записи, "функции" - Round, ByteSub и т.д. выполняют свои действия над массивами, указатели (т.е. State, RoundKey) на которые им передаются.

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

Преобразование ByteSub представляет собой нелинейную замену байт, выполняемую независимо с каждым байтом состояния. Таблицы замены (или S-блоки) являются инвертируемыми и построены из композиции двух преобразований:

1. Первое - получение обратного элемента относительно умножения в поле GF(28), '00' переходит сам в себя.

2. Применение афинного преобразования (над GF(2)), определенного как:

Рисунок убран из работы и доступен только в оригинальном файле.

Табл. 1.3. Таблицы замены

Применение описанного S-блока ко всем байтам состояния обозначено как ByteSub(State). Рисунок 1.5 иллюстрирует применение преобразования ByteSub к состоянию.

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок 1.5 ByteSub действует на каждый байт состояния.

Последние 3 строки состояния циклически сдвигаются на различное число байт. Строка 1 сдвигается на С1 байт, строка 2 - на С2 байт и строка 3 - на С3 байт. Значения сдвигов С1, С2 и С3 зависят от длины блока Nb. Их величины приведены в таблице 1.4.


Таблица 1.4. Величина сдвига для разной длины блоков.

Рисунок убран из работы и доступен только в оригинальном файле.

Операция сдвига последних 3 строк состояния на определенную величину обозначена как ShiftRow(State). Рисунок 1.5 показывает влияние преобразования на состояние.

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок 1.5 ShiftRow действует на строки состояния.

В преобразовании замешивания столбцов (MixColumn) столбцы состояния рассматриваются как многочлены над GF(28) и умножаются по модулю x4+1 на многочлен c(x), выглядящий следующим образом:

c(x)='03' x3 + '01' x2 + '01' x + '02'(1.8)

Это может быть представлено в виде матричного умножения. Пусть b(x)=c(x)a(x),

Табл. 1.6 Матричное умножение

Рисунок убран из работы и доступен только в оригинальном файле.


Применение этой операции ко всем четырем столбцам состояния обозначено как MixColumn(State). Рисунок 1.7 демонстрирует применение MixColumn к состоянию.

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок 1.7 MixColumn действует на столбцы состояния.

В следующей операции цикловой ключ добавляется к состоянию посредством простого EXOR. Цикловой ключ вырабатывается из ключа шифрования посредством алгоритма выработки ключей (key schedule). Длина циклового ключа равна длине блока Nb.

Преобразование, содержащее добавление посредством EXOR циклового ключа к состоянию, обозначено как AddRoundKey(State, RoundKey). Оно проиллюстрированно на рисунке 1.8.

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок 1.8. Добавление ключа

При добавлении ключа цикловой ключ складывается посредством EXOR с состоянием.

Цикловые ключи получаются из ключа шифрования посредством алгоритма выработки ключей. Он содержит два компонента: расширение ключа (Key Expansion) и выбор циклового ключа (Round Key Selection).

Основополагающие принципы алгоритма выглядят следующим образом:

- общее число бит цикловых ключей равно длине блока, умноженной на число циклов плюс 1 (например, для длины блока 128 бит и 10 циклов требуется 1408 бит циклового ключа).

- ключ шифрования расширяется в Расширенный Ключ (Expanded Key).

- цикловые ключи берутся из Расширенного ключа следующим образом: первый цикловой ключ содержит первые Nb слов, второй - следующие Nb слов и т.д.

Расширенный ключ представляет собой линейный массив 4-ех байтовых слов и обозначен как W[Nb*(Nr+1)]. Первые Nk слов содержат ключ шифрования.

Все остальные слова определяются рекурсивно из слов с меньшими индексами. Алгоритм выработки ключей зависит от величины Nk: ниже приведена версия для Nk равного или меньшего 6 и версия для Nk большего 6.

Для Nk<6 или Nk=6 мы имеем:

KeyExpansion(CipherKey,W)

{

for (i = 0; i < Nk; i++) W[i] = CipherKey[i];

for (j = Nk; j < Nb*(Nk+1); j+=Nk)

{

W[j] = W[j-Nk] ^ SubByte( Rotl( W[j-1] ) ) ^ Rcon[j/Nk];

for (i = 1; i < Nk && i+j < Nb*(Nr+1); i++)

W[i+j] = W[i+j-Nk] ^ W[i+j-1];

}

}


Как можно заметить, первые Nk слов заполняются ключом шифрования. Каждое последующее слово W[i] получается посредством EXOR предыдущего слова W[i-1] и слова на Nk позиций ранее W[i-Nk]. Для слов, позиция которых кратна Nk, перед EXOR применяется преобразование к W[i-1], а затем еще прибавляется цикловая константа. Преобразование содержит циклический сдвиг байтов в слове, обозначенный как Rotl, затем следует SubByte - применение замены байт.

Для Nk>6 мы имеем:

KeyExpansion(CipherKey,W)

{

for (i=0; i<Nk; i++) W[i]=CipherKey[i];

for (j=Nk; j<Nb*(Nk+1); j+=Nk)

{

W[j] = W[j-Nk] ^ SubByte(Rotl(W[j-1])) ^ Rcon[j/Nk];

for (i=1; i<4; i++) W[i+j] = W[i+j-Nk] ^ W[i+j-1];

W[j+4] = W[j+4-Nk] ^ SubByte(W[j+3]);

for (i=5; i<Nk; i++) W[i+j] = W[i+j-Nk] ^ W[i+j-1];

}

}

Отличие для схемы при Nk>6 состоит в применении SubByte для каждого 4-го байта из Nk.

Цикловая константа независит от Nk и определяется следующим образом:

Rcon[i] = ( RC[i], '00' , '00' , '00' ),


Где RC[0]='01', RC[i]=xtime(Rcon[i-1])

i-ый цикловой ключ получается из слов массива циклового ключа от W[Nb*i] и доW[Nb(i+1)]. Это показано на рисунке 1.9

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок 1.9 Расширение ключа и выбор циклового ключа для Nb=6 и Nk=4.

Алгоритм выработки ключей можно осуществлять и без использования массива W[Nb*(Nr+1)]. Для реализаций, в которых существенно требование к занимаемой памяти, цикловые ключи могут вычисляться на лету посредством использования буфера из Nk слов. Шифр Rijndael состоит из:

- Начального добавления циклового ключа;

- Nr-1 циклов;

- заключительного цикла.

На псевдо-Си это выглядит следующим образом:

Rijndael (State, CipherKey)

{

KeyExpansion(CipherKey, ExpandedKey); // Расширение ключа

AddRoundKey(State, ExpandedKey); // Добавление циклового ключа

For ( i=1 ; i<Nr ; i++) Round(State,ExpandedKey+Nb*i); // циклы

FinalRound(State, ExpandedKey+Nb*Nr); // заключительный цикл

}


Если предварительно выполнена процедура расширения ключа, то Rijndael будет выглядеть следующим образом:

Rijndael (State, CipherKey)

{

AddRoundKey(State, ExpandedKey);

For ( i=1 ; i<Nr ; i++) Round(State,ExpandedKey+Nb*i);

FinalRound(State, ExpandedKey+Nb*Nr);

}

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

1.2.2 Анализ симметричного блочного шифра DEAL

DEAL (Data Encryption Algorithm with Larger blocks - Алгоритм Шифрования Данных с Укрупненными блоками) является 128-и битным блочным шифром с размерами ключа 128, 192 и 256 бит, что далее здесь будет обозначаться DEAL-128, DEAL-192 и DEAL-256 соответственно [12]. Все версии могут использоваться в любом из четырех стандартных режимах DES'a. Мы начнем с описания работы DEAL в режиме ECB. Пусть С = ЕВ(А) означает зашифрованное DES значение 64-х битного А на ключе В, и пусть Y = EAZ(X) означает зашифрование DEAL 128-и битного X на ключе Z. Открытый текст Р разделяется на блоки Pi по 128 бит каждый, P = P1, P2, …, Рn. Расписание ключей принимает ключ К и возвращает r ключей DES RKi, где i = 1, … , r, как описано ниже. Обозначим XL и XR левую и правую части X соответственно. Шифр-текст вычисляется следующим образом. Положим X0L = PiL, X0R = РiR и вычислим для j= 1, … ,r


XjL=ERKj(XLj-1) XRj-1  (1.9)

XRj = XLj-1(1.10)

Рисунок убран из работы и доступен только в оригинальном файле.

Рисунок 1.10: Один цикл DEAL.

Положим Ci =XrL ||XrR. На рис. 1.10 показан один цикл DEAL. Для DEAL-128 и DEAL-192 мы предлагаем использовать 6 циклов, т. е. r = 6. Однако, как мы увидим ниже, этого может быть недостаточно для DEAL-256, здесь предлагается использовать 8 циклов, r = 8. Представляется, что версия с размером ключа 256 бит используется только когда требуется особенно сильное зашифрование.

Заметим, что последнем цикле DEAL половины блока местами меняются[13]. Причина в следующем: правая часть шифр-текста Сi не шифруется в последнем цикле i-oro зашифрования, и только левая часть входа i + 1-ого зашифрования (который равен Ci  Pi+l) шифруется на последнем цикле. Т. о. правая часть Ci осталась бы не перезашифрованной два цикла. Это может дать поле деятельности злоумышленникам, тем более, что шифр состоит всего из 6-и или 8-и циклов. Заметим, что аналогичное свойство есть и у DES в режиме CBC. Правда, похоже это труднее было бы использовать, ведь у DES 16 циклов. Позволим себе отметить, что обмен местами правой и левой частей на последнем цикле не влияет на стойкость блочного шифра в режиме ECB [14].

Итак, обозначим блоки открытого текста по 128 бит P1, P2, …, Pn и Ci, С2, ,… , Сп -соответствующие им блоки шифр-текста. Тогда:

Сi = EAK(Ci-l Pi),(1.11)

где С0 - начальное значение.

В DES начальная перестановка IP первой применяется к открытому тексту, и аналогично перед выходом шифр-текст пропускается через обратную к ней IP-1. Возможно увеличить скорость DEAL, если убрать из используемого DES эти начальную и конечную перестановки. Легко показать, что для получения корректной реализации DEAL, IP должна быть приложена к обоим частям открытого текста перед зашифрованием, a IP-1 - к обоим частям шифр-текста.

На вход расписания ключей подается s ключей DES, Ki, ,… , Ks, для s = 2, 3, 4, каждый по 64 бит (включая 8 проверочных бит, старших бит каждого байта), на выходе получается r ключей DES, RKj. Мы используем общий метод, приложимый ко всем трем размерам ключа. Во-первых расширяем s ключей до r ключей, путем повторения и с новой константой для каждого нового повторения. Зашифровываем расширенный список ключей DES'om в режиме CBC с фиксированным ключом и нулевым начальным значением. Из полученных блоков шифр-текста и формируются подключи RKi. Далее мы приводим точные определения каждого из расписаний ключей, здесь К = 0x1234 5678 90ab cdefx (шестнадцатеричное число) - фиксированный ключ DES. В DEAL-128 подключи генерируются следующим образом:

RK1 = EK1),

RK2 = EK2  RK1),

RK3=EK(Kl (1) RK2),

RK4 = EK2  (2) RK3),

RK5 =Ek(ki (4) RK4),

RK6 =Ek(k2 (8) RK5),(1.12)

где (i) - 64-х битное целое число, в котором i - 1-ый бит (индексация идет с 0) установлен, а остальные очищены. Например, (1) может быть представлено как шестнадцатеричное "0x8000 0000 0000 0000х".

В DEAL-192 подключи генерируются следующим образом:

RK1 = EK1),

RK2 = EK2 RK1),

RK3=EK(K3 RK2),  

RK4 =Ek(ki (1) RK3),

RK5 =Ek(k2 (2) RK4),

RK6К3  (4) RK5).(1.13)

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

В DEAL-256 подключи генерируются следующим образом:

RK1 = EK1),

RK2=EK2RK1),

RK3=EK(K3RK2),

RK4=Ek(K4 RK3),

RK5 =Ek(K2 (1) RK4),

RK6=EK2  (2) RK5),

RK7К3  (4) RK6),  RK8 =Ek(K4 (8) RK7).(1.14)


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

Заметим, что для всех версий расписания ключей 64-х битные величины RKi используются как ключи DES, поэтому биты проверки четности RKi не используются в i-ом цикле. Однако, все 64 бита RKi, как выхода шифрования на ключе К, используются при генерации следующего подключа.

Принципы разработки расписания ключей, во-первых, состоят в том, чтобы подключи зависели от наибольшего числа битов основного ключа, но не требовали при этом много работы, во-вторых, при вводе s основных ключей размером по 64 бит, любые s последовательных подключей должны иметь энтропию s · 56 бит, и, наконец, не должно быть очевидно зависимых и слабых ключей и не должно остаться свойство дополнительности. Заметим, что последние две проблемы присутствуют и в DES, и -все три - в тройном DES. Мы заметили, что если основные ключи размером по 64 бита каждый, может найтись пара ключей, генерирующих одинаковые множества подключей. Однако, число таких ключей, похоже, настолько невелико, что не представляет угрозы DEAL'y, применяемому для шифрования.

Смещения (i) введены для предотвращения появления слабых ключей. Если бы их не было, существовали бы ключи, для которых все подключи были равны. Например, для DEAL-128 ключи K1 = K2 = Dk(0) сгенерировали бы 6 подключей со значением 0. Смещения и шифрование на фиксированном ключе предотвращают появление слабых и зависимых ключей и свойства дополнительности.

Заметим, что если бит проверки четности используется в каждом байте основного ключа, действующие размеры предложенных ключей составляют 112, 168 и 224 бит соответственно.

Что можно сказать о стойкости DEAL в целом? Прежде всего, заметим[15], что для DEAL простая атака meet-in-the-middle (встретить по середине), аналогичная такой атаке на двойной DES, отыщет ключи за время порядка 2168 зашифрований для шести, и 2224 зашифрований для восьми циклов DEAL соответственно, независимо от расписания ключей. Именно поэтому, предлагается в DEAL-256 производить по крайней мере 8 циклов зашифрования. Для DEAL-128 исчерпывающий поиск ключа займет время порядка 2112 зашифрований.

Самая быстрая из известных атак по нахождению ключа на DEAL (с шестью циклами) - общая атака на 6-и цикловые Фейстелевы шифры, в приложении к DEAL, она требует порядка 2121 зашифрований DES, используя порядка 270 выбранных открытых текстов, для любого расписания ключей. В дальнейшем определим разность между двумя последовательностями бит, как побитное XOR.

В конце этого раздела подведем итог особенностям DEAL.

-DEAL имеет размер блока 128 бит и размер ключа 128, 192 или 256бит (действующий размер, соответственно, - 112, 168 или 224 бита).

- атака по подобранному шифр-тексту требует порядка 264 блоков шифр-текста.

- нет известных, вероятных атак.

- DEAL с шестью циклами имеет скорость, аналогичную скорости тройного DES.

- DEAL может использоваться в стандартных режимах работы.

- DEAL может быть реализован на имеющемся аппаратном и программном обеспечение DES.

- нет очевидно слабых ключей и устранено свойство дополнительности.

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

Собственно результаты стойкости DEAL:

- Существуют эквивалентные ключи для DEAL-192 и DEAL-256.

Алгоритм нахождения требует около шести шифрований DES, чтобы найти набор из 256 эквивалентных ключей для DEAL-192, и восемь шифрований DES, чтобы найти 256 эквивалентных ключей для DEAL-256.

- Существуют эквивалентные ключи для DEAL-128 и алгоритм их нахождения, требующий около 264 вычислений для нахождения пары эквивалентных ключей.

- Атака математически-связанных ключей (related-key attack) на DEAL-192 и DEAL-256, требующая три блока открытого текста, под 233 ключами с точным соответствием, 3*245 байт памяти и около 2137 шифрований DEAL, чтобы найти последние два цикловых подключа для DEAL-192 и DEAL-256. (С большим количеством памяти это можно сделать быстрее).

- несколько возможных расширений этих атак. DEAL-192 может быть дешифрован до четырех циклов, а затем может быть применена атака Бихама (Biham's) на четырехцикловый цепной DES; DEAL-256 может быть дешифрован до шести циклов, а затем может быть применена атака на шестицикловый DEAL-192 подробнее эта операция описана [15].

Эти результаты интересны как для практики, так и для теории. Похоже, что DEAL будет иметь некоторое применение в будущем. DEAL кандидат на AES, но даже если он не станет финалистом, он почти наверняка будет использоваться. Как было указано на первой конференции по AES, широкое распространение "железа под DES" делает DEAL относительно легким для реализации во многих устройствах за очень низкую цену.

В реальном применении эквивалентные ключи DEAL имеют важное практическое следствие - они делают многие стандартные методы хэширования ненадежными.

Атака основанная на математически зависимых ключах вероятно менее применима, но все ещё может быть важна для некоторых приложений эти атаки "снимают" два последних цикла DEAL ценой примерно 2137 шифрований DEAL, используя 3*245 байт памяти и требует все те же три блока открытого текста, зашифрованного 233 зависимыми ключами. Возможны компромиссы времени-памяти.

В настоящее время, имея 3*269 байт памяти, атака будет занимать 2113 вычислительных ресурсов, восстанавливая два последних подключа. После, можно реализовать атака Бихама (Bi ham's) на четырехцикловый цепной DES, которая требует ещё 233 блока открытого текста, зашифрованного только одним ключом, и 288 времени. Таким образом, вся атака займет приблизительно 2113 вычислительной работы, 3*269 байт памяти, все те же три блока открытого текста, зашифрованного 233 зависимыми ключами, ещё 232 блока открытого текста, зашифрованного только одним ключом, которые должны быть выбраны ПОСЛЕ завершения первой атаки. По сравнению с лучшей из ранее известных атак, требующей 2119 вычислительной работы, 264 памяти и 270 выбранных открытых текстов.

На теоретическом уровне эти результаты показывают важный факт: Широко считается, что "назначение ключей" (key shedule), которое использует сильные элементы криптографии будет практически неуязвимо к криптографическому анализу. Это утверждение, к сожалению, не верно. В DEAL используется сильный шифр в очевидно-разумном направлении, чтобы обрабатывать ключ. Однако, использованный метод оставляет уязвимость шифра к анализу зависимого ключа, также оставляет возможность эквивалентных ключей.

1.3 Crypton как перспективный алгоритм

Шифр Crypton представлен южнокорейской компанией Future Systems, с конца 1980-х годов работающей на рынке сетевого обеспечения и защиты информации. Автор алгоритма Че Хун Лим [15],[16] признает, что конструкция его шифра во многом опирается на идеи шифра SQUARE бельгийских криптографов Дамена и Рэмена (также участвующих в конкурсе). Здесь нет традиционной для многих блочных шифров "структуры Фейстела", оперирующей в каждом цикле шифрования половиной блока данных (например, как в DES или CAST). Основу данного шифра составляет другая стандартная конструкция - так называемая SP-сеть, т.е. повторяющаяся цикловая функция из замен-перестановок, ориентированная на распараллеленную нелинейную обработку всего блока данных. Помимо высокой скорости, к преимуществам такой конструкции относят и то, что она облегчает исследование стойкости шифра к методам дифференциального и линейного криптоанализа, являющимся на сегодня основными инструментами вскрытия блочных шифров.

Шифр Crypton, как и Square, эффективно реализуется на разнообразных платформах, и признано, что в корейском алгоритме присутствуют талантливые конструктивные идеи.

1.3.1 Алгоритм CRYPTON

Описание алгоритма было взято из книги автора шифра CRYPTON Че Хун Лим [16] В CRYPTON, каждый блок данных 128 бит представлен в форме массива 4´4 байта. Циклическое преобразование в CRYPTON состоит из четырех шагов: byte-wise substitutions(байт замена), column-wise bit permutation(колончастый способ перестановки битов), column-to-row transposition (перенос столбцов), и key addition(добавление ключа). Процесс кодирования состоит из 4 раундов таких циклических преобразований. Процесс расшифровки может быть сделан идентичным процессу кодирования с различным ключевым списком. На рисунке 1.1 показана структура CRYPTON.


Рисунок убран из работы и доступен только в оригинальном файле.

Рис.1.1 Структура CRYPTON.

Блочный шифр CRYPTON имеет следующие характеристики:

- 12-раундовый самозаменяемый шифр (с одинаковыми процессами для кодирования и расшифрования) с длиной блока 128 битов и длинной ключа до 256 битов.

- хорошая стойкость от существующих атак.

- эффективен и на программном и на аппаратном уровне: благодаря высокой степени паралельности и использованию очень простых логических операций ANDS/XORS, CRYPTON запускается очень быстро на большинстве платформ как в программном обеспечении так и в аппаратных средствах.

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


1.3.2 Основные преобразования блока

1.3.2.1 Байтовая подстановка g

CRYPTON использует нелинейную замену байта, используя четыре 8´8 S-блока, Si(0 ≤i ≤3). Эти S-блоки получены из одного 8´8 S-блока при возведении в степень S (то есть, S = S-1) и удовлетворяют обратные отношения S2=S0-1 и S3=S1-1. Возведенный в степень S-блок S был, сформирован для более эффективной логической реализации.

Преобразование  S-блока состоит из замен байт относительно массива 4´4 байт. Два различных преобразования используются альтернативно в последовательных раундах: в нечетных раундах и e в нечетных раундах. Это показано на рисунке 1.2. Заметим, что эти четыре S-блока устроены так, что следующее закрепляются на любом 4´4 байте масива A:

go  (ge (A)) = ge (go (A)) = A. (1.1)

Это свойство используется, чтобы получить идентичный процесс для кодирования и расшифровки.

A[0] |
|

a03

|

a02

|

a01

|

a00

|
| B[0] | |

S3(a03)

|

S2(a02)

|

S1(a01)

|

S0(a00)

|
---------------------------------------------------------
A[1] | |

a13

|

a12

|

a11

|

a10

|

o

|
B[1]
|
|

S0(a13)

|

S3(a12)

|

S2(a11)

|

S1(a10)

|
---------------------------------------------------------
A[2] | |

a23

|

a22

|

a21

|

a20

|
Þ | B[2] | |

S1(a23)

|

S0(a22)

|

S3(a21)

|

S2(a20)

|
---------------------------------------------------------
A[3] | |

a33

|

a32

|

a31

|

a30

|
| B[3] | |

S2(a33)

|

S1(a32)

|

S0(a31)

|

S3(a30)

|
---------------------------------------------------------
| | | | | | | | | | | | |
---------------------------------------------------------
A[0] | |

a03

|

a02

|

a01

|

a00

|
| B[0] | |

S1(a03)

|

S0(a02)

|

S3(a01)

|

S2(a00)

|
---------------------------------------------------------
A[1] | |

a13

|

a12

|

a11

|

a10

|

e

|
B[1] | |

S2(a13)

|

S1(a12)

|

S0(a11)

|

S3(a10)

|
---------------------------------------------------------
A[2] | |

a23

|

a22

|

a21

|

a20

|
Þ | B[2] | |

S3(a23)

|

S2(a22)

|

S1(a21)

|

S0(a20)

|
---------------------------------------------------------
A[3] | |

a33

|

a32

|

a31

|

a30

|
| B[3] | |

S0(a33)

|

S3(a32)

|

S2(a31)

|

S1(a30)

|
--------------------------------------------------------- --------------------------------------------------
- - -
Дипломная работа на тему: "Интегральная атака против блочного симметричного шифра Crypton" опубликована на сайте http://rosdiplomnaya.com/

Здесь опубликована для ознакомления часть дипломной работы "Интегральная атака против блочного симметричного шифра Crypton". Эта работа найдена в открытых источниках Интернет. А это значит, что если попытаться её защитить, то она 100% не пройдёт проверку российских ВУЗов на плагиат и её не примет ваш руководитель дипломной работы!
Если у вас нет возможности самостоятельно написать дипломную - закажите её написание опытному автору»


Просмотров: 632

Другие дипломные работы по специальности "Информатика":

Web-сайт для учителей информатики: анализ существующих и разработка нового приложения

Смотреть работу >>

Поиск фотооборудования

Смотреть работу >>

Автоматизированная система складского учета в ЗАО "Белгородский бройлер"

Смотреть работу >>

Автоматизированная система учета договоров страхования предпринимательских рисков

Смотреть работу >>

Создание информационно-справочной системы "Методический кабинет"

Смотреть работу >>