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

Аннотация

В основе Sosemanuk лежит поточный шифр SNOW 2.0 и усечённый вариант блочного шифра SERPENT . Его длина ключа варьируется между 128 и 256 битами, а для инициализации используется 128-битное начальное значение (англ. initial value). Как утверждают авторы шифра, любая длина ключа обеспечивает 128-битную безопасность.

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

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

Общая схема работы

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

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

Спецификация

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. Таким образом, происходит инициализация внутреннего состояния поточного шифра.

Key shedule

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

IV injection

Для введения 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.

Различающая атака

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

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

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

Новые атаки

После того, как шифр стал широко известен в криптографическом сообществе, в литературе было опубликовано несколько новых атак на Sosemanuk. Тем не менее, изначально заявленная сложность в 128 бит так и не была взломана.

Guess-and-Determine Attack, 2006

В 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}.}$

Using Linear Masks Attack, 2008

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

Примечания

Литература

• , описание разработчиков