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 cryptanalysis). За этот криптоанализ он получил награду в 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 году Daniel Bernstein опубликовал родственное семействопоточных шифров под названием 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;}$

Здесь используются те же самые арифметические операции, но каждое слово изменяется два раза за преобразование вместо одного.

Кроме того, изменено начальное состояние шифра (расширение ключа) по сравнению с Salsa: первые 128 бит занимают константы, затем следует 256 бит ключа, 32 бита счетчика и затем 96 бит уникальной последовательности nonce.

• Salsa20 Домашняя страница
• Спецификация
• Salsa20/8 и Salsa20/12
• Страница Salsa20 на eSTREAM
• Семейство шифров ChaCha
• Salsa20 speed

• Потоковые шифры

• Страницы, использующие волшебные ссылки RFC