FAZOLE

BEAN je symetrický algoritmus synchronního šifrování toku založený na algoritmu Grain . Jedná se o zástupce tzv. „lightweight“ šifer, to znamená, že jsou zaměřeny na hardwarovou implementaci uvnitř zařízení s omezeným výpočetním výkonem, nízkou pamětí a nízkou spotřebou energie (například RFID tagy nebo senzorové sítě ). Byl navržen v roce 2009 Navi Kumar , Srikanta Oiha , Kritika Jain a Sangita Lal [1] .

Popis

V symetrických proudových algoritmech dochází k šifrování (nebo dešifrování) pomocí gama , to znamená "překrytí" náhodné sekvence bitů (gama) na holém textu (nebo šifrovaném textu). "Překryv" odkazuje na operaci XOR na gama a textových bitech. Herní sekvence, které se také říká keystream (key stream), se získává pomocí generátorů pseudonáhodných čísel [2] .

Stejně jako Grain se BEAN skládá ze dvou 80bitových posuvných registrů a výstupní funkce. Ale zatímco Grain používá jeden registr lineární zpětné vazby (LFSR) a jeden registr nelineární zpětné vazby (NFSR), BEAN používá dva posuvné registry s přenosovou zpětnou vazbou (FCSR) [3] . LFSR se používá v Grain pro větší období sekvence a NFSR pro nelinearitu. FCSR v BEAN kombinuje obě tyto vlastnosti a přitom zůstává kompaktní na hardwarové úrovni [4] .

V obou registrech je další bit, který se má zapsat, roven součtu modulo 2 všech odboček buněk registru. Taková implementace se nazývá Fibonacciho konfigurace . Zatímco v Grain jsou registry implementovány podle konfigurace Galois , to znamená, že poslední 79. bit je zapsán beze změny na 0. místo a součet modulo 2 předchozí th a tap 79. buňky je zapsán do každého dalšího th. buňka [5] . $i$ $(i-1)$

Registry FCSR

Oba registry jsou dlouhé 80 bitů. Označme je jako FCSR-I a FCSR-II a jejich stavy na -tém cyklu jako [6] : $i$ $\mathbf {B} ^{i}$ $\mathbf {S} ^{i}$

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

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

FCSR-I

Zpětnovazební funkce FCSR-I je dána primitivním polynomem 80. stupně [7] : $f(x)$

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

to znamená, že aktualizace stavu FCSR-I v dalším cyklu vypadá takto [6] :

$\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}\operatorname {mod} 2$

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

FCSR II

Podobně pro FCSR-II je funkce zpětné vazby [8] :

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

Aktualizace stavu [6] :

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

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

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

Výstupní funkce

Pro generování gama se používá booleovská funkce . Autoři algoritmu jej nastavili pomocí S-boxu , který jako vstup bere 6 bitů (2 bity definují řádek a 4 bity definují sloupec) a vrací slovo o 4 bitech [9] . Ale protože je ze slova převzat pouze poslední bit, lze jej reprezentovat jako Zhegalkinův polynom [6] : $f(x_{1},...,x_{6})$ $f(\cdot )$

$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}\ plus 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}$

Gamma bity se nacházejí následovně [10] : $z_{0},z_{1},z_{2},...$

$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})$

V jednom cyklu jsou tedy generovány dva bity najednou.

Inicializace stavu

Inicializace probíhá načtením 80bitového klíče do registrů FCSR-I a FCSR-II: $K=(k_{0},k_{1},...,k_{79})$

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

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

Nosné registry jsou inicializovány na nulu: . $m_{s}^{i-81}=m_{b}^{i-81}=0$

Poté FCSR provede 81 nečinných cyklů, po kterých začne generování gama [11] .

Výkon

BEAN vytváří dobrou rovnováhu mezi bezpečností, rychlostí a náklady na implementaci. Grain může generovat dva gama bity na takt pomocí dalšího hardwaru. Zatímco BEAN se s tímto úkolem vypořádá bez dalšího vybavení [12] .

Podle autorů algoritmu [13] je generování bitů pomocí BEAN v průměru 1,5krát rychlejší než pomocí Grain a spotřeba paměti je snížena o 10 %. $10^{7}$

Zabezpečení

Důležitým cílem při vývoji kryptografického algoritmu je dosáhnout lavinový efekt , který spočívá v tom, že když se změní jeden bit klíče (prostý text), změní se alespoň polovina bitů gama (šifrového textu). Pro srovnání BEAN a Grain bylo odebráno 1 000 000 náhodných 80bitových klíčů a 80 bitů gama bylo vygenerováno pro každý klíč pomocí obou algoritmů. Podle autorů v BEANu pro 65,3 % klíčů vyhovují přijaté bity podmínkám lavinového efektu, zatímco v Grain je tento podíl 63,1 % [11] .

Algoritmus byl také testován na statistických testech NIST , které neukázaly odchylku generovaného klíčového proudu od náhodné sekvence [14] .

V roce 2011 Martin Agren a Martin Hell ve svém článku poukázali na neoptimálnost inferenční funkce. Navrhli účinný diskriminační algoritmus pro BEAN, stejně jako algoritmus pro obnovení klíče , který je poněkud rychlejší než vyčerpávající vyhledávání ( vs. vyčerpávající vyhledávání v navrhovaném algoritmu ) a není náročný na paměť [15] . $2^{73}$ $2^{80}$

V roce 2013 stejní autoři ve spolupráci s Hui Wongem a Thomasem Johanssonem objevili nové korelace mezi klíčovými bity a gama bity, které vedly k ještě účinnějšímu algoritmu útoku na obnovu klíče ( ). Kromě toho byla navržena některá vylepšení FCSR a také účinnější funkce odvození, které jsou odolné vůči známým metodám útoku [16] . $2^{57,53}$

Aplikace

Stejně jako mnoho „odlehčených“ kryptografických algoritmů může BEAN najít uplatnění v RFID značkách, bezdrátových senzorových sítích a také ve vestavěných systémech [17] .

Poznámky

↑ Kumar, 2009 .
↑ Kostelní dům, 2002 .
↑ Kumar, 2009 , Obrázek 1, s. 169.
↑ Klapka, 1993 .
↑ Goresky, 2002 .
↑ 1 2 3 4 Agren, 2011 , str. 23.
↑ Kumar, 2009 , Rovnice 1, str. 169.
↑ Kumar, 2009 , Rovnice 3, str. 169.
↑ Kumar, 2009 , Tabulka 1, str. 170.
↑ Agren, 2011 , Rovnice 5, 6, str. 23.
↑ 1 2 Kumar, 2009 , s. 170.
↑ Manifavas, 2016 , str. 338.
↑ Kumar, 2009 , str. 171.
↑ Kumar, 2009 , Tabulka 3, str. 170.
↑ Agren, 2011 , str. 24.
↑ Wang, 2013 .
↑ Manifavas, 2016 .

Literatura

Kumar N., Ojha S., Jain K., Lal S. BEAN: odlehčená proudová šifra // SIN '09 Sborník příspěvků z 2. mezinárodní konference o bezpečnosti informací a sítí, Famagusta, Severní Kypr,. - 2009. - S. 168-171. - doi : 10.1145/1626195.1626238 .
Ågren M., Hell M. Kryptoanalýza proudové šifry BEAN // SIN '11 Sborník příspěvků ze 4. mezinárodní konference o bezpečnosti informací a sítí, Famagusta, Severní Kypr,. - 2011. - S. 21-28. - doi : 10.1145/2070425.2070432 .
Wang H., Hell M., Johansson T., Ågren M. Zlepšený útok obnovy klíče na šifru BEAN Stream // Transactions IEICE on Fundamentals of Electronics, Communications and Computer Sciences. - 2013. - S. 1437-1444. - doi : 10.1587/transfun.E96.A.1437 .
Manifavas C., Hatzivasilis G., Fysarakis K., Papaefstathiou Y. Přehled odlehčených proudových šifer pro vestavěné systémy // Bezpečnostní a komunikační sítě. - 2016. - S. 1226-1246. - doi : 10.1002/sec.1399 .
Goresky M., Klapper AM Fibonacci a Galois reprezentace posuvných registrů zpětné vazby s přenosem // IEEE Transactions on Information Theory. - 2002. - S. 2826-2836. - doi : 10.1109/TIT.2002.804048 .
Klapper AM, Goresky M. 2-adic posuvné registry // Mezinárodní seminář o rychlém softwarovém šifrování. - Springer, 1993. - S. 174-178. - doi : 10.1007/3-540-58108-1 .
Churchhouse R., Churchhouse RF, Churchhouse RF Kódy a šifry: Julius Caesar, Enigma a Internet. - 10.1017/CBO9780511542978, 2002. - S. 67-71. - doi : 10.1007/3-540-58108-1 .

Odkazy

Článek o „lehkých“ streamových šifrách na cryptowiki.net (anglicky)