SOSEMANUK

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

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

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

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 элементов , т.е. поля с элементами. Элементы пространства представлены точно так же как в SNOW 2.0. Воспроизведём это представление. Пусть F_2 обозначает конечное поле с двумя элементами. Пусть β является корнем примитивного полинома:

в 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", описание разработчиков

  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. The eSTREAM Project - eSTREAM Phase 3. www.ecrypt.eu.org. Проверено 14 октября 2017.