Keccak

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

История создания

Предшественником Keccak является алгоритм RadioGatún, также использующий губчатую конструкцию. В 2006 году группа исследователей (Гвидо Бертони, Жоан Демен, Мика Питерс и Жиль Ван Аше) разработала первую версию Keccak для участия в конкурсе NIST по выбору нового стандарта хеширования. Конкурс был объявлен в 2007 году после обнаружения успешных атак на алгоритм SHA-1 и появления признаков ослабления SHA-2.

Keccak обошёл 63 других кандидата, включая пятерых финалистов (BLAKE, Grøstl, JH, Skein и SHAvite-3). В 2012 году NIST объявил Keccak победителем, а алгоритм был стандартизирован как SHA-3. Конкретная версия, утверждённая NIST, немного отличалась от оригинальной параметрами: была изменена ёмкость и количество раундов для повышения запаса прочности.

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

В отличие от классических хеш-функций, использующих конструкцию Меркла — Дамгора (SHA-1, SHA-2), Keccak реализует губчатую конструкцию. Этот подход состоит из двух чередующихся фаз: впитывание (absorbing) и выжимание (squeezing).

Губчатая конструкция

Исходное состояние алгоритма представляет собой битовую строку длиной b = r + c, где:

• r — скорость (rate), количество бит, обрабатываемое за один раунд в процессе впитывания;
• c — ёмкость (capacity), определяющая стойкость алгоритма;
• b — ширина губки, доступная для использования.

Начальное состояние заполняется нулями. Каждый бит сообщения разбивается на блоки размера r. На каждом раунде блок сообщения XOR-ится с состоянием, после чего применяется функция перестановки (Keccak-f). После обработки всех блоков в фазе выжимания из состояния выбираются биты размера r для формирования хеша. Если нужная длина хеша превышает r, процесс выжимания повторяется.

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

Основой Keccak является семейство перестановок Keccak-f с длиной состояния b = 25 × 2^l (l — число от 0 до 6). В SHA-3 используется b = 1600 бит (l = 6). Перестановка состоит из 12 + 2l раундов (24 раунда для SHA-3).

Каждый раунд включает пять шагов:

1. θ (тета) — XOR-взаимодействие столбцов для распространения битов;
2. ρ (ро) — вращение битов внутри каждой дорожки (lane) на заданное число позиций;
3. π (пи) — перестановка дорожек между столбцами;
4. χ (хи) — нелинейная операция, выполняемая по строкам (единственная нелинейная стадия);
5. ι (йота) — добавление константы раунда для синхронизации.

Параметры для SHA-3

Стандарт SHA-3 включает четыре варианта с разной длиной хеша:

Стойкость к коллизиям составляет половину длины выхода (n/2), к прообразу — n.

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

Keccak (SHA-3) спроектирован с избыточным запасом прочности. Создатели алгоритма установили количество раундов (24) в два раза больше, чем требовалось для эффективной диффузии. Ни на момент стандартизации, ни в последующие годы (до 2025 года) не было опубликовано ни одной теоретически или практически успешной атаки на полную версию Keccak, сопоставимой по сложности с полным перебором.

Известные атаки:

• Атаки на варианты с уменьшенным числом раундов (например, на 5-раундовый Keccak);
• Кубические атаки на отдельные стадии;
• Атаки на поглощение с использованием уязвимостей в реализации (при плохом управлении состоянием).

По состоянию на 2025 год наиболее успешные атаки на полный 6-раундовый Keccak (в версии c = 512) имеют сложность выше 2^200 операций, что делает их нефункциональными для полной версии.

Применение

Криптография и информационная безопасность

Keccak применяется в:

• Стандарте NIST FIPS PUB 202;
• Криптографических библиотеках (OpenSSL, Bouncy Castle, libsodium);
• Системах электронной подписи (в составе алгоритмов EdDSA);
• Протоколах аутентифицированного шифрования (например, Keyak, Lakey);
• Генерации псевдослучайных чисел (Keccak в режиме sponge PRNG).

Блокчейны и криптовалюты

Keccak (в варианте Keccak-256) используется в ряде блокчейн-систем:

• Ethereum — для вычисления адреса контрактов (не путать с SHA3-256: Ethereum использует оригинальную версию Keccak-256, не стандартизированную NIST);
• Bitcoin — для улучшенных реализаций (через OpenCL/GPU);
• Системы Proof-of-Work (Cuckoo Cycle, Ethereum before Proof-of-Stake).

Постквантовая криптография

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

• SPHINCS+ — хеш-основанная схема подписи (входит в финалисты проекта NIST по постквантовой криптографии);
• Falcon и Dilithium — в качестве компонента хеширования.

Сравнение с SHA-2

Критика и ограничения

Основные критические замечания в адрес SHA-3:

1. Производительность: В программных реализациях на типичных процессорах x86 SHA-3 в 2–4 раза медленнее SHA-256. Это связано с необходимостью поддержания большого состояния (1600 бит) и малым количеством аппаратной поддержки.
2. Стандартизация: NIST после победы Keccak изменил параметры (в частности, поднял c минимум до 512), что вызвало недовольство некоторых разработчиков из-за снижения скорости по сравнению с оригинальным вариантом.
3. Спор с Ethereum: Продолжительное время существует путаница между Keccak-256 и SHA3-256, поскольку Ethereum использует пре-стандартную версию Keccak, что приводило к ошибкам совместимости между системами.

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

• Название «Keccak» — это комбинация букв из алфавитного списка фамилий создателей: Bertoni (B), Daemen (D), Peeters (P), Van Assche (A). Первоначально планировалось назвать алгоритм «BDPA», но в итоге выбрали более благозвучный вариант.
• Keccak изначально был создан с запасом прочности в два раунда (24 раунда вместо 12). Даже 12-раундный вариант ни разу не был взломан за 10 лет.
• В аппаратных реализациях Keccak может достигать пропускной способности свыше 20 Гбит/с на ПЛИС.

Источники

• Bertoni G., Daemen J., Peeters M., Van Assche G. «The Keccak Reference» (2011).
• NIST. FIPS PUB 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions (2015).
• Aumasson J.-P. «Serious Cryptography: A Practical Introduction to Modern Encryption» (2017).
• Bernstein D. J., Lange T. «Post-Quantum Cryptography: State of the Art» (2017).
• Официальная страница Keccak (keccak.team).