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-битную безопасность.^[4]

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

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

Общая схема работыПравить

схема работы SNOW 2.0

Как и поточный шифр SNOW, алгоритм Sosemanuk использует два основных понятия: регистр сдвига с линейной обратной связью (LFSR) и конечный автомат (FSM). Так, данные, полученные с помощью LFSR, поступают на вход FSM, где происходит их нелинейное преобразование. Затем к четырём выходным значениям конечного автомата применяется табличная замена (S-box) и XOR с соответствующими значениями регистра сдвига. Расписание ключей для шифра составляется с помощью примитива Serpent24 — усечённого варианта SERPENT. Кроме того, выходные значения двенадцатого, восемнадцатого и двадцать четвёртого раунда Serpent24 используются для инъекции начального значения: задания состояния LSM и регистров FSM.^[4]

Следует заметить, что Sosemanuk использует регистр сдвига длины 10, тогда как в SNOW его длина равнялась шестнадцати. Кроме того, в FSM операция применения S-box заменена на операцию Trans, представляющую собой умножение над 32-битным полем и последующий побитовый циклический сдвиг.^[6]

Спецификация^[4]Править

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

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

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

Регистр сдвига с линейной обратной связьюПравить

LFSR algorithm

Sosemanuk использует линейный регистр сдвига длины 10 над конечным 32-битным полем $\text{[math]}$ $\text{[math]}$ $F_{2^{32}}[X]$ .

В начальный момент времени $\text{[math]}$ $\text{[math]}$ $t=0$ происходит инициализация регистра сдвига 32-битными значениями $\text{[math]}$ $\text{[math]}$ $s_{1},s_{2},...,s_{10}$ . Затем, на каждом шаге вычисляется новое значение по формуле:

$\text{[math]}$ $\text{[math]}$ $s_{t+10}=s_{t+9}\oplus \alpha ^{-1}s_{t+3}\oplus \alpha s_{t}$ .

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

$\text{[math]}$ $\text{[math]}$ $\pi (X)=\alpha X^{10}+\alpha \pi ^{-1}X^{7}+X+1\subseteq F_{2^{32}}[X]$

Здесь $\text{[math]}$ $\text{[math]}$ $\alpha$ — корень примитивного многочлена над полем $\text{[math]}$ $\text{[math]}$ $F_{2^{8}}[X]$ :

$\text{[math]}$ $\text{[math]}$ $P(X)=X^{4}+\beta ^{23}X^{3}+\beta ^{245}X^{2}+\beta ^{48}X+\beta ^{239}$

$\text{[math]}$ $\text{[math]}$ $\beta$ — корень примитивного многочлена над полем $\text{[math]}$ $\text{[math]}$ $F_{2}[X]$ :

$\text{[math]}$ $\text{[math]}$ $Q(X)=X^{8}+X^{7}+X^{5}+X^{3}+1$

Поле $\text{[math]}$ $\text{[math]}$ $F_{2^{8}}[X]$ представляет собой отношение $\text{[math]}$ $\text{[math]}$ $F_{2}[X]/Q(X)$ , а конечное поле $\text{[math]}$ $\text{[math]}$ $F_{2^{32}}[X]$ получается из отношения $\text{[math]}$ $\text{[math]}$ $F_{2^{8}}[X]/P(X)$ . Последовательность $\text{[math]}$ $\text{[math]}$ $(s_{t})_{t>1}$ является периодической с максимальным периодом $\text{[math]}$ $\text{[math]}$ $2^{320-1}$ .

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

Конечный автоматПравить

Sosemanuk использует конечный автомат с 64 битами памяти, что соответствует двум 32-битным регистрам $\text{[math]}$ $\text{[math]}$ $R1$ и $\text{[math]}$ $\text{[math]}$ $R2$ . Он принимает на вход несколько значений, полученных с помощью LFSR, обновляет регистры, после чего выдаёт 32-битное значение $\text{[math]}$ $\text{[math]}$ $f_{t}$ по схеме:

$\text{[math]}$ $\text{[math]}$ ${FSM}_{t}:(R1_{t-1},R2_{t-1},s_{t+1},s{t+8},s_{t+9})\mapsto ({R1}_{t},{R2}_{t},f_{t})$

$\text{[math]}$ $\text{[math]}$ $R1_{t}={\begin{cases}(R2_{t-1}+s_{t+1})mod2^{32},&lsb(R1_{t-1})=0\\(R2_{t-1}+s_{t+1}\oplus s_{t+8})mod2^{32},&lsb(R1_{t-1})=1\end{cases}}$

$\text{[math]}$ $\text{[math]}$ $R2_{t}=Trans(R1_{t-1})$

$\text{[math]}$ $\text{[math]}$ $f_{t}=(s_{t+9}+R1_{t}mod2^{32})\oplus R2_{t}$

$\text{[math]}$ $\text{[math]}$ $lsb(X)$ — последний значащий бит $\text{[math]}$ $\text{[math]}$ $X$ (используется little-endian нотация).

$\text{[math]}$ $\text{[math]}$ $Trans(X)=(M\times Xmod2^{32})\lll 7$

$\text{[math]}$ $\text{[math]}$ $M=0x54655307$ (шестнадцатеричная запись первых десяти знаков числа π)

$\text{[math]}$ $\text{[math]}$ $\lll$ — побитовый циклический сдвиг.

Выходное преобразованиеПравить

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

$\text{[math]}$ $\text{[math]}$ $(z_{t+3},z_{t+2},z_{t+1},z_{t})=Serpent1(f_{t+3},f_{t+2},f_{t+1},f_{t})\oplus (s_{t+3},s_{t+2},s_{t+1},s_{t})$

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

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

Для получения выходных значений используется связка LFSR и FSM. В начальный момент времени $\text{[math]}$ $\text{[math]}$ $t=0$ LFSR инициализируется значениями $\text{[math]}$ $\text{[math]}$ $s_{1},s_{2},...,s_{10}$ , а в регистры FSM записываются значения $\text{[math]}$ $\text{[math]}$ $R1_{0}$ и $\text{[math]}$ $\text{[math]}$ $R2_{0}$ . В момент времени $\text{[math]}$ $\text{[math]}$ $t\geq 1$ выполняются следующие действия:

Обновление FSM: вычисляются значения $\text{[math]}$ $\text{[math]}$ $R1_{t}$ , $\text{[math]}$ $\text{[math]}$ $R2_{t}$ и $\text{[math]}$ $\text{[math]}$ $f_{t}$ , исходя из известных $\text{[math]}$ $\text{[math]}$ $R1_{t-1}$ , $\text{[math]}$ $\text{[math]}$ $R2_{t-1}$ , $\text{[math]}$ $\text{[math]}$ $s_{t+1}$ , $\text{[math]}$ $\text{[math]}$ $s_{t+8}$ и $\text{[math]}$ $\text{[math]}$ $s_{t+9}$ .
Обновление LFSR: вычисляется $\text{[math]}$ $\text{[math]}$ $s_{t+10}$ , значение $\text{[math]}$ $\text{[math]}$ $s_{t}$ переходит во внутренний буфер, регистр сдвига сдвигается.

Каждые четыре шага из промежуточных значений $\text{[math]}$ $\text{[math]}$ $f_{t}$ , $\text{[math]}$ $\text{[math]}$ $f_{t+1}$ , $\text{[math]}$ $\text{[math]}$ $f_{t+2}$ , $\text{[math]}$ $\text{[math]}$ $f_{t+3}$ и значений внутреннего буфера $\text{[math]}$ $\text{[math]}$ $s_{t+1}$ , $\text{[math]}$ $\text{[math]}$ $s_{t+1}$ , $\text{[math]}$ $\text{[math]}$ $s_{t+1}$ , $\text{[math]}$ $\text{[math]}$ $s_{t+1}$ посредством применения Serpent1 и XOR вычисляются итоговые значения $\text{[math]}$ $\text{[math]}$ $z_{t+3},z_{t+2},z_{t+1},z_{t}.$ Авторы шифра рекомендуют шифровать группы по четыре байта, используя при этом прямой (little-endian) порядок байтов для увеличения производительности.

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

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

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

Key sheduleПравить

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

IV injectionПравить

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

$\text{[math]}$ $\text{[math]}$ $(Y_{3}^{12},Y_{2}^{12},Y_{1}^{12},Y_{0}^{12})$ — выходные значения 12-го раунда

$\text{[math]}$ $\text{[math]}$ $(Y_{3}^{18},Y_{2}^{18},Y_{1}^{18},Y_{0}^{18})$ — выходные значения 18-го раунда

$\text{[math]}$ $\text{[math]}$ $(Y_{3}^{24},Y_{2}^{24},Y_{1}^{24},Y_{0}^{24})$ — выходные значения 24-го раунда

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

$\text{[math]}$ $\text{[math]}$ $(s_{7},s_{8},s_{9},s_{10})=(Y_{3}^{12},Y_{2}^{12},Y_{1}^{12},Y_{0}^{12})$

$\text{[math]}$ $\text{[math]}$ $(s_{5},s_{6})=(Y_{1}^{18},Y_{3}^{18})$

$\text{[math]}$ $\text{[math]}$ $(s_{1},s_{2},s_{3},s_{4})=(Y_{3}^{24},Y_{2}^{24},Y_{1}^{24},Y_{0}^{24})$

$\text{[math]}$ $\text{[math]}$ $R1_{0}=Y_{0}^{18}$

$\text{[math]}$ $\text{[math]}$ $R2_{0}=Y_{2}^{18}$

Известные атакиПравить

Атаки, предусмотренные разработчиками^[4]Править

Компромисс времени и данныхПравить

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

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

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

Корреляционная атакаПравить

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

Различающая атакаПравить

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

Алгебраическая атакаПравить

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

Новые атакиПравить

После того, как шифр стал широко известен в криптографическом сообществе, в литературе было опубликовано несколько новых атак на Sosemanuk. Тем не менее, изначально заявленная сложность в 128 бит так и не была взломана.http://www.ecrypt.eu.org/stream/e2-sosemanuk.html^[5]

Guess-and-Determine Attack, 2006^[7]Править

В 2006 году коллектив учёных из Японии и Ирана, Юкиясу Цуно (Yukiyasu Tsunoo) Теруо Сайто (Teruo Saito) и др., представили атаку «Предполагай и определяй» сложностью 2²²⁴. Для её осуществления необходимо знать 16 слов ключевого потока. При этом, увеличение длины ключа ведет к уменьшению сложности атаки.

Атака основывается на предположении, что последний значащий бит в регистре $\text{[math]}$ $\text{[math]}$ $R1_{t-1}$ конечного автомата в момент времени $\text{[math]}$ $\text{[math]}$ $t$ равен нулю. Если при $\text{[math]}$ $\text{[math]}$ $t=1$ это утверждение не выполняется, взломать шифр данным способом не получится.

Для осуществления атаки необходимо предположить значения $\text{[math]}$ $\text{[math]}$ $s_{1},s_{2},s_{3},s_{4},R1_{0},R2_{0},s_{7},s_{8}.$

Using Linear Masks Attack, 2008^[8]Править

В 2008 году на конференции ASIACRYPT^[en] учёные из Кореи Юнг-Кеун Ли, Донг Хун Ли и Парк Сангву представили корреляционную атаку на Sosemanuk с помощью использования метода линейной маски (linear masking method). Сложность такой атаки составляла 2¹⁴⁸, и внутреннее 384-битное состояние восстанавливалось с вероятностью 99 %. Для проведения атаки используется линейная аппроксимация с коэффициентом корреляции 2^−21.41, построенная по словам ключевого потока и начальному состоянию регистра сдвига. При этом, начальное состояние LFSR восстанавливается с помощью быстрого преобразования Уолша.

ПримечанияПравить

↑ Sosemanuk Algorithm forencryption and decryption Video on Demand (VoD) (PDF Download Available) (англ.). ResearchGate. Дата обращения: 14 октября 2017. Архивировано 15 октября 2017 года.
↑ The eSTREAM portfolio page (англ.). www.ecrypt.eu.org. Дата обращения: 14 октября 2017. Архивировано 13 февраля 2017 года.
↑ The eSTREAM Project - eSTREAM Phase 3 (неопр.). www.ecrypt.eu.org. Дата обращения: 14 октября 2017. Архивировано 4 сентября 2012 года.
↑ ¹ ² ³ ⁴ Архивированная копия (неопр.). Дата обращения: 7 декабря 2010. Архивировано 27 мая 2011 года.
↑ ¹ ² The eSTREAM portfolio page (англ.). www.ecrypt.eu.org. Дата обращения: 16 декабря 2017. Архивировано 5 апреля 2016 года.
↑ Patrik Ekdahl and Thomas Johansson. A New Version of the Stream Cipher SNOW (англ.) // Springer-Verlag Berlin Heidelberg 2003. Архивировано 14 декабря 2017 года.
↑ [http://www.ecrypt.eu.org/stream/papersdir/2006/009.pdf Evaluation of SOSEMANUK With Regard to Guess-and-Determine Attacks] (англ.) // eSTREAM portfolio. Архивировано 13 января 2017 года.
↑ [https://link.springer.com/content/pdf/10.1007%2F978-3-540-89255-7.pdf Cryptanalysis of Sosemanuk and SNOW 2.0 Using Linear Masks] (англ.) // J. Pieprzyk (Ed.): ASIACRYPT 2008, LNCS 5350, pp. 524–538, 2008..

ЛитератураПравить

«Sosemanuk, a fast software-oriented stream cipher», описание разработчиков
«Evaluation of SOSEMANUK With Regard to Guess-and-Determine Attacks»
«Cryptanalysis of Sosemanuk and SNOW 2.0 Using Linear Masks»

[:0-1] Sosemanuk Algorithm forencryption and decryption Video on Demand (VoD) (PDF Download Available) (англ.). ResearchGate. Дата обращения: 14 октября 2017. Архивировано 15 октября 2017 года.

[2] The eSTREAM portfolio page (англ.). www.ecrypt.eu.org. Дата обращения: 14 октября 2017. Архивировано 13 февраля 2017 года.

[:1-3] The eSTREAM Project - eSTREAM Phase 3 (неопр.). www.ecrypt.eu.org. Дата обращения: 14 октября 2017. Архивировано 4 сентября 2012 года.

[:3-4] ¹ ² ³ ⁴ Архивированная копия (неопр.). Дата обращения: 7 декабря 2010. Архивировано 27 мая 2011 года.

[:2-5] ¹ ² The eSTREAM portfolio page (англ.). www.ecrypt.eu.org. Дата обращения: 16 декабря 2017. Архивировано 5 апреля 2016 года.

[6] Patrik Ekdahl and Thomas Johansson. A New Version of the Stream Cipher SNOW (англ.) // Springer-Verlag Berlin Heidelberg 2003. Архивировано 14 декабря 2017 года.

[7] [http://www.ecrypt.eu.org/stream/papersdir/2006/009.pdf Evaluation of SOSEMANUK With Regard to Guess-and-Determine Attacks] (англ.) // eSTREAM portfolio. Архивировано 13 января 2017 года.

[8] [https://link.springer.com/content/pdf/10.1007%2F978-3-540-89255-7.pdf Cryptanalysis of Sosemanuk and SNOW 2.0 Using Linear Masks] (англ.) // J. Pieprzyk (Ed.): ASIACRYPT 2008, LNCS 5350, pp. 524–538, 2008..

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]