Grain

Grain - симметричный алгоритм синхронного потокового шифрования, ориентированный, в первую очередь на аппаратную реализацию. Шифр представлен на конкурсе eSTREAM в 2004 году Мартином Хеллом, Томасом Юханссоном и Вилли Мейером. Алгоритм стал одним из финалистов конкурса во втором профиле (аппаратно ориентированные шифры).

Шифр состоит из трёх основных блоков: двух 80-битных регистров сдвига с обратной связью и выходной функции. Один из регистров обладает линейной функцией обратной связи (LFSR), второй регистр имеет нелинейную функцию обратной связи (NFSR). Внутреннее состояние шифра полностью определяется регистрами сдвига.

Функция обратной связи данного регистра задаётся примитивным полиномом ${\displaystyle f(x)=1+x^{18}+x^{29}+x^{42}+x^{57}+x^{67}+x^{80}}$

Если представить состояние регистра в виде ${\displaystyle s_{i},s_{i+1},..,s_{i+79}}$, то следующий младший (правый) бит будет задаваться соотношением

 ${\displaystyle s_{i+80}=s_{i+62}+s_{i+51}+s_{i+38}+s_{i+23}+s_{i+13}+s_{i}}$

Функция обратной связи регистра с нелинейной обратной связью задаётся соотношением

  ${\displaystyle g(x)=1+x^{18}+x^{20}+x^{28}+x^{35}+x^{43}+x^{47}+x^{52}+x^{59}+x^{66}+x^{71}+x^{80}+x^{17}x^{20}+x^{43}x^{47}+x^{65}x^{71}+x^{20}x^{28}x^{35}+x^{47}x^{52}x^{59}+x^{17}x^{35}x^{52}x^{71}+x^{20}x^{28}x^{43}x^{47}+x^{17}x^{20}x^{59}x^{65}+x^{17}x^{20}x^{28}x^{35}x^{43}+x^{47}x^{52}x^{59}x^{65}x^{71}+x^{28}x^{35}x^{43}x^{47}x^{52}x^{59}}$

Для битов ${\displaystyle b_{i}}$ регистра NLSR получается выражение

  ${\displaystyle b_{i+80}=s_{i}+b_{i+62}+b_{i+60}+b_{i+52}+b_{i+45}+b_{i+37}+b_{i+33}+b_{i+28}+b_{i+21}+b_{i+14}+b_{i+9}+b_{i}+b_{i+63}b_{i+60}+b_{i+37}b_{i+33}+b_{i+15}b_{i+9}+b_{i+60}b_{i+52}b_{i+45}+b_{i+33}b_{i+28}b_{i+21}+b_{i+63}b_{i+45}b_{i+28}b_{i+9}+b_{i+60}b_{i+52}b_{i+37}b_{i+33}+b_{i+63}b_{i+60}b_{i+21}b_{i+15}+b_{i+63}b_{i+60}b_{i+52}b_{i+45}b_{i+37}+b_{i+33}b_{i+28}b_{i+21}b_{i+15}b_{i+9}+b_{i+52}b_{i+45}b_{i+37}b_{i+33}b_{i+28}b_{i+21}}$

В качестве аргументов функция ${\displaystyle h(x)}$ принимает значения битов из LFSR и NFSR:

 ${\displaystyle h(x)=x_{1}+x_{4}+x_{0}x_{3}+x_{2}x_{3}+x_{3}x_{4}+x_{0}x_{1}x_{2}+x_{0}x_{2}x_{3}+x_{0}x_{2}x_{4}+x_{1}x_{2}x_{4}+x_{2}x_{3}x_{4}}$

где ${\displaystyle x_{0},x_{1},x_{2},x_{3},x_{4}}$ равны соответственно ${\displaystyle s_{i+3},s_{i+25},s_{i+46},s_{i+64},b_{i+63}}$

В результате на выход поступает

 ${\displaystyle z_{i}=\sum _{k\in A}b_{i+k}+h(s_{i+3},s_{i+25},s_{i+46},s_{i+64},b_{i+63}),A=\{1,2,4,10,31,43,56\}}$

Шифр принимает на вход 80-битный ключ (secret key) и 64-битный вектор инициализации (initialization vector).

Перед тем как начать генерировать ключевой поток (keystream), шифр должен инициализировать своё состояние.
Пусть ${\displaystyle K=K_{0},..,K_{79}}$ и ${\displaystyle IV=IV_{0},..,IV_{63}}$. Можно выделить следующие этапы инициализации состояния:

1. Загрузка битов ключа ${\displaystyle K}$ в NFSR, ${\displaystyle b_{i}=K_{i},0\leq i\leq 79}$
2. Загрузка ${\displaystyle IV}$ в LFSR, ${\displaystyle s_{i}=IV_{i},0\leq i\leq 63}$
3. Заполнение оставшихся битов LFSR единицами, ${\displaystyle s_{i}=1,64\leq i\leq 79}$

После этого шифр 160 тактов работает без выдачи ключевого потока, но результат работы шифра подаётся на вход NFSR и LFSR.

В случае когда аппаратная платформа не ограничена в ресурсах, то шифр позволяет достаточно просто увеличить скорость шифрования. Т.к. оба регистра каждый такт сдвигаются на 1 бит, то если просто реализовать несколько раз (${\displaystyle N}$) функции обратной связи ${\displaystyle f(x)}$ и ${\displaystyle g(x)}$ и выходную функцию ${\displaystyle h(x)}$, то скорость шифрования можно увеличить в ${\displaystyle N}$ раз, при этом регистры сдвига за каждый такт также должны сдвигаться на ${\displaystyle N}$ бит. Младшие 15 бит регистров сдвига не используются в функциях обратной связи и поэтому ${\displaystyle N}$ может принимать значения от 1 до 16.
Т.к. при инициализации состояния шифр должен отработать 160 тактов, то это накладывает некоторые ограничения на значение ${\displaystyle N}$, ${\displaystyle i=160/N}$ должно быть целым числом.

Еще в версии 0.0 авторы заявляли, что шифр разработан таким образом, что невозможна атака быстрее, чем полный перебор ключей. Таким образом, лучшая атака должна иметь сложность порядка 2⁸⁰.

В спецификации версии 0.0 Grain ^[1] авторы утверждали: "Grain предоставляет большую надёжность, чем некоторые другие известные аппаратно ориентированные шифры. Хорошо известными примерами таких шифров является E0, используемый в Bluetooth, и A5/1, используемый в GSM. Хотя эти шифры просты в реализации, доказано, что они очень ненадёжны. По сравнению с E0 и A5/1, Grain предоставляет большую надёжность, сохраняя простоту реализации".

В версии 0.0 был обнаружен ряд серьёзных уязвимостей, поэтому в обновлённой версии 1.0 ^[2], у шифра немного изменилась выходная функция и функция обратной связи у регистра с нелинейтой обратной функцией (NFSR). После этого, с октября 2006 года не известно ни об одной атаке против Grain версии 1.0 быстрее, чем полный перебор. Однако, в сентябре 2006 года была опубликована попытка атаки на ключ^[3]. В статье утверждается: "мы нашли связанные ключи и начальные значения в Grain, для любой пары(K,IV) с вероятностью 1/22 существует связанная пара (K’,IV’) которая генерирует ключевой поток сдвинутый на 1 бит. Хотя это и не является успешной атакой на ключ, данный факт показывает возможною слабость шифра при инициализации состояния."

• Поточные шифры
• BEAN

1. ↑ Martin Hell, Thomas Johansson, Willi Meier. Grain - A Stream Cipher for Constrained Environments (англ.) : journal. — eSTREAM, 2005. — 29 April. Архивировано 26 мая 2011 года.
2. ↑ Martin Hell, Thomas Johansson, Willi Meier. Grain - A Stream Cipher for Constrained Environments (англ.) : journal. — eSTREAM, 2006. Архивировано 27 мая 2011 года.
3. ↑ Ozgul Kucuk. Slide Resynchronization Attack on the Initialization of Grain 1.0 (англ.) : journal. — eSTREAM, 2006. — 16 July. Архивировано 27 мая 2011 года.

• Grain на странице проекта eSTREAM Архивная копия от 6 октября 2008 на Wayback Machine
• Описание Grain Архивная копия от 27 мая 2011 на Wayback Machine
• Принципы построения потоковых шифров Архивная копия от 26 мая 2011 на Wayback Machine