Salsa 20

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 2. april 2015; verifikation kræver 31 redigeringer .

Salsa20 er et strømkrypteringssystem udviklet af Daniel Bernstein. Algoritmen blev præsenteret ved eSTREAM- konkurrencen , hvis formål var at skabe europæiske standarder for kryptering af data transmitteret af postsystemer. Algoritmen blev vinderen af konkurrencen i den første profil (stream-cifre til softwareapplikationer med høj gennemstrømning).

Salsa20-chifferet bruger følgende operationer:

tilføjelse af 32-bit tal;
bitvis addition modulo 2 (xor) ;
bitskift .

Algoritmen bruger en hashfunktion med 20 cyklusser . Dens vigtigste transformationer ligner AES- algoritmen .

Beskrivelse af algoritmen

Begreber

I det følgende vil vi kalde et element i mængden {0,1,…,2 32 −1} for et ord og skrive det i hexadecimal form med præfikset 0x.

Operationen med at tilføje to ord modulo 2 32 vil blive angivet med tegnet " ". $+$

Eksklusiv eller (bitvis summering) vil blive angivet med symbolet " " $\plus$

$c$ - bit cyklisk venstreforskydning af et ord vil blive betegnet med . Hvis du forestiller dig hvordan , så $u$ $du vil c$ $u$ ${\displaystyle u=\sum _{i=0}2^{i}u_{i))$

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

Funktioner brugt i algoritmen

quarterround(y)

Systemets hovedenhed er transformationen over fire ord. De mere generelle transformationer beskrevet nedenfor er konstrueret ud fra det. $quarterround(y)$

Dens essens ligger i det faktum, at vi for hvert ord tilføjer de to foregående, forskyder (cyklisk) summen med et bestemt antal bit og bit for bit summerer resultatet med det valgte ord. Efterfølgende operationer udføres med nye ordbetydninger.

Lad os sige, at det er en sekvens af 4 ord, så er funktionen hvor $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).

For eksempel:

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

Du kan tænke på denne funktion som en transformation af ordene y 0 , y 1 , y 2 og y 3 . Hver af disse transformationer er reversible, ligesom funktionen som helhed er.

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

I denne transformation tager vi 16 ord. Vi repræsenterer dem i form af en 4x4 matrix. Vi tager hver række af denne matrix og transformerer ordene i denne matrix med funktionen . Ord fra linjen tages i rækkefølge, startende fra i - th for i -th linje, hvor i = {0,1,2,3}. $quarterround(y)$

Lade være en sekvens af 16 ord, så også være en sekvens af 16 ord hvor $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})=quarterround(y_{0},y_{1},y_{2},y_{3}),

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

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

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

columnround(y)

Her tager vi kolonnerne i den samme matrix. Lad os transformere dem med funktionen , ved analogt at erstatte værdierne i den, begyndende fra den j -te kolonne for den j -te kolonne, hvor j = {0,1,2,3}. $quarterround(y)$

Funktionen columnround(y)=(z) opererer også på en sekvens af 16 ord, således at

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

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

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

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

doubleround(y)

Doubleround(y) -funktionen er en sekventiel anvendelse af kolonnerunden og derefter rækkerunde -funktionerne : doubleround(y) = rowround(columnround(y))

Salsa20()

Denne algoritme bruger en ordindtastning, der starter med den lave byte . For at gøre dette er her en transformation $littleendian(b)$

Lad være en 4-byte sekvens, så være et ord sådan, at $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))

Den endelige transformation er den bitvise summering af den oprindelige sekvens og resultatet af 20 runder af skiftende kolonne- og rækketransformationer.

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

Hvor $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] er bytes x og x j er ord brugt i ovenstående funktioner.

Hvis en

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

så er Salsa20(x) rækkefølgen af resultater

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

Nøgleudvidelse til Salsa20

Udvidelsen konverterer en 32-byte eller 16-byte nøgle k og et 16-byte nummer n til en 64-byte sekvens . $Salsa20_{k}(n)$

K- udvidelsen bruger konstanterne
$\sigma _{0}=(101,120,112,97),~\sigma _{1}=(110,100,32,51),~\sigma _{2}=(50,45,98,121),~\sigma _{ 3}=(116,101,32,107)$

for 32-byte k og

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

for 16-byte k .

Disse er "expand 32-byte k" og "expand 16-byte k" i ASCII -kode.

Lad k 0 , k 1 ,n have 16-byte-sekvenser, så .
$Salsa20_{{k_{0},k_{1}}}(n)=Salsa20(\sigma _{0},k_{0},\sigma _{1},n,\sigma _{2},k_{ 1},\sigma _{3})$

Hvis vi kun har en 16-byte sekvens k så
$Salsa20_{k}(n)=Salsa20(\tau _{0},k,\tau _{1},n,\tau _{2},k,\tau _{3})$

Salsa20 krypteringsfunktion

Byte-sequence cipher , for vil være $l$ $m$ $l\i \{0,1,...2^{{70}}\}$ $Salsa20_{k}(v)\oplus m$

$v$ — unikt 8-byte nummer (ikke).

Chifferteksten vil være på størrelse med byte , ligesom den almindelige tekst. $l$

Salsa20 k ( v ) er en sekvens på 270 bytes.

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

Hvor er en unik sekvens på 8 bytes sådan, at hhv $\understreg {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- en])

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

Ydeevne

På grund af det faktum, at transformationerne af hver kolonne og hver række er uafhængige af hinanden, kan de beregninger, der kræves til kryptering, let paralleliseres . Dette giver en betydelig hastighedsforøgelse for de fleste moderne platforme.

Algoritmen har stort set ingen overheadberegning, der kræves for at køre krypteringscyklussen. Dette gælder også for centrale ændringer. Mange chiffersystemer er afhængige af forudberegninger, hvis resultater skal gemmes i processorens første niveau (L1) cache . Da de afhænger af nøglen, skal beregningerne udføres igen. I Salsa20 er det nok blot at indlæse nøglen i hukommelsen.

Salsa20/8 og Salsa20/12 varianter

Salsa20/8 og Salsa20/12 er krypteringssystemer, der bruger samme mekanisme som Salsa20, men med henholdsvis 8 og 12 krypteringsrunder i stedet for de originale 20. Salsa20 blev lavet med en masse udholdenhed. Hvorimod Salsa20/8 viser gode resultater i hastighed, overhaler den i de fleste tilfælde mange andre krypteringssystemer, inklusive AES og RC4 [1] .

XSalsa20-variant

Der er en variant af Salsa20-algoritmen, også foreslået af Daniel Bernstein, som øger nonce- længden fra 64 bit til 192 bit. Denne variant kaldes XSalsa20. Den øgede størrelse af nonce'en tillader brugen af en kryptografisk stærk pseudo-tilfældig talgenerator til at generere den, mens sikker kryptering med en 64-bit nonce kræver brug af en tæller på grund af den høje sandsynlighed for kollisioner [2] .

Krypteringsanalyse

I 2005 annoncerede Paul Crowley et angreb på Salsa20/5 med en estimeret tidskompleksitet på 2165 . Dette og efterfølgende angreb er baseret på trunkeret differentiel kryptoanalyse . For denne kryptoanalyse modtog han en belønning på $1.000 fra forfatteren af Salsa20.

I 2006 rapporterede Fischer, Meier, Berbain , Biasse og Robshaw et 2117 kompleksitetsangreb mod Salsa/6 og en 2217 kompleksitet mod Salsa20 /7 med forbundne nøgler .

I 2008 rapporterede Aumasson, Fischer, Khazaei, Meier og Rechberger et angreb på Salsa20/7 med en sværhedsgrad på 2153 og det første angreb på Salsa20/8 med en sværhedsgrad på 2251 .

Indtil videre har der ikke været offentlige rapporter om angreb på Salsa20/12 og hele Salsa20/20.

ChaCha

I 2008 udgav Daniel Bernstein en beslægtet familie af stream-cifre kaldet ChaCha, som havde til formål at forbedre data-shuffling i én runde og angiveligt forbedre kryptografisk styrke ved samme eller endda lidt hurtigere hastighed [3] .

ChaCha20 er beskrevet i RFC 7539 (maj 2015).

Systemets hovedenhed fungerer anderledes her. Nu ændrer hver operation et af ordene. Ændringer sker cyklisk "i den modsatte retning", startende fra det 0. ord. Operationerne med addition og bitvis sum veksler sammen med skiftet, ordet tilføjes til det forrige.

Funktionen quarterround(a, b, c, d), hvor a, b, c, d-ord, i ChaCha ser sådan ud:

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;

De samme aritmetiske operationer bruges her, men hvert ord ændres to gange pr. konvertering i stedet for én gang.

Derudover ændres chifferens begyndelsestilstand (nøgleudvidelse) sammenlignet med Salsa: de første 128 bit er konstanter, efterfulgt af 256 bit af nøglen, 32 bit af tælleren og derefter 96 bit af en unik nonce-sekvens.

Noter

↑ Arkiveret kopi . Hentet 11. november 2010. Arkiveret fra originalen 15. december 2017. (ubestemt)
↑ Arkiveret kopi . Hentet 13. september 2016. Arkiveret fra originalen 18. september 2018. (ubestemt)
↑ Arkiveret kopi . Hentet 11. november 2010. Arkiveret fra originalen 2. maj 2018. (ubestemt)

Links

Symmetriske kryptosystemer
Stream-cifre	A3 A5 A8 Decim F-FCSR Korn HC-256 KCipher-2 MICKEY MUGI GEDD Phelix RC4 Kanin FORSEGLE SNE SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistel netværk	GOST 28147-89 (Magma) blæsefisk Camellia CAST-128 CAST-256 CIFERUNIKORN-A CIFERUNIKORN-E CLEFIA Cobra DEL DES DESX DFC E2 ENRUPT FEAL HPC IDE KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 NyDES NDS RC5 RC6 FRØ Simon Sinople skipjack SM4 Speck TE XTEA XXTEA Raiden RTEA Triple DES To fisk
SP netværk	Græshoppe 3 vejs ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bælte CRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer til stede Regnbue SIKRERE HAJ FIRKANT Slange tre fisk
Andet	FRØ NUSH REDOC SC2000 SHACAL CS-Cipher