DFC

DFC
DFC
Создатель	Jacques Stern[en],; Serge Vaudenay[en]
Создан	1998
Опубликован	1998
Размер ключа	128/192/256 бит
Размер блока	128 бит
Число раундов	8
Тип	Сеть Фейстеля

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

Общая структураПравить

Шифрование

Расшифрование

«Запутывающая перестановка» (Confusion Permutation)

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

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

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

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

Этап 1: ВычислениеПравить

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

\text{[math]}

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

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

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

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

\text{[math]}

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]Править

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

Шаг 1Править

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

\text{[math]}

PK=trunc_{256}(K|KS)

.

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

\text{[math]}

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

Шаг 2Править

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

\text{[math]}

OA_{1}=PK_{1}|PK_{8};

\text{[math]}

OB_{1}=PK_{5}|PK_{4};

\text{[math]}

EA_{1}=PK_{2}|PK_{7};

\text{[math]}

EB_{1}=PK_{6}|PK_{3};

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

\text{[math]}

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

\text{[math]}

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

\text{[math]}

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

\text{[math]}

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

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

Шаг 3Править

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

\text{[math]}

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

\text{[math]}

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

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

Если $\text{[math]}$ $\text{[math]}$ $i$ — нечетное, то:

\text{[math]}

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

Если $\text{[math]}$ $\text{[math]}$ $i$ — четное, то:

\text{[math]}

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

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

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

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

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

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

e = 2.b7e151628aed2a6abf7158…

Далее будем считать $\text{[math]}$ $\text{[math]}$ $E C$ только дробную часть шестнадцатеричной записи числа e.

\text{[math]}

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

\text{[math]}

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
KA₁ = b7e15162 8aed2a6a
KA₂ = bf715880 9cf4f3c7
KA₃ = 62e7160f 38b4da56
KB₁ = a784d904 5190cfef
KB₂ = 324e7738 926cfbe5
KB₃ = f4bf8d8d 8c31d763
KS  = da06c80a bb1185eb 4f7c7b57 57f59584 90cfd47d 7c19bb42 158d9554 f7b46bce

КриптостойкостьПравить

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

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

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

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

\text{[math]}

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

\text{[math]}

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

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

\text{[math]}

DFC_{K}(U|V)=(V\oplus C)|(U\oplus C)

, где

\text{[math]}

C

— некая константа.

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

Атака по времениПравить

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

Атака «Photofinishing Attack»Править

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

ПримечанияПравить

↑ ¹ ² Serge Vaudenay^[en] Provable security for block Ciphers by deccorelation (1998) Архивная копия от 6 января 2015 на Wayback Machine
↑ ¹ ² Ларс Кнудсен, Винсент Рэймен (Март 1999) «On the Decorrelated Fast Cipher (DFC) and Its Theory» Архивная копия от 19 августа 2005 на Wayback Machine
↑ Панасенко С. П. Алгоритмы шифрования. Специальный справочник — СПб.: BHV-СПб, 2009. — 576 с. — ISBN 978-5-9775-0319-8
↑ ¹ ² ³ ⁴ Henri Gilbert, Marc Girault, Philippe Hoogvorst, Fabrice Noilhan, Thomas Pornin, Guillaume Poupard, Jacques Stern^[en] and Serge Vaudenay^[en] Decorrelated Fast Cipher: an AES Candidate. Full version Архивная копия от 15 января 2007 на Wayback Machine
↑ Simon Künzli, Willi Meier (2009) Distinguishing Attack on MAG Архивная копия от 27 мая 2011 на Wayback Machine
↑ Пол Кохер^[en] Timing Attacks on Implementations of Diffie-Hellman, PSA, DSS, and Other Systems Архивная копия от 22 октября 2010 на Wayback Machine
↑ A. Shamir. Visual cryptanalysis in Cryptology EUROCRYPT’98 (1998)

СсылкиПравить

[fourth-1] ¹ ² Serge Vaudenay^[en] Provable security for block Ciphers by deccorelation (1998) Архивная копия от 6 января 2015 на Wayback Machine

[first-2] ¹ ² Ларс Кнудсен, Винсент Рэймен (Март 1999) «On the Decorrelated Fast Cipher (DFC) and Its Theory» Архивная копия от 19 августа 2005 на Wayback Machine

[3] Панасенко С. П. Алгоритмы шифрования. Специальный справочник — СПб.: BHV-СПб, 2009. — 576 с. — ISBN 978-5-9775-0319-8

[third-4] ¹ ² ³ ⁴ Henri Gilbert, Marc Girault, Philippe Hoogvorst, Fabrice Noilhan, Thomas Pornin, Guillaume Poupard, Jacques Stern^[en] and Serge Vaudenay^[en] Decorrelated Fast Cipher: an AES Candidate. Full version Архивная копия от 15 января 2007 на Wayback Machine

[5] Simon Künzli, Willi Meier (2009) Distinguishing Attack on MAG Архивная копия от 27 мая 2011 на Wayback Machine

[6] Пол Кохер^[en] Timing Attacks on Implementations of Diffie-Hellman, PSA, DSS, and Other Systems Архивная копия от 22 октября 2010 на Wayback Machine

[7] A. Shamir. Visual cryptanalysis in Cryptology EUROCRYPT’98 (1998)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

DFC
Создатель	Jacques Stern^[en], Serge Vaudenay^[en]
Создан	1998
Опубликован	1998
Размер ключа	128/192/256 бит
Размер блока	128 бит
Число раундов	8
Тип	Сеть Фейстеля

DFC