Keccak-f

Keccak-f — это семейство криптографических перестановок, лежащих в основе хеш-функции Keccak, которая, в свою очередь, стала стандартом SHA-3, принятым Национальным институтом стандартов и технологий США (NIST). Keccak-f представляет собой итеративную подстановочно-перестановочную сеть (SP-сеть), работающую с трёхмерным битовым массивом состояния, и является ключевым вычислительным ядром всего семейства функций «губки» (sponge construction).

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

Семейство Keccak было разработано группой криптографов: Гвидо Бертони (Guido Bertoni), Жоаном Деменом (Joan Daemen), Микаэлем Питерсом (Michael Peeters) и Жилем ван Ашем (Gilles Van Assche). Разработка началась в 2007 году в рамках открытого конкурса NIST на новый стандарт криптографического хеширования (SHA-3). Целью конкурса было создание алгоритма, устойчивого к известным на тот момент атакам (включая коллизионные атаки на SHA-1 и SHA-2) и обладающего высокой производительностью как в программной, так и в аппаратной реализации.

Keccak был объявлен победителем конкурса в 2012 году и стандартизирован как SHA-3 в 2015 году (FIPS PUB 202). Основой алгоритма стала перестановка Keccak-f, которая может быть реализована с различными размерами состояния — от 25 до 1600 бит. Стандартная версия, используемая в SHA-3, — Keccak-f[1600], где число в квадратных скобках обозначает ширину (bitrate + capacity) состояния.

Общая структура

Keccak-f — это итеративная (циклическая) перестановка. Она состоит из последовательности раундов, каждый из которых включает пять шагов, обозначаемых греческими буквами: θ (тета), ρ (ро), π (пи), χ (хи), ι (йота). Число раундов зависит от размера состояния: для Keccak-f[1600] оно равно 24.

Состояние (state)

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

Раундовая функция

Каждый раунд Keccak-f выполняет последовательность из пяти шагов, которые обеспечивают диффузию, нелинейность и случайность перестановки.

Шаг θ (Theta)

Шаг θ обеспечивает диффузию (распространение) битов по всему состоянию. Он вычисляет паритет (чётность) каждого столбца (по оси z) и добавляет его к соседним столбцам. Формально:

1. Вычисляется бит паритета C[x] = XOR всех битов состояния вдоль оси y для каждого x.
2. Вычисляется D[x] = C[x-1] XOR ROT(C[x+1], 1), где ROT — циклический сдвиг на 1 бит.
3. Каждый бит состояния A[x][y][z] заменяется на A[x][y][z] XOR D[x].

Этот шаг гарантирует, что изменение одного бита в столбце влияет на множество других битов в последующих раундах.

Шаг ρ (Rho)

Шаг ρ выполняет циклический сдвиг каждого «слова» (lane) вдоль оси z на различное количество позиций. Для каждого (x, y) задано своё смещение, определённое в спецификации. Например, для (0,0) смещение равно 0, для (1,0) — 1, для (0,1) — 62 и так далее. Этот шаг нарушает локальность и способствует перемешиванию битов внутри каждого слова.

Шаг π (Pi)

Шаг π переупорядочивает (переставляет) слова внутри состояния. Он отображает координаты (x, y) в новые координаты (x', y') по формуле:

• x' = y
• y' = (2x + 3y) mod 5

Этот шаг обеспечивает глобальное перемешивание между различными строками и столбцами состояния.

Шаг χ (Chi)

Шаг χ — единственный нелинейный шаг в раунде. Он применяется к каждой строке (по оси x) независимо. Для каждого бита A[x][y][z] новое значение вычисляется как:

• A'[x][y][z] = A[x][y][z] XOR ((NOT A[x+1][y][z]) AND A[x+2][y][z])

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

Шаг ι (Iota)

Шаг ι добавляет раундовую константу (RC) к единственному слову состояния с координатами (0,0). Константа зависит от номера раунда и вычисляется с помощью линейного регистра сдвига с обратной связью (LFSR). Этот шаг предотвращает симметрии и гарантирует, что каждый раунд отличается от предыдущего.

Количество раундов

Число раундов n_r для Keccak-f задаётся как n_r = 12 + 2l, где l = log2(w). Для w = 64 (Keccak-f[1600]) n_r = 12 + 12 = 24 раунда. Для меньших состояний (например, w = 1, Keccak-f[25]) n_r = 12 раундов.

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

Keccak-f спроектирована так, чтобы быть вычислительно неотличимой от случайной перестановки для любого практического злоумышленника. Основные свойства:

• Обратимость: Каждый шаг обратим, поэтому вся перестановка является биекцией (взаимно однозначным отображением) на множестве состояний.
• Полная диффузия: После шести раундов каждый бит выхода зависит от каждого бита входа.
• Устойчивость к атакам: Конструкция устойчива к дифференциальному криптоанализу (максимальная вероятность дифференциала за 6 раундов не превышает 2^-160), к линейному криптоанализу, к атакам на основе коллизий и к квантовым атакам (для классических хеш-функций).
• Отсутствие слабых ключей: В отличие от блочных шифров, Keccak-f не использует ключ; все раундовые константы фиксированы.

Применение

Основное применение Keccak-f — реализация хеш-функций семейства SHA-3 (SHA3-224, SHA3-256, SHA3-384, SHA3-512) и расширяемых выходных функций (SHAKE128, SHAKE256). В этих конструкциях Keccak-f используется как внутренняя перестановка в режиме «губки» (sponge construction). Кроме того, Keccak-f применяется в:

• Аутентифицированном шифровании: Например, в алгоритме Ketje и Keyak.
• Генерации псевдослучайных чисел.
• Построении криптографических примитивов с доказанной стойкостью.

Варианты

Семейство Keccak-f включает несколько вариантов, различающихся размером слова w:

Стандарт SHA-3 использует только Keccak-f[1600].

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

Keccak-f не имеет серьёзных криптографических уязвимостей, известных на 2024 год. Однако некоторые исследователи отмечают, что её аппаратная реализация может быть менее эффективной по сравнению с некоторыми другими перестановками (например, Ascon или Gimli) для устройств с ограниченными ресурсами (IoT). Кроме того, в отличие от AES, Keccak-f не поддерживает аппаратное ускорение через инструкции (например, AES-NI), что может снижать производительность в программной реализации на процессорах общего назначения. Тем не менее, для большинства задач SHA-3 и Keccak-f остаются надёжным и безопасным выбором.

Источники

• FIPS PUB 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions (NIST, 2015).
• Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche. «The Keccak reference» (2008).
• Joan Daemen, Gilles Van Assche. «Keccak and the SHA-3 Standard» (2017).
• NIST IR 7896: Status Report on the Third Round of the SHA-3 Cryptographic Hash Algorithm Competition (2012).