Salsa20 — системапотокового шифрування, розробленаДеніелом Бернштейном. Алгоритм був представлений на конкурсі«eSTREAM», метою якого було створення європейських стандартів для шифрування даних, переданих поштовими системами. Алгоритм став переможцем конкурсу в першому профілі (потокові шифри для програмного застосування з великою пропускною здатністю).

Шифр Salsa20 використовує наступні операції:

• додавання 32-бітних чисел;
• побітоведодавання по модулю 2 (xor);
• зсув бітів.

Алгоритм використовуєгеш-функцію з 20 циклами. Основні її перетворення нагадують алгоритмAES.

Словом далі будемо називати елемент множини {0,1,...,2³²-1} і записувати його в шістнадцятковому вигляді з префіксом 0х.

Операціюдодавання двох слів по модулю 2³² будемо позначати символом «${\displaystyle +}$».

Виключне або (побітове додавання) будемо позначати символом «${\displaystyle \oplus }$»

${\displaystyle c}$ -бітовий циклічний зсув вліво слова${\displaystyle u}$, який будемо позначати${\displaystyle u⋘c}$. Якщо${\displaystyle u}$ представити як${\displaystyle u=\sum _{i=0}{2}^i{u}_i}$, тоді

${\displaystyle u⋘c=\sum _{i=0}{2}^{i+c\mathrm{mod}32}{u}_i}$

Основним блоком системи є перетворення${\displaystyle quarterround(y)}$ над чотирма словами. З нього будуються далі описані більш загальні перетворення.Його суть полягає в тому, що для кожного слова ми складаємо два попередніх, зсуваємо (циклічно) суму на певну кількість біт і побітово підсумовуємо результат з вибраним словом. Подальші операції проводяться з новими значеннями слів.

Припустимо, що${\displaystyle y}$ — послідовність слів 4${\displaystyle y=(y_0,y_1,y_2,y_3)}$. Тоді функція${\displaystyle quarterround(y)=(z_0,z_1,z_2,z_3)}$ де

${\displaystyle z_1=y_1\oplus ((y_0+y_3)⋘7),}$

${\displaystyle z_2=y_2\oplus ((z_1+y_0)⋘9),}$

${\displaystyle z_3=y_3\oplus ((z_2+z_1)⋘13),}$

${\displaystyle z_0=y_0\oplus ((z_3+z_2)⋘18).}$

Наприклад:

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

Можна розглядати цю функцію перетворення слів y₀, y₁, y₂ y₃. Кожне з таких перетворень оборотне, як і функція в цілому.

В цьому перетворенні ми беремо 16 слів. Представимо їх у вигляді матриці 4х4. Беремо кожен рядок цієї матриці і перетворимо слова цієї матриці функцією${\displaystyle quarterround(y)}$. Слова з рядка беруться за порядком, починаючи зi-го дляi-го рядка, деi={0,1,2,3}.

Нехай${\displaystyle y=(y_0,y_1,y_2,...,y_{15})}$ — послідовність 16 слів, тоді${\displaystyle rowround(y)=(z_0,z_1,z_2,...,z_{15})}$ — також послідовність 16 слів де

${\displaystyle (z_0,z_1,z_2,z_3)=quarterround(y_0,y_1,y_2,y_3),}$

${\displaystyle (z_5,z_6,z_7,z_4)=quarterround(y_5,y_6,y_7,y_4),}$

${\displaystyle (z_{10},z_{11},z_8,z_9)=quarterround(y_{10},y_{11},y_8,y_9),}$

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

Тут ми беремо стовпці такої ж матриці. Перетворимо їх функцією${\displaystyle quarterround(y)}$ за аналогією підставляючи в неї значення, починаючи зj-го дляj-го стовпця, деj={0,1,2,3}.

Функція columnround(y)=(z) теж оперує послідовністю 16 слів так, що

${\displaystyle (z_0,z_4,z_8,z_{12})=quarterround(y_0,y_4,y_8,y_{12}),}$

${\displaystyle (z_5,z_9,z_{13},z_1)=quarterround(y_5,y_9,y_{13},y_1),}$

${\displaystyle (z_{10},z_{14},z_2,z_6)=quarterround(y_{10},y_{14},y_2,y_6),}$

${\displaystyle (z_{15},z_3,z_7,z_{11})=quarterround(y_{15},y_3,y_7,y_{11}).}$

Функціяdoubleround(y) є послідовним застосуванням функційcolumnround а потімrowround:doubleround(y) =rowround(columnround(y))

Даний алгоритм використовує запис слова,що починається з молодшого байта. Для цього тут введено перетворення${\displaystyle littleendian(b)}$

Нехай${\displaystyle b=(b_0,b_1,b_2,b_3)}$ — 4-байтова послідовність, тоді${\displaystyle littleendian(b)}$ — слово, таке, що

${\displaystyle littleendian(b)=b_0+2^8{b}_1+2^{16}{b}_2+2^{24}{b}_3}$

Підсумкове перетворення — це побітове додавання вихідної послідовності і результату 20 раундів почергових перетворень стовпців і рядків.

${\displaystyle Salsa20(x)=x\oplus doubleroun{d}^{10}(x)}$де${\displaystyle x=(x[0],x[1],...,x[63]),}$

${\displaystyle x_0=littleendian(x[0],x[1],x[2],x[3]),}$

${\displaystyle x_1=littleendian(x[4],x[5],x[6],x[7]),}$

…

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

x[i] — байти x, а x_j — слова, які використовуються в описаних вище функціях.

Якщо
${\displaystyle (z_0,z_1,...,z_{15})=doubleroun{d}^{10}(x_0,x_1,...,x_{15})}$,

тоді Salsa20(x) є послідовністю результатів
${\displaystyle littleendia{n}^{-1}(z_0+x_0),...,littleendia{n}^{-1}(z_{15}+x_{15})}$

Розширення перетворює 32-байтний або 16-байтний ключk і 16-байтний номерn в 64-байтну послідовність${\displaystyle Salsa{20}_k(n)}$.
Для розширенняk використовуються константи${\displaystyle {\sigma }_0=(101,120,112,97),{\sigma }_1=(110,100,32,51),{\sigma }_2=(50,45,98,121),{\sigma }_3=(116,101,32,107)}$

для 32-бітногоk і

${\displaystyle {\tau }_0=(101;120;112;97),{\tau }_1=(110;100;32;49),{\tau }_2=(54;45;98;121),{\tau }_3=(116;101;32;107)}$
для 16-бітногоk.Це записи «expand 32-byte k» і «expand 16-byte k»ASCII-коді.

Нехай k₀,k₁,n — 16-байтові послідовності, тоді
${\displaystyle Salsa{20}_{k_0,k_1}(n)=Salsa20({\sigma }_0,k_0,{\sigma }_1,n,{\sigma }_2,k_1,{\sigma }_3)}$.

Якщо у нас тільки одна 16-байтові послідовністьk то
${\displaystyle Salsa{20}_k(n)=Salsa20({\tau }_0,k,{\tau }_1,n,{\tau }_2,k,{\tau }_3)}$

Шифром${\displaystyle l}$-байтної послідовності${\displaystyle m}$, для${\displaystyle l\in \{0,1,..{.2}^{70}\}}$ буде${\displaystyle Salsa{20}_k(v)\oplus m}$
${\displaystyle v}$ — унікальний 8-байтовий номер (nonce).Шифротекст буде розміром${\displaystyle l}$ байт, так само, як вихідний текст.

Salsa20_k(v) — послідовність у 2⁷⁰ байт.

${\displaystyle Salsa{20}_k(v,\underset{\_}{0}),Salsa{20}_k(v,\underset{\_}{1}),Salsa{20}_k(v,\underset{\_}{2}),...,Salsa{20}_k(v,\underset{\_}{2^{64}-1})}$

Де${\displaystyle \underset{\_}{i}}$ — унікальна послідовність у 8 байт${\displaystyle (i_0,i_1,...,i_7)}$ така що${\displaystyle i=i_0+2^8{i}_1+...+2^{56}{i}_7}$Відповідно

${\displaystyle Salsa{20}_k(v)\oplus (m[0],m[1],..,m[l-1])=(c[0],c[1],...,c[l-1])}$

Де${\displaystyle c[i]=m[i]\oplus Salsa{20}_k(v,\mathcal{b}\underset{\_}{i/64}\mathcal{c})[i\mathrm{mod}64]}$

Завдяки тому, що перетворення кожного стовпця і кожного рядка не залежать один від одного, обчислення, необхідні для шифрування, легкорозпаралелюються. Це дає суттєвий виграш у швидкості для більшості сучасних платформ.

Алгоритм практично не має накладних обчислень, необхідних для запуску циклу шифрування. Це так само відноситься до зміни ключа. Велика кількість шифросистем розраховує на попередні обчислення, результати яких повинні зберігатися вкеші першого рівня (L1)процесора. Так як вони залежать від ключа, обчислення доведеться проводити заново. У Salsa20 ж достатньо просто завантажити ключ в пам'ять.

Salsa20/8 і Salsa20/12 - це шифросистеми, що використовують той же механізм, що і Salsa20, але з 8 і 12 раундами шифрування, відповідно, замість 20 оригінальних.Salsa20 був зроблений з великим запасом стійкості. Тоді як Salsa20/8 показує хороші результати у швидкодії, обганяючи в більшості випадків багато інших шифросистем, в тому числіAES іRC4^[1]

Існує варіант алгоритму Salsa20, також запропонований Даніелем Бернштейном, в якому довжинаnonce збільшена з 64 до 192 біт. Цей варіант називається XSalsa20. Збільшений розмір nonce дозволяє використовувати для його генераціїкриптографічно стійкого генератора псевдовипадкових чисел, в той час як для безпечного шифрування з 64-бітним nonce необхідне використання лічильника через високу ймовірність колізій.^[2].

У 2005 році Paul Crowley оголосив проатаки на Salsa20/5 з розрахунковою складністю по часу 2¹⁶⁵. Ця і наступні атаки засновані на урізаному диференціальному криптоаналізі (truncated differential криптоаналіз). За цей криптоаналіз він отримав нагороду в 1000$ від автора Salsa20.

B 2006, Fischer, Meier, Berbain, Biasse, і Robshaw повідомили про атаку на Salsa/6 зі складністю 2¹¹⁷, і про атаку з пов'язаними ключами на Salsa20/7 зі складністю 2²¹⁷

B 2008 році Aumasson, Fischer, Khazaei, Meier і Rechberger повідомили про атаку на Salsa20/7 зі складністю 2¹⁵³ і про першу атаку на Salsa20/8 зі складністю 2²⁵¹.

Поки що не було публічних повідомлень про атаки на Salsa20/12 і повну Salsa20/20.

У 2008 році Даніель Берштейн опублікував споріднене сімействопотокових шифрів під назвою ChaCha, метою якого було поліпшення перемішування даних за один раунд і, ймовірно, поліпшеннякриптостійкості при тій же, або навіть трохи більшій швидкості^[3].

ChaCha20 описаний вRFC 7539 (травень 2015).

Основний блок системи тут працює інакше. Теперкожна операція змінює одне з слів. Зміни відбуваються циклічно «у зворотний бік», починаючи з 0-го слова. Чергуються операції додавання побітової суми разом із зсувом, кожне слово складається з попереднім.

Функція quarterround(a, b, c, d), де a, b, c, d-слова, в ChaCha виглядає наступним чином

${\displaystyle a+=b;d\oplus =a;d⋘=16;}$

${\displaystyle c+=d;b\oplus =c;b⋘=12;}$

${\displaystyle a+=b;d\oplus =a;d⋘=8;}$

${\displaystyle c+=d;b\oplus =c;b⋘=7;}$

Тут використовуються ті ж самі арифметичні операції, але кожне слово змінюється два рази за перетворення замість одного.

• Salsa20 Домашня сторінка[Архівовано 14 травня 2011 уWayback Machine.]
• Специфікація[Архівовано 15 грудня 2017 уWayback Machine.]
• Salsa20/8 і Salsa20/12[Архівовано 15 грудня 2017 уWayback Machine.]
• Сторінка Salsa20 на eSTREAM[Архівовано 5 квітня 2016 уWayback Machine.]
• Сімейство шифрів ChaCha[Архівовано 7 грудня 2020 уWayback Machine.]
• Salsa20 speed[Архівовано 25 серпня 2017 уWayback Machine.]

• Потокові шифри

• Шаблон:Webarchive:посилання на Wayback Machine
• Сторінки, що використовують магічні посилання RFC