Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
§ 13.2. Ключевые функции хэширования
В криптографических приложениях к ключевым функциям хэширования предъявляются следующие основные требования:
— невозможность фабрикации;
— невозможность модификации.
350
Хэш-функции
Первое требование означает высокую сложность подбора сообщения с правильным значением свертки. Второе — высокую сложность подбора для заданного сообщения с известным значением свертки другого сообщения с правильным значением свертки.
Иногда эти свойства объединяют в одно более сильное свойство — свойство вычислительной устойчивости. Это требование означает высокую сложность подбора для заданного множества сообщений (X1 ,..,х,} (быть может, пустого) с известными значениями сверток еще одного сообщения X, X Ф Xi, і = Iv..,/, с правильным значением свертки (возможен случай h(x) = h(xt), і є (I,..., /}).
Заметим, что здесь и всюду ниже слова “высокая сложность” означают такую вычислительную сложность задачи, при которой ее решение с использованием вычислительной техники за реальное время невозможно.
Ключевые функции применяются в ситуациях, когда стороны доверяют друг другу и могут иметь общий секретный ключ. Обычно в этих условиях не требуется, чтобы система обеспечивала защиту в случае отказа получателя от факта получения сообщения или его подмены. Поэтому от ключевых хэш-функций не требуется устойчивости к коллизиям.
Обычные атаки на ключевые хэш-функции заключаются в имитации, то есть в передаче сфабрикованных сообщений в пустом канале, а также в подмене передаваемых сообщений с целью навязывания приемной стороне ложных сообщений.
Заметим, что из свойства вычислительной устойчивости вытекает невозможность определения ключа, используемого хэш-функцией, так как знание ключа дает возможность вычислять значение свертки для любого набора данных. В то же время обратное утверждение неверно, так как подбор значения функции хэширования возможен в некоторых случаях без предварительного определения ключа.
351
І лава 13
В качестве примера рассмотрим широко распространенную хэш-функцию, построенную на основе одношаговой сжимающей функции вида
fk(x,H) = Ек(х®Н),
где Ek — алгоритм блочного шифрования.
Для вычисления значения h(M) сообщение M представляется в виде последовательности ^-битовых блоков МхМъ-Mn • Если при этом длина сообщения не кратна длине блока, то последний блок неким специальным образом дополняется до полного блока. Алгоритм вычисления свертки имеет следующий вид:
H0= о,
H1 = Ek(MlQHl^)i 1 = 1,..., AT, (2)
H(M) = Hir
Данный алгоритм фактически совпадает с режимом шифрования со сцеплением блоков (см. гл. 8), с той лишь разницей, что в качестве результата берется не весь шифртекст Hx^H2,..,Hn , а только его последний блок. Такой режим в
ГОСТе 28147-89 называется режимом выработки имитов-ставки.
Еще одной основой для построения ключевых хэш-функций могут служить бесключевые хэш-функции. При этом для вычисления значения свертки ключ приписывается к исходному сообщению.
Заметим, что если ключ просто дописывать в начало или в конец исходного сообщения, то это может приводить к потенциальным слабостям, позволяющим в некоторых случаях осуществлять модификацию сообщений.
352
Хэш-функции
Пусть, например, ключ к добавляется к началу сообщения согласно формуле hk(x) = А(?,х) . Если функция h построена
на основе одношаговой сжимающей функции по формуле (I)5 то по известным значениям MwH = h(k, М) можно вычислять значения этой функции для любых сообщений вида (MiMr) с дописанным произвольным окончанием М\ Это объясняется итеративностью процедуры вычисления функции, в силу которой для нахождения значения H'=h(k,M,M') не требуется знание ключа к, достаточно воспользоваться уже вычисленным “промежуточным” значением Н. Поэтому такая функция не устойчива к модификации.
В случае когда ключ добавляется в конец сообщения согласно формуле H = hk(M) = h(M,к), знание коллизии для
функции А, то есть пары X1, X2, X1^X2, такой, что
h(xx) = h(x2), позволяет вычислять значения h(x], к) = = й(х2, к) для любого ключа к. Поэтому трудоемкость модификации сообщения М=хі оценивается не величиной 2"),
а сравнима с трудоемкостью поиска коллизии, оцениваемой величиной o(2w/2), так как в данном случае применима атака, основанная на парадоксе “дней рождений”.
В связи с этим более предпочтительными являются способы введения ключа, при которых ключ вставляется в сообщение не один, а, по крайней мере, два раза. В [Меп97] указываются два таких способа:
H = h(k,y,M,k)9 H = h(k,yi,h(k,y2,M)),
где у, у\ и у2 — дополнения ключа к до размера, кратного длине блока п. Для определенных бесключевых хэш-функций h такой подход позволяет строить эффективно вычислимые и устойчивые к атакам ключевые хэш-функции. Недостатком
353
І лава 13
такого метода является слишком большая длина п свертки. Дело в том, что для целей проверки целостности обычно выбирают длину свертки п в пределах 32-Н54, а для аутентификации необходимо условие п > 128.
