DFC

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

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

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

[править | править код]
Шифрование
Расшифрование
«Запутывающая перестановка» (Confusion Permutation)

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

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

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

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

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

Этап 1: Вычисление

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

Раундовый ключ делится на две половины: и . Далее производится следующее вычисление:

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

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

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

Пусть и  — левая и правая части полученного по 32 бита каждая (обозначим это как ), и  — заданные константы длиной 32 и 64 бита соответственно, а  — функция, оставляющая крайних левых бит аргумента, тогда результат функции шифрования:

Таблица поиска (S-box)

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

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

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

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

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

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

.

Полученный разрезаем на 8 32-битных частей .

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

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

где  — заданные 64-битные константы.

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

Пусть  — функции шифрования, описанные в пункте 2, только с 4 раундами вместо 8, использующие для -го раунда раундовые ключи и соответственно. Тогда полагая что получаем искомые раундовые ключи:

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

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

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

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

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

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

Наименование Длина (бит) Назначение
64 Функция Шифрования, Этап 2
32 Функция Шифрования, Этап 2
64 Получение раундовых ключей, Шаг 2
64 Получение раундовых ключей, Шаг 2
256 Получение раундовых ключей, Шаг 1
Таблица поиска 64x32 Функция Шифрования, Этап 2

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

e = 2.b7e151628aed2a6abf7158…

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

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

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

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

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

Для удобства возьмем, что  — левая половина i-го раундового ключа K,  — правая половина. Если равна 0, то на выходе функции шифрования будет некая константа, независящая от . Следовательно, взяв , , равными 0, шифр становится уязвимым для distinguishing attack[англ.] (более подробно о такой атаке с примером[5]). Шанс появления таких ключей равен 2−192.

Следует отметить ещё одну особенность шифра, связанную с плохим выбором констант и . (см. «Раундовые ключи») Если , , , то получим , , . А значит

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

, где  — некая константа.

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

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

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

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

Атака «Photofinishing Attack»

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

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

Примечания

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