Salsa20

Salsa20 — система поточного шифрования разработанная Daniel J. Bernstein. Алгоритм был представлен на конкурсе eSTREAM, целью которого было создание европейских стандартов для поточных систем шифрования. Алгоритм стал победителем конкурса в первом профиле (поточные шифры для программного применения с большой пропускной способностью).

Salsa20 основана на операциях 32-битного суммирования, побитового сложения (XOR) и операции сдвига. Алгоритм использует хеш-функцию с 20-ю циклами. Основные её преобразования напоминают алгоритм AES.

Описание алгоритма

Понятия

Словом далее будем называть элемент множества {0,1,…,2³²−1} и записывать в шестнадцатеричном виде с префиксом 0х.
Операцию сложения двух слов по модулю 2³² будем обозначать знаком «$~+$».
Исключающее или (побитовое суммирование) будем обозначать символом «$\oplus$»
$~c$-битовый циклический левый сдвиг слова $~u$ будем обозначать $u\lll c$. Если $~u$ представить как $~u=\sum_{i=1}2^iu_i$, тогда $u\lll c=\sum_{i=1}2^{i+c \mod 32}u_i$

Функции, используемые в алгоритме

$~quarterround(y_0, y_1, y_2, y_3)$

quarterround(y)

Основным блоком системы является преобразование $~quarterround(y)$ над 4-мя словами. Из него строятся далее описанные более общие преобразования. Его суть заключается в том, что для каждого слова мы складываем два предыдущих, сдвигаем сумму на определенное количество бит и побитово суммируем результат с выбранным словом. Последующие операции производятся с новыми значениями слов.

Допустим, что $~y$ — последовательность 4-х слов $~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).$

Например:

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

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

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}$
В этом преобразовании мы берем 16 слов. Представим их в виде матрицы 4х4. Берем каждый ряд этой матрицы и преобразуем слова этой матрицы функцией $quarterround(y)$. Слова из строки берутся по порядку, начиная с i-го для i-й строки, где i={0,1,2,3}.

Пусть $~y=(y_0,y_1,y_2,...,y_{15})$ — последовательность 16 слов, тогда $~rowround(y)=(z_0,z_1,z_2,...,z_{15})$ — также последовательность 16 слов где

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

Здесь мы берем столбцы такой-же матрицы. Преобразуем их функцией $quarterround(y)$, по аналогии подставляя в неё значения, начиная с j-го для j-го столбца, где j={0,1,2,3}.

Функция columnround(y)=(z) тоже оперирует последовательностью 16-и слов так, что

$~(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) является последовательным применением функций columnround а затем rowround: doubleround(y) = rowround(columnround(y))

Salsa20()

Данный алгоритм использует запись слова начинающуюся с младшего байта. Для этого здесь введено преобразование $~littleendian(b)$

Пусть $~b=(b_0,b_1,b_2,b_3)$ — 4-байтовая последовательность, тогда $~littleendian(b)$ — слово, такое что

$~littleendian(b) = b_0 + 2^8 b_1 + 2^{16}b_2 + 2^{24} b_3$

Итоговое преобразование — это побитовое суммирование исходной последовательности и результата 20 раундов чередующихся преобразований столбцов и строк.

$~Salsa20(x) = x \oplus doubleround^{10}(x)$ Где $~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] — байты x, а x_j — слова, используемые в описанных выше функциях.

Если
$~(z_0, z_1,...,z_{15}) = doubleround^{10}(x_0, x_1,..., x_{15})$,
тогда Salsa20(x) является последовательностью результатов
$~littleendian^{-1}(z_0 + x_0), ..., littleendian^{-1}(z_{15} + x_{15})$

Расширение ключа для Salsa20

Расширение преобразует 32-байтный или 16-байтный ключ k и 16-байтный номер n в 64-байтную последовательность $Salsa20_k(n)$.
Для расширения k используются константы
$\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 и

$\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-байтовые последовательности, тогда
$Salsa20_{k_0,k_1}(n)=Salsa20(\sigma_0,k_0,\sigma_1,n,\sigma_2,k_1,\sigma_3)$.

Если у нас только одна 16-байтовая последовательность k то
$~Salsa20_k(n)=Salsa20(\tau_0,k,\tau_1,n,\tau_2,k,\tau_3)$

Функция шифрования Salsa20

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

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

$Salsa20_k(v,\underline{1}),Salsa20_k(v,\underline{2}),...,Salsa20_k(v,\underline{2^{64}-1})$

Где $\underline{i}$ — уникальная последовательность в 8 байт $(i_0, i_1, ..., i_7)$ такая что $i=i_0 + 2^8i_1 + ... + 2^{56}i_7$ Соответственно

$Salsa20_k(v)\oplus(m[0],m[1],..,m[l-1])=(c[0],c[1],...,c[l-1])$

Где $c[i]=m[i] \oplus Salsa20_k(v,\mathcal {b}\underline{i/64}\mathcal {c})[i\mod 64]$

Скоростные особенности

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

Другим скоростным преимуществом является то, что алгоритм практически не имеет накладных вычислений для запуска цикла шифрования.
Это так же относится к смене ключа. Многие шифросистемы рассчитывают на предварительные вычисления, результаты которых должны лежать в L1-кэше. Так как они зависят от ключа, вычисления придется проводить заново. В Salsa20 же достаточно просто загрузить ключ в память.

Варианты Salsa20/8 и Salsa20/12

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

Криптоанализ

В 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.

ChaCha

Вариант ChaCha функции quarterround(a, b, c, d)

В 2008 году Daniel Bernstein опубликовал родственное семейство поточных шифров под названием ChaCha, целью которого было улучшение перемешивания данных за один раунд и, предположительно, улучшение криптостойкости при той же, или даже немного большей скорости.^[2]

Основной блок системы здесь работает иначе. Теперь каждая операция изменяет одно из слов. Изменения происходят циклически «в обратную сторону», начиная с 0-го слова. Чередуются операции сложения и побитовой суммы вместе со сдвигом. складывается слово с предыдущим.

Функция quarterround(a, b, c, d), где a, b, c, d-слова, в ChaCha выглядит следующим образом

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

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

Примечания

1. ↑ http://cr.yp.to/snuffle/812.pdf
2. ↑ http://cr.yp.to/chacha/chacha-20080128.pdf

Ссылки

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