BEAN

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

Описание

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

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

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

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

Регистры FCSR

Оба регистра имеют длину 80 бит. Обозначим их как FCSR-I и FCSR-II, а их состояния на $i$-ом такте как ${𝐁}^i$ и ${𝐒}^i$ соответственноШаблон:Sfn:

${𝐁}^i=({𝐛}^i,m_b^i)=(b_i,...,b_{i+79},m_b^i)$

${𝐒}^i=({𝐬}^i,m_s^i)=(s_i,...,s_{i+79},m_s^i)$

FCSR-I

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

$f(x)=1+x^{18}+x^{29}+x^{42}+x^{57}+x^{67}+x^{80}$

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

${\sigma }_b^i=b_{i+62}+b_{i+51}+b_{i+38}+b_{i+23}+b_{i+13}+b_i+m_b^i$

$b_{i+80}={\sigma }_b^i\mathrm{mod}2$

$m_b^{i+1}={\sigma }_b^i\mathrm{div}2$

FCSR-II

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

$f(x)=1+x^2+x^3+x^4+x^{79}$

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

${\sigma }_s^i=s_{i+78}+s_{i+77}+s_{i+76}+s_{i+1}+m_s^i$

$s_{i+80}={\sigma }_s^i\mathrm{mod}2$

$m_s^{i+1}={\sigma }_s^i\mathrm{div}2$

Функция вывода

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

$f(x_1,...,x_6)=x_1\oplus x_4\oplus x_1{x}_2\oplus x_1{x}_3\oplus x_1{x}_4\oplus x_1{x}_5\oplus x_2{x}_5$$\oplus x_2{x}_6\oplus x_3{x}_4\oplus x_3{x}_5\oplus x_3{x}_6\oplus x_4{x}_6\oplus x_5{x}_6\oplus$

$\oplus x_1{x}_2{x}_5\oplus x_1{x}_2{x}_6\oplus x_1{x}_3{x}_4\oplus x_1{x}_3{x}_6\oplus x_1{x}_4{x}_5\oplus x_1{x}_4{x}_6$$\oplus x_2{x}_3{x}_6\oplus x_2{x}_4{x}_5\oplus x_2{x}_4{x}_6\oplus x_2{x}_5{x}_6\oplus x_3{x}_4{x}_5\oplus$

$\oplus x_3{x}_4{x}_6\oplus x_4{x}_5{x}_6\oplus x_1{x}_2{x}_3{x}_5\oplus x_1{x}_2{x}_3{x}_6\oplus x_1{x}_2{x}_4{x}_5$$\oplus x_1{x}_2{x}_4{x}_6\oplus x_1{x}_2{x}_5{x}_6\oplus x_1{x}_3{x}_4{x}_5\oplus x_1{x}_3{x}_4{x}_6\oplus$

$\oplus x_1{x}_3{x}_5{x}_6\oplus x_1{x}_4{x}_5{x}_6\oplus x_1{x}_2{x}_3{x}_4{x}_6\oplus x_1{x}_2{x}_4{x}_5{x}_6$

Биты гаммы $z_0,z_1,z_2,...$ находятся следующим образомШаблон:Sfn:

$z_{2i}=f(b_{i+23},b_{i+73},s_{i+5},s_{i+9},s_{i+29},b_{i+51})$

$z_{2i+1}=f(b_{i+23},b_{i+73},s_{i+5},s_{i+9},s_{i+29},s_{i+67})$

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

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

Инициализация происходит путём загрузки 80-битного ключа $K=(k_0,k_1,...,k_{79})$ в регистры FCSR-I и FCSR-II:

$b_i=k_{i+81},$ $i=-81,...,-2$

$s_i=k_{i+81},$ $i=-81,...,-2$

Регистры переноса инициализируются нулями: $m_s^{i-81}=m_b^{i-81}=0$.

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

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

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

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

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

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

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

В 2011 Мартин Агрен и Мартин Хелл в своей статье указали на неоптимальность функции вывода. Они предложили алгоритм эффективного Шаблон:Iw для BEAN, а также алгоритм Шаблон:Iw, который несколько быстрее полного перебора ($2^{73}$ в предложенном алгоритме против $2^{80}$ при полном переборе) и не затратен по памятиШаблон:Sfn.

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

Применение

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

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга

Ссылки

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