Об аргументации отсутствия свойств случайного оракула у некоторых криптографических хеш-функций

Представлены новые алгебраические атаки на хеш-функции вида $\mathrm{MD4}$-$k$, где $k$ — число шагов базового алгоритма $\mathrm{MD4}$, $39 \leq k \leq 48$. Для решения алгебраических уравнений используются SAT-решатели. Представленные атаки демонстрируют отсутствие свойств случайного оракула у рассматриваемых хеш-функций. Более точно, мы строим оценки доли легко обратимых выходов этих функций и показываем, что даже для полнораундовой функции $\mathrm{MD4}$ эта доля весьма высока. Для построения оценок с каждой функцией вида $\mathrm{MD4}$-$k$ связывается специальная функция, длина входа которой существенно меньше $512$. Показано, что любое значение такой функции является значением $\mathrm{MD4}$-$k$. Задача обращения специальной функции, как правило, существенно проще, чем задача обращения $\mathrm{MD4}$-$k$. Оценка доли векторов в $\{0,1\}^{128}$, являющихся значениями специальной функции, даёт оценку доли легко обратимых значений исходной функции $\mathrm{MD4}$-$k$.