Salsa20

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

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

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

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

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

Понятия

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

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

quarterround(y)

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

Допустим, что <math>y</math> — последовательность 4 слов <math>y = (y_0, y_1, y_2, y_3)</math> тогда функция <math>quarterround(y) = (z_0, z_1, z_2, z_3)</math> где

<math>z_1 = y_1 \oplus ((y_0 + y_3) \lll 7),</math>

<math>z_2 = y_2 \oplus ((z_1 + y_0) \lll 9),</math>

<math>z_3 = y_3 \oplus ((z_2 + z_1) \lll 13),</math>

<math>z_0 = y_0 \oplus ((z_3 + z_2) \lll 18).</math>

Например:

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

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

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

rowround(y)

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

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

<math>(z_0, z_1, z_2, z_3) = quarterround(y_0, y_1, y_2, y_3),</math>

<math>(z_5, z_6, z_7, z_4) = quarterround(y_5, y_6, y_7, y_4),</math>

<math>(z_{10}, z_{11}, z_8, z_9) = quarterround(y_{10}, y_{11}, y_8, y_9),</math>

<math>(z_{15}, z_{12}, z_{13}, z_{14}) = quarterround(y_{15}, y_{12}, y_{13}, y_{14}).</math>

columnround(y)

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

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

<math>(z_0, z_4, z_8, z_{12}) = quarterround(y_0, y_4, y_8, y_{12}),</math>

<math>(z_5, z_9, z_{13}, z_1) = quarterround(y_5, y_9, y_{13}, y_1),</math>

<math>(z_{10}, z_{14}, z_2, z_6) = quarterround(y_{10}, y_{14}, y_2, y_6),</math>

<math>(z_{15}, z_3, z_7, z_{11}) = quarterround(y_{15}, y_3, y_7, y_{11}).</math>

doubleround(y)

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

Salsa20()

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

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

<math>littleendian(b) = b_0 + 2^8 b_1 + 2^{16}b_2 + 2^{24} b_3</math>

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

<math>Salsa20(x) = x \oplus doubleround^{10}(x)</math> Где <math>x=(x[0], x[1],..., x[63]), </math>

<math>x_0 = littleendian(x[0], x[1], x[2], x[3]),</math>

<math>x_1 = littleendian(x[4], x[5], x[6], x[7]),</math>

…

<math>x_{15} = littleendian(x[60], x[61], x[62], x[63]).</math>

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

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

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

Расширение преобразует 32-байтный или 16-байтный ключ k и 16-байтный номер n в 64-байтную последовательность <math>Salsa20_k(n)</math>.
Для расширения k используются константы
<math>\sigma_0 = (101, 120, 112, 97),~ \sigma_1 = (110, 100, 32, 51),~ \sigma_2 = (50, 45, 98, 121),~ \sigma_3 = (116, 101, 32, 107)</math>
для 32-битного k и

<math>\tau_0 = (101; 120; 112; 97),~ \tau_1 = (110; 100; 32; 49),~ \tau_2 = (54; 45; 98; 121),~ \tau_3 = (116; 101; 32; 107)</math>
для 16-битного k. Это записи «expand 32-byte k» и «expand 16-byte k» ASCII-коде.

Пусть у k₀,k₁,n — 16-байтовые последовательности, тогда
<math>Salsa20_{k_0,k_1}(n)=Salsa20(\sigma_0,k_0,\sigma_1,n,\sigma_2,k_1,\sigma_3)</math>.

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

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

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

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

<math>Salsa20_k(v,\underline{1}),Salsa20_k(v,\underline{2}),...,Salsa20_k(v,\underline{2^{64}-1})</math>

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

<math>Salsa20_k(v)\oplus(m[0],m[1],..,m[l-1])=(c[0],c[1],...,c[l-1])</math>

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

Производительность

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

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

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

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

Вариант XSalsa20

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

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

В 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, целью которого было улучшение перемешивания данных за один раунд и, предположительно, улучшение криптостойкости при той же, или даже немного большей скорости.

ChaCha20 описан в RFC 7539 (май 2015).

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

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

<math>a += b;~~ d \oplus= a;~~ d \lll= 16;</math>

<math>c += d;~~ b \oplus= c;~~ b \lll= 12;</math>

<math>a += b;~~ d \oplus= a;~~ d \lll= 8;</math>

<math>c += d;~~ b \oplus= c;~~ b \lll= 7;</math>

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

Ссылки

• [cr.yp.to/snuffle.html Salsa20 Домашняя страница]
• [cr.yp.to/snuffle/spec.pdf Спецификация]
• [cr.yp.to/snuffle/812.pdf Salsa20/8 и Salsa20/12]
• [www.ecrypt.eu.org/stream/salsa20pf.html Страница Salsa20 на eSTREAM]
• [cr.yp.to/chacha.html Семейство шифров ChaCha]
• [cr.yp.to/snuffle/speed.pdf Salsa20 speed]

Отрывок, характеризующий Salsa20

И Борис, видимо свалив с себя тяжелую обязанность, сам выйдя из неловкого положения и поставив в него другого, сделался опять совершенно приятен.
– Нет, послушайте, – сказал Пьер, успокоиваясь. – Вы удивительный человек. То, что вы сейчас сказали, очень хорошо, очень хорошо. Разумеется, вы меня не знаете. Мы так давно не видались…детьми еще… Вы можете предполагать во мне… Я вас понимаю, очень понимаю. Я бы этого не сделал, у меня недостало бы духу, но это прекрасно. Я очень рад, что познакомился с вами. Странно, – прибавил он, помолчав и улыбаясь, – что вы во мне предполагали! – Он засмеялся. – Ну, да что ж? Мы познакомимся с вами лучше. Пожалуйста. – Он пожал руку Борису. – Вы знаете ли, я ни разу не был у графа. Он меня не звал… Мне его жалко, как человека… Но что же делать?
– И вы думаете, что Наполеон успеет переправить армию? – спросил Борис, улыбаясь.
Пьер понял, что Борис хотел переменить разговор, и, соглашаясь с ним, начал излагать выгоды и невыгоды булонского предприятия.
Лакей пришел вызвать Бориса к княгине. Княгиня уезжала. Пьер обещался приехать обедать затем, чтобы ближе сойтись с Борисом, крепко жал его руку, ласково глядя ему в глаза через очки… По уходе его Пьер долго еще ходил по комнате, уже не пронзая невидимого врага шпагой, а улыбаясь при воспоминании об этом милом, умном и твердом молодом человеке.
Как это бывает в первой молодости и особенно в одиноком положении, он почувствовал беспричинную нежность к этому молодому человеку и обещал себе непременно подружиться с ним.
Князь Василий провожал княгиню. Княгиня держала платок у глаз, и лицо ее было в слезах.
– Это ужасно! ужасно! – говорила она, – но чего бы мне ни стоило, я исполню свой долг. Я приеду ночевать. Его нельзя так оставить. Каждая минута дорога. Я не понимаю, чего мешкают княжны. Может, Бог поможет мне найти средство его приготовить!… Adieu, mon prince, que le bon Dieu vous soutienne… [Прощайте, князь, да поддержит вас Бог.]
– Adieu, ma bonne, [Прощайте, моя милая,] – отвечал князь Василий, повертываясь от нее.
– Ах, он в ужасном положении, – сказала мать сыну, когда они опять садились в карету. – Он почти никого не узнает.
– Я не понимаю, маменька, какие его отношения к Пьеру? – спросил сын.
– Всё скажет завещание, мой друг; от него и наша судьба зависит…
– Но почему вы думаете, что он оставит что нибудь нам?
– Ах, мой друг! Он так богат, а мы так бедны!
– Ну, это еще недостаточная причина, маменька.
– Ах, Боже мой! Боже мой! Как он плох! – восклицала мать.


Когда Анна Михайловна уехала с сыном к графу Кириллу Владимировичу Безухому, графиня Ростова долго сидела одна, прикладывая платок к глазам. Наконец, она позвонила.
– Что вы, милая, – сказала она сердито девушке, которая заставила себя ждать несколько минут. – Не хотите служить, что ли? Так я вам найду место.
Графиня была расстроена горем и унизительною бедностью своей подруги и поэтому была не в духе, что выражалось у нее всегда наименованием горничной «милая» и «вы».
– Виновата с, – сказала горничная.
– Попросите ко мне графа.
Граф, переваливаясь, подошел к жене с несколько виноватым видом, как и всегда.
– Ну, графинюшка! Какое saute au madere [сотэ на мадере] из рябчиков будет, ma chere! Я попробовал; не даром я за Тараску тысячу рублей дал. Стоит!
Он сел подле жены, облокотив молодецки руки на колена и взъерошивая седые волосы.
– Что прикажете, графинюшка?
– Вот что, мой друг, – что это у тебя запачкано здесь? – сказала она, указывая на жилет. – Это сотэ, верно, – прибавила она улыбаясь. – Вот что, граф: мне денег нужно.
Лицо ее стало печально.
– Ах, графинюшка!…
И граф засуетился, доставая бумажник.
– Мне много надо, граф, мне пятьсот рублей надо.
И она, достав батистовый платок, терла им жилет мужа.
– Сейчас, сейчас. Эй, кто там? – крикнул он таким голосом, каким кричат только люди, уверенные, что те, кого они кличут, стремглав бросятся на их зов. – Послать ко мне Митеньку!
Митенька, тот дворянский сын, воспитанный у графа, который теперь заведывал всеми его делами, тихими шагами вошел в комнату.
– Вот что, мой милый, – сказал граф вошедшему почтительному молодому человеку. – Принеси ты мне… – он задумался. – Да, 700 рублей, да. Да смотри, таких рваных и грязных, как тот раз, не приноси, а хороших, для графини.
– Да, Митенька, пожалуйста, чтоб чистенькие, – сказала графиня, грустно вздыхая.
– Ваше сиятельство, когда прикажете доставить? – сказал Митенька. – Изволите знать, что… Впрочем, не извольте беспокоиться, – прибавил он, заметив, как граф уже начал тяжело и часто дышать, что всегда было признаком начинавшегося гнева. – Я было и запамятовал… Сию минуту прикажете доставить?
– Да, да, то то, принеси. Вот графине отдай.
– Экое золото у меня этот Митенька, – прибавил граф улыбаясь, когда молодой человек вышел. – Нет того, чтобы нельзя. Я же этого терпеть не могу. Всё можно.
– Ах, деньги, граф, деньги, сколько от них горя на свете! – сказала графиня. – А эти деньги мне очень нужны.
– Вы, графинюшка, мотовка известная, – проговорил граф и, поцеловав у жены руку, ушел опять в кабинет.
Когда Анна Михайловна вернулась опять от Безухого, у графини лежали уже деньги, всё новенькими бумажками, под платком на столике, и Анна Михайловна заметила, что графиня чем то растревожена.
– Ну, что, мой друг? – спросила графиня.
– Ах, в каком он ужасном положении! Его узнать нельзя, он так плох, так плох; я минутку побыла и двух слов не сказала…
– Annette, ради Бога, не откажи мне, – сказала вдруг графиня, краснея, что так странно было при ее немолодом, худом и важном лице, доставая из под платка деньги.
Анна Михайловна мгновенно поняла, в чем дело, и уж нагнулась, чтобы в должную минуту ловко обнять графиню.
– Вот Борису от меня, на шитье мундира…
Анна Михайловна уж обнимала ее и плакала. Графиня плакала тоже. Плакали они о том, что они дружны; и о том, что они добры; и о том, что они, подруги молодости, заняты таким низким предметом – деньгами; и о том, что молодость их прошла… Но слезы обеих были приятны…


Графиня Ростова с дочерьми и уже с большим числом гостей сидела в гостиной. Граф провел гостей мужчин в кабинет, предлагая им свою охотницкую коллекцию турецких трубок. Изредка он выходил и спрашивал: не приехала ли? Ждали Марью Дмитриевну Ахросимову, прозванную в обществе le terrible dragon, [страшный дракон,] даму знаменитую не богатством, не почестями, но прямотой ума и откровенною простотой обращения. Марью Дмитриевну знала царская фамилия, знала вся Москва и весь Петербург, и оба города, удивляясь ей, втихомолку посмеивались над ее грубостью, рассказывали про нее анекдоты; тем не менее все без исключения уважали и боялись ее.
В кабинете, полном дыма, шел разговор о войне, которая была объявлена манифестом, о наборе. Манифеста еще никто не читал, но все знали о его появлении. Граф сидел на отоманке между двумя курившими и разговаривавшими соседями. Граф сам не курил и не говорил, а наклоняя голову, то на один бок, то на другой, с видимым удовольствием смотрел на куривших и слушал разговор двух соседей своих, которых он стравил между собой.
Один из говоривших был штатский, с морщинистым, желчным и бритым худым лицом, человек, уже приближавшийся к старости, хотя и одетый, как самый модный молодой человек; он сидел с ногами на отоманке с видом домашнего человека и, сбоку запустив себе далеко в рот янтарь, порывисто втягивал дым и жмурился. Это был старый холостяк Шиншин, двоюродный брат графини, злой язык, как про него говорили в московских гостиных. Он, казалось, снисходил до своего собеседника. Другой, свежий, розовый, гвардейский офицер, безупречно вымытый, застегнутый и причесанный, держал янтарь у середины рта и розовыми губами слегка вытягивал дымок, выпуская его колечками из красивого рта. Это был тот поручик Берг, офицер Семеновского полка, с которым Борис ехал вместе в полк и которым Наташа дразнила Веру, старшую графиню, называя Берга ее женихом. Граф сидел между ними и внимательно слушал. Самое приятное для графа занятие, за исключением игры в бостон, которую он очень любил, было положение слушающего, особенно когда ему удавалось стравить двух говорливых собеседников.
– Ну, как же, батюшка, mon tres honorable [почтеннейший] Альфонс Карлыч, – говорил Шиншин, посмеиваясь и соединяя (в чем и состояла особенность его речи) самые народные русские выражения с изысканными французскими фразами. – Vous comptez vous faire des rentes sur l'etat, [Вы рассчитываете иметь доход с казны,] с роты доходец получать хотите?