Стойкость (безопасность) хеш-функций


 

Один из основных методов криптоанализа хеш-функций заключается в проведении криптоаналитиком (нарушителем) атаки, основанной на «парадоксе дня рождения».

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

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

К основным методам предотвращения такой атаки можно отнести:

· увеличение длины получаемых хеш-кодов (увеличение мощности области хеш-кодов) и

· выполнение требования итерированности шифрующего преобразования.