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

RK1 = EK (К1),

RK2 = EK (К2  RK1),

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

RK4 = EK(К2  (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 = EK (К1),

RK2 = EK (К2 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 = EK (К1),

RK2=EK(К2RK1),

RK3=EK(K3RK2),

RK4=Ek(K4 RK3),

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

RK6=EK(К2  (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)

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

Страницы: 1, 2, 3, 4, 5