Salsa20

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

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

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

Понятия

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

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

quarterround(y)

Допустим, что 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})<<<7),$

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

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

$z_{0}=y_{0}\oplus ((z_{3}+z_{2})<<<18).$

Например:

quarterround(0x00000001; 0x00000000; 0x00000000; 0x00000000)

          = (0x08008145; 0x00000080; 0x00010200; 0x20500000)

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

rowround(y)

Пусть теперь $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}).$

y можно представить как матрицу 4х4, тогда функция rowround(y) — это функции quaterrouund(y) над ее переставленными рядами.

columnround(y)

Функция 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}).$

В матричном представлении y, columnround(y) производит операции quarterround(y) над ее переставленными столбцами.

doubleround(y)

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

Salsa20()

Пусть $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}$

Что является записью 4-х байт начиная с младшего.

$Salsa20(x)=x+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_{1}5=littleendian(x[60],x[61],x[62],x[63]).$

x[i] — байты x, а x_j — слова, используемые в описанных выше функциях.

Если $(z_{0},z_{1},...,z_{15})=doubleround^{1}0(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_0,k_1,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^{7}0\}$ будет $Salsa20_{k}(v)\oplus m$
v — уникальный 8-байтовый номер(nonce).
Шифротекст будет будет размером в 70 байт, так же как и исходный текст.

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^{8}i_{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]$

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

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

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

В 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

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

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

$a+=b;~~d\oplus =a;~~d<<<16;$

$c+=d;~~b\oplus =c;~~b<<<12;$

$a+=b;~~d\oplus =a;~~d<<<8;$

$c+=d;~~b\oplus =c;~~b<<<7;$

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

Ссылки

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