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

Общая структура

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

Функция шифрования

Вход : ${\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, её значения будут описаны ниже. Необходимым критерием таблицы поиска является инъективность .

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

Для повышения стойкости шифра каждый раунд функция шифрования использует разные раундовые ключи ${\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})}$

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

Фиксированные параметры

Для проведения операции шифрования шифром 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}$

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

Таблица поиска RT

Входная последовательность бит(6):	00	01	02	03	04	05	06	07	08	09	0A	0B
Выходная последовательность бит (32):	b7e15162	8aed2a6a	bf715880	9cf4f3c7	62e7160f	38b4da56	a784d904	5190cfef	324e7738	926cfbe5	f4bf8d8d	8c31d763
0C	0D	0E	0F	10	11	12	13	14	15	16	17	18	19	1A	1B
da06c80a	bb1185eb	4f7c7b57	57f59594	90cfd47d	7c19bb42	158d9554	f7b46bce	d55c4d79	fd5f24d6	613c31c3	839a2ddf	8a9a276b	cfbfa1c8	77c56284	dab79cd4
1C	1D	1E	1F	20	21	22	23	24	25	26	27	28	29	2A	2B
c2d3293d	20e9e5ea	f02ac60a	cc93ed87	4422a52e	cb238fee	e5ab6add	835fd1a0	753d0a8f	78e537d2	b95bb79d	8dcaec64	2c1e9f23	b829b5c2	780bf387	37df8bb3
2C	2D	2E	2F	30	31	32	33	34	35	36	37	38	39	3A	3B
00d01334	a0d0bd86	45cbfa73	a6160ffe	393c48cb	bbca060f	0ff8ec6d	31beb5cc	eed7f2f0	bb088017	163bc60d	f45a0ecb	1bcd289b	06cbbfea	21ad08e1	847f3f73
3C	3D	3E	3F
78d56ced	94640d6e	f0d3d37b	e6700831

Константы:

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 основана на декорреляционном методе , разработанном Сержом Ваденэ, с доказуемой стойкостью к известным криптографическим атакам. Однако уже существуют аналитические результаты, показывающие обратное.

Слабые ключи и константы

Для удобства возьмем, что ${\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, шифр становится уязвимым для (более подробно о такой атаке с примером ). Шанс появления таких ключей равен 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) не зависело от входных данных. В противном случае возможно применение атаки Кохера по времени .

Атака «Photofinishing Attack»

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

Примечания

Ссылки