Salsa20

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

Шифр Salsa20 использует следующие операции:

• сложение 32-битных чисел;
• побитовое сложение по модулю 2 (xor);
• сдвиги битов.

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

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

Понятия

Словом далее будем называть элемент множества {0,1,…,2^32−1} и записывать в шестнадцатеричном виде с префиксом 0х.

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

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

${\displaystyle c}$-битовый циклический левый сдвиг слова ${\displaystyle u}$ будем обозначать ${\displaystyle u\lll c}$. Если ${\displaystyle u}$ представить как ${\displaystyle u=\sum _{i=0}2^{i}u_{i}}$, тогда

${\displaystyle u\lll c=\sum _{i=0}2^{i+c\mod 32}u_{i}}$

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

${\displaystyle quarterround(y_{0},y_{1},y_{2},y_{3})}$

quarterround(y)

Основным блоком системы является преобразование ${\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})\lll 7),}$

${\displaystyle z_{2}=y_{2}\oplus ((z_{1}+y_{0})\lll 9),}$

${\displaystyle z_{3}=y_{3}\oplus ((z_{2}+z_{1})\lll 13),}$

${\displaystyle 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)

${\displaystyle 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. Берем каждый ряд этой матрицы и преобразуем слова этой матрицы функцией ${\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}).}$

columnround(y)

Здесь мы берём столбцы такой же матрицы. Преобразуем их функцией ${\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)

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

Salsa20()

Данный алгоритм использует запись слова, начинающуюся с младшего байта. Для этого здесь введено преобразование ${\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 doubleround^{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})=doubleround^{10}(x_{0},x_{1},...,x_{15})}$,

тогда Salsa20(x) является последовательностью результатов

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

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

Расширение преобразует 32-байтный или 16-байтный ключ k и 16-байтный номер n в 64-байтную последовательность ${\displaystyle Salsa20_{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 Salsa20_{k_{0},k_{1}}(n)=Salsa20(\sigma _{0},k_{0},\sigma _{1},n,\sigma _{2},k_{1},\sigma _{3})}$.

Если у нас только одна 16-байтовая последовательность k то
${\displaystyle Salsa20_{k}(n)=Salsa20(\tau _{0},k,\tau _{1},n,\tau _{2},k,\tau _{3})}$

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

Шифром ${\displaystyle l}$-байтной последовательности ${\displaystyle m}$, для ${\displaystyle l\in \{0,1,...2^{70}\}}$ будет ${\displaystyle Salsa20_{k}(v)\oplus m}$

${\displaystyle v}$ — уникальный 8-байтовый номер (nonce).

Шифротекст будет размером в ${\displaystyle l}$ байт, так же, как и исходный текст.

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

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

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

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

Где ${\displaystyle 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].

Вариант XSalsa20

Существует вариант алгоритма Salsa20, также предложенный Даниэлем Бернштейном, в котором длина nonce увеличена с 64 до 192 бит. Данный вариант называется XSalsa20. Увеличенный размер nonce позволяет использовать для его генерации криптографически стойкий генератор псевдослучайных чисел, в то время как для безопасного шифрования с 64-битным nonce необходимо использование счётчика из-за высокой вероятности коллизий[2].

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

В 2005 году Paul Crowley объявил об атаке на Salsa20/5 с расчетной сложностью по времени 2^165. Эта и последующие атаки основаны на усеченном дифференциальном криптоанализе (truncated differential cryptanalysis). За этот криптоанализ он получил награду в 1000$ от автора Salsa20.

B 2006, Fischer, Meier, Berbain, Biasse, и Robshaw сообщили об атаке на Salsa/6 со сложностью 2^117, и об атаке со связанными ключами на Salsa20/7 со сложностью 2^217.

B 2008 году Aumasson, Fischer, Khazaei, Meier и Rechberger сообщили об атаке на Salsa20/7 со сложностью 2^153 и о первой атаке на Salsa20/8 со сложностью 2^251.

Пока что не было публичных сообщений об атаках на Salsa20/12 и полную Salsa20/20.

ChaCha

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

В 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\lll =16;}$

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

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

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

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

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

Примечания

1. Архивированная копия  (неопр.). Дата обращения: 11 ноября 2010. Архивировано 15 декабря 2017 года.
2. Архивированная копия  (неопр.). Дата обращения: 13 сентября 2016. Архивировано 18 сентября 2018 года.
3. Архивированная копия  (неопр.). Дата обращения: 11 ноября 2010. Архивировано 2 мая 2018 года.

Ссылки

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