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

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

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

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

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

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

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

${\displaystyle s_{t+10}=s_{t+9}\oplus \alpha ^{-1}s_{t+3}\oplus \alpha s_{t}}$.

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

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

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

${\displaystyle P(X)=X^{4}+\beta ^{23}X^{3}+\beta ^{245}X^{2}+\beta ^{48}X+\beta ^{239}}$

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

${\displaystyle Q(X)=X^{8}+X^{7}+X^{5}+X^{3}+1}$

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

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

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

${\displaystyle 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}}}$

${\displaystyle R2_{t}=Trans(R1_{t-1})}$

${\displaystyle f_{t}=(s_{t+9}+R1_{t}mod2^{32})\oplus R2_{t}}$

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

${\displaystyle Trans(X)=(M\times Xmod2^{32})\lll 7}$

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

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

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

${\displaystyle (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. В начальный момент времени ${\displaystyle t=0}$ LFSR инициализируется значениями ${\displaystyle s_{1},s_{2},...,s_{10}}$, а в регистры FSM записываются значения ${\displaystyle R1_{0}}$и ${\displaystyle R2_{0}}$. В момент времени ${\displaystyle t\geq 1}$ выполняются следующие действия:

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle (s_{5},s_{6})=(Y_{1}^{18},Y_{3}^{18})}$

${\displaystyle (s_{1},s_{2},s_{3},s_{4})=(Y_{3}^{24},Y_{2}^{24},Y_{1}^{24},Y_{0}^{24})}$

${\displaystyle R1_{0}=Y_{0}^{18}}$

${\displaystyle R2_{0}=Y_{2}^{18}}$

Атака компромисса времени и данных (англ. 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]

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

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

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

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

• «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»