Grain

02.02.2021

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

Описание

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

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

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

Если представить состояние регистра в виде s i , s i + 1 , . . , s i + 79 {displaystyle 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 {displaystyle 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 {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}}

Для битов b i {displaystyle 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 {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}}

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

В качестве аргументов функция h ( x ) {displaystyle 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 {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}}

где x 0 , x 1 , x 2 , x 3 , x 4 {displaystyle 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 {displaystyle s_{i+3},s_{i+25},s_{i+46},s_{i+64},b_{i+63}}

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

z i = ∑ k ∈ 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 } {displaystyle z_{i}=sum _{kin 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), шифр должен инициализировать своё состояние.
Пусть K = K 0 , . . , K 79 {displaystyle K=K_{0},..,K_{79}} и I V = I V 0 , . . , I V 63 {displaystyle IV=IV_{0},..,IV_{63}} . Можно выделить следующие этапы инициализации состояния:

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

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

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

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

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

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

В спецификации версии 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 бит. Хотя это и не является успешной атакой на ключ, данный факт показывает возможною слабость шифра при инициализации состояния."