Конкурс SHA-3

Конкурс SHA-3 — это открытый международный конкурс, организованный и проведённый Национальным институтом стандартов и технологий США (NIST) с 2007 по 2012 год, целью которого являлась разработка и стандартизация нового алгоритма криптографического хеширования для замены семейства SHA-2. По итогам конкурса победителем был признан алгоритм Keccak, который в 2015 году был опубликован как федеральный стандарт США SHA-3.

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

К середине 2000-х годов алгоритмы семейства SHA-1 и SHA-2, разработанные Агентством национальной безопасности США (АНБ), оставались основными стандартами криптографического хеширования. Однако в 2004—2005 годах группа китайских криптоаналитиков под руководством Сяоюня Ван продемонстрировала успешные атаки на ряд хеш-функций, включая MD5, SHA-0 и SHA-1. Хотя SHA-2 оставался устойчивым к известным атакам, его архитектурное сходство с SHA-1 вызывало опасения, что со временем могут быть найдены уязвимости. NIST, стремясь обеспечить долгосрочную криптографическую устойчивость, принял решение о проведении открытого конкурса на создание нового стандарта.

Организация и этапы конкурса

Анонс и требования

В ноябре 2007 года NIST опубликовал официальное объявление о начале конкурса. К участникам предъявлялись следующие ключевые требования:

• Алгоритм должен поддерживать четыре стандартных размера дайджеста: 224, 256, 384 и 512 бит.
• Должна быть обеспечена производительность, сопоставимая с SHA-2, как в программной, так и в аппаратной реализации.
• Алгоритм должен быть свободным от патентных ограничений и доступным для неограниченного использования.
• Кандидаты должны были предоставить полную спецификацию, реализацию на языке C и результаты тестирования.

Первый раунд

На конкурс было подано 64 заявки из различных стран мира, включая США, Россию, Китай, Японию, страны Европы. После первичного отбора по формальным критериям (полнота документации, отсутствие очевидных дефектов) к участию в первом раунде было допущено 51 алгоритм. В октябре 2008 года на конференции в Санта-Барбаре (Калифорния) NIST объявил о переходе во второй раунд 14 кандидатов.

Второй раунд

Второй раунд продлился с 2009 по 2010 год. В этот период участники дорабатывали свои алгоритмы, а криптографическое сообщество проводило углублённый анализ безопасности и производительности. В июле 2009 года NIST сократил список до 5 финалистов:

• BLAKE (авторы: Жан-Филипп Омассон, Лука Энрико, Сэмюэль Неве, Кристиан Рехбергер, Франк-Рене Шефер, Тьерри Тро)
• Grostl (авторы: Прадип Кумар, Пол Ван Ромсей, Аксель Пошманн, Кристиан Рехбергер, Винсент Раймен)
• JH (автор: Хунцзюнь Ву)
• Keccak (авторы: Гвидо Бертони, Жоан Демен, Микаэль Питерс, Жиль Ван Аш)
• Skein (авторы: Ник Фергюсон, Стефан Люкс, Брюс Шнайер, Дуг Уайтинг, Михаэль Вильямс, Хелена Хэндшу, Джесси Уокер)

Финал и отбор победителя

В течение 2010—2012 годов NIST провёл серию закрытых семинаров и открытых обсуждений, анализируя все аспекты финалистов. Ключевыми критериями отбора стали:

• Криптографическая стойкость: устойчивость к коллизиям, прообразам и вторым прообразам.
• Производительность: скорость работы на различных платформах (от смарт-карт до серверов).
• Гибкость и простота реализации: возможность эффективной аппаратной реализации.
• Запас прочности: наличие встроенных механизмов защиты от будущих атак.

2 октября 2012 года NIST объявил победителем конкурса алгоритм Keccak, разработанный командой исследователей из STMicroelectronics и Университета Радбауда (Нидерланды). Keccak был выбран за его новаторскую конструкцию, не основанную на структуре Меркла-Дамгора, а также за превосходную производительность в аппаратной реализации и высокий запас криптографической прочности.

Победитель: алгоритм Keccak

Keccak (произносится как «кетчак») — это семейство криптографических функций, основанных на конструкции «губка» (sponge construction). В отличие от традиционных хеш-функций, использующих итеративную структуру Меркла-Дамгора, Keccak использует губку, которая может как впитывать (absorb) входные данные, так и выжимать (squeeze) выходной хеш произвольной длины. Это делает алгоритм более гибким и устойчивым к некоторым классам атак.

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

• Использует перестановки с фиксированным числом раундов (12 или 24 в зависимости от размера состояния).
• Состояние алгоритма представляет собой трёхмерный массив битов размером 5×5×64 (1600 бит).
• Для стандартных размеров дайджеста (SHA-3-224, SHA-3-256, SHA-3-384, SHA-3-512) используются различные параметры, но все они основаны на одной и той же перестановке.

Стандартизация и публикация

5 августа 2015 года NIST опубликовал стандарт FIPS PUB 202 «SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions», который официально утвердил Keccak как SHA-3. Стандарт включает четыре основные хеш-функции (SHA-3-224, SHA-3-256, SHA-3-384, SHA-3-512) и две функции с расширяемым выходом (SHAKE128 и SHAKE256), которые позволяют генерировать хеш произвольной длины.

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

Несмотря на успех конкурса, некоторые криптографы выражали недовольство результатом. Основные претензии касались:

• Производительности: Keccak показал более низкую скорость в программной реализации на некоторых процессорах по сравнению с SHA-2.
• Сложности анализа: конструкция губки была менее изучена на момент выбора, чем классические схемы.
• Альтернативные кандидаты: многие специалисты отдавали предпочтение алгоритму BLAKE или Skein, которые демонстрировали лучшую программную производительность и имели более простую математическую основу.

Тем не менее, NIST обосновал свой выбор высокой аппаратной эффективностью Keccak, его гибкостью и устойчивостью к будущим атакам, включая возможные квантовые угрозы.

Влияние на криптографию

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

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

Источники

• National Institute of Standards and Technology. «Announcing Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA-3) Family». Federal Register, 2007.
• National Institute of Standards and Technology. «SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions». FIPS PUB 202, 2015.
• Bertoni G., Daemen J., Peeters M., Van Assche G. «The Keccak Reference». 2011.
• Preneel B. «The NIST SHA-3 Competition: A Perspective». Proceedings of the 9th International Conference on Cryptology in India (INDOCRYPT), 2008.
• Aumasson J.-P., et al. «BLAKE: A Secure Hash Function Family». Submission to NIST SHA-3 Competition, 2008.
• Ferguson N., et al. «The Skein Hash Function Family». Submission to NIST SHA-3 Competition, 2008.