DEAL

DEAL
Создатель	Кнудсен, Ларс
Создан	1997 г.
Опубликован	1998 г.
Размер ключа	128/192/256 бит
Размер блока	128 бит
Число раундов	6 (для ключа в 128/192 бит), 8 (для 256 бит)
Тип	Сеть Фейстеля

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

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

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

Один раунд DEAL

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

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

Режим CBC

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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

Ссылки

• Обзор шифров — участников конкурса AES
• Оригинальное описание DEAL
• Заявка DEAL на SCAN
• Слайды, использованные в презентации на конкурсе AES (PDF)