Salsa20

Salsa20

Функция сальсы на четверть круга. Четыре параллельных копии образуют круг.
Общие
Дизайнеры	Дэниэл Дж. Бернштейн
Впервые опубликовано	2007 (разработан в 2005 году)
Преемники	ChaCha
Относится к	Rumba20
Сертификация	eSTREAM портфель
Детали шифра
Размеры ключей	128 или 256 бит
Размер состояния	512 бит
Структура	ARX
Округляет	20
Скорость	3,91 cpb на Intel Core 2 Duo
Best public cryptanalysis
2008 криптоанализ разбивает 8 раундов из 20 для восстановления 256-битного секретного ключа за 2 операции, используя 2 пары потоков ключей.

Salsa20 и тесно связанный ChaCha потоковые шифры, разработанные Дэниелом Дж. Бернстайном. Salsa20, оригинальный шифр, был разработан в 2005 году, а затем передан в eSTREAM Бернстайном. ChaCha - это модификация Salsa20, опубликованная в 2008 году. В нем используется новая функция раунда, которая увеличивает распространение и увеличивает производительность на некоторых архитектурах.

Оба шифра построены на псевдослучайной функции на основе add-rotate-XOR (ARX) operations - 32-битные операции сложения, побитового сложения (XOR) и вращения. Основная функция отображает 256- бит ключ, 64-битный nonce и 64-битный счетчик в 512-битный блок ключевого потока. (также существует версия Salsa со 128-битным ключом). Это дает Salsa20 и ChaCha необычное преимущество, заключающееся в том, что пользователь может эффективно искать любую позицию в ключевом потоке за постоянное время. Salsa20 обеспечивает скорость около 4–14 циклов на байт в программном обеспечении на современных процессорах x86 и разумную производительность оборудования. Он не запатентован, и Бернштейн написал несколько реализаций общественного достояния, оптимизированных для общих архитектур.

• 1 Структура
  • 1.1 XSalsa20 с 192-битным nonce
• 2 Выбор eSTREAM Salsa20
• 3 Криптоанализ Salsa20
• 4 Вариант ChaCha
  • 4.1 XChaCha
  • 4.2 Принятие ChaCha20
• 5 См. Также
• 6 Примечания
• 7 Ссылки
• 8 Внешние ссылки

Внутри шифр использует поразрядное сложение ⊕ (исключающее ИЛИ ), 32-битное сложение mod 2 ⊞ и операции вращения с постоянным расстоянием (<<<) on an internal state of sixteen 32-bit words. Using only Операции add-rotate-xor исключают возможность временных атак в программных реализациях. Внутреннее состояние состоит из шестнадцати 32-битных слов, расположенных в виде матрицы 4 × 4.

Начальное состояние состоит из восьми ключевых слов, двух слов позиции потока, двух слов nonce (по существу, дополнительных битов позиции потока) и четырех фиксированных слов:

Константа слова записывают "развернуть 32-байтовый k" в ASCII (т.е. 4 слова - «expa», «nd 3», «2-by» и «te k»). Это пример номера "ничего в рукаве". Основная операция в Salsa20 - это четвертьраундовый QR (a, b, c, d), который принимает ввод из четырех слов и производит вывод из четырех слов:

b ^ = (a + d) <<< 7; c ^= (b + a) <<< 9; d ^= (c + b) <<< 13; a ^= (d + c) <<< 18;

Раунды с нечетными номерами применяют QR (a, b, c, d)к каждому из четырех столбцов в матрице 4 × 4, а циклы с четными номерами нанесите его на каждый из четырех рядов. Два последовательных цикла (по столбцу и по строке) вместе называются двойным циклом:

// Нечетный раунд QR (0, 4, 8, 12) // столбец 1 QR (5, 9, 13, 1) // столбец 2 QR (10, 14, 2, 6) // столбец 3 QR (15, 3, 7, 11) // столбец 4 // Четное округление QR (0, 1, 2, 3) // строка 1 QR (5, 6, 7, 4) // строка 2 QR (10, 11, 8, 9) // строка 3 QR (15, 12, 13, 14) // строка 4

Реализация на C / C ++ представлена ​​ниже.

#include #define ROTL (a, b) (((a) << (b)) | ((a)>>(32 - (b)))) #define QR (a, b, c, d) (\ b ^ = ROTL (a + d, 7), \ c ^ = ROTL (b + a, 9), \ d ^ = ROTL (c + b, 13), \ a ^ = ROTL (d + c, 18)) # определить ROUNDS 20 void salsa20_block (uint32_t out [16], uint32_t const in [16]) {int i; uint32_t x [16]; for (i = 0; i < 16; ++i) x[i] = in[i]; // 10 loops × 2 rounds/loop = 20 rounds for (i = 0; i < ROUNDS; i += 2) { // Odd round QR(x[ 0], x[ 4], x[ 8], x[12]); // column 1 QR(x[ 5], x[ 9], x[13], x[ 1]); // column 2 QR(x[10], x[14], x[ 2], x[ 6]); // column 3 QR(x[15], x[ 3], x[ 7], x[11]); // column 4 // Even round QR(x[ 0], x[ 1], x[ 2], x[ 3]); // row 1 QR(x[ 5], x[ 6], x[ 7], x[ 4]); // row 2 QR(x[10], x[11], x[ 8], x[ 9]); // row 3 QR(x[15], x[12], x[13], x[14]); // row 4 } for (i = 0; i < 16; ++i) out[i] = x[i] + in[i]; }

В последней строке смешанный массив слово за словом добавляется к исходному массиву, чтобы получить его 64-байтовый блок потока ключей. Это важно, потому что циклы микширования сами по себе обратимый. Другими словами, применение обратных операций приведет к созданию исходной матрицы 4 × 4, включая ключ. Добавление смешанного массива к исходному делает невозможным восстановление входных данных (этот же метод широко используется в хэш-функциях из MD4 - SHA-2.)

Salsa20 выполняет 20 циклов микширования на своем входе. Однако варианты с сокращенным циклом Salsa20 / 8 и Salsa20 / 12 с использованием 8 и 12 соответственно. Эти варианты были введены для дополнения оригинального Salsa20, а не для его замены, и показали даже лучшие результаты в тестах eSTREAM, чем Salsa20, хотя и с соответственно более низким запасом прочности.

XSalsa20 с 192 -bit nonce

В 2008 году Бернштейн предложил вариант Salsa20 со 192-битными одноразовыми номерами под названием XS alsa20. XSalsa20 безопасен, если Salsa20 безопасен, но больше подходит для приложений, где требуются более длинные одноразовые номера. XSalsa20 подает ключ и первые 128 бит одноразового номера в один блок Salsa20 (без окончательного добавления, которое может быть опущено или вычтено после стандартного блока Salsa20) и использует 256 битов вывода в качестве ключа для стандартного Salsa20 с использованием последних 64 бита одноразового номера и позиции потока. В частности, используемые 256 битов вывода соответствуют несекретным частям ввода: индексам 0, 5, 10, 15, 6, 7, 8 и 9.

Salsa20 был выбран в качестве дизайна фазы 3 для профиля 1 (программное обеспечение) проектом eSTREAM, получив наивысший взвешенный балл голосования среди всех алгоритмов профиля 1 в конце фазы 2. Salsa20 имел ранее был выбран проектом eSTREAM в качестве дизайна фазы 2 для профиля 1 (программное обеспечение) и в качестве дизайна фазы 2 для профиля 2 (аппаратное обеспечение), но не был переведен на этап 3 для профиля 2, поскольку eSTREAM считал, что это, вероятно, не хороший кандидат для аппаратных сред с крайне ограниченными ресурсами.

По состоянию на 2015 год опубликованных атак на Salsa20 / 12 или полную версию Salsa20 / 20 не имеется; лучшая известная атака разбивает 8 из 12 или 20 раундов.

В 2005 году Пол Кроули сообщил об атаке на Salsa20 / 5 с расчетной временной сложностью 2 и выиграл приз Бернштейна в 1000 долларов США за «самый интересный криптоанализ Salsa20». Эта атака и все последующие атаки основаны на усеченном дифференциальном криптоанализе. В 2006 году Фишер, Мейер, Бербейн, Биасс и Робшоу сообщили об атаке на Salsa20 / 6 с расчетной временной сложностью 2 и об атаке с использованием связанных ключей на Salsa20 / 7 с расчетной временной сложностью 2.

В 2007 году Tsunoo et al. объявила о криптоанализе Salsa20, который разбивает 8 раундов из 20 для восстановления 256-битного секретного ключа за 2 операции с использованием 2 пар потоков ключей. Однако эта атака не кажется конкурентоспособной с атакой грубой силы.

В 2008 году Аумассон, Фишер, Хазаеи, Мейер и Рехбергер сообщили о криптоаналитической атаке на Salsa20 / 7 с временной сложностью 2, и они сообщили о первой атаке на Salsa20 / 8 с расчетной временной сложностью 2. Эта атака использует новую концепцию вероятностных нейтральных ключевых битов для вероятностного обнаружения усеченного дифференциала. Атака может быть адаптирована для взлома Salsa20 / 7 с помощью 128-битного ключа.

В 2012 году атака Aumasson et al. был улучшен Shi et al. против Salsa20 / 7 (128-битный ключ) до временной сложности 2 и Salsa20 / 8 (256-битный ключ) до 2.

В 2013 году Mouha и Preneel опубликовали доказательство того, что 15 раундов Salsa20 были 128-битная защита от дифференциального криптоанализа. (В частности, у него нет дифференциальной характеристики с большей вероятностью, чем 2, поэтому дифференциальный криптоанализ будет сложнее, чем исчерпание 128-битного ключа.)

ChaCha

Четверть-раундовая функция ChaCha. Четыре параллельных копии образуют круг.
Общие
Дизайнеры	Дэниел Дж. Бернштейн
Впервые опубликовано	2008
На основе	Salsa20
Связанные до	Rumba20
Детали шифра
Размеры ключа	128 или 256 бит
Размер состояния	512 бит
Структура	ARX
Раунды	20
Скорость	3,95 cpb на Intel Core 2 Duo

В 2008 году Бернштейн опубликовал родственное семейство шифров ChaCha, которое стремитесь увеличить диффузию за раунд при достижении той же или немного лучшей производительности. The Aumasson et al. paper также атакует ChaCha, достигая на один раунд меньше: для 256-битного ChaCha6 со сложностью 2 и ChaCha7 со сложностью 2. 128-битный ChaCha6 в пределах 2, но утверждает, что атака не может сломать 128-битный ChaCha7.

Как и Salsa20, Начальное состояние ChaCha включает в себя 128-битную константу, 256-битный ключ, 64-битный счетчик и 64-битный одноразовый номер, организованный как матрица 4 × 4 из 32-битных слов. Но ChaCha переставляет некоторые слова в исходное состояние:

Константа такая же, как Salsa20 («развернуть 32-байтовый k»). ChaCha заменяет четверть раунда Salsa20 QR (a, b, c, d)на

a + = b; d ^ = a; d <<<= 16; c += d; b ^= c; b <<<= 12; a += b; d ^= a; d <<<= 8; c += d; b ^= c; b <<<= 7;

Обратите внимание, что в этой версии каждое слово обновляется дважды, в то время как четверть круга Salsa20 обновляет каждое слово только один раз. Кроме того, четверть-раундовый ChaCha распространяет изменения быстрее. В среднем, после изменения 1 входного бита четверть-раунд Salsa20 изменит 8 выходных бит, в то время как ChaCha изменит 12,5 выходных бит.

Четверть-раунд ChaCha имеет такое же количество сложений, xors и битов вращения, как Salsa20 - четверть раунда, но тот факт, что два поворота кратны 8, позволяет провести небольшую оптимизацию на некоторых архитектурах, включая x86. Кроме того, форматирование ввода было изменено для поддержки эффективной оптимизации реализации SSE, обнаруженной для Salsa20. Вместо чередования округлений вниз по столбцам и по строкам, они выполняются по столбцам и по диагоналям. Как и Salsa20, ChaCha упорядочивает шестнадцать 32-битных слов в матрицу 4 × 4. Если мы индексируем матричные элементы от 0 до 15

Тогда двойной раунд в ChaCha будет:

// Нечетный раунд QR (0, 4, 8, 12) / / 1-й столбец QR (1, 5, 9, 13) // 2-й столбец QR (2, 6, 10, 14) // 3-й столбец QR (3, 7, 11, 15) // 4-й столбец // Четный круглый QR (0, 5, 10, 15) // диагональ 1 (главная диагональ) QR (1, 6, 11, 12) // диагональ 2 QR (2, 7, 8, 13) // диагональ 3 QR (3, 4, 9, 14) // диагональ 4

ChaCha20 использует 10 итераций двойного раунда. Ниже представлена ​​реализация на C / C ++.

#define ROTL (a, b) (((a) << (b)) | ((a)>>(32 - (b)))) #define QR (a, b, c, d) (\ a + = b, d ^ = a, d = ROTL (d, 16), \ c + = d, b ^ = c, b = ROTL (b, 12), \ a + = b, d ^ = a, d = ROTL (d, 8), \ c + = d, b ^ = c, b = ROTL (b, 7)) #define ROUNDS 20 void chacha_block (uint32_t out [16], uint32_t const in [16]) {int i; uint32_t x [16]; for (i = 0; i < 16; ++i) x[i] = in[i]; // 10 loops × 2 rounds/loop = 20 rounds for (i = 0; i < ROUNDS; i += 2) { // Odd round QR(x[0], x[4], x[ 8], x[12]); // column 0 QR(x[1], x[5], x[ 9], x[13]); // column 1 QR(x[2], x[6], x[10], x[14]); // column 2 QR(x[3], x[7], x[11], x[15]); // column 3 // Even round QR(x[0], x[5], x[10], x[15]); // diagonal 1 (main diagonal) QR(x[1], x[6], x[11], x[12]); // diagonal 2 QR(x[2], x[7], x[ 8], x[13]); // diagonal 3 QR(x[3], x[4], x[ 9], x[14]); // diagonal 4 } for (i = 0; i < 16; ++i) out[i] = x[i] + in[i]; }

ChaCha является основой хэш-функции BLAKE, финалистом конкурса хэш-функций NIST и преемниками BLAKE2 / 3, настроенными на еще более высокие скорость. Он также определяет вариант с использованием шестнадцати 64-битных слов (1024 бита состояния) с соответствующим образом скорректированными константами вращения.

XChaCha

Хотя это и не объявлено Бернштейном, это доказательство безопасности XSalsa20 напрямую расширяется до аналогичного шифра XChaCha. Используйте ключ и первые 128 бит одноразового номера (во входных словах с 12 по 15), чтобы сформировать входной блок ChaCha, затем выполните операцию блока (пропуская последнее сложение). Выходные слова 0– 3 и 12–15 (те слова, которые соответствуют неключевым словам ввода) затем формируют ключ, используемый для обычного ChaCha (с последними 64 битами одноразового номера и 64 битами счетчика блоков).

Принятие ChaCha20

Google выбрал ChaCha20 вместе с кодом аутентификации сообщения Бернштейна Poly1305 в качестве замены RC4 в TLS, который используется для обеспечения безопасности в Интернете. Реализация Google защищает трафик HTTPS (TLS / SSL ) между браузером Chrome на телефонах Android и веб-сайтами Google.

Вскоре после принятия Google для TLS алгоритмы ChaCha20 и Poly1305 также использовались для нового шифра [email#160;protected] в OpenSSH. Впоследствии это позволило OpenSSH избежать любой зависимости от OpenSSL с помощью параметра времени компиляции.

ChaCha20 также используется для генератора случайных чисел arc4randomв операционных системах FreeBSD, OpenBSD и NetBSD вместо сломанного RC4 и в DragonFly BSD для подпрограммы ядра CSPRNG. Начиная с версии 4.8, ядро ​​Linux использует алгоритм ChaCha20 для генерации данных для неблокирующего устройства /dev/urandom.

Ссылка на реализацию ChaCha20 опубликована в RFC 7539. Реализация IETF модифицировала опубликованный алгоритм Бернштейна, изменив 64-битный одноразовый номер и 64-разрядный счетчик блоков на 96-разрядный одноразовый номер и 32-разрядный счетчик блоков. Имя не было изменено при изменении алгоритма, поскольку оно криптографически несущественен (оба образуют то, что криптограф распознал бы как 128-битный одноразовый номер), но изменение интерфейса могло бы запутать разработчиков. Из-за уменьшенного счетчика блоков максимальная длина сообщения, которое может быть безопасно зашифровано вариантом IETF, составляет 2 блока по 64 байта (256 ГиБ ). Для приложений, где этого недостаточно, например, для шифрования файлов или дисков, RFC 7539 предлагает использовать исходный алгоритм с 64-битным одноразовым кодом.

Использование ChaCha20 в IKE и IPsec было предложено для стандартизации в RFC 7634. Предлагаемая стандартизация его использования в TLS опубликована как RFC 7905.

ChaCha20 обычно обеспечивает лучшую производительность, чем более распространенный алгоритм Advanced Encryption Standard (AES) на системы, в которых ЦП не поддерживает ускорение AES (например, набор инструкций AES для процессоров x86) или в которых программное обеспечение не поддерживает его. В результате ChaCha20 иногда предпочтительнее AES в некоторых случаях использования, связанных с мобильными устройствами, которые в основном используют процессоры на базе ARM.

В 2018 году RFC 7539 был отменен на RFC 8439.

ChaCha20 - это алгоритм, используемый исключительно системой VPN WireGuard, начиная с версии протокола 1.

• Speck - шифр add-rotate-xor, разработанный NSA

• Snuffle 2005 : функция шифрования Salsa20
• спецификация Salsa20 (PDF )
• Salsa20 / 8 и Salsa20 / 12 (PDF)
• Проект eSTREAM: Salsa20
• Семейство потоков ChaCha шифры
• Использование и развертывание Salsa20