DEAL

DEAL
Создатель:	Кнудсен, Ларс
Опубликован:	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^R_0 = P^R_i$ и $X^L_0 = P^L_i$, и вычислим для j = 1,.. ,r

$X^L_j = E_{RK_i}(X^L_{j-1}) \oplus X^R_{j-1}$
$X^R_j = X^L_{j-1}$

Положим $C_i = X^L_r \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$ $5678 90ab$ $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$ $0000 0000$ $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 (21 февраля 1998). «DEAL - A 128-bit Block Cipher» (PDF/PostScript) (Department of Informatics, University of Bergen, Norway). Проверено 2009-10-26.
• Джон Келси, Брюс Шнайдер (Август 1999). "Криптоанализ DEAL на расписании ключей (eng)" (PDF/PostScript). 6th Annual International Workshop on Selected Areas in Cryptography (SAC '99): страницы 118—134, Кингстон, Онтарио: Springer-Verlag. Проверено 2007-08-23. 

Ссылки

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