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

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

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

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

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