Русская Википедия:Grain
Grain - симметричный алгоритм синхронного потокового шифрования, ориентированный, в первую очередь на аппаратную реализацию. Шифр представлен на конкурсе eSTREAM в 2004 году Мартином Хеллом, Томасом Юханссоном и Вилли Мейером. Алгоритм стал одним из финалистов конкурса во втором профиле (аппаратно ориентированные шифры).
Описание
Шифр состоит из трёх основных блоков: двух 80-битных регистров сдвига с обратной связью и выходной функции. Один из регистров обладает линейной функцией обратной связи (LFSR), второй регистр имеет нелинейную функцию обратной связи (NFSR). Внутреннее состояние шифра полностью определяется регистрами сдвига.
Регистр сдвига с линейной обратной связью
Функция обратной связи данного регистра задаётся примитивным полиномом <math>f(x) = 1 + x^{18} + x^{29} + x^{42} + x^{57} + x^{67} + x^{80}</math>
Если представить состояние регистра в виде <math>s_{i}, s_{i+1}, .. , s_{i+79}</math>, то следующий младший (правый) бит будет задаваться соотношением
<math>s_{i+80} = s_{i+62} + s_{i+51} + s_{i+38} + s_{i+23} + s_{i+13} + s_{i}</math>
Регистр сдвига с нелинейной обратной связью
Функция обратной связи регистра с нелинейной обратной связью задаётся соотношением
<math>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}</math>
Для битов <math>b_{i}</math> регистра NLSR получается выражение
<math>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}</math>
Выходная функция
В качестве аргументов функция <math>h(x)</math> принимает значения битов из LFSR и NFSR:
<math>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}</math>
где <math>x_{0}, x_{1}, x_{2}, x_{3}, x_{4}</math> равны соответственно <math>s_{i+3}, s_{i+25}, s_{i+46}, s_{i+64}, b_{i+63}</math>
В результате на выход поступает
<math>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 \} </math>
Инициализация состояния
Шифр принимает на вход 80-битный ключ (secret key) и 64-битный вектор инициализации (initialization vector).
Перед тем как начать генерировать ключевой поток (keystream), шифр должен инициализировать своё состояние.
Пусть <math>K = K_{0}, .., K_{79} </math> и <math>IV = IV_{0}, .., IV_{63} </math>. Можно выделить следующие этапы инициализации состояния:
1. Загрузка битов ключа <math>K</math> в NFSR, <math>b_{i} = K_{i}, 0 \le i \le 79</math>
2. Загрузка <math>IV</math> в LFSR, <math>s_{i} = IV_{i}, 0 \le i \le 63</math>
3. Заполнение оставшихся битов LFSR единицами, <math>s_{i} = 1, 64 \le i \le 79</math>
После этого шифр 160 тактов работает без выдачи ключевого потока, но результат работы шифра подаётся на вход NFSR и LFSR.
Производительность
В случае когда аппаратная платформа не ограничена в ресурсах, то шифр позволяет достаточно просто увеличить скорость шифрования. Т.к. оба регистра каждый такт сдвигаются на 1 бит, то если просто реализовать несколько раз (<math>N</math>) функции обратной связи <math>f(x)</math> и <math>g(x)</math> и выходную функцию <math>h(x)</math>, то скорость шифрования можно увеличить в <math>N</math> раз, при этом регистры сдвига за каждый такт также должны сдвигаться на <math>N</math> бит. Младшие 15 бит регистров сдвига не используются в функциях обратной связи и поэтому <math>N</math> может принимать значения от 1 до 16.
Т.к. при инициализации состояния шифр должен отработать 160 тактов, то это накладывает некоторые ограничения на значение <math>N</math>, <math>i = 160/N</math> должно быть целым числом.
Безопасность
Еще в версии 0.0 авторы заявляли, что шифр разработан таким образом, что невозможна атака быстрее, чем полный перебор ключей. Таким образом, лучшая атака должна иметь сложность порядка 280.
В спецификации версии 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 бит. Хотя это и не является успешной атакой на ключ, данный факт показывает возможною слабость шифра при инициализации состояния."
См. также
Примечания
Ссылки
- Grain на странице проекта eSTREAM Шаблон:Wayback
- Описание Grain Шаблон:Wayback
- Принципы построения потоковых шифров Шаблон:Wayback
Шаблон:Симметричные криптоалгоритмы
_key_initialization.png){kind=link}
_throughput_rate.png){kind=link}