BEAN
BEAN—симметричный алгоритмсинхронногопотокового шифрования,основанный на алгоритмеGrain.Является представителем так называемых «облегчённых» шифров, то есть ориентированных на аппаратную реализацию внутри устройств с ограниченной вычислительной мощностью, малой памятью и малым энергопотреблением (например,RFID-меткиилисенсорные сети). Был предложен в 2009 годуНави Кумаром,Шрикантой Ойха,Критикой ДжайниСангитой Лал[1].
Описание
[править|править код]![](https://upload.wikimedia.org/wikipedia/commons/thumb/d/de/BEAN-scheme.png/706px-BEAN-scheme.png)
В симметричныхпотоковых алгоритмахшифрование (или дешифрование) происходит путемгаммирования,то есть «наложения» случайной последовательности бит (гаммы) на открытый текст (или шифротекст соответственно). Под «наложением» понимается операцияXORнад битами гаммы и текста. Гаммирующая последовательность, которая также называетсяkeystream(поток ключей), получается с помощьюгенераторов псевдослучайных чисел[2].
ПодобноGrain,BEAN состоит из двух 80-битныхрегистровсдвига и функции вывода. Но если вGrainприменяются одинрегистр с линейной обратной связью (LFSR)и один регистр с нелинейной функцией обратной связи (NFSR), то в BEAN используются дварегистра сдвига с обратной связью по переносу (FCSR)[3].LFSR используется в Grain для большего периода последовательности, а NFSR для обеспечения нелинейности. FCSR в BEAN сочетает оба этих свойства, при этом оставаясь таким же компактным на аппаратном уровне[4].
В обоих регистрах очередной записываемый бит равенсумме по модулю 2всех отводов ячеек регистра. Такая реализация называется конфигурациейФибоначчи.Тогда как в Grain регистры реализованы по конфигурацииГалуа,то есть последний 79-й бит без изменений записывается на 0-е место, а в каждую следующую-ю ячейку записывается сумма по модулю 2 предыдущей-й и отвода 79-й ячейки[5].
Регистры FCSR
[править|править код]Оба регистра имеют длину 80 бит. Обозначим их как FCSR-I и FCSR-II, а их состояния на-ом такте какисоответственно[6]:
FCSR-I
[править|править код]Функция обратной связи FCSR-Iзадаётсяпримитивным многочленом80-й степени[7]:
то есть обновление состояния FCSR-I на очередном такте выглядит следующим образом[6]:
FCSR-II
[править|править код]Аналогично для FCSR-II функция обратной связи[8]:
Обновление состояния[6]:
Функция вывода
[править|править код]Булева функцияиспользуется для генерациигаммы.Авторы алгоритма задают её с помощьюS-блока,принимающего на вход 6 бит (2 бита определяют строку и 4 бита определяют столбец) и возвращающего слово из 4 бит[9].Но поскольку из слова дальше берётся только последний бит,можно представить в видеполинома Жегалкина[6]:
Биты гаммынаходятся следующим образом[10]:
Таким образом, за один такт генерируются сразу два бита.
Инициализация состояния
[править|править код]Инициализация происходит путём загрузки 80-битного ключав регистры FCSR-I и FCSR-II:
Регистры переноса инициализируются нулями:.
Затем FCSR делают 81 такт вхолостую, после чего начинается генерация гаммы[11].
Производительность
[править|править код]BEAN обеспечивает хороший баланс между безопасностью, скоростью и стоимостью реализации. Grain может генерировать два бита гаммы за такт, используя дополнительные аппаратные средства. Тогда как BEAN справляется с этой задачей без дополнительного оборудования[12].
Как утверждают авторы алгоритма[13],генерациябит с помощью BEAN происходит в среднем в 1.5 раза быстрее, чем с помощью Grain, а потребляемая память уменьшается на 10 %.
Безопасность
[править|править код]Важной целью при разработке криптографического алгоритма является достижениелавинного эффекта,который заключается в том, что при изменении одного бита ключа (открытого текста) как минимум половина битов гаммы (шифротекста) изменится. Для сравнения BEAN и Grain было взято 1000000 случайных 80-битных ключей, и для каждого ключа было сгенерировано 80 бит гаммы с помощью обоих алгоритмов. Как утверждают авторы, в BEAN для 65,3 % ключей полученные биты удовлетворяют условиям лавинного эффекта, тогда как в Grain эта доля составляет 63,1 %[11].
Алгоритм был также протестирован настатистических тестах NIST,которые не показали отклонение генерируемого потока ключей от случайной последовательности[14].
В 2011 Мартин Агрен и Мартин Хелл в своей статье указали на неоптимальность функции вывода. Они предложили алгоритм эффективногоразличителя[англ.]для BEAN, а также алгоритматаки на восстановление ключа[англ.],который несколько быстрее полного перебора (в предложенном алгоритме противпри полном переборе) и не затратен по памяти[15].
В 2013 теми же авторами в сотрудничестве с Хуэй Вонгом и Томасом Йоханссоном были обнаружены новые корреляции между битами ключа и битами гаммы, что привело к созданию ещё более эффективного алгоритма атаки на восстановление ключа (). Кроме того, были предложены некоторые улучшения FCSR, а также более эффективные функции вывода, стойкие к известным методам атаки[16].
Применение
[править|править код]Как и многие алгоритмы «облегчённой» криптографии, BEAN может находить своё применение вRFIDметках,беспроводных сенсорных сетях,а также вовстраиваемых системах[17].
Примечания
[править|править код]- ↑Kumar, 2009.
- ↑Churchhouse, 2002.
- ↑Kumar, 2009,Figure 1, с. 169.
- ↑Klapper, 1993.
- ↑Goresky, 2002.
- ↑1234Agren, 2011,с. 23.
- ↑Kumar, 2009,Equation 1, с. 169.
- ↑Kumar, 2009,Equation 3, с. 169.
- ↑Kumar, 2009,Table 1, с. 170.
- ↑Agren, 2011,Eqations 5, 6, с. 23.
- ↑12Kumar, 2009,с. 170.
- ↑Manifavas, 2016,с. 338.
- ↑Kumar, 2009,с. 171.
- ↑Kumar, 2009,Table 3, с. 170.
- ↑Agren, 2011,с. 24.
- ↑Wang, 2013.
- ↑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(англ.)
Эта статья входит в числодобротных статейрусскоязычного раздела Википедии. |