Spritz¶

Spritz — это алгоритм потокового шифрования, предложенный в 2014 году Роном Ривестом и Джейкобом Шульдтом. Он был разработан как альтернатива другим потоковым шифрам, в частности RC4, который к тому времени был признан уязвимым для ряда атак. Spritz основан на перестановке (перемешивании) элементов внутреннего состояния и предназначен для шифрования данных, а также для других криптографических задач, таких как хеширование, генерация псевдослучайных чисел и аутентификация.

¶История

Разработка Spritz была мотивирована накопившимися проблемами с шифром RC4, который на протяжении десятилетий был одним из самых распространённых потоковых шифров. К 2014 году было обнаружено множество криптографических атак на RC4, включая атаки, позволяющие восстанавливать открытый текст при многократном использовании одного и того же ключа (например, атаки на протокол WEP). Рон Ривест, один из создателей RC4, и Джейкоб Шульдт представили Spritz как «губку» (sponge-based) конструкцию, которая, по их замыслу, должна была исправить недостатки предшественника.

Алгоритм был впервые описан в работе «Spritz — a spongy RC4-like stream cipher and hash function», опубликованной 27 октября 2014 года. Авторы позиционировали Spritz как более безопасную и гибкую альтернативу, способную выполнять не только шифрование, но и другие криптографические функции. Однако, несмотря на первоначальный интерес, Spritz не получил широкого распространения в промышленных стандартах, таких как TLS или IPsec, из-за относительно низкой производительности и появления более эффективных алгоритмов (например, ChaCha20).

¶Устройство и принцип работы

Spritz относится к классу потоковых шифров на основе губчатой конструкции (sponge construction). В отличие от классических потоковых шифров, которые генерируют ключевой поток на основе ключа и вектора инициализации, Spritz использует внутреннее состояние, которое обновляется с помощью специальных функций.

¶Внутреннее состояние

Внутреннее состояние Spritz состоит из нескольких компонентов:

Массив S — массив из N элементов (обычно N = 256), каждый из которых содержит значение от 0 до N-1. Изначально массив заполняется последовательно от 0 до N-1 (тождественная перестановка).
Указатели i, j, k — целочисленные индексы, используемые для навигации по массиву S.
Счётчик z — количество выданных байтов ключевого потока.
Флаг w — шаг приращения для указателя i.

¶Основные операции

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

Absorb (Впитывание) — процесс ввода данных (ключа, вектора инициализации, сообщения) в губку. Данные разбиваются на байты, и каждый байт смешивается с внутренним состоянием.
Squeeze (Выжимание) — процесс извлечения псевдослучайных байтов из губки. Эти байты образуют ключевой поток, который используется для шифрования.
Shuffle (Перемешивание) — внутренняя функция, которая перемешивает массив S, изменяя указатели i, j, k. Эта функция выполняется после каждого впитывания или выжимания байта.
Output (Вывод) — функция, вычисляющая следующий байт ключевого потока на основе текущего состояния массива S.

¶Генерация ключевого потока

Процесс генерации ключевого потока в Spritz можно описать следующим образом:

Инициализация: Массив S заполняется тождественной перестановкой. Указатели i, j, k и счётчик z обнуляются. Шаг w устанавливается равным 1.
Absorb ключа: Ключ шифрования вводится в губку с помощью операции Absorb. Каждый байт ключа смешивается с состоянием, после чего выполняется операция Shuffle.
Absorb вектора инициализации (IV): Если используется IV, он также впитывается в губку после ключа.
Squeeze: Из губки извлекается необходимое количество байтов ключевого потока. Для каждого байта выполняется операция Shuffle, а затем вычисляется выходной байт.
Шифрование: Полученный ключевой поток складывается по модулю 2 (XOR) с открытым текстом, образуя шифротекст.

¶Криптографические свойства

Spritz был спроектирован с учётом недостатков RC4. Основные заявленные свойства включают:

Устойчивость к атакам на восстановление ключа: Алгоритм должен быть устойчив к атакам, направленным на восстановление ключа по известному шифротексту.
Устойчивость к атакам на дифференциал: Изменение одного бита в ключе или IV должно приводить к непредсказуемому изменению ключевого потока (лавинный эффект).
Длинный период: Период генерации псевдослучайной последовательности должен быть достаточно большим, чтобы избежать повторения ключевого потока.
Отсутствие слабых ключей: В отличие от RC4, для которого были известны слабые ключи (например, в протоколе WEP), Spritz не должен иметь таких ключей.

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

¶Применение

Spritz не получил широкого промышленного внедрения. Он рассматривался как потенциальная замена RC4 в некоторых протоколах, но на практике не используется в крупных коммерческих продуктах или стандартах. Основные причины:

Низкая производительность: Spritz значительно медленнее, чем современные потоковые шифры, такие как ChaCha20 или AES в режиме CTR. Это делает его непригодным для высоконагруженных систем.
Появление более эффективных альтернатив: К моменту публикации Spritz уже существовали и активно внедрялись более быстрые и безопасные алгоритмы (например, ChaCha20, который стал стандартом в TLS 1.3).
Криптоаналитические уязвимости: Выявленные недостатки в стойкости снизили доверие к алгоритму.

Тем не менее, Spritz представляет академический интерес как пример конструкции «губки» на основе перестановок и как попытка исправить ошибки RC4. Он может использоваться в образовательных целях для изучения принципов работы потоковых шифров.

¶Критика

Основная критика в адрес Spritz связана с его производительностью. По сравнению с RC4, который был очень быстрым в программной реализации, Spritz оказался значительно медленнее. Сравнение с ChaCha20, который также является потоковым шифром, показало, что Spritz уступает ему в скорости в несколько раз.

Кроме того, криптоаналитики отметили, что конструкция Spritz не является полностью оригинальной. Она во многом повторяет идеи, заложенные в более ранних алгоритмах на основе губок, таких как Keccak (стандарт SHA-3), но с менее проработанной математической основой. Это привело к тому, что Spritz не смог конкурировать с уже существующими и проверенными решениями.

¶Интересные факты

Название «Spritz» является отсылкой к RC4, который также известен как «Ron's Code 4» или «Rivest Cipher 4». Spritz можно интерпретировать как «RC4-like sponge».
Алгоритм был опубликован в день, когда исполнилось 27 лет со дня первой публикации RC4.
Несмотря на отсутствие практического применения, Spritz включён в некоторые криптографические библиотеки как экспериментальный алгоритм.

¶Источники

Rivest, R. L., & Schuldt, J. C. N. (2014). Spritz — a spongy RC4-like stream cipher and hash function.
Banik, S., & Isobe, T. (2016). Cryptanalysis of the Full Spritz Stream Cipher.
Bernstein, D. J. (2008). ChaCha, a variant of Salsa20.