BEAN

BEAN — симметричный алгоритм синхронного потокового шифрования, основанный на алгоритме Grain. Является представителем так называемых «облегчённых» шифров, то есть ориентированных на аппаратную реализацию внутри устройств с ограниченной вычислительной мощностью, малой памятью и малым энергопотреблением (например, RFID-метки или сенсорные сети). Был предложен в 2009 году Нави Кумаром, Шрикантой Ойха, Критикой Джайн и Сангитой Лал.

Описание

В симметричных потоковых алгоритмах шифрование (или дешифрование) происходит путем гаммирования, то есть «наложения» случайной последовательности бит (гаммы) на открытый текст (или шифротекст соответственно). Под «наложением» понимается операция XOR над битами гаммы и текста. Гаммирующая последовательность, которая также называется keystream (поток ключей), получается с помощью генераторов псевдослучайных чисел .

Подобно Grain, BEAN состоит из двух 80-битных регистров сдвига и функции вывода. Но если в Grain применяются один регистр с линейной обратной связью (LFSR) и один регистр с нелинейной функцией обратной связи (NFSR), то в BEAN используются два регистра сдвига с обратной связью по переносу (FCSR). LFSR используется в Grain для большего периода последовательности, а NFSR для обеспечения нелинейности. FCSR в BEAN сочетает оба этих свойства, при этом оставаясь таким же компактным на аппаратном уровне.

В обоих регистрах очередной записываемый бит равен сумме по модулю 2 всех отводов ячеек регистра. Такая реализация называется конфигурацией Фибоначчи. Тогда как в Grain регистры реализованы по конфигурации Галуа, то есть последний 79-й бит без изменений записывается на 0-е место, а в каждую следующую -ю ячейку записывается сумма по модулю 2 предыдущей -й и отвода 79-й ячейки.

Регистры FCSR Оба регистра имеют длину 80 бит. Обозначим их как FCSR-I и FCSR-II, а их состояния на -ом такте как и соответственно:

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

то есть обновление состояния FCSR-I на очередном такте выглядит следующим образом:

FCSR-II Аналогично для FCSR-II функция обратной связи:

Обновление состояния:

Функция вывода Булева функция используется для генерации гаммы. Авторы алгоритма задают её с помощью S-блока, принимающего на вход 6 бит (2 бита определяют строку и 4 бита определяют столбец) и возвращающего слово из 4 бит. Но поскольку из слова дальше берётся только последний бит, можно представить в виде полинома Жегалкина:

Биты гаммы находятся следующим образом:

Таким образом, за один такт генерируются сразу два бита.

Инициализация состояния Инициализация происходит путём загрузки 80-битного ключа в регистры FCSR-I и FCSR-II:

Регистры переноса инициализируются нулями: .

Затем FCSR делают 81 такт вхолостую, после чего начинается генерация гаммы.

Производительность BEAN обеспечивает хороший баланс между безопасностью, скоростью и стоимостью реализации. Grain может генерировать два бита гаммы за такт, используя дополнительные аппаратные средства. Тогда как BEAN справляется с этой задачей без дополнительного оборудования.

Как утверждают авторы алгоритма, генерация бит с помощью BEAN происходит в среднем в 1.5 раза быстрее, чем с помощью Grain, а потребляемая память уменьшается на 10 %.

Безопасность Важной целью при разработке криптографического алгоритма является достижение лавинного эффекта, который заключается в том, что при изменении одного бита ключа (открытого текста) как минимум половина битов гаммы (шифротекста) изменится. Для сравнения BEAN и Grain было взято 1000000 случайных 80-битных ключей, и для каждого ключа было сгенерировано 80 бит гаммы с помощью обоих алгоритмов. Как утверждают авторы, в BEAN для 65,3 % ключей полученные биты удовлетворяют условиям лавинного эффекта, тогда как в Grain эта доля составляет 63,1 %.

Алгоритм был также протестирован на статистических тестах NIST, которые не показали отклонение генерируемого потока ключей от случайной последовательности.

В 2011 Мартин Агрен и Мартин Хелл в своей статье указали на неоптимальность функции вывода. Они предложили алгоритм эффективного для BEAN, а также алгоритм , который несколько быстрее полного перебора ( в предложенном алгоритме против при полном переборе) и не затратен по памяти.

В 2013 теми же авторами в сотрудничестве с Хуэй Вонгом и Томасом Йоханссоном были обнаружены новые корреляции между битами ключа и битами гаммы, что привело к созданию ещё более эффективного алгоритма атаки на восстановление ключа (). Кроме того, были предложены некоторые улучшения FCSR, а также более эффективные функции вывода, стойкие к известным методам атаки.

Применение Как и многие алгоритмы «облегчённой» криптографии, BEAN может находить своё применение в RFID метках, беспроводных сенсорных сетях, а также во встраиваемых системах.

Примечания

Литература

Ссылки

Статья про «облегчённые» потоковые шифры на cryptowiki.net

Категория:Шифры