Интегральная атака против блочного симметричного шифра Crypton (стр. 3 из 11)

- Nr-1 циклов;

- заключительного цикла.

На псевдо-Си это выглядит следующим образом:

Rijndael (State, CipherKey)

{

KeyExpansion(CipherKey, ExpandedKey); // Расширениеключа

AddRoundKey(State, ExpandedKey); // Добавлениецикловогоключа

For ( i=1 ; i<Nr ; i++) Round(State,ExpandedKey+Nb*i); // циклы

FinalRound(State, ExpandedKey+Nb*Nr); // заключительныйцикл

}

Если предварительно выполнена процедура расширения ключа, то Rijndael будет выглядеть следующим образом:

Rijndael (State, CipherKey)

{

AddRoundKey(State, ExpandedKey);

For ( i=1 ; i<Nr ; i++) Round(State,ExpandedKey+Nb*i);

FinalRound(State, ExpandedKey+Nb*Nr);

}

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

1.2.2 Анализ симметричного блочного шифра DEAL

DEAL (DataEncryptionAlgorithmwithLargerblocks - Алгоритм Шифрования Данных с Укрупненными блоками) является 128-и битным блочным шифром с размерами ключа 128, 192 и 256 бит, что далее здесь будет обозначаться DEAL-128, DEAL-192 и DEAL-256 соответственно [12]. Все версии могут использоваться в любом из четырех стандартных режимах DES'a. Мы начнем с описания работы DEAL в режиме ECB. Пусть С = Е_В(А) означает зашифрованное DES значение 64-х битного А на ключе В, и пусть Y = EA_Z(X) означает зашифрование DEAL 128-и битного X на ключе Z. Открытый текст Р разделяется на блоки Pi по 128 бит каждый, P = P₁, P₂, …, Р_n. Расписание ключей принимает ключ К и возвращает r ключей DESRK_i, где i = 1, … , r, как описано ниже. Обозначим X^L и X^R левую и правую части X соответственно. Шифр-текст вычисляется следующим образом. Положим X₀^L = P_i^L, X₀^R = Р_i^Rи вычислим для j= 1, … ,r

X_j^L=E_RKj(X^L_j-1) X^R_j-1 (1.9)

X^R_j= X^L_j-1(1.10)

Рисунок 1.10: ОдинциклDEAL.

ПоложимC_i =X_r^L ||X_r^R. На рис. 1.10 показан один цикл DEAL. Для DEAL-128 и DEAL-192 мы предлагаем использовать 6 циклов, т. е. r = 6. Однако, как мы увидим ниже, этого может быть недостаточно для DEAL-256, здесь предлагается использовать 8 циклов, r = 8. Представляется, что версия с размером ключа 256 бит используется только когда требуется особенно сильное зашифрование.

Заметим, что последнем цикле DEAL половины блока местами меняются[13]. Причина в следующем: правая часть шифр-текста С_iне шифруется в последнем цикле i-oro зашифрования, и только левая часть входа i + 1-ого зашифрования (который равен C_iP_i+l) шифруется на последнем цикле. Т. о. правая часть Ci осталась бы не перезашифрованной два цикла. Это может дать поле деятельности злоумышленникам, тем более, что шифр состоит всего из 6-и или 8-и циклов. Заметим, что аналогичное свойство есть и у DES в режиме CBC. Правда, похоже это труднее было бы использовать, ведь у DES 16 циклов. Позволим себе отметить, что обмен местами правой и левой частей на последнем цикле не влияет на стойкость блочного шифра в режиме ECB [14].

Итак, обозначим блоки открытого текста по 128 бит P₁, P₂, …, P_n и C_i, С₂, ,… , С_п -соответствующие им блоки шифр-текста. Тогда:

С_i= EA_K(C_i-lP_i),(1.11)

где С₀ - начальное значение.

В DES начальная перестановка IP первой применяется к открытому тексту, и аналогично перед выходом шифр-текст пропускается через обратную к ней IP^-1. Возможно увеличить скорость DEAL, если убрать из используемого DESэти начальную и конечную перестановки. Легко показать, что для получения корректной реализации DEAL, IP должна быть приложена к обоим частям открытого текста перед зашифрованием, aIP^-1 - к обоим частям шифр-текста.

На вход расписания ключей подается s ключей DES, Ki, ,… , K_s, для s = 2, 3, 4, каждый по 64 бит (включая 8 проверочных бит, старших бит каждого байта), на выходе получается r ключей DES, RK_j. Мы используем общий метод, приложимый ко всем трем размерам ключа. Во-первых расширяем s ключей до r ключей, путем повторения и с новой константой для каждого нового повторения. Зашифровываем расширенный список ключей DES'om в режиме CBC с фиксированным ключом и нулевым начальным значением. Из полученных блоков шифр-текста и формируются подключи RKi. Далее мы приводим точные определения каждого из расписаний ключей, здесь К = 0x1234 5678 90abcdefx (шестнадцатеричное число) - фиксированный ключ DES. В DEAL-128 подключи генерируются следующим образом:

RK₁ = E_K (К₁),

RK₂ = E_K (К₂RK₁),

RK₃=E_K(K_l (1)RK₂),

RK₄ = E_K(К₂ (2)RK₃),

RK₅=E_k(k_i (4)RK₄),

RK₆=E_k(k₂ (8)RK₅),(1.12)

где (i) - 64-х битное целое число, в котором i - 1-ый бит (индексация идет с 0) установлен, а остальные очищены. Например, (1) может быть представлено как шестнадцатеричное "0x8000 0000 0000 0000_х".

В DEAL-192 подключи генерируются следующим образом:

RK₁ = E_K (К₁),

RK₂ = E_K (К₂RK₁),

RK₃=E_K(K₃RK₂),

RK₄=E_k(k_i (1)RK₃),

RK₅=E_k(k₂ (2)RK₄),

RK₆ =Е_К(К₃ (4)RK₅).(1.13)

Эти версии расписания ключей требуют 6 расписаний ключей DES и 6 зашифрований DES на фиксированном ключе. Подключи нужно сгенерировать только один раз, если их впоследствии сохранить.

В DEAL-256 подключи генерируются следующим образом:

RK₁ = E_K (К₁),

RK₂=E_K(К₂RK₁),

RK₃=E_K(K₃RK₂),

RK₄=E_k(K₄RK₃),

RK₅=E_k(K₂ (1)RK₄),

RK₆=E_K(К₂ (2)RK₅),

RK₇ =Е_К(К₃ (4)RK₆), RK₈=E_k(K₄ (8)RK₇).(1.14)

Эта версия расписания ключей требует 8 расписаний ключей DES и 8 зашифрований DES на фиксированном ключе. Подключи нужно сгенерировать только один раз, если их впоследствии сохранить.

Заметим, что для всех версий расписания ключей 64-х битные величины RKi используются как ключи DES, поэтому биты проверки четности RKi не используются в i-ом цикле. Однако, все 64 бита RKi, как выхода шифрования на ключе К, используются при генерации следующего подключа.

Принципы разработки расписания ключей, во-первых, состоят в том, чтобы подключи зависели от наибольшего числа битов основного ключа, но не требовали при этом много работы, во-вторых, при вводе s основных ключей размером по 64 бит, любые s последовательных подключей должны иметь энтропию s · 56 бит, и, наконец, не должно быть очевидно зависимых и слабых ключей и не должно остаться свойство дополнительности. Заметим, что последние две проблемы присутствуют и в DES, и -все три - в тройном DES. Мы заметили, что если основные ключи размером по 64 бита каждый, может найтись пара ключей, генерирующих одинаковые множества подключей. Однако, число таких ключей, похоже, настолько невелико, что не представляет угрозы DEAL'y, применяемому для шифрования.

Смещения (i) введены для предотвращения появления слабых ключей. Если бы их не было, существовали бы ключи, для которых все подключи были равны. Например, для DEAL-128 ключи K1 = K2 = D_k(0) сгенерировали бы 6 подключей со значением 0. Смещения и шифрование на фиксированном ключе предотвращают появление слабых и зависимых ключей и свойства дополнительности.

Заметим, что если бит проверки четности используется в каждом байте основного ключа, действующие размеры предложенных ключей составляют 112, 168 и 224 бит соответственно.

Что можно сказать о стойкости DEAL в целом? Прежде всего, заметим[15], что для DEAL простая атака meet-in-the-middle (встретить по середине), аналогичная такой атаке на двойной DES, отыщет ключи за время порядка 2¹⁶⁸ зашифрований для шести, и 2²²⁴ зашифрований для восьми циклов DEAL соответственно, независимо от расписания ключей. Именно поэтому, предлагается в DEAL-256 производить по крайней мере 8 циклов зашифрования. Для DEAL-128 исчерпывающий поиск ключа займет время порядка 2¹¹² зашифрований.

Самая быстрая из известных атак по нахождению ключа на DEAL (с шестью циклами) - общая атака на 6-и цикловые Фейстелевы шифры, в приложении к DEAL, она требует порядка 2¹²¹ зашифрований DES, используя порядка 2⁷⁰ выбранных открытых текстов, для любого расписания ключей. В дальнейшем определим разность между двумя последовательностями бит, как побитное XOR.

В конце этого раздела подведем итог особенностям DEAL.

-DEAL имеет размер блока 128 бит и размер ключа 128, 192 или 256бит (действующий размер, соответственно, - 112, 168 или 224 бита).

- атака по подобранному шифр-тексту требует порядка 2⁶⁴ блоков шифр-текста.

- нет известных, вероятных атак.

- DEAL с шестью циклами имеет скорость, аналогичную скорости тройного DES.

- DEAL может использоваться в стандартных режимах работы.

- DEALможет быть реализован на имеющемся аппаратном и программном обеспечение DES.

- нет очевидно слабых ключей и устранено свойство дополнительности.

Наконец, позволим себе заметить, что ввиду довольно сложного расписания ключей, DEAL не практично использовать в случайных функциях.

Собственно результаты стойкости DEAL:

- Существуют эквивалентные ключи для DEAL-192 и DEAL-256.

Алгоритм нахождения требует около шести шифрований DES, чтобы найти набор из 256 эквивалентных ключей для DEAL-192, и восемь шифрований DES, чтобы найти 256 эквивалентных ключей для DEAL-256.

- Существуют эквивалентные ключи для DEAL-128 и алгоритм их нахождения, требующий около 2⁶⁴ вычислений для нахождения пары эквивалентных ключей.

- Атака математически-связанных ключей (related-keyattack) на DEAL-192 и DEAL-256, требующая три блока открытого текста, под 2³³ ключами с точным соответствием, 3*2⁴⁵ байт памяти и около 2¹³⁷ шифрований DEAL, чтобы найти последние два цикловых подключа для DEAL-192 и DEAL-256. (С большим количеством памяти это можно сделать быстрее).