FASOLE

BEAN este un algoritm simetric de criptare a fluxului sincron bazat pe algoritmul Grain . Este un reprezentant al așa-numitelor cifruri „ușoare”, adică se concentrează pe implementarea hardware în interiorul dispozitivelor cu putere de calcul limitată, memorie redusă și consum redus de energie (de exemplu, etichete RFID sau rețele de senzori ). A fost propus în 2009 de Navi Kumar , Srikanta Oiha , Kritika Jain și Sangita Lal [1] .

Descriere

În algoritmii de streaming simetric , criptarea (sau decriptarea) are loc prin gamma , adică „suprapunerea” unei secvențe aleatorii de biți (gamma) pe textul simplu (sau, respectiv, ciphertext). „Suprapunere” se referă la operația XOR pe biții gamma și text. Secvența de joc, numită și keystream (key stream), este obținută folosind generatoare de numere pseudoaleatoare [2] .

La fel ca Grain , BEAN constă din două registre de deplasare de 80 de biți și o funcție de ieșire. Dar în timp ce Grain folosește un registru de feedback liniar (LFSR) și un registru de funcție de feedback neliniar (NFSR), BEAN folosește două registre de deplasare cu feedback de transport (FCSR) [3] . LFSR este utilizat în Grain pentru perioada mai mare a secvenței și NFSR pentru neliniaritate. FCSR în BEAN combină ambele aceste proprietăți, rămânând la fel de compact la nivel hardware [4] .

În ambele registre, următorul bit care trebuie scris este egal cu suma modulo 2 a tuturor accesărilor celulelor registrului. O astfel de implementare se numește configurație Fibonacci . În timp ce în Grain, registrele sunt implementate conform configurației Galois , adică ultimul 79 de bit este scris neschimbat pe locul 0, iar suma modulo 2 a celei de-a 79-a celulă anterioară este scrisă în fiecare următor. celula [5] . $i$ $(i-1)$

Registrele FCSR

Ambele registre au o lungime de 80 de biți. Să le desemnăm ca FCSR-I și FCSR-II, iar stările lor pe ciclul --lea ca și respectiv [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

Funcția de feedback FCSR-I este dată de un polinom primitiv de gradul 80 [7] : $f(x)$

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

adică actualizarea stării FCSR-I în ciclul următor arată astfel [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

În mod similar pentru FCSR-II, funcția de feedback [8] este:

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

Actualizare de stat [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$

Funcția de ieșire

Funcția booleană este utilizată pentru a genera gama . Autorii algoritmului îl setează folosind o cutie S care ia 6 biți ca intrare (2 biți definesc un rând și 4 biți definesc o coloană) și returnează un cuvânt de 4 biți [9] . Dar, deoarece numai ultimul bit este luat din cuvânt, acesta poate fi reprezentat ca un polinom Zhegalkin [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}\ oplus 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}$

Biții gamma se găsesc după cum urmează [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})$

Astfel, doi biți sunt generați simultan într-un ciclu.

Inițializarea stării

Inițializarea are loc prin încărcarea unei chei de 80 de biți în registrele FCSR-I și 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$

Registrele de transport sunt inițializate la zero: . $m_{s}^{i-81}=m_{b}^{i-81}=0$

Apoi FCSR face 81 de cicluri inactiv, după care începe generarea gamma [11] .

Performanță

BEAN atinge un echilibru bun între securitate, viteză și costul implementării. Grain poate genera doi biți gamma pe ceas folosind hardware suplimentar. În timp ce BEAN face față acestei sarcini fără echipamente suplimentare [12] .

Potrivit autorilor algoritmului [13] , generarea de biți folosind BEAN este în medie de 1,5 ori mai rapidă decât folosind Grain, iar memoria consumată este redusă cu 10%. $10^{7}$

Securitate

Un obiectiv important în dezvoltarea unui algoritm criptografic este acela de a obține un efect de avalanșă , adică atunci când un bit al cheii (text simplu) se schimbă, cel puțin jumătate din biții gama (text cifrat) se vor schimba. Pentru a compara BEAN și Grain, s-au luat 1.000.000 de chei aleatoare de 80 de biți și au fost generați 80 de biți de gamma pentru fiecare cheie folosind ambii algoritmi. Potrivit autorilor, în BEAN pentru 65,3% din chei, biții recepționați îndeplinesc condițiile efectului de avalanșă, în timp ce în Grain această pondere este de 63,1% [11] .

Algoritmul a fost testat și pe teste statistice NIST , care nu au arătat o abatere a fluxului de chei generat de la o secvență aleatorie [14] .

În 2011, Martin Agren și Martin Hell în articolul lor au subliniat neoptimalitatea funcției de inferență. Ei au propus un algoritm discriminator eficient pentru BEAN, precum și un algoritm de atac de recuperare cheie , care este ceva mai rapid decât căutarea exhaustivă ( comparativ cu căutarea exhaustivă în algoritmul propus ) și nu necesită multă memorie [15] . $2^{73}$ $2^{80}$

În 2013, aceiași autori, în colaborare cu Hui Wong și Thomas Johansson, au descoperit noi corelații între biții cheie și biții gamma, conducând la un algoritm și mai eficient de atac de recuperare a cheii ( ). În plus, au fost propuse unele îmbunătățiri ale FCSR, precum și funcții de inferență mai eficiente care sunt rezistente la metodele de atac cunoscute [16] . $2^{57.53}$

Aplicație

La fel ca mulți algoritmi de criptare „ușoare”, BEAN își poate găsi aplicația în etichetele RFID , rețelele de senzori fără fir , precum și în sistemele încorporate [17] .

Note

↑ Kumar, 2009 .
↑ Churchhouse, 2002 .
↑ Kumar, 2009 , Figura 1, p. 169.
↑ Clapper, 1993 .
↑ Goresky, 2002 .
↑ 1 2 3 4 Agren, 2011 , p. 23.
↑ Kumar, 2009 , Ecuația 1, p. 169.
↑ Kumar, 2009 , Ecuația 3, p. 169.
↑ Kumar, 2009 , Tabelul 1, p. 170.
↑ Agren, 2011 , Equations 5, 6, p. 23.
↑ 1 2 Kumar, 2009 , p. 170.
↑ Manifavas, 2016 , p. 338.
↑ Kumar, 2009 , p. 171.
↑ Kumar, 2009 , Tabelul 3, p. 170.
↑ Agren, 2011 , p. 24.
↑ Wang, 2013 .
↑ Manifavas, 2016 .

Literatură

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. Criptanalysis 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 AM Fibonacci și Galois reprezentări ale registrelor cu deplasare cu feedback-ul de transport // IEEE Transactions on Information Theory. - 2002. - P. 2826-2836. - doi : 10.1109/TIT.2002.804048 .
Klapper AM, 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 RF, Churchhouse RF Coduri și cifruri: Iulius Caesar, Enigma și Internetul - 10.1017/CBO9780511542978, 2002. - P. 67-71. - doi : 10.1007/3-540-58108-1 .

Link -uri

Articol despre cifrurile de flux „ușoare” pe cryptowiki.net (engleză)