Перейти к содержанию

BEAN

Добавить ссылки
Материал из Мегавики — свободной энциклопедии
Данная страница не проверялась участниками с соответствующими правами.
У этого термина существуют и другие значения, см. 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-е место, а в каждую следующую i-ю ячейку записывается сумма по модулю 2 предыдущей (i−1)-й и отвода 79-й ячейки[5].

Регистры FCSR[править]

Оба регистра имеют длину 80 бит. Обозначим их как FCSR-I и FCSR-II, а их состояния на i-ом такте как 𝐁i и 𝐒i соответственно[6]:

𝐁i=(𝐛i,mbi)=(bi,...,bi+79,mbi)

𝐒i=(𝐬i,msi)=(si,...,si+79,msi)

FCSR-I[править]

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

f(x)=1+x18+x29+x42+x57+x67+x80

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

σbi=bi+62+bi+51+bi+38+bi+23+bi+13+bi+mbi

bi+80=σbimod⁡2

mbi+1=σbidiv⁡2

FCSR-II[править]

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

f(x)=1+x2+x3+x4+x79

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

σsi=si+78+si+77+si+76+si+1+msi

si+80=σsimod⁡2

msi+1=σsidiv⁡2

Функция вывода[править]

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

f(x1,...,x6)=x1⊕x4⊕x1x2⊕x1x3⊕x1x4⊕x1x5⊕x2x5⊕x2x6⊕x3x4⊕x3x5⊕x3x6⊕x4x6⊕x5x6⊕

⊕x1x2x5⊕x1x2x6⊕x1x3x4⊕x1x3x6⊕x1x4x5⊕x1x4x6⊕x2x3x6⊕x2x4x5⊕x2x4x6⊕x2x5x6⊕x3x4x5⊕

⊕x3x4x6⊕x4x5x6⊕x1x2x3x5⊕x1x2x3x6⊕x1x2x4x5⊕x1x2x4x6⊕x1x2x5x6⊕x1x3x4x5⊕x1x3x4x6⊕

⊕x1x3x5x6⊕x1x4x5x6⊕x1x2x3x4x6⊕x1x2x4x5x6

Биты гаммы z0,z1,z2,... находятся следующим образом[10]:

z2i=f(bi+23,bi+73,si+5,si+9,si+29,bi+51)

z2i+1=f(bi+23,bi+73,si+5,si+9,si+29,si+67)

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

Инициализация состояния[править]

Инициализация происходит путём загрузки 80-битного ключа K=(k0,k1,...,k79) в регистры FCSR-I и FCSR-II:

bi=ki+81, i=−81,...,−2

si=ki+81, i=−81,...,−2

Регистры переноса инициализируются нулями: msi−81=mbi−81=0.

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

Производительность[править]

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

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

Безопасность[править]

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

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

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

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

Ссылки[править]


Источник — https://megawiki.ru/wiki/BEAN