06.11 // NIST сообщает новые подробности о конкурсе на стандарт хэш-функции SHA-3

Объявлена последняя дата приёма кандидатов – 31 октября 2008 года.
В первом раунде конкурса будут выставлены на обсуждение все допущенные кандидаты, из них отобраны примерно 5 финалистов, затем состоится второй раунд и финал.
Длительность каждого раунда по оптимистическим оценкам будет не более 12-15 месяцев.

Напомним, что после нахождения коллизий в хэш-фукнциях MD4, MD5, SHA0 и публикации теоретической работы, доказывающей возможность взлома SHA-1, Национальный Институт Стандартов и Технологий США занимается разработкой нового стандарта хэширования.

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

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

Алгоритмы функций вычисления для разного размера блоков должны быть идентичны и иметь минимум отличий в реализации. Использования абсолютно разных наборов алгоритмов для получения четырёх фиксированных значений длины выхода не допускается.

Однако выдвигаются и пожелания по усовершенствованию существующих алгоритмов работы хэш-функций: возможно включение опции рандомизированного хэширования, улучшенное распараллеливание, оптимальная работа на множестве современных платформ (включая как 64-битные процессоры так и 8-битные процессоры и смарт-карты).
Возможен отход от потенциально нестойкого метода Дамгарда-Меркла, на котором построено большинство существующих хэш-функций.

Желательно сохранить или увеличить эффективность по сравнению с SHA-2 и создать класс хэш-функций, на которые потенциально не будут действовать атаки, нацеленные на SHA-2.

Допускается параметризация (изменение параметров): например, числа раундов с учётом допустимых пределов "эффективности в обмен на безопасность". Хотя в стандарт такая возможность скорее всего включена не будет, но будет полезна для исследования стойкости ослабленных версий.

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

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

Специфические требования к стойкости (значения указаны на уровне теоретических пределов, в реальности они могут быть немного меньше) на размер выходного блока в n бит такие:

• В конструкциях кодов аутентификации сообщений (HMAC) и псевдослучайных функций (PRF) стойкость по числу запросов должна быть не менее 2^(n/2) бит против атак-различителей.
• Стойкость рандомизированного хэширования против атаки нахождения H(M₁, r₁) = H(M₂, r₂) — не менее n бит, при условии, что значение рандомизатора r₁ не контролируется атакующим.

Стандартные и дополнительные параметры стойкости:

• Стойкость к нахождению коллизий — не менее n/2 бит.
• Стойкость к нахождению прообраза — n бит.
• Стойкость к нахождению второго прообраза — n-k битов для любого сообщения, короче 2^k битов.
• Устойчивость к атакам на изменение длины сообщения.
• Подмножество хэш функций (например полученное усечением числа битов выхода) размером m битов должно сохранять свойства n-битного множества в пересчёте на m, с учётом статистических (неотличимых от случайных) отклонений. Не должно существовать атаки на быстрое нахождение малостойких подмножеств хэш-функции из исходного множества n.
• Устойчивость к новым типам атак, например, на основе мультиколлизий.

Также должны быть приведены доказательства стойкости против основных методов взлома криптографических примитивов (начиная с дифференциального криптоанализа).

В случае возникновения затруднений с отбором кандидатов, NIST оставляет за собой право пересмотреть сроки этапов конкурса.

Источник: NIST hash competition