Функция перестановки Keccak-f

Keccak-f — это семейство обратимых перестановок, лежащих в основе криптографических хеш-функций семейства SHA-3 (Secure Hash Algorithm 3), а также алгоритмов расширения ключа и аутентификации (например, SHAKE, cSHAKE, KMAC). Keccak-f является центральным компонентом конструкции «губка» (sponge construction), обеспечивая перемешивание и рассеивание входных данных. Перестановка определяется для семи возможных размеров состояния: 25, 50, 100, 200, 400, 800 и 1600 бит, что соответствует числу раундов от 12 до 24.

История и происхождение

Keccak был разработан группой криптографов: Гвидо Бертони, Жоаном Дайменом, Микаэлем Петерсом и Жилем ван Ассхе. Алгоритм был представлен в 2008 году на конкурсе SHA-3, организованном Национальным институтом стандартов и технологий США (NIST). В 2012 году Keccak был объявлен победителем конкурса, а в 2015 году стандартизирован как SHA-3 (FIPS PUB 202). Название «Keccak» происходит от словосочетания «KECCAK» (Keyed Cryptographic Cipher and Accumulator Kernel), что отражает его универсальность. Перестановка Keccak-f является ключевым элементом, обеспечивающим криптографическую стойкость.

Структура и принцип работы

Состояние и представление

Состояние Keccak-f представляет собой трёхмерный массив битов размером \(5 \times 5 \times w\), где \(w\) — ширина «слоя» (lane), равная \(2^l\) бит, а \(l\) — целое число от 0 до 6. Для самого распространённого варианта Keccak-f[1600] \(w = 64\) бита, а общее состояние — 1600 бит. Состояние можно представить как трёхмерную решётку, где координаты \((x, y, z)\) задают положение бита, причём \(x\) и \(y\) изменяются от 0 до 4, а \(z\) — от 0 до \(w-1\).

Раунды и этапы

Каждая перестановка Keccak-f состоит из \(n_r\) раундов, где \(n_r = 12 + 2l\). Для Keccak-f[1600] \(l = 6\), следовательно, \(n_r = 24\). Каждый раунд включает пять последовательных этапов, обозначаемых греческими буквами:

1. θ (Theta) — этап линейного смешивания столбцов. Каждый бит состояния заменяется на XOR суммы битов в том же столбце и соседних столбцах. Формально: \(C[x] = A[x,0] \oplus A[x,1] \oplus A[x,2] \oplus A[x,3] \oplus A[x,4]\) для всех \(x\), затем \(D[x] = C[x-1] \oplus \text{rot}(C[x+1], 1)\), и \(A[x,y] = A[x,y] \oplus D[x]\). Этот этап обеспечивает диффузию — распространение влияния каждого бита на многие другие.

1. ρ (Rho) — циклический сдвиг битов внутри каждого «слоя» (lane). Каждый слой с координатами \((x, y)\) сдвигается на определённое количество позиций, заданное таблицей смещений. Например, для слоя (1,0) сдвиг составляет 1 бит, для (0,2) — 62 бита. Сдвиги различны для всех слоёв, что предотвращает коллизии.

1. π (Pi) — перестановка позиций слоёв. Слой \((x, y)\) перемещается на новую позицию \((x', y')\), где \(x' = y\) и \(y' = (2x + 3y) \mod 5\). Этот этап разрушает столбцовую структуру, улучшая перемешивание.

1. χ (Chi) — нелинейный этап, единственный, вносящий нелинейность в перестановку. Каждый бит заменяется по правилу: \(A[x,y] = A[x,y] \oplus ((\neg A[x+1,y]) \land A[x+2,y])\). Это эквивалентно применению 5-битной S-блоковой функции к каждой строке состояния. Этап обеспечивает стойкость к дифференциальному и линейному криптоанализу.

1. ι (Iota) — добавление раундовой константы. Раундовый ключ (константа) XORится с единственным слотом (0,0). Константы различны для каждого раунда и вычисляются на основе линейного регистра сдвига с обратной связью (LFSR). Этап предотвращает симметрии, которые могли бы возникнуть при одинаковых раундах.

Обратимость

Все этапы перестановки обратимы. Этап θ обратим благодаря линейности, ρ и π — простые перестановки, χ обратим, так как является биективной функцией на 5-битных строках, ι — XOR с константой. Таким образом, Keccak-f является биективной функцией, что необходимо для конструкции «губка», где требуется как прямое, так и обратное преобразование (например, при сжатии и расширении).

Классификация и варианты

Keccak-f существует в семи вариантах, отличающихся размером состояния:

Наиболее распространённый вариант — Keccak-f[1600], используемый в SHA-3 и SHAKE. Меньшие варианты применяются в устройствах с ограниченными ресурсами, например, в смарт-картах или RFID-метках.

Применение

Криптографические хеш-функции SHA-3

Keccak-f является основой для четырёх стандартизированных хеш-функций: SHA3-224, SHA3-256, SHA3-384, SHA3-512. В них размер состояния — 1600 бит, а скорость (rate) — количество битов, обрабатываемых за один цикл «губки» — зависит от требуемой длины хеша. Например, для SHA3-256 скорость составляет 1088 бит, а ёмкость (capacity) — 512 бит. Перестановка применяется многократно: сначала для впитывания (absorbing) входных данных, затем для выжимания (squeezing) хеша.

Функции расширения ключа и аутентификации

Keccak-f используется в алгоритмах SHAKE128 и SHAKE256 — расширяемых выходных функциях (XOF), которые позволяют получать хеш произвольной длины. Также на основе Keccak-f построены cSHAKE (customizable SHAKE), KMAC (Keccak Message Authentication Code) и TupleHash. Эти алгоритмы стандартизированы в NIST SP 800-185.

Другие области

Keccak-f применяется в криптовалютах (например, в алгоритме Proof-of-Work для Monero), в системах шифрования (например, в режиме Duplex), а также в генераторах псевдослучайных чисел. Благодаря высокой производительности на программном и аппаратном уровне, Keccak-f используется в протоколах TLS 1.3, в операционных системах (Linux, OpenBSD) и в библиотеках OpenSSL.

Криптостойкость

Keccak-f считается криптостойкой перестановкой. На 2025 год не опубликовано атак, которые бы значительно снижали её стойкость. Наиболее известные атаки — дифференциальный и линейный криптоанализ — неэффективны из-за нелинейного этапа χ и большого числа раундов (24 для 1600-битного варианта). Атаки на сокращённые версии (например, на 4-5 раундов) демонстрируют возможность восстановления состояния, но для полного числа раундов сложность превышает \(2^{1600}\) операций.

Исследования показывают, что Keccak-f обладает высокой степенью диффузии: после 1-2 раундов каждый бит состояния зависит от всех входных битов. Это свойство делает перестановку устойчивой к атакам на основе коллизий и прообразов.

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

• Keccak-f не является блочным шифром, хотя его структура напоминает SP-сеть. Отсутствие ключа делает его чистой перестановкой, что позволяет использовать его в конструкции «губка» без необходимости в секретном ключе.
• Название «Keccak» происходит от слов «KECCAK» (Keyed Cryptographic Cipher and Accumulator Kernel), хотя сам алгоритм не является шифром.
• В 2017 году была обнаружена уязвимость в реализации Keccak-f в некоторых аппаратных модулях безопасности (HSM), связанная с побочными каналами (side-channel), но она не затрагивала математическую стойкость перестановки.
• Keccak-f является одним из немногих криптографических примитивов, которые были выбраны NIST после открытого конкурса, что гарантирует его высокий уровень доверия.

Источники

• FIPS PUB 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. National Institute of Standards and Technology, 2015.
• Bertoni G., Daemen J., Peeters M., Van Assche G. The Keccak Reference, Version 3.0, 2011.
• NIST SP 800-185: SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash, and ParallelHash, 2016.
• Daemen J., Rijmen V. The Design of Rijndael: AES — The Advanced Encryption Standard. Springer, 2002 (глава о конструкции SP-сетей).
• Preneel B. Analysis and Design of Cryptographic Hash Functions. COSIC, 2003.