Вот возможный способ выполнить итеративное криптографическое хеширование в два раза быстрее, чем обычным способом.
Учитывая функцию сжатия $f: \{0,1\}^{a+b} \rightarrow \{0,1\}^b$. Предположим, что сообщение имеет длину $4a$ биты после заполнения. Обычно четыре блока сообщений вводятся один за другим в блок данных. $x_i \in \{0,1\}^b$:
$$
м = м_0 \| м_1 \| м_2 \| м_3; \; |м_я| = а
$$
$$
x_{i+1} = f(x_i \| m_i); \; я=0,1,2,3; \; х_0 = IV
$$
$$
ч = х_4
$$
Первая идея ускорить хеширование — упростить функцию сжатия, например. г. заменять $f$ по функции $г$ который построен аналогично, но использует только $\фракция 1 4$ внутренних раундов. Вычислить $x_4$ как указано выше с использованием $г$ вместо $f$ и завершить по $ч=р(х_4)$, куда $р$ является псевдослучайной функцией, которая не позволяет вычислить $x_4$ из хэша $ч$.
Я считаю, что это может быть защищено от атак с прообразом, но не от атак столкновений, потому что существует слишком большая корреляция между $x_i$ и $х_{я+1}$, позволяющий строить блоки сообщений $m_i, \overline m_i, m_{i+1}, \overline m_{i+1}$ так что
$$g(g(x_i\|m_i)\|m_{i+1})=g(g(x_i\|\overline m_i)\|\overline m_{i+1})$$
Теперь идея состоит в том, чтобы вставить каждый блок сообщения дважды:
$$
x_{i+1} = g(x_i \| m_{i \bmod 4}); \; я=0,...,7
$$
$$
ч = х_8
$$
Сейчас есть как минимум пять звонков на $г$ между инъекциями двух разных блоков $m_i, m_j$. Например $m_2$ хешируется, когда $я=2$ и $m_3$ когда $я=7$, таким образом, не должно быть полезной корреляции между $x_2$ и $x_7$. Но эта схема использует только $\фракция 1 2$ всего раундов по сравнению с обычным методом.
Будет ли это безопасно, учитывая круглое число $f$ достаточно, чтобы сделать обычный метод безопасным?
