Keccak

Keccak — это семейство криптографических хеш-функций, которые могут генерировать хеш фиксированной длины (например, 224, 256, 384 или 512 бит) из входных данных произвольной длины. Хеш-функции используются для создания уникального "отпечатка" данных, который применяется в криптографии для обеспечения целостности, аутентификации и защиты данных. Keccak также поддерживает другие режимы работы, такие как генерация случайных чисел, создание кодов аутентификации сообщений (MAC) и шифрование.

Keccak был выбран для SHA-3, но стандарт SHA-3 немного отличается от оригинального Keccak из-за изменений, внесённых NIST (например, в способе обработки входных данных). Однако основа алгоритма осталась той же.

Основные характеристики Keccak

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

Как работает Keccak?

Keccak основан на губчатой конструкции, которая состоит из двух основных фаз: поглощение (absorbing) и выжимание (squeezing). Вот пошаговое объяснение:

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

Губчатая конструкция делит внутреннее состояние алгоритма на две части:

• r (bitrate): Часть состояния, которая взаимодействует с входными данными.
• c (capacity): Часть состояния, которая обеспечивает криптографическую стойкость и не взаимодействует напрямую с входными данными.

Общий размер состояния — это сумма $r + c$, которая обычно составляет 1600 бит (25 слов по 64 бита).

Этапы работы

1. Инициализация:
   • Внутреннее состояние (массив из 1600 бит) инициализируется нулями.
   • Входные данные разбиваются на блоки размером $r$ бит.
2. Фаза поглощения (Absorbing):
   • Входные данные разделяются на блоки фиксированной длины (равной $r$).
   • Каждый блок XOR’ится с частью состояния, после чего применяется функция перестановки (Keccak-f).
   • Этот процесс повторяется, пока все входные данные не будут обработаны.
3. Фаза выжимания (Squeezing):
   • После обработки всех входных данных алгоритм начинает выдавать выходные данные.
   • Выходные биты извлекаются из части состояния размером $r$.
   • Если требуется больше выходных данных, чем $r$, применяется дополнительная перестановка Keccak-f, чтобы "выжать" следующие биты.

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

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

• θ (тета): Линейное преобразование, которое добавляет диффузию между битами.
• ρ (ро): Циклический сдвиг битов для повышения диффузии.
• π (пи): Перестановка битов для изменения их позиций.
• χ (хи): Нелинейное преобразование, которое добавляет криптографическую стойкость.
• ι (йота): Добавление константы для предотвращения симметрии.

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

Параметры Keccak

Keccak поддерживает различные конфигурации, определяемые параметрами $r$ (bitrate) и $c$ (capacity). Например:

• Для SHA-3-256: $r=1088$, $c = 512$, выход 256 бит.
• Для SHA-3-512: $r = 576$, $c = 1024$, выход 512 бит.

Чем больше $c$, тем выше криптографическая стойкость, но тем меньше пропускная способность (так как $r$ уменьшается).

Применение Keccak

Keccak используется в различных областях криптографии:

• Хеширование данных: Создание контрольных сумм для проверки целостности данных (например, в блокчейнах).
• Цифровые подписи: Обеспечение аутентичности и целостности сообщений.
• Генерация случайных чисел: Используется в криптографически безопасных генераторах псевдослучайных чисел.
• Коды аутентификации сообщений (MAC): Например, в алгоритмах типа KMAC (Keccak Message Authentication Code).
• Блокчейн: Keccak используется в Ethereum как хеш-функция (называемая Keccak-256).
• Шифрование и другие приложения: Благодаря губчатой конструкции, Keccak может использоваться в потоковых шифрах и других криптографических примитивах.

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

• Устойчивость к атакам: Keccak разработан с учётом современных криптографических атак, таких как дифференциальный и линейный криптоанализ.
• Гибкость: Поддерживает выходные данные произвольной длины, что делает его универсальным для различных приложений.
• Простота реализации: Алгоритм относительно прост для реализации на аппаратном и программном уровне.
• Высокая производительность: Оптимизирован для параллельных вычислений и работы на современных процессорах.

Отличия Keccak от SHA-3

Хотя Keccak стал основой для SHA-3, NIST внёс несколько изменений в алгоритм:

• Дополнение входных данных (padding): SHA-3 использует другой метод дополнения (padding), чтобы улучшить совместимость и безопасность.
• Ограничение функциональности: SHA-3 ограничен хеш-функциями фиксированной длины, тогда как Keccak поддерживает более широкий спектр применений (например, XOF — eXtendable Output Functions, такие как SHAKE128 и SHAKE256).
• Параметры: Некоторые параметры были уточнены для соответствия стандартам NIST.

Keccak в сравнении с SHA-1 и SHA-2

• Конструкция: SHA-1 и SHA-2 используют конструкцию Меркла-Дамгора, тогда как Keccak использует губчатую конструкцию, что делает его более устойчивым к определённым атакам (например, атакам на основе длины сообщения).
• Безопасность: SHA-1 считается устаревшим из-за уязвимостей к атакам на коллизии. SHA-2 всё ещё считается безопасным, но Keccak (SHA-3) предлагает дополнительный уровень защиты и гибкости.
• Производительность: Keccak может быть медленнее на некоторых платформах по сравнению с SHA-2, но его оптимизация для аппаратных реализаций делает его конкурентоспособным.

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

• Конкурс NIST: Keccak победил в конкурсе SHA-3, обойдя 63 других кандидата, благодаря своей безопасности и универсальности.
• Ethereum: Keccak-256 широко используется в блокчейне Ethereum для хеширования транзакций, адресов и других данных.
• SHAKE: Keccak включает функции с расширяемым выходом (SHAKE128 и SHAKE256), которые позволяют генерировать хеш произвольной длины, что делает их уникальными по сравнению с традиционными хеш-функциями.

Заключение

Keccak — это мощная и универсальная криптографическая хеш-функция, которая лежит в основе стандарта SHA-3 и используется во многих современных криптографических системах. Её губчатая конструкция обеспечивает гибкость, высокую криптографическую стойкость и эффективность. Keccak подходит как для традиционных задач хеширования, так и для более сложных криптографических приложений, таких как блокчейны, цифровые подписи и генерация случайных чисел.