Стандарты Хеш-функций. Основные определения и требования безопасности к функциям хеширования

3. Стандарты Хеш-функций.

Можно выделить три основных подхода к построению функций хеширования:

·  функций хеширования на основе блочных шифров;

·  функций хеширования на модулярной арифметике;

·  заказные функций хеширования или специальные функций хеширования.

Международная организация по стандартизации ISO/IEC разработала стандарт ISO/IEC-10118 для описания различных классов функций хеширования. В части 10118-2 [1] определены функций хеширования основанные на блочных шифрах в конструкции Matyas-Meyer-Oseas, когда независимый блочный шифр в алгоритме MDC-2 с двумя и более функциями, производит значение хэша удвоенной и утроенной длины, соответственно. Часть 10118-3 [1] определяет три заказных алгоритма: RIPEMD-128, RIPEMD-160 и SHA-1. Эта часть стандарта в настоящее время пересматривается, с оценкой новых криптографических примитивов, которые будут приняты как стандарты ISO. Кроме отмеченных трёх алгоритмов, изучаются функции хеширования: SHA-2/256, SHA-2/384, SHA-2/512 и Whirlpool. Часть 10118-4 [3] описывает MASH-1and MASH-2 функции хеширования, которые используют модулярную арифметику.

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

3.1 Основные определения и требования безопасности к функциям хеширования.

Основные определения функции хеширования и их криптографических свойств приведем в изложении Блэка и Рогавэя [4]. Функции хеширования, функции сжатия и итерационные функции хеширования являются конструктивными элементами алгоритмов хеширования

Определение 1. Функцией хеширования называется функция отображения , где область значений , а  для некоторого .

Определение 2. Функцией сжатия называется функция отображения , где

 и  для некоторых , ,  и .

Определение 3. Итерационной функцией хешированияотфункции сжатия  является функции хеширования  определенная , где  при .

Большинство функции хеширования это итеративные конструкции, которые используют функцию сжатия , предварительное разбиение данных  на подблоки  и связку по обратному входу промежуточных результатов вычислений хеш значений. Модель итеративной хэш-функции определена в ISO/IEC 10118. На рис. 1 представлена общая модель итеративной функции хеширования.

Рис.1. Итеративная модель функции хеширования.

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

_,

,

.

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

Стандарт ISO/IEC 10118 не определяет методы дополнения строки данных, но предполагается, что могут быть использованы методы, определенные в ISO/IEC 9797.

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

Определение 4 (Стойкость к вычислению прообраза) [5].Функция хеширования является стойкой к вычислению прообраза силой , если не существует вероятностного  алгоритма , с входными значениями  и значениями на выходе , временем выполнения не более чем , где  и вероятностью не менее , оцененной при случайном выборе  и .

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

Определение 5 (Стойкость к вычислению второго прообраза) [5]. Пусть  – конечное подмножество . Функция хеширования  является стойкой к вычислению второго прообраза силой , если не существует вероятностного алгоритма, с  и , временем выполнения не более чем , где  и  и вероятностью не менее , оцененной при случайном выборе  и .

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

Определение 6 (Стойкость к коллизиям) [5].Функция хеширования является стойкой к коллизиям силой , если не существует вероятностного алгоритма  с известными выходными значениями , временем выполнения не более чем , где  и  и вероятностью не менее , оцененной при случайном выборе .

Стойкость функций хеширования к коллизиям определяет безопасность систем аутентификации с цифровой подписью.

Определение 7. Хеш функция называется простой или слабой, если  является стойкой к вычислению прообраза и стойкой к вычислению второго прообраза.

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