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 элементов <math>\mathbb{F}_{2^{32}}</math>, т.е. поля с <math>2^{32}</math> элементами. Элементы пространства <math>\mathbb{F}_{2^{32}}</math> представлены точно так же как в SNOW 2.0. Воспроизведём это представление. Пусть F_2 обозначает конечное поле с двумя элементами. Пусть β является корнем примитивного полинома:

<math>Q(X) = X^8 + X^7 + X^5 + X^3 + 1</math>

в 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

Литература

[www.ecrypt.eu.org/stream/p3ciphers/sosemanuk/sosemanuk_p3.pdf "Sosemanuk, a fast software-oriented stream cipher"], описание разработчиков

Отрывок, характеризующий SOSEMANUK

– C'est vous, Clement? – сказал он. – D'ou, diable… [Это вы, Клеман? Откуда, черт…] – но он не докончил, узнав свою ошибку, и, слегка нахмурившись, как с незнакомым, поздоровался с Долоховым, спрашивая его, чем он может служить. Долохов рассказал, что он с товарищем догонял свой полк, и спросил, обращаясь ко всем вообще, не знали ли офицеры чего нибудь о шестом полку. Никто ничего не знал; и Пете показалось, что офицеры враждебно и подозрительно стали осматривать его и Долохова. Несколько секунд все молчали.
– Si vous comptez sur la soupe du soir, vous venez trop tard, [Если вы рассчитываете на ужин, то вы опоздали.] – сказал с сдержанным смехом голос из за костра.
Долохов отвечал, что они сыты и что им надо в ночь же ехать дальше.
Он отдал лошадей солдату, мешавшему в котелке, и на корточках присел у костра рядом с офицером с длинной шеей. Офицер этот, не спуская глаз, смотрел на Долохова и переспросил его еще раз: какого он был полка? Долохов не отвечал, как будто не слыхал вопроса, и, закуривая коротенькую французскую трубку, которую он достал из кармана, спрашивал офицеров о том, в какой степени безопасна дорога от казаков впереди их.
– Les brigands sont partout, [Эти разбойники везде.] – отвечал офицер из за костра.
Долохов сказал, что казаки страшны только для таких отсталых, как он с товарищем, но что на большие отряды казаки, вероятно, не смеют нападать, прибавил он вопросительно. Никто ничего не ответил.
«Ну, теперь он уедет», – всякую минуту думал Петя, стоя перед костром и слушая его разговор.
Но Долохов начал опять прекратившийся разговор и прямо стал расспрашивать, сколько у них людей в батальоне, сколько батальонов, сколько пленных. Спрашивая про пленных русских, которые были при их отряде, Долохов сказал:
– La vilaine affaire de trainer ces cadavres apres soi. Vaudrait mieux fusiller cette canaille, [Скверное дело таскать за собой эти трупы. Лучше бы расстрелять эту сволочь.] – и громко засмеялся таким странным смехом, что Пете показалось, французы сейчас узнают обман, и он невольно отступил на шаг от костра. Никто не ответил на слова и смех Долохова, и французский офицер, которого не видно было (он лежал, укутавшись шинелью), приподнялся и прошептал что то товарищу. Долохов встал и кликнул солдата с лошадьми.
«Подадут или нет лошадей?» – думал Петя, невольно приближаясь к Долохову.
Лошадей подали.
– Bonjour, messieurs, [Здесь: прощайте, господа.] – сказал Долохов.
Петя хотел сказать bonsoir [добрый вечер] и не мог договорить слова. Офицеры что то шепотом говорили между собою. Долохов долго садился на лошадь, которая не стояла; потом шагом поехал из ворот. Петя ехал подле него, желая и не смея оглянуться, чтоб увидать, бегут или не бегут за ними французы.
Выехав на дорогу, Долохов поехал не назад в поле, а вдоль по деревне. В одном месте он остановился, прислушиваясь.
– Слышишь? – сказал он.
Петя узнал звуки русских голосов, увидал у костров темные фигуры русских пленных. Спустившись вниз к мосту, Петя с Долоховым проехали часового, который, ни слова не сказав, мрачно ходил по мосту, и выехали в лощину, где дожидались казаки.
– Ну, теперь прощай. Скажи Денисову, что на заре, по первому выстрелу, – сказал Долохов и хотел ехать, но Петя схватился за него рукою.
– Нет! – вскрикнул он, – вы такой герой. Ах, как хорошо! Как отлично! Как я вас люблю.
– Хорошо, хорошо, – сказал Долохов, но Петя не отпускал его, и в темноте Долохов рассмотрел, что Петя нагибался к нему. Он хотел поцеловаться. Долохов поцеловал его, засмеялся и, повернув лошадь, скрылся в темноте.

Х
Вернувшись к караулке, Петя застал Денисова в сенях. Денисов в волнении, беспокойстве и досаде на себя, что отпустил Петю, ожидал его.
– Слава богу! – крикнул он. – Ну, слава богу! – повторял он, слушая восторженный рассказ Пети. – И чег'т тебя возьми, из за тебя не спал! – проговорил Денисов. – Ну, слава богу, тепег'ь ложись спать. Еще вздг'емнем до утг'а.
– Да… Нет, – сказал Петя. – Мне еще не хочется спать. Да я и себя знаю, ежели засну, так уж кончено. И потом я привык не спать перед сражением.
Петя посидел несколько времени в избе, радостно вспоминая подробности своей поездки и живо представляя себе то, что будет завтра. Потом, заметив, что Денисов заснул, он встал и пошел на двор.
На дворе еще было совсем темно. Дождик прошел, но капли еще падали с деревьев. Вблизи от караулки виднелись черные фигуры казачьих шалашей и связанных вместе лошадей. За избушкой чернелись две фуры, у которых стояли лошади, и в овраге краснелся догоравший огонь. Казаки и гусары не все спали: кое где слышались, вместе с звуком падающих капель и близкого звука жевания лошадей, негромкие, как бы шепчущиеся голоса.
Петя вышел из сеней, огляделся в темноте и подошел к фурам. Под фурами храпел кто то, и вокруг них стояли, жуя овес, оседланные лошади. В темноте Петя узнал свою лошадь, которую он называл Карабахом, хотя она была малороссийская лошадь, и подошел к ней.
– Ну, Карабах, завтра послужим, – сказал он, нюхая ее ноздри и целуя ее.
– Что, барин, не спите? – сказал казак, сидевший под фурой.
– Нет; а… Лихачев, кажется, тебя звать? Ведь я сейчас только приехал. Мы ездили к французам. – И Петя подробно рассказал казаку не только свою поездку, но и то, почему он ездил и почему он считает, что лучше рисковать своей жизнью, чем делать наобум Лазаря.
– Что же, соснули бы, – сказал казак.
– Нет, я привык, – отвечал Петя. – А что, у вас кремни в пистолетах не обились? Я привез с собою. Не нужно ли? Ты возьми.
Казак высунулся из под фуры, чтобы поближе рассмотреть Петю.
– Оттого, что я привык все делать аккуратно, – сказал Петя. – Иные так, кое как, не приготовятся, потом и жалеют. Я так не люблю.
– Это точно, – сказал казак.
– Да еще вот что, пожалуйста, голубчик, наточи мне саблю; затупи… (но Петя боялся солгать) она никогда отточена не была. Можно это сделать?
– Отчего ж, можно.
Лихачев встал, порылся в вьюках, и Петя скоро услыхал воинственный звук стали о брусок. Он влез на фуру и сел на край ее. Казак под фурой точил саблю.
– А что же, спят молодцы? – сказал Петя.
– Кто спит, а кто так вот.
– Ну, а мальчик что?
– Весенний то? Он там, в сенцах, завалился. Со страху спится. Уж рад то был.
Долго после этого Петя молчал, прислушиваясь к звукам. В темноте послышались шаги и показалась черная фигура.
– Что точишь? – спросил человек, подходя к фуре.
– А вот барину наточить саблю.
– Хорошее дело, – сказал человек, который показался Пете гусаром. – У вас, что ли, чашка осталась?
– А вон у колеса.
Гусар взял чашку.
– Небось скоро свет, – проговорил он, зевая, и прошел куда то.
Петя должен бы был знать, что он в лесу, в партии Денисова, в версте от дороги, что он сидит на фуре, отбитой у французов, около которой привязаны лошади, что под ним сидит казак Лихачев и натачивает ему саблю, что большое черное пятно направо – караулка, и красное яркое пятно внизу налево – догоравший костер, что человек, приходивший за чашкой, – гусар, который хотел пить; но он ничего не знал и не хотел знать этого. Он был в волшебном царстве, в котором ничего не было похожего на действительность. Большое черное пятно, может быть, точно была караулка, а может быть, была пещера, которая вела в самую глубь земли. Красное пятно, может быть, был огонь, а может быть – глаз огромного чудовища. Может быть, он точно сидит теперь на фуре, а очень может быть, что он сидит не на фуре, а на страшно высокой башне, с которой ежели упасть, то лететь бы до земли целый день, целый месяц – все лететь и никогда не долетишь. Может быть, что под фурой сидит просто казак Лихачев, а очень может быть, что это – самый добрый, храбрый, самый чудесный, самый превосходный человек на свете, которого никто не знает. Может быть, это точно проходил гусар за водой и пошел в лощину, а может быть, он только что исчез из виду и совсем исчез, и его не было.
Что бы ни увидал теперь Петя, ничто бы не удивило его. Он был в волшебном царстве, в котором все было возможно.
Он поглядел на небо. И небо было такое же волшебное, как и земля. На небе расчищало, и над вершинами дерев быстро бежали облака, как будто открывая звезды. Иногда казалось, что на небе расчищало и показывалось черное, чистое небо. Иногда казалось, что эти черные пятна были тучки. Иногда казалось, что небо высоко, высоко поднимается над головой; иногда небо спускалось совсем, так что рукой можно было достать его.
Петя стал закрывать глаза и покачиваться.
Капли капали. Шел тихий говор. Лошади заржали и подрались. Храпел кто то.
– Ожиг, жиг, ожиг, жиг… – свистела натачиваемая сабля. И вдруг Петя услыхал стройный хор музыки, игравшей какой то неизвестный, торжественно сладкий гимн. Петя был музыкален, так же как Наташа, и больше Николая, но он никогда не учился музыке, не думал о музыке, и потому мотивы, неожиданно приходившие ему в голову, были для него особенно новы и привлекательны. Музыка играла все слышнее и слышнее. Напев разрастался, переходил из одного инструмента в другой. Происходило то, что называется фугой, хотя Петя не имел ни малейшего понятия о том, что такое фуга. Каждый инструмент, то похожий на скрипку, то на трубы – но лучше и чище, чем скрипки и трубы, – каждый инструмент играл свое и, не доиграв еще мотива, сливался с другим, начинавшим почти то же, и с третьим, и с четвертым, и все они сливались в одно и опять разбегались, и опять сливались то в торжественно церковное, то в ярко блестящее и победное.
«Ах, да, ведь это я во сне, – качнувшись наперед, сказал себе Петя. – Это у меня в ушах. А может быть, это моя музыка. Ну, опять. Валяй моя музыка! Ну!..»
Он закрыл глаза. И с разных сторон, как будто издалека, затрепетали звуки, стали слаживаться, разбегаться, сливаться, и опять все соединилось в тот же сладкий и торжественный гимн. «Ах, это прелесть что такое! Сколько хочу и как хочу», – сказал себе Петя. Он попробовал руководить этим огромным хором инструментов.