Truncated differential characteristics with minimum number of active bytes for simplified Whirlpool.pdf Хэш-функция Whir/poo/ (далее W) разработана Винсентом Риджменом (VincentRijmen) и Пауло Баррето (Paolo Barreto) и опубликована в 2000 г. [1]. Претерпев рядизменений, касающихся преобразований, лежащих в её основе, она была стандарти-зована в окончательном варианте в [2]. Хэш-функция Whir/poo/ построена на основеAES-подобного блочного шифра W. В атаке отражениями (rebound attack) [3], пред-ложенной Марио Ламбергером и др.(Mario Lamberger etc.), найдены коллизии толькодля пяти полных раундов блочного шифра W (из 14). Сложность такой атаки состав-ляет 2120 (в то время как парадокс о днях рождения даёт сложность 2256).Будем рассматривать хэш-функции V и U, которые являются упрощёнными вари-антами хэш-функции W: их блочные шифры представляют собой всего один или двараунда блочного шифра W соответственно.Под дифференциальной характеристикой в задаче поиска одноблоковой колли-зии будем понимать набор разностей (AM; AH0 , AH1), где AH0 -разность начальныххэш-значений, а AH1 -разность хэш-значений после обработки одного блока сообще-ний. Под активным байтом в дифференциальной характеристике понимается ненуле-вой байт, который подается на нелинейное преобразование. В случае хэш-функции W(соответственно, и для V и U) единственным нелинейным преобразованием является S,в основе которого лежит S-box, реализующий нелинейную подстановку.Пусть M1 и M2 - пара сообщений, такая, что M1 ф M2 = AM. Рассматривая раз-личные значения AM, найдём минимальное количество активных байт в дифференци-альной характеристике (AM; 0, 0), при которых существует коллизия, поскольку, какправило, минимизация количества активных байт ведёт к максимизации вероятностидифференциальной характеристики.Утверждение 1. Для функции V наименьшее количество активных байт в диф-ференциальной характеристике равно 23, а для функции U - 45.Для оценки вероятности дифференциальной характеристики используем следую-щее свойство нелинейного преобразования S: пусть a,b . {0,1}8 . Тогда для фиксиро-ванной пары (a, b) число решений уравненияS(x) ф S(x ф a) = bотносительно переменной x может быть равным 0, 2, 4, 6, 8 и 256 (a = b = 0).Обозначим Pa,b = N/28 , где N - число решений уравнения для пары (a,b). Вели-чина Pa,b является вероятностью дифференциальной характеристики для S-box с раз-ностью a на входе и разностью b на выходе. Соответственно она принимает одно изследующих значений: 0, 2 - 7 , 2 - 6 , 3 2 - 7 , 2 - 5 и 1.Максимальной вероятности дифференциальной характеристики (AM; 0, 0) можнодобитьсяпри предположении, что все её активные байты проходят через S-box с ве-роятностью 2- 5 ; таким образом, получаемСледствие 1. Максимальная вероятность нахождения коллизии для хэш-функ-ции V составляет 2- 1 1 5 , а для U - 2 - 2 2 5 .Итак, даже сильно упрощённая хэш-функция Whir/poo/ обладает значительнойстойкостью к нахождению коллизий.

Скачать электронную версию публикации