Хэшфункции

Хэшфункции

Основные определения, обозначения и алгоритмы. Под термином "хэшфункция" понимается функция, отображающая электронные данные произвольной длины (иногда длина ограничена, но достаточно большим числом), в значения фиксированной длины. Последние часто называют хэшкодами. Таким образом, у всякой хэшфункции h имеется большое количество коллизий, то есть пар значений x и y таких, что h(x)=h(y). Основное требование, предъявляемое криптографическими приложениями к хэшфункциям, состоит в отсутствии эффективных алгоритмов поиска коллизий. Хэшфункция, обладающая таким свойством, называется хэшфункцией, свободной от коллизий. Кроме того, хэшфункция должна быть односторонней, то есть функцией, по значению которой вычислительно трудно найти ее аргумент и, в то же время, функцией, для аргумента которой, вычислительно трудно найти другой аргумент, который давал бы то же самое значение функции.

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

Введем следующие обозначения. Хэшфункция h обозначается как h(α) и h(α,β) для одного и двух аргументов соответственно. Хэшкод функции h обозначается как H. При этом H0=I обозначает начальное значение (вектор инициализации) хэшфункции. Под обозначением будет пониматься операция сложения по модулю 2 или логическая операция XOR (исключающая ИЛИ). Результат шифрования блока B блочным шифром на ключе k обозначается Ek(B).

Для лучшего понимания дальнейшего материала приведем небольшой пример построения хэшфункции. Предположим нам необходимо получить хэшкод для некоторой программы M. В качестве шифрующего преобразования в хэшфункции будут использоваться процедуры шифра DES с ключом k. Тогда, чтобы получить хэшкод H программы M при помощи хэшфункции h необходимо выполнить следующую итеративную операцию:

где код программы M разбит на n 64битных блока. Хэшкодом данной хэшфункции является значение H=h(M, I)=Hn.

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

Атака, основанная на "парадоксе дня рождения", заключается в следующем. Пусть a предметов выбираются с возвращением из некоторого множества с мощностью n. Тогда вероятность того, что два из них окажутся одинаковыми, составляют

Практически это означает, что в случайно подобранной группе из 24 человек вероятность наличия двух лиц с одним и тем же днем рождения составляет значение примерно 1/2. Этот старый и хорошо изученный парадокс и положен в основу криптоанализа хэшфункций.

Например, для криптоанализа хэшфункций, основанных на использовании криптоалгоритма DES, указанная атака может быть проведена следующим образом. Пусть n мощность области хэшкодов (для криптоалгоритма DES она равна 264). Предположим, что есть две программы m1 и m2. Первая программа достоверна, а для второй криптоаналитик пытается получить то же самое значение хэшкода, выдав таким образом программу m1 за программу m2 (то есть криптоаналитик пытается получить коллизию). Для этого криптоаналитик подготавливает порядка различных, незначительно отличающихся версий m1 и m2 и для каждой из них вычисляет хэшкод. С высокой вероятностью криптоаналитику удается обнаружить пару версий m`1 и m`2, имеющих один и тот же хэшкод. В дальнейшем при использовании данного хэшкода можно выдать программу m`2 вместо программы m`1, содержание которой близко к содержанию программы m1.

К основным методам предотвращения данной атаки можно отнести: увеличение длины получаемых хэшкодов (увеличение мощности области хэшкодов) и выполнение требования итерированности шифрующего преобразования.


Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок