DFC

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Шифрование
Расшифрование

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

Общая структура[править | править исходный текст]

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

Функция шифрования [2][4][править | править исходный текст]

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

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

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

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

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

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

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

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

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

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][править | править исходный текст]

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

Шаг 1[править | править исходный текст]

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

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

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

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

Шаг 2[править | править исходный текст]

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

OA_{1}=PK_{1}|PK_{8};
OB_{1}=PK_{5}|PK_{4};
EA_{1}=PK_{2}|PK_{7};
EB_{1}=PK_{6}|PK_{3};

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

OA_{i}=OA_{1}\oplus KA_{i-1};
OB_{i}=OB_{1}\oplus KB_{i-1};
EA_{i}=EA_{1}\oplus KA_{i-1};
EB_{i}=EB_{1}\oplus KB_{i-1};

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

Шаг 3[править | править исходный текст]

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

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

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

Если i — нечетное, то:

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

Если i — четное, то:

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

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

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

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

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

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

e = 2.b7e151628aed2a6abf7158…

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

trunc_{2144} (EC)=RT_{0}|RT_{1}|RT_{2}|\ldots|RT_{63}|KC|KD
~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 06cbbffea 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 основана на декорреляционном методе[1], разработанном Сержом Ваденэ, с доказуемой стойкостью к известным криптографическим атакам. Однако уже существуют аналитические результаты, показывающие обратное.

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

Для удобства возьмем, что LK_i — левая половина i-го раундового ключа K, RK_i — правая половина. Если RK_i равна 0, то на выходе функции шифрования Z_{K_i} \left( X \right) будет некая константа, независящая от X. Следовательно, взяв LK_2, LK_4, LK_6 равными 0, шифр становится уязвимым к distinguishing attack (англ.) (более подробно о такой атаке с примером[5]). Шанс появления таких ключей равен 2−192.

Следует отметить еще одну особенность шифра, связанную с плохим выбором констант KA_i и KB_i. (см. «Раундовые ключи») Если KA_3  = KB_3  = 0, KA_2  = KA_4, KB_2  = KB_4, то получим OA_1  = OA_3 , OA_2  = EA_2  = 0, OA_2  = OA_4  = 0. А значит

Enc_{OK\left( K \right)} \left( {X_L |X_R } \right) = X_R |X_L
Enc_{EK\left( K \right)} \left( {X_L |X_R } \right) = X_R |X_L

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

DFC_K(U|V)=(V \oplus C)|(U \oplus C), где C — некая константа.

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

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

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

Атака «Photofinishing Attack»[править | править исходный текст]

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

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

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