SOSEMANUK

Sosemanuk - быстрый программно-ориентированный поточный шифр

Аннотация

Sosemanuk является новым симметричным ПО – ориентированным потоковым шифром, согласно Profile 1 "ECRYPT call for stream cipher primitives". Длина ключа колеблется от 128 до 256 бит. Начальное значение устанавливается объёмом 128 бит. Как утверждается, любая длина ключа достигает 128-битной защиты. Шифр Sosemanuk использует как основные принципы из потокового шифра SNOW 2.0 так и некоторые преобразования выведенные из блочного шифра SERPENT. Sosemanuk нацелен на улучшение SNOW 2.0 как в смысле безопасности так и смысле эффективности. В частности, он использует быструю IV-setup процедуру. Так же необходимо снижение числа статических данных в пользу улучшения производительности на нескольких архитектурах(платформах).

Введение

Шифр Sosemanuk использует как основные принципы потокового шифра SNOW 2.0 [10] («Snow» – англ. «снег»), так и некоторые трансформации(преобразования), выведенные из блочного шифра SERPENT [2] («SERPENT» – англ. «змея»). По этой причине его название должно быть связано и со змеёй, и со снегом. Однако хорошо известно, что снежных змей не существует, так как змеи либо засыпают, либо перебираются в тёплые края на время зимы. Кроме того, Sosemanuk – популярный вид спорта, распространенный среди племён Восточной Канады. Идея игры состоит в метании деревянной палки вдоль снежного берега настолько, насколько это возможно. Название происходит из наречия народов и содержит сравнение палки на снегу со змеёй. «Kwakweco-cime win» является одним из названий подобной игры, но оно не звучит соответствующе для названия шифра.

Потоковый шифр Sosemanuk – новый симметричный потоковый шифр для ПО приложений. Длина ключа колеблется от 128 до 256 бит. Как утверждается, любая длина ключа достигает 128-битной защищённости. В его основе лежит конструкция SNOW 2.0, которая очень элегантна и достигает очень большой пропускной способности на Pentium 4. Шифр Sosemanuk нацелен на улучшение SNOW 2.0 в двух отношениях. Во-первых, он избегает некоторые структурные свойства, которые являются потенциальными недостатками, даже если шифр SNOW 2.0 с 128-битным ключом устойчив перед всеми известными видами атак. Во-вторых, эффективность улучшается на нескольких архитектурах(платформах) с помощью уменьшения размера внутреннего состояния, что позволяет обеспечить более прямое отображение данных в регистрах процессора. Sosemanuk так же требует уменьшения количества статических данных; это уменьшение даёт большую производительность на нескольких архитектурах(платформах). Другое преимущество шифра Sosemanuk состоит в следующем: процедура генерации ключа основывается на уменьшенной версии хорошо известного блочного шифра SERPENT, улучшающего классические процедуры как в плане эффективности, так и защищённости.

Обозначения

SERPENT и его производные

SERPENT [2] – является блочным шифром, соответствующий AES (Advanced Encryption Standard). SERPENT работает над блоками из 128 бит, которые разделены на четыре 32-битные слова, которые объединяются в так называемые “bitslice” («slice» - англ.«часть/доля») раздел. Таким образом, SERPENT может быть определён как шифр, работающий над четвёрками 32-битными словами. Пронумеруем SERPENT’ входные и выходные четвёрки от 0 до 3, и запишем их в порядке: (Y3, Y2, Y1, Y0). Y0 является минимальным значимым словом, и содержит минимальные значимые биты из 32х 4-битных слов, входящих в S-ячейку шифра SERPENT. В то время как SERPENT-выход записывается в 16 бит, значения Yi записываются прямым порядком байт(последний значимый байт - первый), и Y0 выводится первым, далее Y1, и так далее. Из SERPENT мы определяем два примитива, Serpent1 и Serpent24.

Serpent1

Раунды SERPENT состоят из (именно в следующем порядке): • побитовой операции XOR; • приложение S-ячейки(которое выражается как набор битовых перестановок между четырьмя используемыми 32-битными словами, в «bitslice» разделе); • линейная биективная трансформация (которая состоит из нескольких операций XOR, сдвигов и поворотов в «bitslice» разделе). Serpent1 – один раунд SERPENT’a, без добавления ключа и линейной трансформации. SERPENT использует 8 уникальных S-ячеек , пронумерованных с S0 до S7 на 4-битных словах. Мы определили Serpent1 как приложение ячейки S2, в «bitslice» разделе. Это третий уровень S-ячейки SERPENTа. Serpent1 принимает четыре 32-битных слова на вход, и предоставляет четыре 32-битных слова на выход.

Serpent24

Serpent24 – это SERPENT, уменьшенный до 24 раундов вместо 32 раундов полной версии SERPENT. Serpent24 эквивалентен первым 24 раундам SERPENT, где последний раунд (24) является полным и включает полный раунд с линейной трансформации и операцию XOR с 25 подраундом. Другими словами, 24 раунд Serpent24 является эквивалентным тридцатисекундному раунду SERPENT, за исключением того, что содержит линейную трансформацию, и используются 24, 25 подраунды (32 и 33 подраунд в SERPENT). Таким образом, последний раунд выражение equation on Page 224 in [2] is

Serpent24 использует только 25 128-битных подраундов, которые являются первыми 25 подраундами SERPENT. Serpent24 в Sosemanuk используется для этапа инициализации, только в режиме шифрования. Расшифрование не используется.

LFSR

Базовое конечное поле

Большая часть потоковых шифров внутреннего состояния поддерживаются в LFSR, который содержит 10 элементов F232 , т.е. поле с 232 элементами. Элементы пространства F232 представлены точно так же как в SNOW 2.0. Воспроизведём это представление. Пусть F2 обозначает конечное поле с двумя элементами. Пусть β является корнем примитивного полинома:

в F2[X]. Определим поле F28 как частное F2[X]/Q(X). Каждый элемент в F28 представляется, используя базис (β7, β6, ... β, 1). Поскольку выбранный полином примитивный(простой), то then β является мультипликативным генератором всех multiplicative generator of all обратимых элементов из F28: каждый ненулевой элемент из F28 равен βk для некоторого целого неотрицательного k(0 · k · 254). Любой элемент из F28 идентифицируется с 8-битным числом следующей биективной функцией:

Где каждый xi является либо 0 либо 1. Например, β23 представляется целым числом Φ(β23) = 0xE1 (в шестнадцатеричной системе). Следовательно, дополнение двух элементов в F28 соответствует битовой операции XOR между соответственными целочисленными представлениями. Умножение на β равносильно левому сдвигу на один бит целочисленного представления. Он следует за операцией XOR с фиксированной маской, если самый старший бит, который был удалён при помощи сдвига, равен 1.

Пусть α является корнем примитивного (простого) полинома:

из F28[X]. Поле F232 далее определяется как частное F28 [X]/P(X), то есть, его элементы представляются в базисе (α3, α2, α, 1). Любой элемент из F232 идентифицируется с 32-битным целым числом следующей биективной функцией:

Таким образом, дополнение двух элементов в F232 соответствует побитовой операции XOR между их целочисленными представлениями. В дальнейшем эта операция будет обозначена. Sosemanuk также использует операции умножения и деления элементов из F232 на α. Умножение z (из F232) на α соответствует левому сдвигу на 8 бит ψ(z), следующий за операцией XOR с 32-битной маской, которая зависит только от наиболее значимых байт ψ(z). Деление z (из F232) на α является правым сдвигом на 8 бит ψ(z), следующий за операцией XOR с 32-битной маской, которая зависит только от менее значимых байт ψ(z).

Рисунок 1: LFSR

Определение LFSR

LFSR работает над элементами из F232. Начальное состояние в момент времени t = 0, влечёт за собой десять 32-битных значений s1 – s10. На каждом этапе, новое значение вычисляется с помощью следующей рекурсии:

и регистр сдвигается (см. рисунок 1 для иллюстрации работы LFSR). LFSR связан со следующим полиномом обратной связи:

Поскольку LFSR является не единственным и так как π является простым полиномом, то последовательность 32-битных слов (st)t≥1 является периодической и имеет максимальный период (2320 − 1).

Finite State Machine (машина конечного состояния)

Finite State Machine (FSM) является компонентой с 64 битами памяти, которая соответствует двум 32-битным регистрам: R1 и R2. На каждом этапе, FSM принимает на вход несколько слов из состояния LFSR; он соответственно обновляет биты памяти и производит 32-бита на выход. FSM работает на состоянии LFSR в момент времени t ≥ 1 как показано ниже:

где

где lsb(x) - наименьший значимый бит x, mux(c, x, y) равен x если c = 0, или y если c = 1. Внутренняя переходная функция Trans из F232 определяется

где M является постоянным значением 0x54655307 и ‘<<<’ означает битовый поворот 32-битного значения (в данном случае, на 7 бит).

Трансформация на выходе

Выходы FSM сгруппированы по четыре, и Serpent1 применяется к каждой группе; далее результат комбинируется операцией XOR с соответствующими удалёнными значениями из LFSR, для получения на выходе значений zt:

Четыре последовательных раундов Sosemanuk схематично изображены на рисунке 2.

Рабочий процесс Sosemanuk

Шифр Sosemanuk комбинирует в себе FSM и LFSR для получения выходных значений zt. Момент времени t = 0 обозначает внутреннее состояние после инициализации; первое выходное значение – z1 . Рисунок 3 даёт графическое представление Sosemanuk. В момент времени t ≥ 1, мы выполняем следующие операции:

• Обновляется FSM: R1t, R2t и промежуточное значение ft вычисляется из R1t−1,

R2t−1, st+1, st+8 и st+9.

• Обновляется LFSR: st+10 вычисляется исходя из st, st+3 и st+9. Значение st отправляется во внутренний буфер, и LFSR сдвигается.

Раз в четыре шага, четыре выходных значения zt, zt+1, zt+2 и zt+3 получаются из собранных значений ft, ft+1, ft+2, ft+3 и st, st+1, st+2, st+3. Таким образом, Sosemanuk производит 32-битные значения. Рекомендуется зашифровывать их в группы по четыре байта, используя прямой порядок байтов, так как последний способ обладает большей скоростью на более широко используемых ПО – платформах высокого класса (x86- совместимый PC). Кроме того SERPENT использует этот метод. Следовательно, первые четыре итерации Sosemanuk будут следующими.

• Начальное состояние LFSR содержит значения s1 – s10; никакого значения s0 не определяется. Начальное состояние FSM содержит R10 и R20.
• В течение первого этапа, R11, R21 и f1 вычисляются исходя из R10, R20, s2, s9 и s10.
• Из первого этапа получается буферизованные промежуточные значения s1 и f1.
• В течение первого этапа, обратное слово s11 вычисляется из s10, s4 и s1, обновляется внутреннее состояние LFSR, что приводит к новому состоянию, которое является композицией s2 и s11.
• Первые четыре выходных значения являются z1, z2, z3 и z4, и вычисляются, используя приложение Serpent1 над (f4, f3, f2, f1), где выход комбинируется операциями XOR с (s4, s3, s2, s1).

Рисунок 2: Трансформация на выходе на четырёх последовательных раундов Sosemanuk.

Рисунок 3: Схематичное представление Sosemanuk

Литература

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

Для улучшения этой статьи желательно?: Обновить статью, актуализировать данные. Добавить иллюстрации. Переработать оформление в соответствии с правилами написания статей.