FIPS PUB 202

FIPS PUB 202 — это стандарт Федерального правительства США (Federal Information Processing Standards Publication), официально утверждённый Национальным институтом стандартов и технологий (NIST) 5 августа 2015 года. Стандарт определяет алгоритм SHA-3 (Secure Hash Algorithm 3) — семейство криптографических хеш-функций, предназначенных для обеспечения целостности данных, аутентификации сообщений и создания цифровых подписей. FIPS PUB 202 был разработан как альтернатива и преемник более ранних стандартов SHA-1 и SHA-2, особенно в свете уязвимостей, обнаруженных в SHA-1, и потенциальных угроз квантовых вычислений для алгоритмов SHA-2.

История разработки

Предпосылки создания

Необходимость в новом стандарте хеширования возникла после того, как в 2004–2005 годах были опубликованы успешные атаки на алгоритмы SHA-0 и SHA-1 (коллизионные атаки, продемонстрировавшие нахождение двух различных сообщений с одинаковым хешем). Хотя SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512) оставался стойким, его архитектурное сходство с SHA-1 вызывало опасения, что со временем могут быть найдены аналогичные уязвимости. Кроме того, развитие квантовых вычислений поставило под угрозу многие классические криптографические схемы, основанные на математических задачах, таких как факторизация и дискретный логарифм. Хеш-функции, включая SHA-2, считались менее уязвимыми к квантовым атакам (квантовый алгоритм Гровера лишь квадратично ускоряет поиск коллизий), но требовалось создание более надёжного резервного варианта.

Конкурс SHA-3

В 2007 году NIST объявил открытый международный конкурс на создание нового криптографического хеш-алгоритма, который стал бы стандартом SHA-3. Конкурс проходил в несколько раундов:

• 2007–2008 — подача заявок: поступило 64 предложения от криптографов со всего мира.
• 2009 — первый раунд: отбор 51 кандидата.
• 2010 — второй раунд: сокращение до 14 финалистов.
• 2012 — третий раунд: выбор 5 финалистов (BLAKE, Grøstl, JH, Keccak, Skein).
• 2 октября 2012 года — NIST объявил победителем алгоритм Keccak, разработанный командой Гвидо Бертони, Жоана Даймена, Микаэля Петерса и Жиля Ван Ассхе. Основными критериями победы стали высокая производительность, простота реализации, устойчивость к известным атакам и гибкость (возможность настройки параметров безопасности).

Утверждение стандарта

После победы Keccak прошёл дополнительную доработку и стандартизацию. Окончательная версия алгоритма была опубликована в проекте FIPS PUB 202 в 2014 году, а 5 августа 2015 года стандарт был официально утверждён. В документе были определены четыре варианта хеш-функции: SHA3-224, SHA3-256, SHA3-384, SHA3-512, а также две функции расширения вывода (XOF): SHAKE128 и SHAKE256.

Алгоритм SHA-3

Основы конструкции

В отличие от SHA-1 и SHA-2, основанных на конструкции Меркла — Дамгора, SHA-3 использует принципиально иную архитектуру — губка (sponge construction). Губка состоит из двух фаз:

1. Впитывание (absorbing) — входные данные разбиваются на блоки фиксированного размера и последовательно «впитываются» в состояние алгоритма с помощью функции перестановки.
2. Выжимание (squeezing) — из состояния извлекаются выходные данные (хеш) заданной длины.

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

Варианты SHA-3

Стандарт FIPS PUB 202 определяет следующие алгоритмы:

Уровень безопасности означает, что для нахождения коллизии (двух сообщений с одинаковым хешем) требуется примерно 2^(n/2) операций, где n — длина выхода. Для SHA3-256 это 2^128 операций.

Функции расширения вывода (SHAKE)

SHAKE128 и SHAKE256 являются функциями расширения вывода (eXtendable Output Functions, XOF). В отличие от обычных хеш-функций, они позволяют получать выходные данные произвольной длины (от 1 бита до теоретически неограниченного размера). Это удобно для приложений, где требуется хеш нестандартной длины, например, для генерации ключей или маскирования данных. Уровень безопасности SHAKE128 — 128 бит, SHAKE256 — 256 бит.

Применение

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

SHA-3 используется в тех же областях, что и SHA-2, но с дополнительными преимуществами:

• Цифровые подписи — в стандартах ECDSA, EdDSA, RSA-PSS.
• Аутентификация сообщений — в сочетании с HMAC (Keyed-Hash Message Authentication Code).
• Генерация псевдослучайных чисел — например, в NIST SP 800-90A.
• Хранение паролей — в сочетании с солью и итерациями (PBKDF2, bcrypt, argon2).
• Блокчейн и криптовалюты — некоторые криптовалюты (например, Ethereum в перспективе) рассматривают SHA-3 как альтернативу SHA-256.

Стандартизация

SHA-3 включён в ряд международных и национальных стандартов:

• FIPS PUB 202 (США).
• ISO/IEC 10118-3 (международный стандарт на хеш-функции).
• ГОСТ Р 34.11-2021 (Россия) — хотя в России основным стандартом является «Стрибог», SHA-3 может использоваться в совместимых реализациях.
• PKCS#11 (Cryptographic Token Interface).

Реализации

Алгоритм SHA-3 реализован в большинстве современных криптографических библиотек:

• OpenSSL (с версии 1.1.1).
• Bouncy Castle (Java, C#).
• Botan (C++).
• libsodium (C).
• Python (модуль hashlib с версии 3.6).
• .NET (класс SHA3_256 в .NET 6+).

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

Производительность

На программном уровне SHA-3 в среднем медленнее SHA-2 на 20–40% при обработке больших объёмов данных. Однако на аппаратном уровне (FPGA, ASIC) SHA-3 может быть быстрее и компактнее благодаря простой структуре перестановок. Для коротких сообщений (менее 64 байт) SHA-3 часто показывает сопоставимую или даже лучшую скорость.

Безопасность

SHA-3 считается более устойчивым к атакам, использующим структурные особенности конструкции Меркла — Дамгора (например, атаки на основе удлинения сообщения). Функции SHAKE предоставляют дополнительную гибкость, отсутствующую в SHA-2. Стойкость SHA-3 к квантовым атакам оценивается как достаточная для постквантового периода: для нахождения коллизии требуется 2^(n/3) операций на квантовом компьютере (по алгоритму Гровера), что для n=256 даёт 2^85 операций — всё ещё практически недостижимо.

Критика

Основная критика SHA-3 связана с его относительно низкой производительностью по сравнению с SHA-2 на массовых процессорах (x86-64, ARM). Кроме того, некоторые эксперты отмечают, что SHA-3 не принёс принципиально новых возможностей, которые не могли бы быть реализованы с помощью SHA-2, а его внедрение потребовало значительных затрат на обновление оборудования и программного обеспечения. В России SHA-3 не получил широкого распространения из-за наличия собственного стандарта «Стрибог» (ГОСТ Р 34.11-2012).

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

• Алгоритм Keccak был разработан командой из Бельгии, что делает его первым европейским криптографическим стандартом, принятым NIST.
• В процессе конкурса SHA-3 алгоритм Keccak изначально не был фаворитом — многие эксперты отдавали предпочтение BLAKE или Skein.
• Функции SHAKE128 и SHAKE256 позволяют получать хеши произвольной длины, что делает их удобными для создания «хеш-деревьев» (Merkle trees) и генерации ключей.
• В 2019 году NIST опубликовал обновление FIPS PUB 202, добавившее уточнения по реализации SHAKE и исправления опечаток.

Источники

• FIPS PUB 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, NIST, August 2015.
• National Institute of Standards and Technology (NIST), «SHA-3 Competition: Finalists», 2012.
• Bertoni, G., Daemen, J., Peeters, M., Van Assche, G. «The Keccak Reference», 2011.
• ISO/IEC 10118-3:2018, «Information technology — Security techniques — Hash-functions — Part 3: Dedicated hash-functions».
• ГОСТ Р 34.11-2021, «Информационная технология. Криптографическая защита информации. Функция хэширования».