Grain

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

Описание

Файл:Grain structure.png

Структура шифра Grain

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

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

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

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

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

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

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

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

Для битов $b_i$ регистра NLSR получается выражение

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

Выходная функция

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

 $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$

где $x_0,x_1,x_2,x_3,x_4$ равны соответственно $s_{i+3},s_{i+25},s_{i+46},s_{i+64},b_{i+63}$

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

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

Инициализация состояния

Файл:Grain (cipher) key initialization.png

Инициализация состояния

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

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

1. Загрузка битов ключа $K$ в NFSR, $b_i=K_i,0\le i\le 79$
2. Загрузка $IV$ в LFSR, $s_i=I{V}_i,0\le i\le 63$
3. Заполнение оставшихся битов LFSR единицами, $s_i=1,64\le i\le 79$

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

Производительность

Файл:Grain (cipher) throughput rate.png

Ускорение шифрования

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

Безопасность

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

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

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

См. также

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

Ссылки

• Grain на странице проекта eSTREAM Шаблон:Wayback
• Описание Grain Шаблон:Wayback
• Принципы построения потоковых шифров Шаблон:Wayback