SOSEMANUK

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

SOSEMANUK – синхронный поточный шифр, разработанный в ноябре 2004 года группой французских ученых во главе с Комом Берба (фр. Côme Berbain)[1]. В апреле 2008 года стал одним из финалистов проекта eStream по профилю 1 (высокоэффективные поточные шифры для программной реализации)[2]. Согласно портфолио проекта eStream, Sosemanuk представляет собой полностью свободное программное обеспечение с открытым исходным кодом, которое может быть использовано для любых целей, включая коммерческие[3].

Аннотация[править | править код]

В основе Sosemanuk лежит поточный шифр SNOW 2.0 и усеченный вариант блочного шифра SERPENT. Его длина ключа варьируется между 128 и 256 битами, а для инициализации используется 128-битное начальное значение (англ. initial value). Как утверждают авторы шифра, любая длина ключа обеспечивает 128-битную безопасность.

Шифр устойчив ко всем известным видам атак. Самая успешная атака на Sosemanuk оценивалась 2138 порядком сложности, что, тем не менее, хуже заявленной сложности в 128 бит[3].

В реализации шифра Sosemanuk были исправлены некоторые структурные недостатки SNOW 2.0, а так же увеличена производительность за счет уменьшения размера внешних и статических данных.

Структура алгоритма[править | править код]

Как и поточный шифр SNOW, алгоритм Sosemanuk использует два основных понятия: регистр сдвига с линейной обратной связью (LFSR) и конечный автомат (FSM). Кроме того, шифр использует два примитива из алгоритма SERPENT: serpent1 и serpent24.

Serpent1 - один раунд SERPENT, без смешивания с ключом и линейного преобразования. Представляет собой использование таблицы подстановок (S-box), при этом входные 128 бит, разбитые на четыре 32-битных слова, преобразуются в выходные четыре 32-битных слова.

Serpent24 - алгоритм SERPENT, использующий 24 раунда из 32. Последний раунд является полным, при этом включает в себя линейное преобразование и XOR с 25-м раундовым ключом.В Sosemanuk используется для инициализации в режиме шифрования.

Регистр сдвига с линейной обратной связью[править | править код]

LFSR algorithm

Sosemanuk использует линейный регистр сдвига длины 10 над конечным 32-битным полем .

В начальный момент времени происходит инициализация регистра сдвига 32-битными значениями . Затем, на каждом шаге вычисляется новое значение по формуле:

.

Обратная связь регистра сдвига задается многочленом:

Здесь - корень примитивного многочлена над полем :

- корень примитивного многочлена над полем :

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

Выходное преобразования Sosemanuk

Конечный автомат[править | править код]

Sosemanuk использует конечный автомат с 64 битами памяти, что соответствует двум 32-битным регистрам и . Он принимает на вход несколько значений, полученных с помощью LFSR, обновляет регистры, после чего выдает 32-битное значение по схеме:

- последний значащий бит (используется little-endian нотация).

(шестнадцатеричная запись первых десяти знаков числа π)

- побитовый циклический сдвиг.

Выходное преобразование[править | править код]

К четырем выходным значениям конечного автомата применяется алгоритм Serpent1, после чего к результату и соответствующим значениям, полученным из регистра сдвига, применяется операция XOR:

Схема шифрования[править | править код]

Схема шифрования

Для получения выходных значений используется связка LFSR и FSM. В начальный момент времени LFSR инициализируется значениями , а в регистры FSM записываются значения и . В момент времени выполняются следующие действия:

  1. Обновление FSM: вычисляются значения , и , исходя из известных , , , и .
  2. Обновление LFSR: вычисляется , значение переходит во внутренний буфер, регистр сдвига сдвигается.

Каждые четыре шага из промежуточных значений , , , и значений внутреннего буфера , , , посредством применения Serpent1 и XOR вычисляются итоговые значения . Авторы шифра рекомендуют шифровать группы по четыре байта, используя при этом little-endian порядок байтов для увеличения производительности.

Расписание ключей и введение начального значения[править | править код]

В шифре Sosemanuk процесс инициализации происходит в два этапа:

  • Задается расписание ключей (key schedule), в котором секретный ключ не зависит от начального значения
  • Вводится начальное значение (IV injection), при этом используется заданное расписание ключей и IV. Таким образом, происходит инициализация внутреннего состояния поточного шифра.

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

Расписание ключей шифра Sosemanuk задается с помощью Serpent24, который предоставляет 25 128-битных раундовых ключей. Эти ключи идентичны первым 25 ключам, полученным из расписания ключей SERPENT. Несмотря на то, что можно задать ключ любой длины от 128 до 256, шифр обеспечивает лишь 128-битную безопасность, вследствие чего длина ключа 128 считается стандартной.

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

Для введения IV используются выходные значения двенадцатого, восемнадцатого и двадцать четвертого раунда Serpent24.

- выходные значения 12-го раунда

- выходные значения 18-го раунда

- выходные значения 24-го раунда

Начальные значения LFSR и FSM:

Известные атаки[править | править код]

Разработчиками шифра были рассмотрены следующие виды атак:

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

Атака компромисса времени и данных (англ. Time-memory-data tradeoff attack) основана на предположении, что злоумышленнику известен алгоритм шифрования и выходное значение. Авторы шифра рассматривают случай восстановления пары «ключ - начальное значение». В связи с 128-битной длиной ключа и такой же длиной начального значения сложность такой атаки оценивается 2128 количеством операций.

«Предполагай и определяй»[править | править код]

Атака «Предполагай и определяй» (англ. Guess and determine attack) основана на утверждении, что, предполагая значения нескольких ключей, злоумышленник может восстановить все внутреннее состояние. Авторы шифра рассматривают данный вид атаки в предположении, что злоумышленник получает значения шести 32-битных ключей. В этом случае сложность атаки составляет 256 бит.

Корреляционная атака[править | править код]

По утверждению авторов, известные корреляционные атаки (англ. Correlation attacks) на шифр SNOW не имеет смысла применять к шифру Sosemanuk, в связи с тем, что линейные соотношения входных и выходных данных не сохраняются после применения алгоритма Serpent1.

Различающая атака[править | править код]

В описании шифра рассмотрены известные на момент разработки различающие атаки (англ. Distinguishing attacks) на шифр SNOW. В явном виде они не могут быть применены к Sosemanuk из-за сложности подбора маски после применения Serpent1.

Алгебраическая атака[править | править код]

Разработчики шифра считают, что ни одна из известных на момент разработки алгебраических атак (англ. Algebraic attacks) не применима к шифру ввиду невозможности явно вычислить алгебраическую имунность (англ. algebraic immunity) выходных функций от входных значений. 

После того, как шифр стал широко известен в криптографическом сообществе, в литературе было опубликовано несколько новых атак на Sosemanuk. Тем не менее, изначально заявленная сложность в 128 бит так и не была взломана.

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

  1. Sosemanuk Algorithm forencryption and decryption Video on Demand (VoD) (PDF Download Available) (англ.). ResearchGate. Проверено 14 октября 2017.
  2. The eSTREAM portfolio page (англ.). www.ecrypt.eu.org. Проверено 14 октября 2017.
  3. 1 2 The eSTREAM Project - eSTREAM Phase 3. www.ecrypt.eu.org. Проверено 14 октября 2017.

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

"Sosemanuk, a fast software-oriented stream cipher", описание разработчиков