Криптографическая губка

Криптографическая губка (англ. sponge construction, Sponge function) — это класс алгоритмов хеширования и шифрования, построенный на основе итеративной перестановки с фиксированным размером состояния. Криптографическая губка представляет собой математическую конструкцию, которая принимает входные данные произвольной длины и выдает выходные данные произвольной длины, сочетая свойства хеш-функции, поточного шифра и генератора псевдослучайных чисел. Конструкция была предложена в 2007 году группой криптографов под руководством Гвидо Бертони (Guido Bertoni), Жоана Демена (Joan Daemen), Микаэля Петерса (Michaël Peeters) и Жиля ван Аше (Gilles Van Assche). Наибольшую известность конструкция получила благодаря победе алгоритма Keccak (SHA-3) в конкурсе Национального института стандартов и технологий США (NIST) на новый стандарт хеширования.

Принцип работы

Конструкция губки основана на трех основных компонентах: состоянии (state) фиксированного размера \( b \) (бит), функции перестановки \( f \), которая преобразует состояние, и режиме работы, разделяющем состояние на две части: внутреннюю (capacity, \( c \)) и внешнюю (bitrate, \( r \)). Размер состояния \( b = r + c \). Внешняя часть \( r \) используется для ввода данных и вывода результата, а внутренняя \( c \) определяет стойкость алгоритма к атакам.

Процесс работы губки делится на две фазы: впитывание (absorbing) и выжимание (squeezing).

Фаза впитывания (Absorbing)

1. Исходное состояние инициализируется нулями (или другим фиксированным значением).
2. Входное сообщение разбивается на блоки размером \( r \) бит. Если длина сообщения не кратна \( r \), выполняется дополнение (padding) — обычно с использованием битовой последовательности, гарантирующей однозначность разбиения (например, дополнение «10*1» в Keccak).
3. Каждый блок \( m_i \) (размером \( r \)) накладывается операцией XOR на внешнюю часть состояния.
4. После каждого наложения применяется перестановка \( f \) ко всему состоянию \( b \). Процесс повторяется для всех блоков сообщения.

Фаза выжимания (Squeezing)

1. После обработки всех входных блоков, внешняя часть \( r \) текущего состояния выдается как первый блок выходных данных.
2. Если требуемая длина выходного сообщения превышает \( r \), применяется перестановка \( f \) к состоянию, и следующая внешняя часть \( r \) добавляется к выходу.
3. Процесс повторяется до тех пор, пока не будет получена выходная последовательность нужной длины.

Математическое описание

Пусть \( M \) — входное сообщение, дополненное до длины, кратной \( r \). Обозначим \( P \) — последовательность блоков \( p_1, p_2, \dots, p_k \). Состояние \( S \) — это \( b \)-битный вектор. Фаза впитывания описывается рекуррентно:

\[ S_0 = 0^b \] \[ S_i = f(S_{i-1} \oplus (p_i \| 0^c)), \quad i = 1, \dots, k \]

где \( \oplus \) — побитовое XOR, а \( \| \) — конкатенация. После обработки всех блоков получается конечное состояние \( S_k \).

Фаза выжимания для получения \( Z \) бит выходных данных:

\[ Z = \text{Trunc}_r(S_k) \| \text{Trunc}_r(f(S_k)) \| \text{Trunc}_r(f(f(S_k))) \| \dots \]

где \( \text{Trunc}_r \) — взятие первых \( r \) бит состояния.

Свойства и стойкость

Стойкость криптографической губки определяется размером внутренней части \( c \). Основные параметры безопасности:

• Устойчивость к коллизиям: сложность нахождения двух различных сообщений с одинаковым хешем составляет примерно \( 2^{c/2} \) операций.
• Устойчивость к прообразу: сложность восстановления сообщения по хешу составляет примерно \( 2^{c} \) операций.
• Устойчивость ко второму прообразу: сложность нахождения второго сообщения с тем же хешем, что и заданное, составляет примерно \( 2^{c} \) операций.

Для достижения уровня безопасности \( n \) бит (например, 256 бит) обычно выбирают \( c = 2n \). Например, в SHA-3-256 параметры: \( b = 1600 \), \( c = 512 \), \( r = 1088 \).

Конструкция губки обладает свойством индифферентности (indifferentiability) от случайного оракула, что доказывает ее стойкость против широкого класса атак, включая атаки на основе коллизий, дифференциальные и линейные атаки.

Применение

Хеширование

Основное применение конструкции — криптографические хеш-функции. Наиболее известный представитель — SHA-3 (Keccak), стандартизированный NIST в 2015 году. SHA-3 поддерживает четыре варианта длины хеша: 224, 256, 384 и 512 бит. Также существуют варианты с уменьшенным состоянием, такие как Keccak-f[400], Keccak-f[800] и Keccak-f[1600].

Поточное шифрование

Губка может использоваться как поточный шифр. В этом случае ключ и инициализационный вектор (IV) подаются на вход в фазе впитывания, а выходная последовательность в фазе выжимания используется как гамма шифра. Примеры: Keyak, Ketje — алгоритмы, построенные на основе губки.

Аутентифицированное шифрование (AEAD)

Конструкция губки позволяет реализовать режим аутентифицированного шифрования с дополнительными данными (AEAD). Алгоритмы Ascon (победитель конкурса NIST по легковесной криптографии, 2023) и Gimli используют губку для одновременного шифрования и вычисления имитовставки (MAC).

Генерация псевдослучайных чисел

Губка может служить генератором псевдослучайных чисел (PRNG). Семя (seed) подается на вход, а выходная последовательность произвольной длины получается в фазе выжимания.

Построение MAC-кодов

Коды аутентичности сообщений (MAC) на основе губки строятся путем включения ключа во входные данные. Пример: KMAC (Keccak Message Authentication Code), стандартизированный NIST.

Преимущества и недостатки

Преимущества

• Универсальность: одна конструкция позволяет реализовать хеш-функцию, шифр, MAC и генератор случайных чисел.
• Простота анализа: стойкость сводится к стойкости внутренней перестановки \( f \).
• Гибкость: возможность варьировать размер состояния \( b \) и параметры \( r \) и \( c \) под конкретные требования безопасности и производительности.
• Устойчивость к атакам на удлинение сообщения: в отличие от конструкции Меркла-Дамгора, губка не подвержена атакам на удлинение длины хеша (length extension attack).

Недостатки

• Производительность: для хеширования больших объемов данных губка может быть медленнее, чем специализированные конструкции, такие как BLAKE2.
• Требования к памяти: размер состояния \( b \) может быть большим (например, 1600 бит в SHA-3), что не всегда удобно для встраиваемых систем с ограниченной памятью.

Примеры реализации

Keccak (SHA-3)

Keccak использует перестановку Keccak-f[1600] с 24 раундами. Параметры для различных вариантов:

Ascon

Ascon — легковесный алгоритм, победитель конкурса NIST по легковесной криптографии (2023). Использует состояние \( b = 320 \) бит (\( r = 64 \), \( c = 256 \)). Предназначен для микроконтроллеров, RFID-меток и IoT-устройств.

Gimli

Gimli — алгоритм с состоянием \( b = 384 \) бит (12 слов по 32 бита). Использует 24 раунда перестановки. Применяется в проектах, требующих высокой производительности на программных и аппаратных платформах.

Критика и альтернативы

Конструкция губки подвергалась критике за относительно низкую скорость работы на больших данных по сравнению с оптимизированными реализациями SHA-2 и BLAKE2. Однако для легковесных и встраиваемых систем она остается одной из наиболее сбалансированных. Альтернативными подходами являются:

• Конструкция Меркла-Дамгора (SHA-2, MD5) — классическая, но уязвимая к атакам на удлинение.
• Конструкция HAIFA (BLAKE) — улучшенная версия Меркла-Дамгора с добавлением соли и счетчика блоков.
• Конструкция на основе сжатия с перестановкой (Skein, Threefish) — использует большие состояния и операции над 64-битными словами.

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

• Название «губка» (sponge) отражает аналогию с физической губкой: она впитывает воду (входные данные) и затем выжимает ее (выходные данные).
• Внутренняя перестановка Keccak-f[1600] основана на пяти операциях: θ (тета), ρ (ро), π (пи), χ (хи) и ι (йота), каждая из которых выполняется над 64-битными словами.
• SHA-3 был выбран NIST в 2012 году после пятилетнего конкурса, в котором участвовали 64 алгоритма. Keccak победил благодаря высокой безопасности и гибкости.
• Конструкция губки запатентована авторами, но патент был передан в общественное достояние, что позволяет свободно использовать алгоритм без лицензионных отчислений.

Источники

• Bertoni, G., Daemen, J., Peeters, M., & Van Assche, G. (2007). Sponge functions. ECRYPT Hash Workshop.
• Bertoni, G., Daemen, J., Peeters, M., & Van Assche, G. (2011). The Keccak reference.
• NIST FIPS 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions (2015).
• Daemen, J., & Rijmen, V. (2002). The Design of Rijndael: AES — The Advanced Encryption Standard.
• Dobraunig, C., Eichlseder, M., Mendel, F., & Schläffer, M. (2016). Ascon v1.2. Submission to NIST Lightweight Cryptography Competition.