Хэш-функции. Определение, свойства, применение

Под Хэш-функцией понимается получение контрольной характеристики от двоичной последовательности основанное на контрольном суммировании и криптографических преобразованиях. Чаще всего Хэш функции является односторонними функциями (Пример с разбитой вазой: т.е. из состояния А легко в В, а из В→А не возможно) Но бывают односторонние функции с лазейкой (можно собрать, если знаешь что)

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

Хэширования удовлетворяют требованиям:

1.Сжатие. Функция отображает произвольное входное сообщение x произвольной конечной длины в Хэш значение: y=h(x) небольшой фиксированной длины. При этом исходное значение является прообразом.

2.Простота вычисления. Для заданной функции h и сообщения x, h(x) вычисляется не выше, чем с полиномиальной сложностью.

3.Стойкость к вычислению прообразов. Не возможность нахождения неизвестного прообраза для любых предварительно заданных Хэш значений, то есть для заданной функции h вычислительно не возможно найти преобразование x при известном хэш значении y = h(x) для любого y.

4.Стойкость к вычислению второго прообраза. Невозможность нахождения любого другого прообраза, который давал бы такое же Хэш значение, как и заданный. То есть для заданной фцнкции h и прообраза x вычислительно не возможно найти другой прообраз x’≠x, для которого выполнялось бы условие: h(x)=h(x’)

5.Стойкость к коллизиям – невозможность нахождения двух прообразов, для которых вырабатывалось бы одинаковое хэш значение (более жёсткое).

Все существующие Хэш функции делятся на 2 базовых класса:

1.Безключевые Хэш фунции зависящие только от сообщения.

2.Хэш функции с Секретным ключом зависящие как от сообщения так и от секретного ключа.

Все атаки на Хэш функцию разделяются на две группы:

1) Атаки базирующиеся на уязвимости самого алгоритма прообразов (аналитические атаки). Они основываются на недостатках внутренней структуры Хэш функций.

2) И атаки не зависящие от алгоритмов (прямой грубый перебор)

Оценочные значения вычислительной стойкости к Хэш функциям
Тип функции	Цель атаки	Идеальная стойкость
1.Однонаправленная Хэш функция	Нахождение прообраза. Нахождение втор. прообраза.	Достигается при значении h=2^L, где L-длина Хэш значений.
2.Бесколлизионная h	Нахождение любой коллизии.	2^L/2
3.Функция выработки кодов аутентификации сообщений (подкласс ключевых функций)	Точное нахождение ключа. Подделка сообщений.	(K/L)+((2^K-1)/ (1-2^-^L)) K-длина секретного ключа Вероятность успешной подделки: Pm=max(2^-^K;2^-^L)

В качестве основных критериев оценки функций хэширования используются стойкость и вычислительная сложность (скорость) вычисления хэш функций.

min современные требования по стойкости соответствуют сложности атаки = 2¹²⁸. Таким образом для применения в криптосистемах рекомендуется использовать однонаправленные хэш функции, имеющие стойкость к коллизиям не менее 2¹²⁸, т. е. функция с длиной хэш значения не менее 256 бит.

Дата добавления: 2015-04-23