Представленная статья является первым моим пробным переводом "научно-технической" статьи, а именно работы Даниэля Бернштейна "ChaCha, a variant of Salsa20". Ввиду этого я ожидаю комментарии, связанные с конструктивной критикой неточностей перевода и предложениями по их исправлению.

Аннотация

ChaCha8 это 256-битный поточный шифр, основанный на 8-раунодовом шифре Salsa20/8. Новшества, привнесенные при работе от Salsa20/8 до ChaCha8, позволили улучшить перемежение бит за раунд, тем самым повысив стойкость к криптоанализу при сохранении, а иногда и уменьшении, времени требуемого на вычисления одного раунда. ChaCha12 и ChaCha20 являются аналогичными модификациями 12-раундового и 20-раундового шифров Salsa20/12 и Salsa20/20. В данной статье описывается семейство шифров ChaCha и объясняется разница между Salsa20 и ChaCha.

1. Введение

1.1 Справка

Поточный шифр Salsa20/20 преобразует 256-битный ключ в 2⁶⁴ потоков со случайным доступом, каждый из которых содержит 2⁶⁴ блока объемом 64 байт со случайным доступом. Конструкция Salsa20/20 проще чем у AES. Поэтому общественность решила, что шифр не является безопасным.

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

1.2 Значение статьи

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

Но улучшенное перемежение не требует дополнительных операций. За один ChaCha-раунд происходит 16 сложений, 16 побитных сложений по модулю 2 и 16 циклических сдвигов 32-битных слов, как и в Salsa20. Кроме этого, в ChaCha такой же уровень параллелизма и векторизации, как и в Salsa20, с осуществлением сохранения одного из 17 регистров, которые используется для реализации «исходных» механизмов Salsa20. Поэтому не сложно догадаться, что ChaCha-раунд может достигать ту же программную скорость, что Salsa20-раунд, а иногда и большую, в зависимости от платформы. От сюда получается, что если ChaCha обладает таким же безопасным минимальным количеством раундов, что и Salsa20, то ChaCha работает с большой скоростью, чем Salsa20, при этом обеспечивая такой же уровень безопасности.

Конечно, теоретические высказывания обязаны подкрепляться практическими вычислениями. Поэтому далее будет приведено сравнение, которое производилось между новейшей публикацией ChaCha и наиболее оптимизированной публикацией Salsa20, на нескольких компьютерах, с использованием бенчмарка eSTREAM. Результаты приведены в таблице 1.

Таблица 1 – Сравнение Salsa20 и ChaCha

Компьютер			Циклов/Байт
Компьютер			8 раундов		12 раундов		20 раундов
Архитектура	МГц	Процессор	Salsa20	ChaCha	Salsa20	ChaCha	Salsa20	ChaCha
ppc32	533	PowerPC G4	1.99	1.86	2.74	2.61	4.24	4.13
amd64	2137	Core 2 Duo	1.87	1.87	2.53	2.54	3.90	3.95
ppc64	2000	PowerPC G5	3.24	3.06	4.74	4.57	7.81	7.58
amd64	2000	Athlon 64 X2	3.47	3.29	4.86	4.61	7.64	7.23
amd64	3000	Pentium D	5.39	3.87	7.16	5.27	10.65	8.23
x86	1300	Pentium M	5.30	4.88	7.44	7.06	11.70	11.08
x86	900	Athlon	4.62	5.36	6.44	7.58	10.04	12.21
sparc	1050	UltraSPARC	6.65	6.60	9.17	9.17	14.34	14.29
x86	3200	Pentium D	7.13	6.75	9.77	9.33	14.33	14.27
x86	1900	Pentium 4	5.41	7.08	8.21	9.72	11.74	15.03

Таким образом, были получены следующие результаты измерений:

одинаковая скорость на 64-битной amd64-архитектуре Core 2.
одинаковая скорость на 64-битной sparc-архитектуре UltraSPARC.
на 5% быстрее на 64-битной amd64-архитектуре Athlon 64.
на 5% быстрее на 32-битной x86-архитектуре Pentium D.
на 5% быстрее на 64-битной ppc64-архитектуре Core 2.
на 6% быстрее на 32-битной ppc32-архитектуре Core 2.
на 8% быстрее на 32-битной x86-архитектуре Core 2.
на 28% быстрее на 64-битной amd64-архитектуре Core 2.

Данная статья предполагается для тех читателей, которые знакомы с Salsa20 и нацелены на изучение изменений произошедших от Salsa20 до ChaCha. В главе 2 содержится сравнение «четверть-раунда» Salsa20 и «четверть-раунда» ChaCha. В главе 3 содержится сравнение матриц Salsa20 и ChaCha.

2. "Четверть-раунд"

2.1 Разбор "четверть-раунда" Salsa20

В Salsa20 происходит преобразование 4 32-битных слов a, b, c и d:

Операции представлены в виде кода на языке программирования С:

побитное сложение по модулю 2.
сложение по модулю 2³².
циклическое смещение на определенное количество бит.

Всего в Salsa20 16 слов, но в «четверть-раунде» происходит работа только с четырьмя. Вопрос с доступом и связи всех 16 слов является проблематичным на некоторых платформах; Salsa20 снижает частоту
доступа путем выполнения нескольких операций с четырьмя словами, прежде чем переходить к следующим четырем словам.

2.2 "Четверть-раунд" ChaCha

ChaCha, как и Salsa20, использует 4 операции сложения, 4 операции побитного сложения по модулю 2 и 4 циклических сдвига для преобразования четырех 32-битных слов. Однако, ChaCha использует эти операции в другом порядке, тем самым изменяя каждое слова не один, а два раза. Таким образом, в ChaCha используются следующие операции:

Очевидно то, что в «четверть-раунде» ChaCha, в отличие от «четверть-раунда» Salsa20, каждое входное слово влияет на каждое выходное слово. Менее очевидно, то, что «четверть-раунд» ChaCha распространяет изменения через биты быстрее чем «четверть-раунд» Salsa20. Это можно заметить при наблюдении всевозможных однобитных входных изменений: в отсутствии переносов, «четверть-раунд» ChaCha изменяет (в среднем) выходных 12,5 бит, в то время как «четверть-раунд» Salsa20 только 8 выходных бит.

Почти двукратный прирост в скорости является важнейшим отличием ChaCha от Salsa20. После публикации этого достижения, Аумассон, Фишер, Хазаи, Майер и Рехбергер при работе с шифром ChaCha, опираясь на исследования Salsa20, пришли к заключению, что с помощью их классических атак им удастся сломать ChaCha, в котором используется на один раунд меньше, чем при такой же атаке на Salsa20. Но в действительности, ChaCha обладает такой же устойчивостью к криптоанализу.

Код, представленный выше, демонстрирует не менее важное изменение: произошло изменение расстояния циклического сдвига от 7, 9, 13, 18 до 16, 12, 8 и 7 соответственно. Это не дает большого прироста в безопасности, но зато повышает производительность.

3. Матрица

3.1 Обзор матрицы Salsa20

Salsa20 оперирует с 16 словами: четырьмя входными словами, которые наиболее интересны атакующим (одноразовое число и блочный счетчик), 8 слов ключа и 4 константы, которые представлены в матрице размерностью 4 х 4:

Матрица Salsa20/r инверсивно преобразуется на протяжении r раундов. После этого результат складывается с исходной матрицей для получения 16-словного (64-байтного) выходного блока.

В некоторые программных реализациях Salsa20 предусмотрены собственные изменения матрицы, в результате которых матрица приобретает следующий вид:

Видно, что из-за преобразований в первом раунде Salsa20 «четверть-раунды» для каждого столбца распараллеливаются, изменяя сначала вторую строку, затем третью, четвертой и в итоге первую строку. Если строки матрицы собраны в векторы, тогда все эти 4 «четверть-раунда» могут выполняться с помощью SIMD-операций.

Второй раунд Salsa20 применяет «четверть-раундовые» операции для диагоналей, изменяя четвертую строку, затем третью, вторую и в итоге первую строку. Эти операции над входными словами в каждой строке преобразуют диагонали в столбцы, тем самым позволяя выполнять SIMD-операции без затрачивания больших ресурсов.

Третий раунд повторяет первый; четвертый раунд повторяет второй; и так далее.

3.2 Матрица ChaCha

В ChaChar, как и в Salsa20/r, строится матрица 4 х 4, претерпевающая инверсивные преобразования на протяжении r раундов, после чего результат складывается с исходной матрицей для получения 16-словного (64-байтного) блока на выходе.

Только здесь имеется три отличия. Во-первых, в ChaCha изменен порядок слов в блоке на выходе, чтобы выполнялись правила, описанные выше. Это никак не отражается на безопасности; это сделано для сохранения производительности на SIMD-платформах; на другие платформы это не влияет.

Во-вторых, в ChaCha исходная матрица строится таким образом, что все значимые для злоумышленника слова находятся внизу матрицы:

Слова ключа расположены на второй и третьей строчке; первое входное слово выделено под значение счетчика, за ним следует одноразовое число; константы такие как в Salsa20. В первом раунде ChaCha значение ключа складывается со значениями констант, затем происходит сложение по модулю 2 с входными словами, циклический сдвиг, сложение результата с ключом и так далее.

Расположение входных данных в Salsa20 было выбрано таким образом, чтобы лучше были заметны все изменения. Считалось, что мировым «широким» аналитикам потребовалось бы больше времени для работы с ChaCha, чем с Salsa20 из-за измененного порядка операций и измененного расположения слов в матрице. С другой стороны, расположение переменных в Salsa20 дает ненужную гибкость для злоумышленников, и нет никаких доказательств того, что это действительно улучшает безопасность. В этом плане более интересен анализ на уровне бит.

В-третьих, операции в ChaCha происходят в одинаковом порядке в каждом раунде. В первом раунде обрабатываются следующие «четверть-раунды»: (0, 4, 8, 12), (1, 5, 9, 13), (2, 6, 10, 14), (3, 7, 11, 15), (0, 5, 10, 15), (1, 6, 11, 12), (2, 7, 8, 13), (3, 4, 9, 14), в скобках указаны позиции слов в матрице. 4 «четверть-раундовых-слова» всегда расположены в порядке снизу-вверх. Такой порядок улучшает рассеивание.

ChaCha, модификация Salsa20