Конкурс на алгоритм хеширования SHA-3

Размещено на http://www.Allbest.ru/

Харьковский национальный экономический университет

Конкурс на алгоритм хеширования SHA-3

Евсеев С.П., к.т.н., доцент

Король О.Г., преподаватель

Куницина Е.А., студентка

Постановка проблемы в общем виде и анализ литературы

Рост вычислительных возможностей и использование электронных документов в банковских системах выдвигает новые требования по надежности и оперативности передаваемой и обрабатываемой информации. Отличием обрабатываемых данных в внутриплатежных банковских системах от компьютерных систем является обязательное использование в транзакциях электронной цифровой подписи (ЦП) - блока данных небольшого размера, полученного в результате криптографического преобразования сообщения произвольной длины с использованием личного секретного ключа отправителя [1]. ЦП обеспечивающая аутентичность сообщения и неоспоримость использования данного секретного ключа состоит из 2-х процедур: генерации ключей и формирования хеш-кода, при этом львиную долю при оценке производительности составляет алгоритм формирования хеш-кода. Исследования [1, 2] используемых в современных системах защиты стандартов ЦП показали, что большинство наиболее распространённых алгоритмов формирования хеш-кодов устарели и не обеспечивают требуемой криптостойкости и производительности, в то время как новые алгоритмы требуют тщательного исследования и стандартизации [1, 2].

Целью статьи является анализ основных требований к проектированию алгоритмов-конкурсантов по формированию хеш-кода, отобранных во второй тур конкурса на американский стандарт SHA-3.

Анализ требований конкурса SHA-3. Основные требования, выдвигаемые Национальным институтом стандартов и технологий США (NIST) к алгоритмам-конкурсантам предполагают создание класса хэш-функций потенциально стойких к атакам, нацеленным на SHA-2, а также сохранение или увеличение эффективности хеширования по сравнению с SHA-2 [3].

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

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

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

Руководители конкурса допускают использование параметризации в алгоритмах-конкурсантах - изменение параметров числа раундов с учётом допустимых пределов “эффективности в обмен на безопасность”. Хотя в стандарт такая возможность не будет включена.

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

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

в конструкциях кодов аутентификации сообщений (HMAC) и псевдослучайных функций (PRF) стойкость по числу запросов должна быть не менее 2 (n/2) бит против атак-различителей;

стойкость рандомизированного хеширования против атаки нахождения H(M₁, r₁) = H(M₂, r₂) - не менее n бит, при условии, что значение рандомизатора r₁ не контролируется атакующим.

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

- стойкость к нахождению коллизий - не менее n/2 бит;

- стойкость к нахождению прообраза - n бит;

- стойкость к нахождению второго прообраза - n - k битов для любого сообщения, короче 2k битов;

- устойчивость к атакам на изменение длины сообщения;

- подмножество хеш-функций (например, полученное усечением числа битов выхода) размером m битов должно сохранять свойства n-битного множества в пересчёте на m, с учётом статистических (неотличимых от случайных) отклонений. Не должно существовать атаки на быстрое нахождение малостойких подмножеств хеш-функции из исходного множества n;

- устойчивость к новым типам атак, например, на основе мультиколлизий.

Анализ алгоритмов, принимавших участие в 1 раунде конкурса. Национальным институтом стандартов и технологий США 31 октября 2008 года был проведен первый раунд конкурса SHA-3, в таблице 1 приведены основные характеристики алгоритмов хеширования, представленные на конкурс.

Таблица 1

Характеристики алгоритмов хеширования кандидатов 1 раунда конкурса

Анализ таблицы 1 показывает, что основное внимание разработчиков алгоритмов-конкурсантов было направлено на выполнение основных требований по производительности и возможности оптимальной работы алгоритма при его реализации на множестве современных платформ. Вместе с тем, руководители конкурса при отборе алгоритмов-кандидатов во второй тур обратили внимание на стойкость данных алгоритмов к различным видам атак. алгоритм хеширование защита криптографический атака

Анализ кандидатов, прошедших во 2 раунд. Во 2 раунд были отобраны алгоритмы хеширования, в которых не была затронута каким-либо образом безопасность. В некоторых случаях, представленный вариант был слишком медленным или требовал слишком много памяти, но NIST считает, что в некоторых случаях, настраиваемые параметры могут быть откорректированы, чтобы дать приемлемый уровень производительности без ущерба для безопасности [3].

Краткие характеристики кандидатов, отобранных на 2 тур, представлены в таблице 2.

Таблица 2

Характеристики хеш алгоритмов-кандидатов на 2 тур конкурса SHA-3

Предварительное изучение алгоритмов-участников показало, что каждый из них позаимствовал некоторые принципы построения у алгоритма AES для обеспечения стойкости хеш-кодов.

Вывод

Таким образом, главным требованием к алгоритмам-конкурсантам руководители NIST выдвинули безопасность, что и явилось основным критерием отбора кандидатов во 2 раунд. Только 14 алгоритмов из 51 представленных смогли продемонстрировать необходимый уровень защиты от криптографических атак. К основным критериям отбора также относится производительность и возможность работы на большом числе платформ, что также позволило руководителям конкурса “отсеять” несколько кандидатов (алгоритмы Vortex, LUX и т.д.). По заявлению NIST алгоритмы, имеющие уровень производительности сопоставимый или лучше, чем в SHA-2, смогли пройти во 2 раунд. Перспективным направлением дальнейших исследований является анализ статистической стойкости алгоритмов-конкурсантов 2 раунда, их реализация на различных платформах с целью оценки производительности и адаптации их применения в банковских транзакциях документооборота внутриплатежных банковских систем.

Список литературы

1. Информационная технология. Криптографическая защита информации. Цифровая подпись, основанная на эллиптических кривых. Формирование и проверка. ДСТУ 4145 - 2002. - К.: Держстандарт України, 2002. --35 с.

2. NESSIE consortium, “NESSIE Security report.” Deliverable report D20 - NESSIE, 2002. - NES/DOC/ENS/WP5/D20 [Electronic resource]

3. Status Report on the First Round of the SHA-3 Cryptographic Hash Algorithm Competitionhttp Andrew Regenscheid, Ray Perlner, Shu-jen Chang, John Kelsey, Mridul Nandi, Souradyuti Paul. [Електронний ресурс]

Размещено на Allbest.ru