Ключевые функции хэширования

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

В настоящий момент в Российской Федерации не существует стандартизированного решения, которое бы регламентировало алгоритм ключевой функции хэширования, обеспечивающий оба перечисленных выше свойства^[1]. Поэтому мы остановимся на принципах построения ключевых функций хэширования, а также приведем описание алгоритмов, которые могут стать прототипами стандартизированных решений.

Пусть — пространство двоичных последовательностей произвольной длины, a FI, — пространство двоичных последовательностей фиксированной длины п.

Определение 8.3. Пусть п, т — натуральные числа. Мы будем рассматривать отображения

где к — секретный ключ такой, что len к = т, а а — сообщение.

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

• 1. При любом фиксированном значении k € F.™ функция сжатия Н{а) — Мае (/с. а) является криптографической функцией хэширования, то есть для нее выполнены свойства однонаправленности, а также сложности построения коллизии и второго прообраза, см. определение 8.1.
• 2. Задана определения неизвестного значения k е F™ при известном наборе сообщений ах,…, а* и соответствующих им значений Mac (A;, ai),… Мас (/е. a_t) должна является трудноразрешимой для максимально возможного натурального значения t.

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

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

Введенный нами параметр t задает количество пар а*. Мас (/с, a,), i = 1… А, для которых известен результат действия ключевой функции хэширования. Этот параметр, как правило, называется объемом используемой информации для фиксированного ключа к, а значение параметра t выступает в качестве границы применимости того или иного метода компрометации функции хэширования.

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

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

Предположим, что тотальный перебор всех возможных значений из F™ является единственным способом определения секретного ключа к е IF2', тогда трудоемкость такого метода есть 0(2^т) опробований неизвестного ключа. С другой стороны, воспользовавшись парадоксом «дней рождений», мы можем построить коллизию с трудоемкостью 0(2 2) выбора случайных сообщений при фиксированном ключе к. Полагая указанные значения равными, получаем п — 2 т. Отметим, что на практике длина ключа выбирается с учетом свойств и ограничений используемых криптографических преобразований и равенство п = 2т не выполняется.

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

• 1. Подход с использованием криптографической функции хэширования. Функции, построенные на основе данного подхода, принято называть НМЛС (hash message authentification code).
• 2. Подход с использованием блочного алгоритма шифрования. Функции, построенные на основе данного подхода, принято называть СМАС (cipher message authentification code).
• 3. Подход, основанный на использовании «универсального» хэширующего преобразования. Функции, построенные на основе данного подхода, принято называть UMAC (message authentication code based on universal hashing).
• 4. Произвольный подход, основанный на применении криптографических преобразований, отличных от функций хэширования или блочного шифрования.

Первые два подхода наиболее известны и распространены. Подход для построения функций на основе криптографических функций хэширования в настоящее время стандартизирован американским институтом стандартизации NIST, см. FIPS PUB 198 [6J.

Для построения функций на основе СМАС предложено несколько независимых вариантов, для которых известны практические реализации в некоторых зарубежных средствах криптографической защиты информации. Кроме того, к данному классу алгоритмов можно отнести отечественный режим выработки имитовсгавки, регламентируемый ГОСТ Р 34.13−2015.

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

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

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

• [1] В Российской Федерации принят стандарт ГОСТ Р 34.13−2005, которыйрегламентирует использование режима работы блочного шифра для выработкиимитовставки, обеспечивающей целостность передаваемой информации, см. подраздел 8.2.2.1.