Введение
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 даже более важной.