BEAN

У этого термина существуют и другие значения, см. Bean.

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

## Содержание

* 1 Описание
* 1.1 Регистры FCSR
* 1.1.1 FCSR-I
* 1.1.2 FCSR-II
* 1.2 Функция вывода
* 1.3 Инициализация состояния
* 2 Производительность
* 3 Безопасность
* 4 Применение
* 5 Примечания
* 6 Литература
* 7 Ссылки

## Описание

[править | править код]

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

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

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

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

### Регистры FCSR

[править | править код]

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

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

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

#### FCSR-I

[править | править код]

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

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

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

σ b i = b i + 62 + b i + 51 + b i + 38 + b i + 23 + b i + 13 + b i + m b i {\displaystyle \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 = σ b i mod ⁡ 2 {\displaystyle b_{i+80}=\sigma _{b}^{i}\operatorname {mod} 2}

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

#### FCSR-II

[править | править код]

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

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

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

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

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

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

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

[править | править код]

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

f ( x 1 , . . . , x 6 ) = x 1 ⊕ x 4 ⊕ x 1 x 2 ⊕ x 1 x 3 ⊕ x 1 x 4 ⊕ x 1 x 5 ⊕ x 2 x 5 {\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}} ⊕ x 2 x 6 ⊕ x 3 x 4 ⊕ x 3 x 5 ⊕ x 3 x 6 ⊕ x 4 x 6 ⊕ x 5 x 6 ⊕ {\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 }

⊕ x 1 x 2 x 5 ⊕ x 1 x 2 x 6 ⊕ x 1 x 3 x 4 ⊕ x 1 x 3 x 6 ⊕ x 1 x 4 x 5 ⊕ x 1 x 4 x 6 {\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}} ⊕ x 2 x 3 x 6 ⊕ x 2 x 4 x 5 ⊕ x 2 x 4 x 6 ⊕ x 2 x 5 x 6 ⊕ x 3 x 4 x 5 ⊕ {\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 }

⊕ x 3 x 4 x 6 ⊕ x 4 x 5 x 6 ⊕ x 1 x 2 x 3 x 5 ⊕ x 1 x 2 x 3 x 6 ⊕ x 1 x 2 x 4 x 5 {\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}} ⊕ x 1 x 2 x 4 x 6 ⊕ x 1 x 2 x 5 x 6 ⊕ x 1 x 3 x 4 x 5 ⊕ x 1 x 3 x 4 x 6 ⊕ {\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 }

⊕ x 1 x 3 x 5 x 6 ⊕ x 1 x 4 x 5 x 6 ⊕ x 1 x 2 x 3 x 4 x 6 ⊕ x 1 x 2 x 4 x 5 x 6 {\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}}

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

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

z 2 i + 1 = f ( b i + 23 , b i + 73 , s i + 5 , s i + 9 , s i + 29 , s i + 67 ) {\displaystyle 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 ) {\displaystyle K=(k_{0},k_{1},...,k_{79})} в регистры FCSR-I и FCSR-II:

b i = k i + 81 , {\displaystyle b_{i}=k_{i+81},} i = − 81 , . . . , − 2 {\displaystyle i=-81,...,-2}

s i = k i + 81 , {\displaystyle s_{i}=k_{i+81},} i = − 81 , . . . , − 2 {\displaystyle i=-81,...,-2}

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

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

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

[править | править код]

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

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

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

[править | править код]

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

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

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

В 2013 теми же авторами в сотрудничестве с Хуэй Вонгом и Томасом Йоханссоном были обнаружены новые корреляции между битами ключа и битами гаммы, что привело к созданию ещё более эффективного алгоритма атаки на восстановление ключа ( 2 57.53 {\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. ↑ 1 2 3 4 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. ↑ 1 2 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 (англ.)

Эта статья входит в число добротных статей русскоязычного раздела Википедии.

|