Interested Article - Grain

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

Описание

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

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

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

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

Если представить состояние регистра в виде , то следующий младший (правый) бит будет задаваться соотношением

 

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

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

  

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

  

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

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

 

где равны соответственно

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

 

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

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

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

Перед тем как начать генерировать ключевой поток ( keystream ), шифр должен инициализировать своё состояние.
Пусть и . Можно выделить следующие этапы инициализации состояния:

1. Загрузка битов ключа  в NFSR, 
2. Загрузка  в LFSR, 
3. Заполнение оставшихся битов LFSR единицами, 

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

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

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

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

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

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

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

См. также

Примечания

  1. , , . (англ.) : journal. — eSTREAM, 2005. — 29 April. 26 мая 2011 года.
  2. , , . (англ.) : journal. — eSTREAM, 2006. 27 мая 2011 года.
  3. . (англ.) : journal. — eSTREAM, 2006. — 16 July. 27 мая 2011 года.

Ссылки

Источник —

Same as Grain