Iată o modalitate posibilă de a efectua hashing criptografic iterativ de două ori mai rapid decât în mod obișnuit.
Dată o funcție de compresie $f: \{0,1\}^{a+b} \rightarrow \{0,1\}^b$. Să presupunem că mesajul este lung $4a$ biți după umplutură. În mod normal, cele patru blocuri de mesaje sunt injectate unul după altul într-un bloc de date $x_i \in \{0,1\}^b$:
$$
m = m_0 \| m_1 \| m_2 \| m_3; \; |m_i| = a
$$
$$
x_{i+1} = f(x_i \| m_i); \; i=0,1,2,3; \; x_0 = IV
$$
$$
h = x_4
$$
O primă idee de hash mai rapid este de a simplifica funcția de compresie, de ex. g. a inlocui $f$ printr-o functie $g$ care este construit în mod similar, dar folosește numai $\frac 1 4$ a rundelor interne. Calcula $x_4$ ca mai sus cu utilizarea $g$ în loc de $f$ și finalizați până la $h=p(x_4)$, Unde $p$ este o funcție pseudoaleatoare care nu permite calcularea $x_4$ din hash $h$.
Consider că acest lucru ar putea fi sigur împotriva atacurilor preimagine, dar nu a atacurilor de coliziune, deoarece există prea multă corelație între $x_i$ și $x_{i+1}$, permițând construirea de blocuri de mesaje $m_i, \overline m_i, m_{i+1}, \overline m_{i+1}$ astfel încât
$$g(g(x_i\|m_i)\|m_{i+1})=g(g(x_i\|\overline m_i)\|\overline m_{i+1})$$
Ideea este acum să introduceți fiecare bloc de mesaje de două ori:
$$
x_{i+1} = g(x_i \| m_{i \bmod 4}); \; i=0,...,7
$$
$$
h = x_8
$$
Acum sunt cel puțin cinci apeluri către $g$ între injecțiile a două blocuri diferite $m_i, m_j$. De exemplu $m_2$ este hashing când $i=2$ și $m_3$ când $i=7$, astfel încât nu ar trebui să existe o corelație exploatabilă între $x_2$ și $x_7$. Cu toate acestea, această schemă folosește numai $\frac 1 2$ rundele în total, comparativ cu metoda obișnuită.
Ar fi acest lucru sigur, având în vedere numărul rotund de $f$ este suficient pentru a face metoda obișnuită sigură?
