C++ C++ C# C# ASP.NET Security ASP.NET Security ASM ASM Скачать Скачать Поиск Поиск Хостинг Хостинг  
  Программа для работы с LPT портом...
Язык: .NET — ©Alexey...
  "ASP.NET Atlas" – AJAX в исполнении Micro...
Язык: .NET — ©legigor@mail.ru...
  "Невытесняющая" Многопоточность...
Язык: C/C++ — ©...
  Update World C++: Сборник GPL QT исходников
  Весь сайт целиком можно загрузить по ссылкам из раздела Скачать

 DEAL – 128-и битный блочный шифр / Шифрование / Алгоритмы

DEAL – 128-и битный блочный шифр

 

Lars R. Knudsen

21 февраля 1998

 

Перевод с английского: Кочетков Н. Н.

октябрь 1998

 

Аннотация

 

Мы предлагаем новый блочный шифр, DEAL, основанный на DES (DEA). Размер блока DEAL – 128 бит, размер ключа может быть 128, 192 или 256 бит. Предлагаемый нами шифр имеет несколько преимуществ перед другими схемами: благодаря большему размеру блоков, проблема «атаки по подобранному шифр-тексту» становится менее существенной, а скорость шифрования соответствует скорости тройного DES. Мы предполагаем, что наиболее реалистичная (или наименее нереалистичная) атака на любую версию DEAL’а – это исчерпывающий поиск ключей. Мы предложили ANSI (институту) включить DEAL в стандарт ANSI X9.52. К тому же мы предлагаем DEAL, как кандидат на стандарт NIST AES.

 

1 Введение

DES (или DEA) [15] – блочный шифр с размером блока 64 бита и 64-х битным ключом, в котором эффективны 56 бит. Это – итеративный 16-и цикловой шифр, в нем шифр-текст вычисляется путем итеративного приложения цикловой функции к открытому тексту. DES имеет так называемую Фейстелеву структуру: в каждом цикле половина блока пропускается через нелинейную функцию, ее выход XOR’ится с другой половиной, после чего обе половины меняются местами.

Для современных приложений размер ключа DES стал слишком мал. Винер [20] показал, что сконструировать специализированное устройство, способное произвести исчерпывающий поиск ключа DES в среднем всего за 3.5 часа, будет стоить примерно 1 миллион US$. К тому же, недавно было показано, что и от программных атак ключ размером 56 бит не предоставляет значительной защиты – ключ DES был найден путем исчерпывающего поиска средствами распространенными по Internet’у.

Правда, на проблему недостаточного размера ключа указывали уже почти сразу после публикации DES [6]. Поэтому, часто DES используется по тройной схеме шифрования, называемой тройным DES’ом (Triple-DES) , где открытый текст трижды шифруется на трех независимых ключах. В другом варианте, называемом двухключевым тройным DES’ом, открытый текст сперва шифруется ключом К1, затем расшифровывается ключом К2 и, наконец, опять зашифровывается ключом К1 [18]. Однако, размер блока в 64 бита делает эти схемы уязвимыми к атаке по подобранному шифр-тексту, которая основана на том факте, что для большего числа режимов работы с DES [16] после зашифрования 233 блоков можно ожидать одинаковые блоки шифр-текста, это дает утечку информации об открытом тексте [5, 9, 13]. К тому же, тройной DES с тремя независимыми ключами уязвим к атаке по зависимому(?) ключу [7], время выполнения которой примерно такое же, как время исчерпывающего поиска ключа в простом DES.

Комиссия X9.F.1 Национального Американского Института Стандартов (ANSI) работает над принятием набора режимов тройного шифрования DES [21]. Один из этих режимов – с обратной связью по шифр-тексту (Triple DES Cipher Block Chaining – TCBC), где блоком для обратной связи является блок шифр-текста после 3-х зашифрований, – также называется внешним (outer-) CBC режимом. Однако, этот режим уязвим к атаке по подобранному шифр-тексту. Поэтому, предлагается использовать тройной DES в режиме с обратной связью по шифр-тексту с внутренней обратной связью, также называется внутренним (inner-) CBC режимом, где обратная связь осуществляется после каждого зашифрования одинарным DES’ом. Хотя этот режим менее уязвим к атаке по подобранному шифр-тексту, эффективная атака по открытию ключа может быть проведена за время много меньшее, чем можно было бы ожидать для схемы с тройным шифрованием [1].

Coupersmith, Jonson и Matyas [5, 4] предлагают для тройного DES’а режим CBC с OFB Masking (CBCM). Wagner [5] провел криптоанализ предложения, предшествовавшего данной разработке, где каждая из двух начальных величин может принимать только 220 значений. Режим CBCM не уязвим к атаке по подобранному шифр-тексту, и уровень защищенности предполагается 280. Неудобство предложенной схемы в том, что для зашифрования блока открытого текста размером 64 бита используется 4 зашифрования DES на трех различных ключах. Ранее Biham и Knudsen показали, что DES в режиме CBCM уязвим к атаке по выбранному шифр-тексту, в которой используется 265 блоков выбранного шифр-текста и сложностью которой по времени – 258 [2].

Мы предлагаем r-цикловой Фейстелев шифр, использующий DES в качестве цикловой функции. В результате получается шифр с размером блока 128 бит и r · 64 битами цикловых ключей, получаемых по алгоритму расписания ключей. Расписание ключей разработано так, что размер ключа может принимать одно из трех различных значений: 128, 192 или 256 бит. Мы рекомендуем при первых двух размерах ключа положить r = 6, а при размере ключа 256 бит r = 8. Ниже мы объясним, почему мы рекомендуем r ≥ 6. Если биты проверки четности каждого байта ключа не используются при шифровании, как это происходит в DES, действующие размеры ключей уменьшаются до 112-и, 168-и и 224-х бит соответственно. Исчерпывающий поиск ключа еще совершенно невозможен (см., например, обсуждение размеров ключей в [3]). К тому же, для успешной атаки по подобранному шифр-тексту необходимо ввести порядка 264 блоков шифр-текста. Скорость предложенного нами шифра такая же, как у тройного DES’а, если использовать 6 зашифрований для закрытия двух блоков открытого текста по 64 бита, более того, его можно применять с использованием существующих средств DES.

Национальный Институт Стандартов и Технологии (NIST) недавно объявил о намерении стандартизировать новый алгоритм шифрования, Advanced Encryption Standart, как замену DES [14]. Заявление NIST о том, что до того, как AES будет готов, пройдет несколько лет, и что они намерены признать «Тройной DES-алгоритм, раз он принят стандартом ANSI» [14], делает инициативу ANSI даже более важной.

 

2 DEAL

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

(1)

.

(2)

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


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

Работа режима CBC более подробно описана в [16]. Итак, обозначим блоки открытого текста по 128 бит P1, P2, … , Pn и С1, С2, … , Сn – соответствующие им блоки шифр-текста. Тогда:

,

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

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

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

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

,

,

,

,

,

,

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

 

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

,

,

,

,

,

.

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

 

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

,

,

,

,

,

,

,

.

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

 

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

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

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

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

Вышеописанная структура DEAL могла бы быть и другой – есть несколько возможных вариантов. Вместо Фейстелевой структуры можно использовать структуру MISTY, впервые описанную в [12], она позволяет в большей степени распараллелить вычисления (в аппаратном исполнении). Однако, эта структура разработана гораздо позже и еще не так глубоко проанализирована. Другой вариант – использовать DEAL в режиме «DES-X» [8], в котором дополнительный ключ XOR’ится с открытым текстом и с шифр-текстом. Или, вместо использования DES, как цикловой функции, можно использовать DES-X. Недостаток последних двух предложений в том, что потребуется генерировать большее число подключей, и, следовательно, расписание ключей DEAL станет сложнее.

 

2.1 Стойкость DEAL’а

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

Patarin в [17] показал, что для того, чтобы отличить 5-и или 6-и цикловой n-битный Фейстелев шифр со случайной цикловой функцией от истинно случайной 2n-битной перестановки, требуется знать по крайней мере 22n / 3 открытых текстов и соответствующих им шифр-текстов. Далее он предполагает, что требуется 2n пар. Если считать, что DES моделирует случайную перестановку[1], то, по предположению Patarin’а, требуется порядка 264 зашифрований, чтобы отличить DEAL от случайной перестановки; такова же и сложность атаки по подобранному шифр-тексту. Самая быстрая из известных атак по нахождению ключа на DEAL (с шестью циклами), которую мы сознаем, – общая атака на 6-и цикловые Фейстелевы шифры [10], в приложении к DEAL, она требует порядка 2121 зашифрований DES, используя порядка 270 выбранных открытых текстов, для любого расписания ключей. В дальнейшем определим разность между двумя последовательностями бит, как побитное XOR.

Утверждение 1: Существует атака на шестицикловый DEAL с независимыми цикловыми ключами, которая требует порядка 2121 зашифрований DES, используя порядка 270 выбранных открытых текстов.

Доказательство: Рассмотрим 5-и цикловую версию и пару открытых текстов с разностью α ≠ 0 в правых частях и равными левыми частями. Предположим, что шифр-тексты после 5-и циклов имеют разность α в левых частях и равные правые части. Это означает, что в обоих зашифрованиях на входах DES (в цикловой функции DEAL) были одинаковые значения на первом и на пятом циклах. Далее, разность на входах DES и на втором и на четвертом циклах была α. Но отсюда следует, что выходы DES в третьем цикле равны, стало быть, и входы DES на третьем цикле тоже равны. Это ведет к противоречию, т. к. это означает, что выходы DES на втором и на четвертом циклах равны, что невозможно, т. к. мы предположили, что они не равны. Таким образом предположение, что разность между шифр-текстами после 5-и циклов равна α в левых и 0 в правых частях, не верно. Другими словами, мы определили 5-и цикловой дифференциал с нулевой вероятностью. Это может быть использовано для атаки на DEAL.

Атака происходит следующим образом. Выберем 264 открытых текстов с фиксированными левыми и различными правыми частями, обозначим их  при i = 1, …, 264. Обозначим соответствующие им шифр-тексты . Вычислим  и найдем совпадения при ≠ j. Можно ожидать порядка 263 таких совпадений: . Положим . Для всех таких совпадающих пар и для всех значений ключа в шестом цикле расшифруем один цикл шифр-текстов. Если разности после 5-и циклов равны α и 0, предполагаемое значение ключа не верно. Заметим, что при правильном значении ключа такие разности после 5-и циклов появиться не могут, но при неправильном они будут появляться с вероятностью 2-64 для каждой анализируемой пары. Таким образом с 263 парами порядка половины ключей будут отброшены. При повторении атаки 56 раз останутся возможными только немногие значения ключа в шестом цикле. В общем, атака требует 56 ∙ 264 ≈ 270 выбранных открытых текстов, (256 + 255 + 254 + … + 2+ 1) ∙ 264 ≈ 257 ∙ 264 = 2121 зашифрований DES и 264 слов памяти.                                                                                                                                      

Вышеописанная атака, приложенная к DEAL-192 быстрее, чем исчерпывающий поиск ключа, хотя предпосылки весьма нереалистичные. Если атакующему удастся найти 264 или более пар открытых и шифр-текстов, может войти в игру атака по подобранному шифр-тексту, и в любом случае понадобится шифр с большим размером блока. Наиболее изученная атака на DEAL-128 – исчерпывающий поиск ключа – требует времени порядка 2112 зашифрований. Мы не нашли атаки на DEAL с восемью циклами лучшей, чем вышеописанный исчерпывающий поиск ключа «meet-in-the-middle». Может быть, существуют и более быстрые атаки, например, удачное обобщение вышеприведенной атаки на 6 циклов, но такого плана атаки потребуют нереальное количество выбранных открытых текстов и нереальный объем памяти.

Атака на 6 циклов объясняет наши рекомендации – использовать для DEAL r ≥ 6. При r ≤ 5 возможно указать дифференциалы с нулевой вероятностью. Это означает, что для некоторых разностях в парах открытого текста, некоторые другие разности невозможны в соответствующих парах шифр-текста. Прежде всего, такого свойства нет у некоторых современных блочных шифров, потом, такие дифференциалы могут быть использованы в атаках по вскрытию ключа со сложностью порядка 288 для DEAL только с 5-ю циклами [10]. (Заметим, что такая атака – только верхний предел уровня защищенности).

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

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

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

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

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

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

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

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

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

 

3 Заключение

Мы описали блочный шифр, DEAL, с размером блока 128 бит и размером ключа 128, 192 или 256 бит, как альтернативу существующим тройным режимам шифрования. DEAL может использоваться во всех четырех, разработанных для DES, стандартных режимах шифрования. Для первых двух размеров ключа схема шифрует два блока по 64 бита, используя шесть зашифрований DES, таким образом ее производительность равна производительности тройного DES. Производительность DEAL с восемью циклами (и размером ключа 256 бит) равна DES в режиме CBCM. Благодаря большим размерам блока и ключа, исчерпывающий поиск ключа и атака по подобранному шифр-тексту невыполнимы. К тому же, избегаются слабые места DES и тройного DES. Нет очевидно слабых ключей, не осталось свойства дополнительности, и успех атак по зависимому ключу весьма маловероятен. Мы рекомендовали ANSI принять DEAL, как часть [21]. Кроме того, мы предлагаем DEAL, как возможный кандидат на Advanced Encryption Standard [14].

 

4 Благодарности

Автор благодарен Don Coupersmith’y, Bart Preneel’y, Vincent Rijmen’y и Matthew Robshaw’y за множество значительных комментариев.

 

Ссылки

См. оригинал статьи на английском, раздел References.

 

 

 



[1] Заметим, что хотя наиболее изученная атака на DES – линейная атака Matsui [11] –, требует знания «всего» 243 открытых текстов, она требует, чтобы все эти открытые и шифр-тексты были известны, что не может предполагаться в приложении DES к DEAL.