В криптографии , DEAL (Алгоритм Шифрования Данных с Крупными блоками — англ. Data Encryption Algorithm with Larger blocks ) — это блочный шифр , производный от DES . DEAL был впервые представлен Ларсом Кнудсеном в виде доклада на конференции Selected Areas in Cryptography в 1997 году . Впоследствии этот же алгоритм был представлен Ричардом Аутербриджем на конкурсе AES в 1998 году .

DEAL представляет собой сеть Фейстеля использующую DES как функцию в раунде сети. Удовлетворяя требованиям AES, DEAL имеет длину блока 128 бит и длину ключа 128, 192 или 256 бит. В случае длины в 128 или 192 бит используется 6 раундов, в случае 256 бит — 8 раундов. Алгоритм сопоставим по производительности с Triple DES , но по сравнению с конкурентами в конкурсе AES алгоритм оказывается довольно медленным.

Предпосылки к созданию

К 1998 году стало ясно, что существовавший до этого на правах стандарта шифр DES совершенно не удовлетворяет требованиям времени. Было показано, что за сумму порядка одного миллиона долларов можно создать устройство, перебирающее все ключи DES меньше чем за 3,5 часа. Существовавшая альтернатива — «тройной DES» — так же не обеспечивал требуемой надежности, так как (в некоторых режимах своей работы) уязвим для атаки по подобранному шифро-тексту. Учитывая широкую распространённость DES к тому моменту (в том числе в виде эффективных аппаратных реализаций) Ларсом Кнудсеном был предложен шифр DEAL — шифр с Фейстелевой структурой, использующий DES в качестве раундовой функции и имеющий r раундов. Таким образом DEAL представляет собой шифр с размером блока 128 бит и r — 64 битами раундовых ключей, вычисляемых с помощью алгоритма расписания ключей. Расписание ключей предусматривает что размер исходного ключа один принимает одно из трёх различных значений: 128, 192 или 256 бит. Для первых двух размеров ключей предлагалось положить r = 6, а при размере ключа 256 бит r = 8. Полученный таким образом ключ по скорости сопоставим с Triple DES

Алгоритм

Режимы работы с ключами длиной 128, 192 и 256 бит обозначаются соответственно DEAL-128, DEAL-192 и DEAL-256. Каждая из модификаций с разными длинами ключа может использовать все четыре стандартных режима DES-а.

Режим ECB

Рассмотрим первый режим работы — ECB (Electronic Code Book). Обозначим С = ${\displaystyle E_{B}}$ (А) результат шифрования 64-битного блока А на ключе В, и Y = ${\displaystyle EA_{Z}}$ (X) — результат шифрования с помощью DEAL-128 блока X на ключе Z. Согласно требованиям AES, исходный текст Р разбивается на блоки ${\displaystyle P_{i}}$ по 128 бит каждый, ${\displaystyle P=P_{1},P_{2}..,P_{n}}$ Из исходного ключа K с помощью расписания ключей получается r ключей для работы DES ${\displaystyle RK_{i}}$ , где i = 1, …, r. Алгоритм расписания описан ниже. Обозначим ${\displaystyle X^{L}}$ и ${\displaystyle X^{R}}$ как «левую» и «правую» части блока Х соответственно. Шифрование описывается следующими выражениями:
Положим ${\displaystyle X_{0}^{R}=P_{i}^{R}}$ и ${\displaystyle X_{0}^{L}=P_{i}^{L}}$ , и вычислим для j = 1,.. ,r

${\displaystyle X_{j}^{L}=E_{RK_{i}}(X_{j-1}^{L})\oplus X_{j-1}^{R}}$
${\displaystyle X_{j}^{R}=X_{j-1}^{L}}$

Положим ${\displaystyle C_{i}=X_{r}^{L}\parallel X_{r}^{R}}$

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

В заключительном раунде DEAL «правая» и «левая» половинки блока так же меняются (а не остаются на местах как в DES). Это обусловлено следующем: «правая» часть шифруемого блока ${\displaystyle C_{i}}$ не шифруется в последнем раунде i-го прохода DEAL, и только «левая» половина блока на i + 1-м проходе (исходный блок которого равен ${\displaystyle C_{i}\oplus P_{i+1}}$ ) шифруется в первом раунде. Это означает, что «правая» часть ${\displaystyle C_{i}}$ не будет шифроваться вообще в течение двух раундов. Это можно рассматривать как уязвимость алгоритма, учитывая что с DEAL используется всего 6 или 8 раундов. Подобной «особенностью» обладает и DES в режиме CBC. Но, учитывая что у DES 16 раундов, это не становиться столь яркой уязвимостью. Так или иначе — эта перестановка не влияет на стойкость блочного шифра в режиме ECB

Режим CBC

Итак, обозначим блоки открытого текста по 128 бит ${\displaystyle P_{1},P_{2},..,P_{n}}$ и ${\displaystyle C_{1},C_{2},..,C_{n}}$ — соответствующие им блоки шифр-текста. Тогда используя рекуррентное соотношение: ${\displaystyle C_{i}=EA_{K}(C_{i-1}\oplus P_{i})}$ , где ${\displaystyle C_{0}}$ — начальное значение
получаем шифроблоки в режиме CBC.

Расписание ключей

Входными параметрами для расписания ключей являются s ключей DES, каждый по 56 бит плюс 8 «проверочных» бит. Для разных исходных длин ключа s = 2, 3, 4, и входные ключи обозначаются: ${\displaystyle K_{1}..,K_{s}}$ . На выходе получаем r ключей DES, ${\displaystyle RK_{i}}$ . Расписание ключей единообразно для всех трёх длин исходного ключа. Сначала расширяем s ключей до r ключей, создавая отсутствующие ключи операцией XOR с новой константой для каждого нового ключа. Константа используется чтобы исключить слабые ключи. К полученным ключам применим DES в режиме CBC с фиксированным ключом и нулевым начальным значением. Из полученных блоков шифр-текста и формируются подключи ${\displaystyle RK_{i}}$ . Далее — точные описания вышеописанных операций. Здесь ${\displaystyle K=0x1234}$ ${\displaystyle 567890ab}$ ${\displaystyle cdef_{x}}$ (шестнадцатеричное число) — фиксированный ключ для DES.
В DEAL-128 подключи генерируются следующим образом:

${\displaystyle RK_{1}=E_{k}(K_{1}^{1}),}$
${\displaystyle RK_{2}=E_{k}(K_{2}\oplus RK_{1}),}$
${\displaystyle RK_{3}=E_{k}(K_{1}\oplus \langle 1\rangle \oplus RK_{2}),}$
${\displaystyle RK_{4}=E_{k}(K_{2}\oplus \langle 2\rangle \oplus RK_{3}),}$
${\displaystyle RK_{5}=E_{k}(K_{1}\oplus \langle 4\rangle \oplus RK_{4}),}$
${\displaystyle RK_{6}=E_{k}(K_{2}\oplus \langle 8\rangle \oplus RK_{5}),}$

где ${\displaystyle \langle i\rangle }$ — 64-битное целое число, в котором i — 1-й бит (нумерация с 0) установлен в «1», а остальные — в «0». Например, ${\displaystyle \langle 1\rangle }$ может быть представлено как шестнадцатеричное « ${\displaystyle K=0x8000}$ ${\displaystyle 00000000}$ ${\displaystyle 0000_{x}}$ ».

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

${\displaystyle RK_{1}=E_{k}(K_{1}^{1}),}$
${\displaystyle RK_{2}=E_{k}(K_{2}\oplus RK_{1}),}$
${\displaystyle RK_{3}=E_{k}(K_{1}\oplus \oplus RK_{2}),}$
${\displaystyle RK_{4}=E_{k}(K_{2}\oplus \langle 1\rangle \oplus RK_{3}),}$
${\displaystyle RK_{5}=E_{k}(K_{1}\oplus \langle 2\rangle \oplus RK_{4}),}$
${\displaystyle RK_{6}=E_{k}(K_{3}\oplus \langle 4\rangle \oplus RK_{5}),}$

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

${\displaystyle RK_{1}=E_{k}(K_{1}^{1}),}$
${\displaystyle RK_{2}=E_{k}(K_{2}\oplus RK_{1}),}$
${\displaystyle RK_{3}=E_{k}(K_{3}\oplus RK_{2}),}$
${\displaystyle RK_{4}=E_{k}(K_{4}\oplus RK_{3}),}$
${\displaystyle RK_{5}=E_{k}(K_{1}\oplus \langle 1\rangle \oplus RK_{4}),}$
${\displaystyle RK_{6}=E_{k}(K_{2}\oplus \langle 2\rangle \oplus RK_{5}),}$
${\displaystyle RK_{7}=E_{k}(K_{3}\oplus \langle 4\rangle \oplus RK_{6}),}$
${\displaystyle RK_{8}=E_{k}(K_{4}\oplus \langle 8\rangle \oplus RK_{7}),}$

Таким образом для генерации раундовых ключей DEAL необходимо 8 «проходов» DEAL. Чтобы не тратить процессорное время эти ключи следует сохранить для всего процесса шифрования или расшифрования.

Стойкость алгоритма

Анализ алгоритма показал множество недостатков: наличие подмножеств слабых ключей, подверженность дифференциальному криптоанализу, отсутствие усиления при использовании 192-битных ключей по сравнению с 128-битными. Во-первых, алгоритм расписания ключей не дает достаточно сильных ключей. Действительно, в случае «нулевого» исходного ключа DEAL раундовые ключи получаются слабыми: у первых трёх только один-два бита отличаются от нулей. Во-вторых, после разбиения исходного блока на два по 64 бита, полученные шифротексты «сшиваются» либо с помощью CBC, либо конкатенацией. Такая схема уязвима для дифференциального анализа. Получаемая надежность оказывается порядка ${\displaystyle 2^{65}}$ , вместо ${\displaystyle 2^{128}}$ .

В связи с этими недостатками шифр DEAL не смог пройти в финал конкурса AES, и не рассматривался как кандидат в промышленный стандарт. Но тем не менее он получил некоторое распространение.

Литература

• Lars Knudsen. (неопр.) . — Department of Informatics, University of Bergen, Norway, 1998. — 21 February ( т. Technical report no. 151 ). 28 марта 2009 года.
• Джон Келси, Брюс Шнайдер (Август 1999). ( PDF / PostScript ) . 6th Annual International Workshop on (SAC '99) . Кингстон, Онтарио: Springer-Verlag . pp. страницы 118—134 . Дата обращения: 23 августа 2007 .

Ссылки

• (PDF)