DFC — Википедия

DFC (Decorrelated Fast Cipher) — блочный симметричный криптоалгоритм, созданный в 1998 году совместно криптографами Парижской Высшей нормальной школы, Национального центра научных исследований (CNRS) и телекоммуникационного гиганта France Telecom под руководством известного криптолога Сержа Воденэ^[en], специально для участия в конкурсе AES. Относится к семейству PEANUT (Pretty Encryption Algorithm with n-Universal Transformation) шифров.^[1]

Общая структура[править | править код]

DFC — блочный шифр с длинной блока 128 бит, представляющий 8-раундовую Сеть Фейстеля. Используется 64-битовая функция шифрования с восемью различными раундовыми ключами ${\displaystyle K_{i},i=1\ldots n,n=8}$ по 128 бит, получаемыми из одного исходного ключа шифрования. Каждый раунд функция шифрования использует левую половину исходного текста (блока) и два 64-битных ключа, являющихся половинами соответствующего раундового, для получения 64-битного шифрованного текста. Полученная зашифрованная левая половина блока прибавляется к правой. Затем, согласно идее сети Фейстеля, левая и правая части блока меняются местами^[2]. Расшифровывание происходит так же как и шифрование с использованием раундовых ключей в обратном порядке. Длина исходного ключа шифрования не ограничивается тремя фиксированными размерами, предусмотренными конкурсом AES (128, 192 и 256 битов), и может быть переменного размера от 0 до 256 бит^[3].

Функция шифрования^[2][4][править | править код]

Вход: ${\displaystyle X}$ — 64-битная левая половина исходного текста (блока); ${\displaystyle K_{i}}$ — соответствующий раундовый ключ.

Выход: ${\displaystyle Y}$ — 64-битная зашифрованная левая половина исходного текста.

Этап 1: Вычисление[править | править код]

Раундовый ключ ${\displaystyle K_{i}}$ делится на две половины: ${\displaystyle A_{i}}$ и ${\displaystyle B_{i}}$. Далее производится следующее вычисление:

${\displaystyle Z=(A_{i}\cdot X+B_{i}\mod (2^{64}+13))\mod 2^{64}}$

Этап 2: «Запутывающая перестановка»[править | править код]

«Запутывающая перестановка» (Confusion Permutation) использует S-box, трансформирующий входные 6 бит в 32 бита с помощью таблицы замены RT (Далее считаем ${\displaystyle RT()}$ функцией данного преобразования).

Пусть ${\displaystyle Z_{l}}$ и ${\displaystyle Z_{r}}$ — левая и правая части полученного ${\displaystyle Z}$ по 32 бита каждая (обозначим это как ${\displaystyle Z=Z_{l}|Z_{r}}$), ${\displaystyle KC}$ и ${\displaystyle KD}$ — заданные константы длиной 32 и 64 бита соответственно, а ${\displaystyle trunc_{n}()}$ — функция, оставляющая ${\displaystyle n}$ крайних левых бит аргумента, тогда результат функции шифрования:

${\displaystyle Y=(Z_{r}\oplus RT(trunc_{6}(Z_{l})))|(Z_{l}\oplus KC)+KD\mod 2^{64}}$

Таблица поиска (S-box)[править | править код]

S-блок — основной компонент симметричных криптоалгоритмов, производящий замену n входных бит на m выходных по некоторой таблице поиска. Используется для максимального устранения зависимостей между ключом шифрования и шифротекстом, что позволяет выполнить свойство Шеннона о запутанности криптоалгоритма. Обычно используются S-блоки с фиксированной таблицей поиска (DES,Rijndael), но в некоторых криптоалгоритмах таблица поиска генерируется с использованием входного ключа шифрования (Blowfish,Twofish). В DFC используется фиксированная таблица поиска RT, её значения будут описаны ниже. Необходимым критерием таблицы поиска является инъективность.

Раундовые ключи^[4][править | править код]

Для повышения стойкости шифра каждый раунд функция шифрования использует разные раундовые ключи ${\displaystyle K_{i}}$. Для их получения используется основной ключ шифра ${\displaystyle K}$. Алгоритм получения состоит в следующем.

Шаг 1[править | править код]

Сначала дополним основной ключ шифра ${\displaystyle K}$ (длина которого колеблется от 0 до 256 бит) заданной константой ${\displaystyle KS}$ длиной 256 бит, отрезая лишние символы.

${\displaystyle PK=trunc_{256}(K|KS)}$.

Полученный ${\displaystyle PK}$ разрезаем на 8 32-битных частей ${\displaystyle PK_{i},i=1\ldots 8}$.

${\displaystyle PK=PK_{1}|\ldots |PK_{8}}$

Шаг 2[править | править код]

Определим несколько вспомогательных переменных, используя полученные ${\displaystyle PK_{i}}$:

${\displaystyle OA_{1}=PK_{1}|PK_{8};}$

${\displaystyle OB_{1}=PK_{5}|PK_{4};}$

${\displaystyle EA_{1}=PK_{2}|PK_{7};}$

${\displaystyle EB_{1}=PK_{6}|PK_{3};}$

а также для i=2,3,4

${\displaystyle OA_{i}=OA_{1}\oplus KA_{i-1};}$

${\displaystyle OB_{i}=OB_{1}\oplus KB_{i-1};}$

${\displaystyle EA_{i}=EA_{1}\oplus KA_{i-1};}$

${\displaystyle EB_{i}=EB_{1}\oplus KB_{i-1};}$

где ${\displaystyle KA_{1},KB_{1},KA_{2},KB_{2},KA_{3},KB_{3}}$ — заданные 64-битные константы.

Шаг 3[править | править код]

Таким образом мы получили из исходного ключа ${\displaystyle K}$ длиной 256 бит два ключа ${\displaystyle OK(K),EK(K)}$ длиной по 512 бит каждый.

${\displaystyle OK(K)=OA_{1}|OB_{1}|\ldots |OA_{4}|OB_{4}}$

${\displaystyle EK(K)=EA_{1}|EB_{1}|\ldots |EA_{4}|EB_{4}}$

Пусть ${\displaystyle Enc_{OK(K)}(),Enc_{EK(K)}()}$ — функции шифрования, описанные в пункте 2, только с 4 раундами вместо 8, использующие для ${\displaystyle i}$-го раунда ${\displaystyle i=1\ldots 4}$ раундовые ключи ${\displaystyle OA_{i}|OB_{i}}$ и ${\displaystyle EA_{i}|EB_{i}}$ соответственно. Тогда полагая что ${\displaystyle K_{0}=0|_{128}}$ получаем искомые раундовые ключи:

Если ${\displaystyle i}$ — нечетное, то:

${\displaystyle K_{i}=Enc_{OK(K)}(K_{i-1})}$

Если ${\displaystyle i}$ — четное, то:

${\displaystyle K_{i}=Enc_{EK(K)}(K_{i-1})}$

Раундовые ключи найдены.

Фиксированные параметры^[4][править | править код]

Для проведения операции шифрования шифром DFC, как показано выше, требуются следующие фиксированные параметры:

Наименование	Длина (бит)	Назначение
${\displaystyle KD}$	64	Функция Шифрования, Этап 2
${\displaystyle KC}$	32	Функция Шифрования, Этап 2
${\displaystyle KA_{1},KA_{2},KA_{3}}$	64	Получение раундовых ключей, Шаг 2
${\displaystyle KB_{1},KB_{2},KB_{3}}$	64	Получение раундовых ключей, Шаг 2
${\displaystyle KS}$	256	Получение раундовых ключей, Шаг 1
Таблица поиска ${\displaystyle RT_{i},i=0\ldots 63}$	64x32	Функция Шифрования, Этап 2

Для задания фиксированных параметров обычно используется шестнадцатеричная запись числа e:

e = 2.b7e151628aed2a6abf7158…

Далее будем считать ${\displaystyle EC}$ только дробную часть шестнадцатеричной записи числа e.

${\displaystyle trunc_{2144}(EC)=RT_{0}|RT_{1}|RT_{2}|\ldots |RT_{63}|KC|KD}$

${\displaystyle trunc_{640}(EC)=KA_{1}|KA_{2}|KA_{3}|KB_{1}|KB_{2}|KB_{3}|KS}$

Таким образом получим следующее (данные представлены в шестнадцатеричной системе исчисления):

Константы:

KD  = 86d1bf27 5b9b251d KC  = eb64749a KA1 = b7e15162 8aed2a6a KA2 = bf715880 9cf4f3c7 KA3 = 62e7160f 38b4da56 KB1 = a784d904 5190cfef KB2 = 324e7738 926cfbe5 KB3 = f4bf8d8d 8c31d763 KS  = da06c80a bb1185eb 4f7c7b57 57f59584 90cfd47d 7c19bb42 158d9554 f7b46bce 

Криптостойкость[править | править код]

Криптостойкость — способность алгоритма шифрования противостоять возможным атакам на него. Структура DFC основана на декорреляционном методе^[1], разработанном Сержом Ваденэ, с доказуемой стойкостью к известным криптографическим атакам. Однако уже существуют аналитические результаты, показывающие обратное.

Слабые ключи и константы^[4][править | править код]

Для удобства возьмем, что ${\displaystyle LK_{i}}$ — левая половина i-го раундового ключа K, ${\displaystyle RK_{i}}$ — правая половина. Если ${\displaystyle RK_{i}}$ равна 0, то на выходе функции шифрования ${\displaystyle Z_{K_{i}}\left(X\right)}$ будет некая константа, независящая от ${\displaystyle X}$. Следовательно, взяв ${\displaystyle LK_{2}}$, ${\displaystyle LK_{4}}$, ${\displaystyle LK_{6}}$ равными 0, шифр становится уязвимым для distinguishing attack^[en] (более подробно о такой атаке с примером^[5]). Шанс появления таких ключей равен 2⁻¹⁹².

Следует отметить ещё одну особенность шифра, связанную с плохим выбором констант ${\displaystyle KA_{i}}$ и ${\displaystyle KB_{i}}$. (см. «Раундовые ключи») Если ${\displaystyle KA_{3}=KB_{3}=0}$, ${\displaystyle KA_{2}=KA_{4}}$, ${\displaystyle KB_{2}=KB_{4}}$, то получим ${\displaystyle OA_{1}=OA_{3}}$, ${\displaystyle OA_{2}=EA_{2}=0}$, ${\displaystyle OA_{2}=OA_{4}=0}$. А значит

${\displaystyle Enc_{OK\left(K\right)}\left({X_{L}|X_{R}}\right)=X_{R}|X_{L}}$

${\displaystyle Enc_{EK\left(K\right)}\left({X_{L}|X_{R}}\right)=X_{R}|X_{L}}$

Таким образом получаем нулевые раундовые ключи для всех раундов, значит

${\displaystyle DFC_{K}(U|V)=(V\oplus C)|(U\oplus C)}$, где ${\displaystyle C}$ — некая константа.

По получившемуся закрытому тексту можно восстановить исходный текст.

Атака по времени[править | править код]

Атака по времени — одна из разновидностей атаки по сторонним каналам. Реализации устойчивых шифров (DFC не исключение) должны быть такими, чтобы время вычисления операций по модулю (mod) не зависело от входных данных. В противном случае возможно применение атаки Кохера по времени^[6].

Атака «Photofinishing Attack»[править | править код]

Эли Бихам предложил эффективную технологию реалиции шифра, основанную на 1-битновом SIMD-микропроцессоре. Этот вид реализации не подвержен атаке Шамира «Photofinishing attack»^[7].

Примечания[править | править код]

Ссылки[править | править код]

• LASEC. Информация о DFC
• DFCv2