[Перевод] ChaCha, модификация Salsa2002.01.2024 23:30

Представленная статья является первым моим пробным переводом «научно-технической» статьи, а именно работы Даниэля Бернштейна «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-битный ключ в 264 потоков со случайным доступом, каждый из которых содержит 264 блока объемом 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

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

·    одинаковая скорость на 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.

     — сложение по модулю 232.

 — циклическое смещение на определенное количество бит.

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

© Habrahabr.ru