Salsa20

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 2 aprilie 2015; verificarea necesită 31 de modificări .

Salsa20 este un sistem de criptare a fluxurilor dezvoltat de Daniel Bernstein. Algoritmul a fost prezentat la competiția eSTREAM , al cărei scop a fost crearea unor standarde europene pentru criptarea datelor transmise prin sistemele de poștă. Algoritmul a devenit câștigătorul competiției în primul profil (cifruri de flux pentru aplicații software cu debit mare).

Cifrul Salsa20 utilizează următoarele operații:

adăugarea de numere pe 32 de biți;
adiție pe biți modulo 2 (xor) ;
deplasări de biți .

Algoritmul folosește o funcție hash cu 20 de cicluri . Transformările sale principale seamănă cu algoritmul AES .

Descrierea algoritmului

Concepte

În cele ce urmează, vom numi un element al mulțimii {0,1,…,2 32 −1} cuvânt și îl vom scrie în formă hexazecimală cu prefixul 0x.

Operația de adăugare a două cuvinte modulo 2 32 va fi notată prin semnul " ". $+$

Exclusiv sau (sumare pe biți) va fi notat cu simbolul " " $\oplus$

$c$ - biți deplasarea ciclică la stânga a unui cuvânt va fi notat cu . Dacă vă imaginați cum , atunci $u$ $voi c$ $u$ $u=\sum _{i=0}2^{i}u_{i)$

$u\lll c=\sum_{i=0}2^{i+c \mod 32}u_i$

Funcții utilizate în algoritm

quarterround(y)

Unitatea principală a sistemului este transformarea în patru cuvinte. Transformările mai generale descrise mai jos sunt construite din aceasta. $sfert(e)$

Esența lui constă în faptul că pentru fiecare cuvânt îi adăugăm pe cele două anterioare, deplasăm (ciclic) suma cu un anumit număr de biți și însumăm bit cu bit rezultatul cu cuvântul selectat. Operațiile ulterioare sunt efectuate cu semnificații noi ale cuvintelor.

Să presupunem că este o secvență de 4 cuvinte, atunci funcția este unde $y$ $y=(y_{0},y_{1},y_{2},y_{3})$ $quarterround(y)=(z_{0},z_{1},z_{2},z_{3})$

z_{1}=y_{1}\oplus ((y_{0}+y_{3})\lll 7),

z_{2}=y_{2}\oplus ((z_{1}+y_{0})\lll 9),

z_{3}=y_{3}\oplus ((z_{2}+z_{1})\lll 13),

z_{0}=y_{0}\oplus ((z_{3}+z_{2})\lll 18).

De exemplu:

sfert(0x00000001; 0x00000000; 0x00000000; 0x00000000)
= (0x08008145; 0x00000080; 0x00010200; 0x20500000)

Vă puteți gândi la această funcție ca la o transformare a cuvintelor y 0 , y 1 , y 2 și y 3 . Fiecare dintre aceste transformări este reversibilă, la fel ca și funcția în ansamblu.

rowround(y)

$y={\begin{pmatrix}y_{{0}}&y_{{1}}&y_{{2}}&y_{{3}}\\y_{{4}}&y_{{5}}&y_{{6 }}&y_{{7}}\\y_{{8}}&y_{{9}}&y_{{{10}}&y_{{11}}\\y_{{{12}}&y_{{{13}}&y_{ {14}}&y_{{15}}\end{pmatrix}}$

În această transformare luăm 16 cuvinte. Le reprezentăm sub forma unei matrice 4x4. Luăm fiecare rând din această matrice și transformăm cuvintele acestei matrice cu funcția . Cuvintele din rând sunt luate în ordine, pornind de la i -a pentru a i -a linie, unde i = {0,1,2,3}. $sfert(e)$

Fie o secvență de 16 cuvinte, apoi să fie și o secvență de 16 cuvinte unde $y=(y_{0},y_{1},y_{2},...,y_{15})$ $rowround(y)=(z_{0},z_{1},z_{2},...,z_{15})$

(z_{0},z_{1},z_{2},z_{3})=sfert(y_{0},y_{1},y_{2},y_{3}),

(z_{5},z_{6},z_{7},z_{4})=sfert(y_{5},y_{6},y_{7},y_{4}),

(z_{10},z_{11},z_{8},z_{9})=sfert(y_{10},y_{11},y_{8},y_{9}),

(z_{15},z_{12},z_{13},z_{14})=sfert(y_{15},y_{12},y_{13},y_{14}).

columnround(y)

Aici luăm coloanele aceleiași matrice. Să le transformăm cu funcția , prin analogie substituind valorile în ea, pornind de la j -a coloană pentru j -a coloană, unde j = {0,1,2,3}. $sfert(e)$

Funcția columnround(y)=(z) operează și pe o secvență de 16 cuvinte, astfel încât

(z_{0},z_{4},z_{8},z_{12})=sfert(y_{0},y_{4},y_{8},y_{12}),

(z_{5},z_{9},z_{13},z_{1})=sfert(y_{5},y_{9},y_{13},y_{1}),

(z_{10},z_{14},z_{2},z_{6})=sfert(y_{10},y_{14},y_{2},y_{6}),

(z_{15},z_{3},z_{7},z_{11})=sfert(y_{15},y_{3},y_{7},y_{11}).

doubleround(y)

Funcția doubleround(y) este o aplicare secvențială a funcțiilor columnround și apoi rowround : doubleround (y) = rowround(columnround(y))

Salsa20()

Acest algoritm folosește o intrare de cuvânt care începe cu octetul mic . Pentru a face acest lucru, iată o transformare $littleendian(b)$

Să fie o secvență de 4 octeți, apoi să fie un cuvânt astfel încât $b=(b_{0},b_{1},b_{2},b_{3})$ $littleendian(b)$

{\displaystyle littleendian(b)=b_{0}+2^{8}b_{1}+2^{16}b_{2}+2^{24}b_{3))

Transformarea finală este sumarea pe biți a secvenței inițiale și rezultatul a 20 de runde de transformări alternative de coloane și rânduri.

$Salsa20(x)=x\oplus doubleround^{10}(x)$

Unde $x=(x[0],x[1],...,x[63]),$

x_{0}=littleendian(x[0],x[1],x[2],x[3]),

x_{1}=littleendian(x[4],x[5],x[6],x[7]),

…

x_{15}=littleendian(x[60],x[61],x[62],x[63]).

x[i] sunt octeții x și x j sunt cuvinte folosite în funcțiile de mai sus.

În cazul în care un

$(z_{0},z_{1},...,z_{15})=doubleround^{10}(x_{0},x_{1},...,x_{15})$ ,

atunci Salsa20(x) este succesiunea rezultatelor

$littleendian^{-1}(z_{0}+x_{0}),...,littleendian^{-1}(z_{15}+x_{15})$

Extensie cheie pentru Salsa20

Extensia convertește o tastă de 32 sau 16 octeți k și un număr de 16 octeți n într-o secvență de 64 de octeți . $Salsa20_{k}(n)$

Extensia k folosește constantele
$\sigma _{0}=(101,120,112,97),~\sigma _{1}=(110,100,32,51),~\sigma _{2}=(50,45,98,121),~\sigma _{ 3}=(116,101,32,107)$

pentru 32 de octeți k și

$\tau _{0}=(101;120;112;97),~\tau _{1}=(110;100;32;49),~\tau _{2}=(54;45;98; 121),~\tau _{3}=(116;101;32;107)$

pentru k de 16 octeți .

Acestea sunt „expand 32-byte k” și „expand 16-byte k” în codul ASCII .

Fie k 0 ,k 1 ,n să aibă secvențe de 16 octeți, atunci .
$Salsa20_{{k_{0},k_{1}}}(n)=Salsa20(\sigma _{0},k_{0},\sigma _{1},n,\sigma _{2},k_{ 1},\sigma _{3})$

Dacă avem o singură secvență de 16 octeți k atunci
$Salsa20_{k}(n)=Salsa20(\tau _{0},k,\tau _{1},n,\tau _{2},k,\tau _{3})$

Funcția de criptare Salsa20

Cifrarea secvenței de octeți , pentru va fi $l$ $m$ $l\în \{0,1,...2^{{70}}\}$ $Salsa20_{k}(v)\oplus m$

$v$ — număr unic de 8 octeți (nonce).

Textul cifrat va avea dimensiunea unui octet , la fel ca textul simplu. $l$

Salsa20 k ( v ) este o secvență de 270 de octeți.

Salsa20_{k}(v,{\underline {0)}), Salsa20_{k}(v,{\underline {1))), Salsa20_{k}(v,{\subline {2)}) ,...,Salsa20_{k}(v,{\subliniat {2^{64}-1)))

Unde este o secvență unică de 8 octeți astfel încât respectiv $\subliniază {i}$ $(i_{0},i_{1},...,i_{7})$ $i=i_{0}+2^{8}i_{1}+...+2^{{{56}}i_{7}$

Salsa20_{k}(v)\oplus (m[0],m[1],...,m[l-1])=(c[0],c[1],...,c[l- unu])

Unde $c[i]=m[i]\oplus Salsa20_{k}(v,{\mathcal {b}}\underline {i/64}{\mathcal {c}})[i\mod 64]$

Performanță

Datorită faptului că transformările fiecărei coloane și ale fiecărui rând sunt independente unele de altele, calculele necesare pentru criptare pot fi ușor paralelizate . Acest lucru oferă un câștig semnificativ de viteză pentru majoritatea platformelor moderne.

Algoritmul nu are, practic, niciun calcul general necesar pentru a rula ciclul de criptare. Acest lucru este valabil și pentru schimbările cheie. Multe sisteme de cifrare se bazează pe precalculări, ale căror rezultate trebuie stocate în memoria cache de prim nivel (L1) a procesorului . Deoarece depind de cheie, calculele vor trebui efectuate din nou. În Salsa20, este suficient să încărcați pur și simplu cheia în memorie.

Variante Salsa20/8 și Salsa20/12

Salsa20/8 și Salsa20/12 sunt sisteme de criptare care folosesc același mecanism ca Salsa20, dar cu 8 și, respectiv, 12 runde de criptare, în loc de cele 20 inițiale. Salsa20 a fost făcută cu multă putere de rezistență. În timp ce Salsa20/8 arată rezultate bune în viteză, depășind în majoritatea cazurilor multe alte sisteme de criptare, inclusiv AES și RC4 [1] .

Varianta XSalsa20

Există o variantă a algoritmului Salsa20, propusă și de Daniel Bernstein, care crește lungimea nonce de la 64 de biți la 192 de biți. Această variantă se numește XSalsa20. Dimensiunea crescută a nonce permite utilizarea unui generator de numere pseudo-aleatoare puternic criptografic pentru a- l genera, în timp ce criptarea securizată cu un nonce pe 64 de biți necesită utilizarea unui contor din cauza probabilității mari de coliziuni [2] .

Criptanaliză

În 2005, Paul Crowley a anunțat un atac asupra Salsa20/5 cu o complexitate de timp estimată la 2165 . Acest atac și atacurile ulterioare se bazează pe criptoanaliza diferențială trunchiată . Pentru această criptoanaliză, el a primit o recompensă de 1.000 de dolari de la autorul cărții Salsa20.

În 2006, Fischer, Meier, Berbain , Biasse și Robshaw au raportat un atac de complexitate 2117 împotriva Salsa/6 și o complexitate 2217 împotriva Salsa20 /7 cu chei conectate .

În 2008, Aumasson, Fischer, Khazaei, Meier și Rechberger au raportat un atac asupra Salsa20/7 cu o dificultate de 2153 și primul atac asupra Salsa20/8 cu o dificultate de 2251 .

Până acum, nu au existat rapoarte publice de atacuri asupra Salsa20/12 și a întregului Salsa20/20.

ChaCha

În 2008, Daniel Bernstein a publicat o familie similară de cifruri de flux numită ChaCha, care urmărea să îmbunătățească amestecarea datelor într-o singură rundă și se presupune că îmbunătățește puterea criptografică la aceeași viteză sau chiar puțin mai mare [3] .

ChaCha20 este descris în RFC 7539 (mai 2015).

Unitatea principală a sistemului funcționează diferit aici. Acum fiecare operație schimbă unul dintre cuvinte. Modificările apar ciclic „în sens opus”, începând de la al 0-lea cuvânt. Operațiile de adunare și suma pe biți alternează odată cu deplasarea, cuvântul se adaugă celui anterior.

Funcția quarterround(a, b, c, d), unde a, b, c, d-cuvinte, în ChaCha arată astfel:

a+=b;~~d\oplus =a;~~d\lll =16;

c+=d;~~b\oplus =c;~~b\lll =12;

a+=b;~~d\oplus =a;~~d\lll =8;

c+=d;~~b\oplus =c;~~b\lll =7;

Aici se folosesc aceleași operații aritmetice, dar fiecare cuvânt este schimbat de două ori pe conversie, în loc de o singură dată.

În plus, starea inițială a cifrului (extensia cheii) este schimbată în comparație cu Salsa: primii 128 de biți sunt constante, urmați de 256 de biți ai cheii, 32 de biți ai contorului și apoi 96 de biți dintr-o secvență unică nonce.

Note

↑ Copie arhivată . Consultat la 11 noiembrie 2010. Arhivat din original pe 15 decembrie 2017. (nedefinit)
↑ Copie arhivată . Consultat la 13 septembrie 2016. Arhivat din original la 18 septembrie 2018. (nedefinit)
↑ Copie arhivată . Consultat la 11 noiembrie 2010. Arhivat din original pe 2 mai 2018. (nedefinit)

Link -uri

Criptosisteme simetrice
Cifruri în flux	A3 A5 A8 Decim F-FCSR Cereale HC-256 KCipher-2 MICKEY MUGI ŞTIUCĂ Phelix RC4 Iepure SIGILIU ZĂPADĂ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Rețeaua Feistel	GOST 28147-89 (Magma) blowfish Camelia CAST-128 CAST-256 CIFERUNICORN-A CIFERUNICORN-E CLEFIA Cobra AFACERE DES DESX DFC E2 ENRUPT FEAL HPC IDEE KASUMI Khafre Khufu LOKI97 MacGuffin MARTE PLASĂ CEȚA1 NewDES NDS RC5 RC6 SEMINTA Simon Sinople lista SM4 Speck CEAI XTEA XXTEA Raiden RTEA Triplu DES Doi pești
Rețeaua SP	Lăcustă 3 căi ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Centura CRYPTON Diamant2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer prezent Curcubeu MAI SIGUR RECHIN PĂTRAT Şarpe trei pești
Alte	BROASCĂ NUSH REDOC SC2000 SHACAL CS-Cipher