Оценка характеристик перемешивания хэш-функций семейства MD

Матрично-графовый подход (МГП), нашедший успешное применение к оценке свойств итеративных блочных шифров и генераторов ключевого расписания, впервые представлен как инструмент оценивания перемешивающих свойств алгоритмов хэширования. Особенность применения МГП к хэш-функциям связана с неочевидностью построения перемешивающих матриц, характеризующих зависимость битов сгенерированного хэш-значения от битов исходного сообщения. Для хэш-функций MD4, MD5, SHA-1, SHA-256 построены перемешивающие матрицы порядка $512+n$, где $n$ — длина блока, с которым оперирует односторонняя функция сжатия алгоритма хэширования при обработке 512-битового блока входного сообщения ($n=128$ для MD4 и MD5, $n=160$ для SHA-1 и $n=256$ для SHA-256). К исследованным характеристикам перемешивания относятся локальные экспоненты перемешивающих матриц, то есть для каждой матрицы $M$ определено наименьшее натуральное число $\gamma$, такое, что при любом натуральном $\tau \ge \gamma$ положительны все столбцы матрицы $M^{\tau}$ с номерами $513, 514, \ldots, 512+n$. Значения локальных экспонентов являются нижними оценками числа итераций, после которых каждый бит сгенерированного хэш-значения может существенно зависеть от всех битов исходного сообщения. Полученные значения ($\gamma=21$ для MD4, MD5, SHA-256 и $\gamma=23$ для SHA-1) косвенно свидетельствуют о схожих криптографических качествах рассмотренных алгоритмов хэширования, несмотря на варианты их усиления за счёт увеличения длины блока и усложнения функции сжатия.