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). Обозначим С = <math> E_B </math>(А) результат шифрования 64-битного блока А на ключе В, и Y = <math> EA_Z </math>(X) — результат шифрования с помощью DEAL-128 блока X на ключе Z. Согласно требованиям AES, исходный текст Р разбивается на блоки <math>P_i</math> по 128 бит каждый, <math> P = P_1, P_2.., P_n </math> Из исходного ключа K с помощью расписания ключей получается r ключей для работы DES <math>RK_i</math>, где i = 1, …, r. Алгоритм расписания описан ниже. Обозначим <math>X^L</math> и <math>X^R</math> «правую» и «левую» части блока Х соответственно. Шифрование описывается следующими выражениями:
Положим <math>X^R_0 = P^R_i</math> и <math>X^L_0 = P^L_i</math>, и вычислим для j = 1,.. ,r

<math>X^L_j = E_{RK_i}(X^L_{j-1}) \oplus X^R_{j-1}</math>
<math>X^R_j = X^L_{j-1}</math>

Положим <math> C_i = X^L_r \parallel X^R_r </math> На рисунке изображена одна итерация цикла для DEAL. Для DEAL-128 и DEAL-192 используются 6 циклов, полагая r = 6. Однако, такого количества раундов может оказаться недостаточно для DEAL-256, в котором необходимо использовать большее количество раундов: r = 8. По замыслу разработчиков DEAL-256 должен использоваться только когда требуется особенно сильное шифрование.
В заключительном раунде DEAL «правая» и «левая» половинки блока так же меняются (а не остаются на местах как в DES). Это обусловлено следующем: «правая» часть шифруемого блока <math> C_i </math> не шифруется в последнем раунде i-ого прохода DEAL, и только «левая» половина блока на i + 1-м проходе (исходный блок которого равен <math> C_i \oplus P_{i+1} </math>) шифруется в первом раунде. Это означает, что «правая» часть <math> C_i </math> не будет шифроваться вообще в течение двух раундов. Это можно рассматривать как уязвимость алгоритма, учитывая что с DEAL используется всего 6 или 8 раундов. Подобной «особенностью» обладает и DES в режиме CBC. Но, учитывая что у DES 16 раундов, это не становиться столь яркой уязвимостью. Так или иначе — эта перестановка не влияет на стойкость блочного шифра в режиме ECB

Режим CBC

Итак, обозначим блоки открытого текста по 128 бит <math> P_1, P_2,.. , P_n </math> и <math> C_1, C_2,.. , C_n </math> — соответствующие им блоки шифр-текста. Тогда используя рекуррентное соотношение: <math> C_i = EA_K(C_{i-1} \oplus P_i) </math>, где <math> C_0 </math> — начальное значение
получаем шифроблоки в режиме CBC.

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

Входными параметрами для расписания ключей являются s ключей DES, каждый по 56 бит плюс 8 «проверочных» бит. Для разных исходных длин ключа s = 2, 3, 4, и входные ключи обозначаются: <math> K_1.., K_s </math>. На выходе получаем r ключей DES, <math>RK_i</math>. Расписание ключей единообразно для всех трёх длин исходного ключа. Сначала расширяем s ключей до r ключей, создавая отсутствующие ключи операцией XOR с новой константой для каждого нового ключа. Константа используется чтобы исключить слабые ключи. К полученным ключам применим DES в режиме CBC с фиксированным ключом и нулевым начальным значением. Из полученных блоков шифр-текста и формируются подключи <math> RK_i</math>. Далее — точные описания вышеописанных операций. Здесь <math> K = 0x1234</math> <math>5678 90ab</math> <math>cdef_x</math> (шестнадцатеричное число) — фиксированный ключ для DES.
В DEAL-128 подключи генерируются следующим образом:

<math> RK_1 = E_k(K^1_1), </math>
<math> RK_2 = E_k(K_2 \oplus RK_1), </math>
<math> RK_3 = E_k(K_1 \oplus \langle 1 \rangle \oplus RK_2), </math>
<math> RK_4 = E_k(K_2 \oplus \langle 2 \rangle \oplus RK_3), </math>
<math> RK_5 = E_k(K_1 \oplus \langle 4 \rangle \oplus RK_4), </math>
<math> RK_6 = E_k(K_2 \oplus\langle 8 \rangle \oplus RK_5), </math>

где <math> \langle i \rangle </math> — 64-х битное целое число, в котором i — 1-й бит (нумерация с 0) установлен в «1», а остальные — в «0». Например, <math> \langle 1 \rangle </math> может быть представлено как шестнадцатеричное «<math> K = 0x8000</math> <math>0000 0000</math> <math>0000_x</math>».

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

<math> RK_1 = E_k(K^1_1), </math>
<math> RK_2 = E_k(K_2 \oplus RK_1), </math>
<math> RK_3 = E_k(K_1 \oplus \oplus RK_2), </math>
<math> RK_4 = E_k(K_2 \oplus \langle 1 \rangle \oplus RK_3), </math>
<math> RK_5 = E_k(K_1 \oplus \langle 2 \rangle \oplus RK_4), </math>
<math> RK_6 = E_k(K_3 \oplus\langle 4 \rangle \oplus RK_5), </math>

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

<math> RK_1 = E_k(K^1_1), </math>
<math> RK_2 = E_k(K_2 \oplus RK_1), </math>
<math> RK_3 = E_k(K_3 \oplus RK_2), </math>
<math> RK_4 = E_k(K_4 \oplus RK_3), </math>
<math> RK_5 = E_k(K_1 \oplus \langle 1 \rangle \oplus RK_4), </math>
<math> RK_6 = E_k(K_2 \oplus \langle 2 \rangle \oplus RK_5), </math>
<math> RK_7 = E_k(K_3 \oplus \langle 4 \rangle \oplus RK_6), </math>
<math> RK_8 = E_k(K_4 \oplus \langle 8 \rangle \oplus RK_7), </math>

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

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

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

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

Литература

• Lars Knudsen (21 февраля 1998). «[www2.mat.dtu.dk/people/Lars.R.Knudsen/newblock.html DEAL - A 128-bit Block Cipher]» (PDF/PostScript) (Department of Informatics, University of Bergen, Norway). Проверено 2009-10-26.
• Джон Келси, Брюс Шнайдер (Август 1999). "[www.schneier.com/paper-deal.html Криптоанализ DEAL на расписании ключей (eng)]" (PDF/PostScript). 6th Annual International Workshop on Selected Areas in Cryptography (SAC '99): страницы 118—134, Кингстон, Онтарио: Springer-Verlag. Проверено 2007-08-23. 

Ссылки

• [www.ixbt.com/soft/alg-encryption-aes.shtml Обзор шифров — участников конкурса AES]
• [www.mat.dtu.dk/people/Lars.R.Knudsen/newblock.html Оригинальное описание DEAL]
• [www.users.zetnet.co.uk/hopwood/crypto/scan/cs.html Заявка DEAL на SCAN]
• [csrc.nist.gov/CryptoToolkit/aes/round1/conf1/deal-slides.pdf Слайды, использованные в презентации на конкурсе AES] (PDF)

Отрывок, характеризующий DEAL

– Такие предложения, как то, чтобы очистить Одер и Вислу, можно делать принцу Баденскому, а не мне, – совершенно неожиданно для себя почти вскрикнул Наполеон. – Ежели бы вы мне дали Петербуг и Москву, я бы не принял этих условий. Вы говорите, я начал войну? А кто прежде приехал к армии? – император Александр, а не я. И вы предлагаете мне переговоры тогда, как я издержал миллионы, тогда как вы в союзе с Англией и когда ваше положение дурно – вы предлагаете мне переговоры! А какая цель вашего союза с Англией? Что она дала вам? – говорил он поспешно, очевидно, уже направляя свою речь не для того, чтобы высказать выгоды заключения мира и обсудить его возможность, а только для того, чтобы доказать и свою правоту, и свою силу, и чтобы доказать неправоту и ошибки Александра.
Вступление его речи было сделано, очевидно, с целью выказать выгоду своего положения и показать, что, несмотря на то, он принимает открытие переговоров. Но он уже начал говорить, и чем больше он говорил, тем менее он был в состоянии управлять своей речью.
Вся цель его речи теперь уже, очевидно, была в том, чтобы только возвысить себя и оскорбить Александра, то есть именно сделать то самое, чего он менее всего хотел при начале свидания.
– Говорят, вы заключили мир с турками?
Балашев утвердительно наклонил голову.
– Мир заключен… – начал он. Но Наполеон не дал ему говорить. Ему, видно, нужно было говорить самому, одному, и он продолжал говорить с тем красноречием и невоздержанием раздраженности, к которому так склонны балованные люди.
– Да, я знаю, вы заключили мир с турками, не получив Молдавии и Валахии. А я бы дал вашему государю эти провинции так же, как я дал ему Финляндию. Да, – продолжал он, – я обещал и дал бы императору Александру Молдавию и Валахию, а теперь он не будет иметь этих прекрасных провинций. Он бы мог, однако, присоединить их к своей империи, и в одно царствование он бы расширил Россию от Ботнического залива до устьев Дуная. Катерина Великая не могла бы сделать более, – говорил Наполеон, все более и более разгораясь, ходя по комнате и повторяя Балашеву почти те же слова, которые ои говорил самому Александру в Тильзите. – Tout cela il l'aurait du a mon amitie… Ah! quel beau regne, quel beau regne! – повторил он несколько раз, остановился, достал золотую табакерку из кармана и жадно потянул из нее носом.
– Quel beau regne aurait pu etre celui de l'Empereur Alexandre! [Всем этим он был бы обязан моей дружбе… О, какое прекрасное царствование, какое прекрасное царствование! О, какое прекрасное царствование могло бы быть царствование императора Александра!]
Он с сожалением взглянул на Балашева, и только что Балашев хотел заметить что то, как он опять поспешно перебил его.
– Чего он мог желать и искать такого, чего бы он не нашел в моей дружбе?.. – сказал Наполеон, с недоумением пожимая плечами. – Нет, он нашел лучшим окружить себя моими врагами, и кем же? – продолжал он. – Он призвал к себе Штейнов, Армфельдов, Винцингероде, Бенигсенов, Штейн – прогнанный из своего отечества изменник, Армфельд – развратник и интриган, Винцингероде – беглый подданный Франции, Бенигсен несколько более военный, чем другие, но все таки неспособный, который ничего не умел сделать в 1807 году и который бы должен возбуждать в императоре Александре ужасные воспоминания… Положим, ежели бы они были способны, можно бы их употреблять, – продолжал Наполеон, едва успевая словом поспевать за беспрестанно возникающими соображениями, показывающими ему его правоту или силу (что в его понятии было одно и то же), – но и того нет: они не годятся ни для войны, ни для мира. Барклай, говорят, дельнее их всех; но я этого не скажу, судя по его первым движениям. А они что делают? Что делают все эти придворные! Пфуль предлагает, Армфельд спорит, Бенигсен рассматривает, а Барклай, призванный действовать, не знает, на что решиться, и время проходит. Один Багратион – военный человек. Он глуп, но у него есть опытность, глазомер и решительность… И что за роль играет ваш молодой государь в этой безобразной толпе. Они его компрометируют и на него сваливают ответственность всего совершающегося. Un souverain ne doit etre a l'armee que quand il est general, [Государь должен находиться при армии только тогда, когда он полководец,] – сказал он, очевидно, посылая эти слова прямо как вызов в лицо государя. Наполеон знал, как желал император Александр быть полководцем.
– Уже неделя, как началась кампания, и вы не сумели защитить Вильну. Вы разрезаны надвое и прогнаны из польских провинций. Ваша армия ропщет…
– Напротив, ваше величество, – сказал Балашев, едва успевавший запоминать то, что говорилось ему, и с трудом следивший за этим фейерверком слов, – войска горят желанием…
– Я все знаю, – перебил его Наполеон, – я все знаю, и знаю число ваших батальонов так же верно, как и моих. У вас нет двухсот тысяч войска, а у меня втрое столько. Даю вам честное слово, – сказал Наполеон, забывая, что это его честное слово никак не могло иметь значения, – даю вам ma parole d'honneur que j'ai cinq cent trente mille hommes de ce cote de la Vistule. [честное слово, что у меня пятьсот тридцать тысяч человек по сю сторону Вислы.] Турки вам не помощь: они никуда не годятся и доказали это, замирившись с вами. Шведы – их предопределение быть управляемыми сумасшедшими королями. Их король был безумный; они переменили его и взяли другого – Бернадота, который тотчас сошел с ума, потому что сумасшедший только, будучи шведом, может заключать союзы с Россией. – Наполеон злобно усмехнулся и опять поднес к носу табакерку.
На каждую из фраз Наполеона Балашев хотел и имел что возразить; беспрестанно он делал движение человека, желавшего сказать что то, но Наполеон перебивал его. Например, о безумии шведов Балашев хотел сказать, что Швеция есть остров, когда Россия за нее; но Наполеон сердито вскрикнул, чтобы заглушить его голос. Наполеон находился в том состоянии раздражения, в котором нужно говорить, говорить и говорить, только для того, чтобы самому себе доказать свою справедливость. Балашеву становилось тяжело: он, как посол, боялся уронить достоинство свое и чувствовал необходимость возражать; но, как человек, он сжимался нравственно перед забытьем беспричинного гнева, в котором, очевидно, находился Наполеон. Он знал, что все слова, сказанные теперь Наполеоном, не имеют значения, что он сам, когда опомнится, устыдится их. Балашев стоял, опустив глаза, глядя на движущиеся толстые ноги Наполеона, и старался избегать его взгляда.
– Да что мне эти ваши союзники? – говорил Наполеон. – У меня союзники – это поляки: их восемьдесят тысяч, они дерутся, как львы. И их будет двести тысяч.
И, вероятно, еще более возмутившись тем, что, сказав это, он сказал очевидную неправду и что Балашев в той же покорной своей судьбе позе молча стоял перед ним, он круто повернулся назад, подошел к самому лицу Балашева и, делая энергические и быстрые жесты своими белыми руками, закричал почти:
– Знайте, что ежели вы поколеблете Пруссию против меня, знайте, что я сотру ее с карты Европы, – сказал он с бледным, искаженным злобой лицом, энергическим жестом одной маленькой руки ударяя по другой. – Да, я заброшу вас за Двину, за Днепр и восстановлю против вас ту преграду, которую Европа была преступна и слепа, что позволила разрушить. Да, вот что с вами будет, вот что вы выиграли, удалившись от меня, – сказал он и молча прошел несколько раз по комнате, вздрагивая своими толстыми плечами. Он положил в жилетный карман табакерку, опять вынул ее, несколько раз приставлял ее к носу и остановился против Балашева. Он помолчал, поглядел насмешливо прямо в глаза Балашеву и сказал тихим голосом: – Et cependant quel beau regne aurait pu avoir votre maitre! [A между тем какое прекрасное царствование мог бы иметь ваш государь!]
Балашев, чувствуя необходимость возражать, сказал, что со стороны России дела не представляются в таком мрачном виде. Наполеон молчал, продолжая насмешливо глядеть на него и, очевидно, его не слушая. Балашев сказал, что в России ожидают от войны всего хорошего. Наполеон снисходительно кивнул головой, как бы говоря: «Знаю, так говорить ваша обязанность, но вы сами в это не верите, вы убеждены мною».