Dragon (шифр)

Dragon — поточный шифр, впервые представленный^[1] на ежегодной международной конференции ICISC в 2003 году. В апреле 2005 года, он был отправлен на конкурс eSTREAM, целью которого было выявление поточных шифров, пригодных для повсеместного использования в приложениях с большими требованиями по производительности.

Разработчиками Dragon являются Ed Dawson, Kevin Chen, Matt Henricksen, William Millan, Leonie Simpson, HoonJae Lee и SangJae Moon.

Введение

Устройство поточных шифров традиционно основано на действии регистров сдвига с линейной обратной связью, так как последние хорошо изучены и удовлетворяют общепринятым статистическим критериям. Нелинейность в гамме шифра может быть представлена либо действием нелинейного фильтра, либо нерегулярным тактовым сигналом схемы, либо и тем и другим. При аппаратной реализации, шифры работающие с битовыми потоками демонстрируют высокую производительность, но являются достаточно медленными при реализации в программном обеспечении. Шифры основанные на регистрах сдвига с линейной обратной связью и использующие малое число обратных связей могут быть уязвимы для атак, но увеличение числа последних может негативно повлиять на эффективность шифра. Кроме того надёжность шифров с линейной функцией изменения состояния подвергается сомнению при использовании алгебраических атак.^[2]

Шифры работающие со словами могут превосходить по производительности шифры ориентированные на работу с битами как при аппаратной, так и при программной реализации. Они шифруют в несколько раз больше данных за итерацию, чем шифры использующие однобитовые регистры сдвига с линейной обратной связью. При программной реализации они могут опережать даже быстрые блочные шифры, такие как AES практически на порядок^[3]. Несмотря на то, что достаточно просто измерить производительность шифров ориентированных на работу со словами, сложно точно оценить их надёжность.

Dragon был разработан с учётом требований как к производительности, так и к безопасности. Он использует регистр сдвига с нелинейной обратной связью вместе с нелинейным фильтром, чтобы генерировать гамму шифра в форме 64-битных слов. Dragon имеет производительность порядка нескольких гигабит в секунду и требует около 4 килобайт памяти.

Спецификация

Dragon может использоваться со 128-битными ключом и инициализирующим вектором или с 256-битными ключом и инициализирующим вектором. Данные версии называются Dragon-128 и Dragon-256 соответственно. Они работают практически идентично, за исключением процесса инициализации ключа.

Обе версии шифра Dragon построены с использованием единственного 1024-битного регистра сдвига с нелинейной обратной связью и 64-битной памяти M. Начальное состояние создается с использованием ключа и инициализирующего вектора при поддержке функции изменения состояния F. Функция изменения также используется при генерации потока ключей.

F-функция

Работа F-функции

Dragon-128 и Dragon-256 используют одну и ту же функцию F. F является обратимым отображением из 192 бит в 192 бита: она принимает 6 x 32 бит в качестве входных данных (обозначаемых a, b, c, d, e, f) и выдаёт 6 x 32 бит на выходе (обозначаемых a', b', c', d', e', f'). Сеть состоит из трех слоев: слой первоначального перемешивания, слой S-блоков, и слой окончательного перемешивания. Слои перемешивания используют сложение по модулю 2³² и сложение по модулю 2 (⊕). Слой S-блоков состоит из G- и H-функций, которые в свою очередь содержат 8 × 32 S-блоков.

G- и H-функции

G и H функции — нелинейные виртуальные 32 x 32 S-блоки, построенные из двух 8 x 32-битных S-блоков. 32 бита на входе разбиваются на четыре байта, х = x₀ ‖ x₁ ‖ x₂ ‖ x₃, где a ‖ b обозначает конкатенацию a и b.

{\begin{aligned}G_{1}\left(x\right)&=S_{1}\left(x_{0}\right)\oplus S_{1}\left(x_{1}\right)\oplus S_{1}\left(x_{2}\right)\oplus S_{2}\left(x_{3}\right)\\G_{2}\left(x\right)&=S_{1}\left(x_{0}\right)\oplus S_{1}\left(x_{1}\right)\oplus S_{2}\left(x_{2}\right)\oplus S_{1}\left(x_{3}\right)\\G_{3}\left(x\right)&=S_{1}\left(x_{0}\right)\oplus S_{2}\left(x_{1}\right)\oplus S_{1}\left(x_{2}\right)\oplus S_{1}\left(x_{3}\right)\\H_{1}\left(x\right)&=S_{2}\left(x_{0}\right)\oplus S_{2}\left(x_{1}\right)\oplus S_{2}\left(x_{2}\right)\oplus S_{1}\left(x_{3}\right)\\H_{2}\left(x\right)&=S_{2}\left(x_{0}\right)\oplus S_{2}\left(x_{1}\right)\oplus S_{1}\left(x_{2}\right)\oplus S_{2}\left(x_{3}\right)\\H_{3}\left(x\right)&=S_{2}\left(x_{0}\right)\oplus S_{1}\left(x_{1}\right)\oplus S_{2}\left(x_{2}\right)\oplus S_{2}\left(x_{3}\right)\\\end{aligned}}

Инициализация

Схема инициализации шифра Dragon

Для инициализации ключа регистр сдвига с нелинейной обратной связью разбивается на восемь 128-битных слов, обозначаемых W₀ … W₇. Инициализация проходит в две фазы.

Фаза 1:"Размножение" состояния шифра: Во время первой фазы начальное состояние 1024-битного регистра сдвига с нелинейной обратной связью и 64-битной памяти М «размножается» с использованием ключа (K) и инициализирующего вектора (IV).

Dragon-128 принимает 128-битный ключ и 128-битный IV и «размножает» состояние регистра сдвига с нелинейной обратной связью так, что (W₀ ‖ … ‖ W₇) = (K ‖ K^' ⊕ IV^' ‖ IV ‖ K ⊕ IV^' ‖ K^' ‖ K ⊕ IV ‖ IV^' ‖ K^' ⊕ IV), где штрих показывает, что старшую и младшую 64-битные половины поменяли местами.

Dragon-256 принимает 256-битный ключ и 128-битный IV и «размножает» состояние регистра сдвига с нелинейной обратной связью так, что (W₀ ‖ … ‖ W₇) = (K ‖ K ⊕ IV ‖ ~(K ⊕ IV) ‖ IV).

В обоих случаях 64-битная память М предварительно заполняется константным значением 0x0000447261676F6E, которое является ASCII представлением слова «Dragon».

Фаза 2:Перемешивание состояния шифра: Во время второй фазы, функция изменения состояния применяется 16 раз, чтобы перемешать содержимое регистра сдвига с нелинейной обратной связью и 64-битной памяти М. 128-битный аргумент функции F формируется, как линейная комбинация трёх слов регистра сдвига с нелинейной обратной связью, в точности a ‖ b ‖ c ‖ d = (W₀ ⊕ W₆ ⊕ W₇). Кроме того e ‖ f = M.

Схема тактируется таким образом, что W₇ пропускается в момент времени t, и поэтому W_i^t+1 = W_t^i-1, 0 ≤ i ≤ 7. 128-битное слово по обратной связи формирующее содержимое W₀^t+1 получается сложением по модулю 2 W₀^t₀ c (a^' ‖ b^' ‖ c^' ‖ d^'). Оставшиеся два 32-битных слова конкатенируются и используются для обновления памяти: e^' ‖ f^' = M.

Чтобы защититься от атак, которые требуют знания большого количества элементов потока ключей и против неизвестных будущих атак, для каждой пары K и IV может быть создано не больше 2⁶⁴ бит потока ключей.

Генерация потока ключей

Во время генерации потока ключей 1024-битный регистр сдвига с нелинейной обратной связью разделяется на 32 32-битных слова B_i, 0 ≤ i ≤ 31. В процессе также используется F-функция.

В каждой итерации, четыре 32-битных входных аргумента F выбираются из регистра сдвига с нелинейной обратной связью из слов B₀, B₉, B₁₆ и B₁₉. Оставшиеся два аргумента являются результатом сложения по модулю 2 слов B₃₀ и B₃₁ с M_L и M_R соответственно, где M_L и M_R младшее и старшее слова памяти M соответственно.

Регистр сдвига с нелинейной обратной связью сдвигается на два разряда, и B₀ и B₁ заполняются действием обратной связи с выходов F-функции b^' и c^' соответственно. 64-битное слово потока ключей z формируется конкатенацией a^' и e^' 64-битная память М работает в качестве счётчика в процессе генерации потока ключей и инкрементируется каждый цикл.

Реализация и производительность

Шифр Dragon был разработан с расчётом на возможность эффективной реализации как аппаратной, так и программной.

Программная реализация

Были произведены оценки производительности^[4], которые показывают, что Dragon достаточно эффективен как в терминах производительности, так и по затратам на память.

Аппаратная реализация

Реализация Dragon на аппаратном уровне позволяет достичь высокой степени параллелизма. Операции над шестью входными аргументами F-функции могут быть разделены на три группы, каждая из которых использует два аргумента. Предварительное перемешивание и заключительное перемешивание реализованы при помощи 32-битных модульных сумматоров. G- и H-функции были реализованы с помощью LUT- таблиц и операторов XOR. При производстве по технологии Samsung 0.13um ASIC, при тактовой частоте 2.6 GHz минимальная задержка составляет 2.774 нс при производительности 23 Gbps.

Для улучшения скорости работы аппаратной реализации была предложена специальная вычислительная структура^[5]. На устройстве ПЛИС фирмы Altera эффективная реализация Dragon достигает производительности 1.06 Gbps.

Криптоанализ

В 2005 году Hakan Englund и Alexander Maximov провели исследования Dragon на надёжность^[6], выявив в нём уязвимость. В этом же году авторы шифра опубликовали статью^[7], отрицающую возможность эффективной эксплуатации этой уязвимости. Однако в 2007 году Joo Yeon Cho и Josef Pieprzyk усовершенствовали ранее предложенную методику атаки^[8]. И хотя такая атака и является практически не осуществимой на практике, это не повысило репутации шифра.

Заключение

Пройдя через две фазы конкурса eSTREAM, шифр Dragon не прошёл в финал, уступив более сильным конкурентам.

См. также

Примечания

↑ Chen, K., Millan, W., Fuller, J., Simpson, L., Dawson, E., Lee, H., Moon, S.:Dragon: A Fast Word Based Stream Cipher. In: Park, C.-s., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 33-50. Springer, Heidelberg (2005) ([1] Архивная копия от 1 июля 2012 на Wayback Machine)
↑ Courtois, N.: Higher Order Correlation Attacks, XL Algorithm and Cryptanalysis of Toyocrypt. In: Lee, P., Lim, C. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 182—199. Springer, Heidelberg (2003)
↑ National Institute of Standards and Technology. Federal Information Processing Standards Publication 197 (2001)
↑ The eSTREAM Project — eSTREAM Phase 3 (неопр.). Дата обращения: 28 октября 2011. Архивировано 31 октября 2011 года.
↑ Lee, H., Moon, S.: Parallel Stream Cipher for Secure High-Speed Communications. Signal Processing 82(2), 137—143 (2002)
↑ Hakan Englund and Alexander «Attack the Dragon» (неопр.). Дата обращения: 28 октября 2011. Архивировано 27 мая 2011 года.
↑ Ed Dawson, Matt Henricksen, Willam Millan, and Leonie Simpson, «The Dragon Is Alive and Well»[2] Архивная копия от 27 мая 2011 на Wayback Machine
↑ Joo Yeon Cho and Josef Pieprzyk, «An Improved Distinguisher for Dragon» [3] Архивная копия от 27 сентября 2011 на Wayback Machine

Литература

Matt Robshaw^[англ.], Olivier Billet. New Stream Cipher Designs: The Estream Finalists (англ.). — Berlin: Springer, 2008.

Ссылки

Dragon: A Fast Word Based Stream Cipher — Описание шифра Dragon

[1] Chen, K., Millan, W., Fuller, J., Simpson, L., Dawson, E., Lee, H., Moon, S.:Dragon: A Fast Word Based Stream Cipher. In: Park, C.-s., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 33-50. Springer, Heidelberg (2005) ([1] Архивная копия от 1 июля 2012 на Wayback Machine)

[2] Courtois, N.: Higher Order Correlation Attacks, XL Algorithm and Cryptanalysis of Toyocrypt. In: Lee, P., Lim, C. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 182—199. Springer, Heidelberg (2003)

[3] National Institute of Standards and Technology. Federal Information Processing Standards Publication 197 (2001)

[4] The eSTREAM Project — eSTREAM Phase 3 (неопр.). Дата обращения: 28 октября 2011. Архивировано 31 октября 2011 года.

[5] Lee, H., Moon, S.: Parallel Stream Cipher for Secure High-Speed Communications. Signal Processing 82(2), 137—143 (2002)

[6] Hakan Englund and Alexander «Attack the Dragon» (неопр.). Дата обращения: 28 октября 2011. Архивировано 27 мая 2011 года.

[7] Ed Dawson, Matt Henricksen, Willam Millan, and Leonie Simpson, «The Dragon Is Alive and Well»[2] Архивная копия от 27 мая 2011 на Wayback Machine

[8] Joo Yeon Cho and Josef Pieprzyk, «An Improved Distinguisher for Dragon» [3] Архивная копия от 27 сентября 2011 на Wayback Machine

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]