81
ние свертки и сравнивает его с имеющимся контрольным значением. Несовпадение говорит о том, что данные были изменены.
ХФ, служащая для выработки имитовставки, должна позволять (в отличие от обычной контрольной суммы) осуществлять обнаружение не только случайных ошибок в наборах данных, возникающих при их хранении и передаче, но и сигнализировать об активных атаках противника, пытающегося осуществить навязывание ложной информации. Для того чтобы противник не смог самостоятельно вычислить контрольное значение свертки и тем самым осуществить успешную имитацию или подмену данных, ХФ должна зависеть от секретного, не известного противнику параметра – ключа пользователя. Этот ключ должен быть известен передающей и проверяющей сторонам. Такие ХФ будем называть ключевыми.
Имитовставки, которые формируются с помощью ключевых хэшфункций, не должны позволять противнику создавать поддельные сообщения (от англ. fabrication) при атаках типа имитация (от англ. impersonation) и модифицировать передаваемые сообщения (от англ. modification) при атаках типа «подмена» (от англ. substitution).
При решении второй задачи – аутентификации источника данных – мы имеем дело с не доверяющими друг другу сторонами. В связи с этим подход, при котором обе стороны обладают одним и тем же секретным ключом, уже неприменим. В такой ситуации применяют схемы цифровой подписи, позволяющие осуществлять аутентификацию источника данных. Как правило, при этом сообщение, прежде чем быть подписано личной подписью, основанной на секретном ключе пользователя, «сжимается» с помощью ХФ, выполняющей функцию кода обнаружения ошибок (см. далее). В данном случае хэш-функция не зависит от секретного ключа и может быть фиксирована и известна всем. Основными требованиями к ней являются гарантии невозможности подмены подписанного документа, а также подбора двух различных сообщений с одинаковым значением ХФ (в этом случае говорят, что такая пара сообщений образует коллизию).
Формализуя сказанное, введем следующее определение. Обозначим через Х множество, элементы которого будем называть сообщениями. Обычно сообщения представляют собой последовательности символов некоторого алфавита, как правило, двоичного. Пусть Y – множество двоичных векторов фиксированной длины.
82
Хэш-функцией называется всякая функция h: Х Y, легко вычислимая и такая, что для любого сообщения М значение h(M) = H (свертка) имеет фиксированную битовую длину.
Обычно число возможных сообщений значительно превосходит число возможных значений сверток, в силу чего для каждого значения свертки имеется большое множество прообразов, т. е. сообщений с заданным значением ХФ. Заметим, что при случайном и равновероятном выборе сообщений условие равномерности распределения значений ХФ эквивалентно наличию одинакового числа прообразов для каждого значения свертки.
Обычно ХФ строят на основе так называемых одношаговых сжимающих функций у = F(х1,х2) двух переменных, где хi и у – двоичные векторы длины m и n соответственно, причем n – длина свертки. Для получения значения h(M) сообщение M сначала разбивается на блоки длины m (при этом если длина сообщения не кратна m, то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам m1,m2,…,mN применяют следующую последовательную процедуру вычисления свертки:
H0= ,
Hi=F(mi,Hi-1), где i=1,…,N,
h(M)=HN [9.1]
Здесь – некоторый фиксированный начальный вектор. Если функция F зависит от ключа, то этот вектор можно заполнить нулевыми значениями. Если же функция F не зависит от ключа, то чтобы исключить возможность перебора сообщений (при попытках обращения ХФ), этот вектор можно составить из произвольных фрагментов, допустим, указывающих дату, время, порядковый номер сообщения и т. п.
При таком подходе свойства ХФ хэш-образ полностью определяется свойствами одношаговой сжимающей функции F.
Особо выделяют два важных типа криптографических хэшфункций – ключевые и бесключевые. Первые применяются в системах с симметричными ключами. Ключевые ХФ называют кодами аутентификации сообщений (message authentication code). Они дают возможность без дополнительных средств гарантировать как правильность источника данных, так и целостность данных в системах с доверяющими друг другу пользователями.
Бесключевые ХФ называются кодами обнаружения ошибок (modification detection code(MDC)) или manipulation detection code, message
83
integritу code (MIC). Они дают возможность с помощью дополнительных средств (например, шифрования, использования защищенного канала или цифровой подписи) гарантировать целостность данных. Эти ХФ могут применяться в системах как с доверяющими, так и не доверяющими друг другу пользователями. Рассмотрим их более подробно.
Ключевые функции хэширования
В криптографических приложениях к ключевым функциям хэширования предъявляются следующие основные требования:
–невозможность фабрикации;
–невозможность модификации.
Первое требование означает высокую сложность подбора сообщения с правильным значением свёртки. Второе – высокую сложность подбора для заданного сообщения с известным значением свёртки другого сообщения с правильным значением свертки.
Иногда эти свойства объединяют в одно более сильное свойство – свойство вычислительной устойчивости. Это требование означает высокую сложность подбора для заданного множества сообщений {х1,..,хt} (быть может, пустого) с известными значениями сверток еще одного сообщения х, х хi, i = 1,...,t, с правильным значением свёртки
(возможен случай h(х) = h(хi), i {1,...,t}).
Заметим, что здесь и ниже слова «высокая сложность» означают такую вычислительную сложность задачи, при которой ее решение с использованием вычислительной техники за реальное время невозможно.
Ключевые функции применяются в ситуациях, когда стороны доверяют друг другу и могут иметь общий секретный ключ. Обычно в этих условиях не требуется, чтобы система обеспечивала защиту в случае отказа получателя от факта получения сообщения или его подмены. Поэтому от ключевых хэш-функций не требуется устойчивости к коллизиям.
Обычные атаки на ключевые ХФ заключаются в имитации, т. е. в передаче сфабрикованных сообщений в пустом канале, а также в подмене передаваемых сообщений с целью навязывания приемной стороне ложных сообщений.
Заметим, что из свойства вычислительной устойчивости вытекает невозможность определения ключа, используемого хэш-функцией,
84
так как знание ключа дает возможность вычислять значение свертки для любого набора данных. В то же время обратное утверждение неверно, так как подбор значения функции хэширования возможен в некоторых случаях без предварительного определения ключа. В качестве примера рассмотрим широко распространенную хэш-функцию, построенную на основе одношаговой сжимающей функции вида
Fk(х,H)=Ek(х H),
где Ek – алгоритм блочного шифрования.
Для вычисления значения h(M) сообщение M представляется в виде последовательности n-битовых блоков m1,m2…mN. Если при этом длина сообщения не кратна длине блока, то последний блок неким специальным образом дополняется до полного блока. Алгоритм вычисления свертки имеет следующий вид:
H0=0,
Hi=Ek(mi Hi-1), где i=1,…,N,
h(M)=HN |
[9.2] |
Данный алгоритм фактически совпадает с режимом шифрования со сцеплением блоков, с той лишь разницей, что в качестве результата берется не весь шифртекст h1,h2…hN, а только его последний блок. Такой режим в ГОСТ 28147-89 называется режимом выработки имитовставки.
Еще одной основой для построения ключевых хэш-функций могут служить бесключевые ХФ. При этом для вычисления значения свёртки ключ приписывается к исходному сообщению.
Заметим, что если ключ просто дописывать в начало или в конец исходного сообщения, то это может приводить к потенциальным слабостям, позволяющим в некоторых случаях осуществлять модификацию сообщений.
Пусть, например, ключ k добавляется к началу сообщения согласно формуле hk(х) = h(k, х). Если функция h построена на основе одношаговой сжимающей функции по формуле [9.1], то по известным значениям M и H = h(k,M) можно вычислять значения этой функции для любых сообщений вида (M,M’) с дописанным произвольным окончанием M’. Это объясняется итеративностью процедуры вычисления функции, в силу которой для нахождения значения H’= h(k,M,M’) не требуется знание ключа k, достаточно воспользоваться уже вычисленным «промежуточным» значением H. Поэтому такая функция не устойчива к модификации.
85
В случае, когда ключ добавляется в конец сообщения согласно формуле H = hk (M) = h(M,k), знание коллизии для функции h, т. е. пары х1,х2, х1 х2, такой, что h(х1)=h(х2) позволяет вычислять значения h(х1,k)=h(х2,k) для любого ключа k. Поэтому трудоемкость модификации сообщения M=х1 оценивается не величиной O(2n), а сравнима с трудоемкостью поиска коллизии, оцениваемой величиной O(2n/2), так как в данном случае применима атака, основанная на парадоксе «дней рождений».
В связи с этим более предпочтительными являются способы введения ключа, при которых ключ вставляется в сообщение не один, а по крайней мере два раза. Рассмотрим два таких способа:
H=h(k,у,М, k),
где у, у1 и у2 – дополнения ключа k до размера, кратного длине блока n. Для определенных бесключевых хэш-функций h такой подход позволяет строить эффективно вычислимые и устойчивые к атакам ключевые ХФ. Недостатком такого метода является слишком большая длина n свертки. Дело в том, что для целей проверки целостности обычно выбирают длину свертки n в пределах 32 64, а для аутентификации необходимо условие n 128.
В заключение отметим, что существуют ключевые ХФ, не использующие какую-либо основу типа блочного шифрования или вычисления бесключевой ХФ, а разработанные независимо с учетом эффективной реализации на современных вычислительных машинах. Примером служит ключевая хэш-функция, используемая в алгоритме
MAA (Message Authenticator Algorithm), утвержденном стандартом ISO 8731-2.
Бесключевые функции хэширования
К бесключевым ХФ предъявляют требования, чтобы они были однонаправленными, устойчивыми к коллизиям и устойчивыми к нахождению второго прообраза.
Это означает высокую сложность нахождения сообщения с заданным значением свертки; пары сообщений с одинаковыми значениями свертки; второго сообщения с тем же значением свертки для заданного сообщения с известным значением свёртки.
Односторонняя или однонаправленная хэш-функция – хэшфункция, являющаяся вычислительно необратимой функцией.