Salsa20

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 2. dubna 2015; ověření vyžaduje 31 úprav .

Salsa20 je systém šifrování streamu vyvinutý Danielem Bernsteinem. Algoritmus byl prezentován na soutěži eSTREAM , jejímž účelem bylo vytvořit evropské standardy pro šifrování dat přenášených poštovními systémy. Algoritmus se stal vítězem soutěže v prvním profilu (streamové šifry pro softwarové aplikace s vysokou propustností).

Šifra Salsa20 používá následující operace:

sčítání 32bitových čísel;
bitové sčítání modulo 2 (xor) ;
bitové posuny .

Algoritmus používá hashovací funkci s 20 cykly . Jeho hlavní transformace se podobají algoritmu AES .

Popis algoritmu

Koncepty

Dále nazveme prvek množiny {0,1,…,2 32 −1} slovem a zapíšeme jej v hexadecimálním tvaru s předponou 0x.

Operace přidání dvou slov modulo 2 32 bude označena znaménkem " ". $+$

Exkluzivní nebo (bitová sumace) bude označeno symbolem " " $\oplus$

$C$ - bitový cyklický levý posun slova bude označen . Když si představíte jak , tak $u$ $u\ll c$ $u$ ${\displaystyle u=\sum _{i=0}2^{i}u_{i))$

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

Funkce použité v algoritmu

quarterround(y)

Hlavní jednotkou systému je transformace přes čtyři slova. Z toho jsou konstruovány obecnější transformace popsané níže. $čtvrtletí(y)$

Jeho podstata spočívá v tom, že ke každému slovu sečteme dvě předchozí, posuneme (cyklicky) součet o určitý počet bitů a bit po bitu sečteme výsledek s vybraným slovem. Následné operace se provádějí s novými významy slov.

Řekněme, že jde o posloupnost 4 slov, pak je funkce kde $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).

Například:

čtvrtletí (0x00000001; 0x00000000; 0x00000000; 0x00000000)
= (0x08008145; 0x00000080; 0x00010200; 0x20500000)

Tuto funkci si můžete představit jako transformaci slov y 0 , y 1 , y 2 a y 3 . Každá z těchto transformací je vratná, stejně jako funkce jako celek.

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

V této transformaci vezmeme 16 slov. Reprezentujeme je ve formě matice 4x4. Vezmeme každý řádek této matice a transformujeme slova této matice pomocí funkce . Slova z řádku se berou v pořadí, počínaje i -tým pro i -tý řádek, kde i = {0,1,2,3}. $čtvrtletí(y)$

Nechť je posloupnost 16 slov, pak také posloupnost 16 slov kde $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})=čtvrteční (y_{15},y_{12},y_{13},y_{14}).

columnround(y)

Zde vezmeme sloupce stejné matice. Transformujme je pomocí funkce , analogicky do ní dosadíme hodnoty, počínaje j -tým sloupcem za j -tý sloupec, kde j = {0,1,2,3}. $čtvrtletí(y)$

Funkce columnround(y)=(z) také pracuje se sekvencí 16 slov, takže

(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)

Funkce doubleround(y) je sekvenční aplikací funkcí columnround a poté rowround : doubleround (y) = rowround(columnround(y))

Salsa20()

Tento algoritmus používá vstup slova začínající nízkým byte . K tomu je zde transformace $littleendian(b)$

Nechť je 4bajtová sekvence, pak je slovo takové, že $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))

Konečná transformace je bitovým součtem původní sekvence a výsledkem 20 kol střídání sloupcových a řádkových transformací.

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

Kde $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] jsou byty x a xj jsou slova použitá ve výše uvedených funkcích.

Pokud

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

pak Salsa20(x) je posloupnost výsledků

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

Rozšíření klíče pro Salsa20

Rozšíření převádí 32bajtový nebo 16bajtový klíč k a 16bajtové číslo n na 64bajtovou sekvenci . $Salsa20_{k}(n)$

Rozšíření k používá konstanty
$\sigma _{0}=(101,120,112,97),~\sigma _{1}=(110,100,32,51),~\sigma _{2}=(50,45,98,121),~\sigma _{ 3}=(116,101,32,107)$

pro 32bajtové k a

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

pro 16bajtové k .

Jedná se o "rozbalit 32 bajtů k" a "rozbalit 16 bajtů k" v kódu ASCII .

Nechť k 0 ,k 1 ,n má 16bajtové sekvence, pak .
$Salsa20_{{k_{0},k_{1}}}(n)=Salsa20(\sigma _{0},k_{0},\sigma _{1},n,\sigma _{2},k_{ 1},\sigma _{3})$

Pokud máme pouze jednu 16bajtovou sekvenci k , pak
$Salsa20_{k}(n)=Salsa20(\tau _{0},k,\tau _{1},n,\tau _{2},k,\tau _{3})$

Funkce šifrování Salsa20

Byte-sequence cipher , for will be $l$ $m$ $l\in \{0,1,...2^{{70}}\}$ $Salsa20_{k}(v)\oplus m$

$proti$ — jedinečné 8bajtové číslo (nonce).

Šifrovaný text bude mít velikost bajtů , stejně jako prostý text. $l$

Salsa20 k ( v ) je sekvence 270 bajtů.

Salsa20_{k}(v,{\podtržení {0))),Salsa20_{k}(v,{\podtržení {1))),Salsa20_{k}(v,{\podtržení {2))) ,...,Salsa20_{k}(v,{\podtržení {2^{64}-1)))

Kde je jedinečná sekvence 8 bajtů taková, že resp $\podtržení {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- jeden])

Kde $c[i]=m[i]\oplus Salsa20_{k}(v,{\mathcal {b}}\podtržení {i/64}{\mathcal {c}})[i\mod 64]$

Výkon

Vzhledem k tomu, že transformace každého sloupce a každého řádku jsou na sobě nezávislé, lze výpočty potřebné pro šifrování snadno paralelizovat . To poskytuje významný nárůst rychlosti pro většinu moderních platforem.

Algoritmus nemá prakticky žádné režijní výpočty potřebné ke spuštění šifrovacího cyklu. To platí i pro klíčové změny. Mnoho šifrovacích systémů se spoléhá na předběžné výpočty, jejichž výsledky musí být uloženy v mezipaměti procesoru první úrovně (L1) . Protože závisí na klíči, bude nutné provést výpočty znovu. V Salsa20 stačí klíč jednoduše nahrát do paměti.

Varianty Salsa20/8 a Salsa20/12

Salsa20/8 a Salsa20/12 jsou šifrovací systémy využívající stejný mechanismus jako Salsa20, ale s 8, respektive 12 šifrovacími koly, namísto původních 20. Salsa20 byla vyrobena s velkou výdrží. Zatímco Salsa20/8 vykazuje dobré výsledky v rychlosti, ve většině případů předčí mnoho jiných šifrovacích systémů, včetně AES a RC4 [1] .

Varianta XSalsa20

Existuje varianta algoritmu Salsa20, rovněž navržená Danielem Bernsteinem, která zvyšuje délku nonce z 64 bitů na 192 bitů. Tato varianta se nazývá XSalsa20. Zvětšená velikost nonce umožňuje použít k jeho generování kryptograficky silný generátor pseudonáhodných čísel , zatímco bezpečné šifrování s 64bitovým nonce vyžaduje použití čítače kvůli vysoké pravděpodobnosti kolizí [2] .

Kryptoanalýza

V roce 2005 Paul Crowley oznámil útok na Salsu20/5 s odhadovanou časovou složitostí 2165 . Tento a následující útoky jsou založeny na zkrácené diferenciální kryptoanalýze . Za tuto kryptoanalýzu obdržel od autora Salsa20 odměnu 1 000 $.

V roce 2006 Fischer, Meier, Berbain , Biasse a Robshaw ohlásili útok na složitost 2117 proti Salsa/6 a složitost 2217 proti Salsa20 /7 s propojenými klíči .

V roce 2008 Aumasson, Fischer, Khazaei, Meier a Rechberger ohlásili útok na Salsu20/7 s obtížností 2153 a první útok na Salsu20/8 s obtížností 2251 .

Dosud nebyly zveřejněny žádné veřejné zprávy o útocích na Salsu20/12 a celou Salsu20/20.

ChaCha

V roce 2008 publikoval Daniel Bernstein příbuznou rodinu proudových šifer nazvanou ChaCha, jejímž cílem bylo zlepšit míchání dat v jednom kole a údajně zlepšit šifrovací sílu při stejné nebo dokonce mírně vyšší rychlosti [3] .

ChaCha20 je popsán v RFC 7539 (květen 2015).

Hlavní jednotka systému zde funguje jinak. Nyní každá operace změní jedno ze slov. Změny probíhají cyklicky „v opačném směru“, počínaje 0. slovem. Operace sčítání a bitového součtu se střídají spolu s posunem, slovo je přidáno k předchozímu.

Funkce čtvrtletí (a, b, c, d), kde slova a, b, c, d, v ChaCha vypadá takto:

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;

Jsou zde použity stejné aritmetické operace, ale každé slovo se při převodu změní dvakrát místo jednou.

Navíc je oproti Salse změněn počáteční stav šifry (rozšíření klíče): prvních 128 bitů jsou konstanty, následuje 256 bitů klíče, 32 bitů čítače a poté 96 bitů jedinečné sekvence nonce.

Poznámky

↑ Archivovaná kopie . Získáno 11. listopadu 2010. Archivováno z originálu 15. prosince 2017. (neurčitý)
↑ Archivovaná kopie . Získáno 13. září 2016. Archivováno z originálu 18. září 2018. (neurčitý)
↑ Archivovaná kopie . Získáno 11. listopadu 2010. Archivováno z originálu 2. května 2018. (neurčitý)

Odkazy

Symetrické kryptosystémy
Streamové šifry	A3 A5 A8 Decim F-FCSR Obilí HC-256 KCipher-2 MICKEY MUGI ŠTIKA Phelix RC4 Králičí TĚSNĚNÍ SNÍH SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Síť Feistel	GOST 28147-89 (Magma) nafukovací ryba Kamélie CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra OBCHOD DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Chufu LOKI97 MacGuffin MARS PLETIVO MISTY1 NewDES NDS RC5 RC6 SEMÍNKO Simone Sinople skipjack SM4 Smítko ČAJ XTEA XXTEA Raiden RTEA Trojitý DES Dvě ryby
Síť SP	Saranče 3 způsob ABC ÁRIE AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Pás KRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer současnost, dárek Duha BEZPEČNĚJŠÍ ŽRALOK NÁMĚSTÍ Had tři ryby
jiný	ŽÁBA NUSH REDOC SC2000 SHACAL CS-Cipher