KCipher-2

KCipher-2 (K2 Stream Cipher)
Создатель	KDDI R&D Laboratories, Inc.
Опубликован	2007
Размер ключа	128 бит
Тип	Потоковый шифр

KCipher-2 (обновленная версия K2 Stream Cipher) — высокопроизводительный симметричный потоковый шифр (генератор потокового ключа), разработанный тремя японскими криптографами: Toshiaki Tanaka, Shinsaku Kiyomoto, Kouichi Sakurai. Шифр использует 2 независимых входных параметра, 128-битовый ключ и 128-битовый инициализирующий вектор. Использование данного алгоритма KCipher-2 позволяет повысить уровень защищенности в ряде сервисов, таких как мультимедийные сервисы и услуги широкополосной связи.

KCipher-2 может быть эффективно реализован в программном обеспечении для быстрого шифрования и расшифровки, благодаря своей несложной конструкции. Используются только 4 простые операции: исключающее «ИЛИ», сложение, сдвиг и таблицы поиска. Если алгоритм реализован в оборудовании, то внутренние вычисления могут быть распараллелены для достижения большей эффективности. Более того, так как внутреннее представление исчисляется всего лишь сотнями бит, KCipher-2 подходит для условий с ограниченными ресурсами.

История

Шифр впервые был опубликован как «K2 Stream Cipher» на специальной секции «Современное состояние потоковых шифров» (SASC) в 2007 году, организованной Европейской сетью передового опыта в области криптологии (ENCRYPT). С тех пор как алгоритм шифра был опубликован, его безопасность и эффективность были тщательно оценены посредством академических и промышленных исследований. В 2012 году KCipher-2 был включен в международный стандарт потоковых шифров ISO/IEC 18033-4, и в марте 2013 года Японское Министерство внутренних дел и Коммуникаций совместно с Министерством Экономики, Торговли и Промышленности объявили о включении шифра в список рекомендованных электронным правительством шифров. На момент публикации RFC 7008, август 2013 г., уязвимостей не было обнаружено. KCipher-2 используется в промышленных программах, особенно в мобильном мониторинге здоровья и сервисах диагностики в Японии.

Достигнутая производительность

Скорости свыше 5 Гб/с были достигнуты на ПК. KCipher-2 может расшифровать фильм размером в 4,7 ГБ за 8 секунд, в то время как американскому стандарту AES потребовалось бы 1,5 минуты.

Скорости свыше 380 Мб/с достигнуты на смартфонах, оборудованных ОС Android. Расшифровка 400 видео файлов (размером 100 КБ каждый) происходит приблизительно за 1 секунду, что в 7-10 раз быстрее AES.

Уровень загруженности центрального процессора в 0,5 % был достигнут при расшифровки видео, эквивалентного 1seg, на мобильном телефоне при воспроизведении в режиме реального времени, что являлось невозможным при существующих методах.

Алгоритм конфигурации не зависит от архитектуры центрального процессора. Он может обеспечить достаточную производительность в различных средах.

Основные характеристики

• 128-битный ключ
• 128-битный инициализирующий вектор
• 640-битное состояние
• Шестнадцать 32-битных регистров (РСОС-А, РСОС-В)
• Четыре 32-битные внутренних регистра памяти в нелинейной функции
• 64-битный ключевой поток в одном цикле
• Максимальное число циклов без повторной инициализации — $2^{58}$ ($2^{64}$ бит ключевого потока)

Обоснование выбора модели

Основные потоковые шифры используют несколько независимых регистров сдвига с линейной обратной связью (РСЛОС) совместно с нелинейными функциями для генерации потокового ключа. Некоторые потоковые шифры используют общую нелинейную функцию для неравномерного тактирования одного или более РСЛОС. Описаны разнообразные управляющие тактами потоковые шифры и атаки на них.

Механизм контроля тактов потоковых шифров обычно либо контролирует тактирование РСЛОС, либо прореживает или сужает вывод. Такое управление тактами ухудшает производительность потокового шифра, потому что некоторые выходные биты отбрасываются. Если применить сжатие к потоковому шифру с пословной обработкой, то производительность заметно ухудшится. Бит-ориентированный механизм тактового контроля также малоэффективен для улучшения РСЛОС. С другой стороны, динамическая обратная связь для РСЛОС является эффективным методом улучшения безопасности потоковых шифров.

KCipher-2 — это потоковый шифр, который оперирует словами и имеет действенную динамическую обратную связь для неравномерного тактирования. Основная идея модели — скорректировать операцию смешения во время обновления состояния. Полиномы с обратной связью для РСЛОС с пословной обработкой описываются коэффициентами; умножение входного слова на коэффициент означает смешение слов. Типичным примером является РСЛОС шифра SNOW2.0[3]. В общем случае полином с обратной связью — примитивный полином. Создатели применяют неравномерное тактирование для смешивающей операции, и модификация вызывает лишь небольшое ухудшение скорости шифрования и расшифровки. Другими словами, по крайней мере один РСОС неравномерно тактируется, чтобы динамически модифицировать функцию обратной связи для контроллера с динамической обратной связью, который получает выходные данные от других РСОС. Например функция с обратной связью определённая как ${s_{t+a}}=\alpha _{0}^{(0,\;1)}s_{t+b}\oplus \alpha _{1}^{(0,\;1)}s_{t+c}\oplus \alpha _{2}^{(0,\;1)}s_{t+d}$, где (0,1) выбираются контроллером с динамической обратной связью. РСОС, контролируемый таким контроллером, называется регистром сдвига с динамической обратной связью (РСДОС). Механизм управления динамической обратной связью улучшает безопасность потокового шифра, потому что заменяет детерминированные линейные повторы некоторых регистров на вероятностные. Это эффективно защищает от ряда атак. Главное, KCipher-2 достигает не только высокой производительности подобно потоковым шифрам, основанным на РСЛОС, но и высокой защищенности.

Скорость генерации потокового ключа KCipher-2 составляет 4.97 циклов/байт в серии Pentium 4. Таким образом, данный шифр составляет конкуренцию другим потоковым шифрам из списка CRYPTREC. К тому же, KCipher-2 разрабатывался с учётом двух атак на SNOW2.0, алгебраической и дифференциальной, и имеет к ним бо́льшую устойчивость. Фактически, до сих пор не обнаружено атак на KCipher-2, меньших $2^{256}$ операций. В итоге KCipher-2 достигает высшей защищенности чем существующие потоковые шифры.

Компоненты и функции KCipher-2

KCipher-2 состоит из двух типов регистров сдвигов с обратной связью (РСОС), РСОС-А (5 регистров) и РСОС-В (11 регистров), нелинейной функции с четырьмя внутренними регистрами R1, R2, L1, L2 и управляющего устройства динамической обратной связи. РСОС-В — регистр сдвига с динамической обратной связью. Размер каждого регистра составляет 32 бита.

Оценка безопасности шифра

К. Ю. Лювен провёл криптографическую оценку шифра K2. Оценка основана на попытках атаковать К2 различными способами, соответствующими передовым достижениям криптоанализа потоковых шифров. Его работа включала анализ линейных атак, алгебраических атак, корреляционных и быстрых корреляционных атак, дифференциальных атак, включающих установку связанных ключей, атак «предполагать и определять», статистических свойств, периодичности и дифференциальных атак.

Относительно линейных атак был применен метод линейной маскировки версии К2, игнорирующий эффект динамической обратной связи. Лучшая найденная корреляция использует 13 линейных приближений и составляет $2^{-156}$, что не допускает успешных атак. В алгебраическом анализе изучены структура и количественные свойства полученных систем уравнений, и утверждается, что алгебраические атаки неосуществимы. Анализ в отношении корреляционных и быстрых корреляционных атак (также не принимая во внимание контроллер динамической обратной связи) показал, что данный подход безуспешен. Дифференциальный анализ (в предположении, что отсутствует контроллер динамической обратной связи и сложение по модулю заменено на исключающее «ИЛИ»), включающий атаку на связанном ключе, связанном инициализирующем векторе, а также сочетание этих атак, полагает, что К2 может быть устойчивым против дифференциальных атак. Подходы к байтово- и словесно-ориентированным атакам «предполагать и определять» дали результат сложностью $2^{320}$, откуда следует, что эти методы неприменимы к К2. Что касается рассмотрения периодичности, коротких периодов в К2 не было найдено. Статистические тесты не обнаружили никаких структурных недостатков в модели К2. Анализы также показали, что К2 также обеспечивает хорошую устойчивость против дифференциальных атак по модулю n.

Таким образом, в К2 уязвимостей не было обнаружено и шифр считается устойчивым.

Интеллектуальная собственность и лицензии

Всё интеллектуальное имущество, связанное с KCipher-2, принадлежит корпорации KDDI. Эксперты CRYPTREC могут использовать KCipher-2 без лицензионных отчислений. KCipher-2 будет обеспечен любой правительственной организации по умеренной цене и разумным условиям.

Продукты и системы KCipher-2

Корпорация KDDI R & D Laboratories произвела пакет программ для разработки приложений (SDK) для KCipher-2. Данный шифровальный алгоритм используется в следующих системах/приложениях:

• Система мобильной связи государственного учреждения (2000 лицензий)
• Локационная система управления государственного учреждения (5000 лицензий)
• ПО для рабочих групп на базе Интернет-технологий (1000 лицензий)
• Мультимедийный проигрыватель для потребительских приложений (около миллиона пользователей)

Версии шифра

Дата	Версия	История изменений
Январь 2007	K2 Ver.1.0[6]	Первая публикация на международной конференции.
Июль 2007	K2 Ver.2.0[7]	Шаг загрузки ключа в процессе инициализации был изменён, чтобы более эффективно распространять ключ и инициализирующий вектор во внутреннее состояние.
2008	KCipher-2 Ver.2.0	Было изменено только имя шифра с «K2» на «KCipher-2».

Литература

• Впервые опубликован: Kiyomoto, S., Tanaka, T., and Sakurai, K., «A Word-Oriented Stream Cipher Using Clock Control», In SASC 2007 Workshop Record, pp.260-274, January, 2007
• Kiyomoto, S., Tanaka, T., and Sakurai, K., «K2: A Stream Cipher Algorithm Using Dynamic Feedback Control», In Proc. of SECRYPT 2007, pp.204-213, July, 2007
• Kiyomoto, S., Tanaka, T., and Sakurai, K., «K2 Stream Cipher», Communications in Computer and Information Science, E-business and Telecommunications, 4th International Conference, ICETE 2007, Barcelona, Spain, July 28-31, 2007, Revised Selected Papers, pp. 214—226 (недоступная ссылка)
• «Stream Cipher KCipher-2» (February 1, 2010), Specification of cipher in the e-Government Recommended Ciphers List
• Matt Henricksen, Wun She Yap, Chee Hoo Yian, Shinsaku Kiyomoto, and Toshiaki Tanaka, «Side-Channel Analysis of the K2 Stream Cipher», ACISP 2010 Proceedings of the 15th Australasian conference on Information security and privacy, pp. 53-73 (недоступная ссылка)
• Andrey Bogdanov, Bart Preneel, and Vincent Rijmen, «Security Evaluation of the K2 Stream Cipher», Version 1.1 — 7 March 2011
• Priemuth-Schmid, D., «Attacks on Simplified Versions of K2», Proc. SIIS 2011, LNCS 7053, pp. 117–127.
• Request for Comments: 7008, «A Description of the KCipher-2 Encryption Algorithm», August 2013
• Описание шифра на сайте разработчика