BEAN

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

Описание

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

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

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

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

Регистры FCSR

Оба регистра имеют длину 80 бит. Обозначим их как FCSR-I и FCSR-II, а их состояния на ${\displaystyle i}$-ом такте как ${\displaystyle \mathbf {B} ^{i}}$ и ${\displaystyle \mathbf {S} ^{i}}$ соответственно[6]:

${\displaystyle \mathbf {B} ^{i}=(\mathbf {b} ^{i},m_{b}^{i})=(b_{i},...,b_{i+79},m_{b}^{i})}$

${\displaystyle \mathbf {S} ^{i}=(\mathbf {s} ^{i},m_{s}^{i})=(s_{i},...,s_{i+79},m_{s}^{i})}$

FCSR-I

Функция обратной связи FCSR-I ${\displaystyle f(x)}$ задаётся примитивным многочленом 80-й степени[7]:

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

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

${\displaystyle \sigma _{b}^{i}=b_{i+62}+b_{i+51}+b_{i+38}+b_{i+23}+b_{i+13}+b_{i}+m_{b}^{i}}$

${\displaystyle b_{i+80}=\sigma _{b}^{i}\operatorname {mod} 2}$

${\displaystyle m_{b}^{i+1}=\sigma _{b}^{i}\operatorname {div} 2}$

FCSR-II

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

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

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

${\displaystyle \sigma _{s}^{i}=s_{i+78}+s_{i+77}+s_{i+76}+s_{i+1}+m_{s}^{i}}$

${\displaystyle s_{i+80}=\sigma _{s}^{i}\operatorname {mod} 2}$

${\displaystyle m_{s}^{i+1}=\sigma _{s}^{i}\operatorname {div} 2}$

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

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

${\displaystyle 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}}$${\displaystyle \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 }$

${\displaystyle \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}}$${\displaystyle \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 }$

${\displaystyle \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}}$${\displaystyle \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 }$

${\displaystyle \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}}$

Биты гаммы ${\displaystyle z_{0},z_{1},z_{2},...}$ находятся следующим образом[10]:

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

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

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

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

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

${\displaystyle b_{i}=k_{i+81},}$ ${\displaystyle i=-81,...,-2}$

${\displaystyle s_{i}=k_{i+81},}$ ${\displaystyle i=-81,...,-2}$

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

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

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

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

Как утверждают авторы алгоритма[13], генерация ${\displaystyle 10^{7}}$ бит с помощью BEAN происходит в среднем в 1.5 раза быстрее, чем с помощью Grain, а потребляемая память уменьшается на 10 %.

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

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

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

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

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

Применение

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

Примечания

1. Kumar, 2009.
2. Churchhouse, 2002.
3. Kumar, 2009, Figure 1, с. 169.
4. Klapper, 1993.
5. Goresky, 2002.
6. Agren, 2011, с. 23.
7. Kumar, 2009, Equation 1, с. 169.
8. Kumar, 2009, Equation 3, с. 169.
9. Kumar, 2009, Table 1, с. 170.
10. Agren, 2011, Eqations 5, 6, с. 23.
11. Kumar, 2009, с. 170.
12. Manifavas, 2016, с. 338.
13. Kumar, 2009, с. 171.
14. Kumar, 2009, Table 3, с. 170.
15. Agren, 2011, с. 24.
16. Wang, 2013.
17. Manifavas, 2016.

Литература

• Kumar N., Ojha S., Jain K., Lal S. BEAN: a lightweight stream cipher // SIN '09 Proceedings of the 2nd international conference on Security of information and networks, Famagusta, North Cyprus,. — 2009. — P. 168—171. — doi:10.1145/1626195.1626238.
• Ågren M., Hell M. Cryptanalysis of the stream cipher BEAN // SIN '11 Proceedings of the 4th international conference on Security of information and networks, Famagusta, North Cyprus,. — 2011. — P. 21—28. — doi:10.1145/2070425.2070432.
• Wang H., Hell M., Johansson T., Ågren M. Improved Key Recovery Attack on the BEAN Stream Cipher // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. — 2013. — P. 1437—1444. — doi:10.1587/transfun.E96.A.1437.
• Manifavas C., Hatzivasilis G., Fysarakis K., Papaefstathiou Y. A survey of lightweight stream ciphers for embedded systems // Security and Communication Networks. — 2016. — P. 1226—1246. — doi:10.1002/sec.1399.
• Goresky M., Klapper A. M. Fibonacci and Galois representations of feedback-with-carry shift registers // IEEE Transactions on Information Theory. — 2002. — P. 2826—2836. — doi:10.1109/TIT.2002.804048.
• Klapper A. M., Goresky M. 2-adic shift registers // International Workshop on Fast Software Encryption. — Springer, 1993. — P. 174-178. — doi:10.1007/3-540-58108-1.
• Churchhouse R., Churchhouse R. F., Churchhouse R. F. Codes and ciphers: Julius Caesar, the Enigma, and the Internet.. — 10.1017/CBO9780511542978, 2002. — P. 67-71. — doi:10.1007/3-540-58108-1.

Ссылки

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