Salsa20

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Описание алгоритма[править | править исходный текст]

Понятия[править | править исходный текст]

Словом далее будем называть элемент множества {0,1,…,232−1} и записывать в шестнадцатеричном виде с префиксом 0х.
Операцию сложения двух слов по модулю 232 будем обозначать знаком «~+».
Исключающее или (побитовое суммирование) будем обозначать символом «\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)

Можно рассматривать эту функцию как преобразования слов y1, y2, y3 и y4. Каждое из таких преобразований обратимо, как и функция в целом.

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, а xj — слова, используемые в описанных выше функциях.

Если
~(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-коде.

Пусть у k0,k1,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 байт, так же как и исходный текст.

Salsa20k(v) — последовательность в 270 байт.

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 с расчетной сложностью по времени 2165. Эта и последующие атаки основаны на усеченном дифференциальном криптоанализе(truncated differential cryptanalysis). За этот криптоанализ он получил награду в 1000$ от автора Salsa20.
B 2006, Fischer, Meier, Berbain, Biasse, и Robshaw сообщили об атаке на Salsa/6 со сложностью 2117, и об атаке со связанными ключами на Salsa20/7 со сложностью 2217
B 2008 году Aumasson, Fischer, Khazaei, Meier и Rechberger сообщили об атаке на Salsa20/7 со сложностью 2153 и о первой атаке на Salsa20/8 со сложностью 2251.

Пока что не было публичных сообщений об атаках на 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;

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

Примечания[править | править исходный текст]

Ссылки[править | править исходный текст]