Salsa20

Материал из Википедии — свободной энциклопедии
(перенаправлено с «ChaCha20»)
Перейти к навигации Перейти к поиску

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

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

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

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

[править | править код]

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

Операцию сложения двух слов по модулю 232 будем обозначать знаком «».

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

-битовый циклический левый сдвиг слова будем обозначать . Если представить как , тогда

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

[править | править код]

Основным блоком системы является преобразование над четырьмя словами. Из него строятся далее описанные более общие преобразования.

Его суть заключается в том, что для каждого слова мы складываем два предыдущих, сдвигаем (циклично) сумму на определённое количество бит и побитово суммируем результат с выбранным словом. Последующие операции производятся с новыми значениями слов.

Допустим, что  — последовательность 4 слов тогда функция где

Например:

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

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

В этом преобразовании мы берем 16 слов. Представим их в виде матрицы 4х4. Берем каждый ряд этой матрицы и преобразуем слова этой матрицы функцией . Слова из строки берутся по порядку, начиная с i-го для i-й строки, где i={0,1,2,3}.

Пусть  — последовательность 16 слов, тогда  — также последовательность 16 слов где

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

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

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

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

Пусть  — 4-байтовая последовательность, тогда  — слово, такое, что

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

Где

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

Если

,

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

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

[править | править код]

Расширение преобразует 32-байтный или 16-байтный ключ k и 16-байтный номер n в 64-байтную последовательность .

Для расширения k используются константы

для 32-байтного k и

для 16-байтного k.

Это записи «expand 32-byte k» и «expand 16-byte k» в ASCII-коде.

Пусть у k0,k1,n — 16-байтовые последовательности, тогда
.

Если у нас только одна 16-байтовая последовательность k то

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

[править | править код]

Шифром -байтной последовательности , для будет

 — уникальный 8-байтовый номер (nonce).

Шифротекст будет размером в байт, так же, как и исходный текст.

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

Где  — уникальная последовательность в 8 байт такая что Соответственно

Где

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

[править | править код]

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

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

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

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

Примечания

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