# More efficient way of iterative hashing

Here is a possible way to perform iterative cryptographic hashing twice as fast as in the ordinary way.

Given a compression function $$f: \{0,1\}^{a+b} \rightarrow \{0,1\}^b$$. Assume the message is of length $$4a$$ bits after padding. Normally the four message blocks are injected one after another into a data block $$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$$ A first idea to hash faster is to simplify the compression function, e. g. replace $$f$$ by a function $$g$$ that is built similarly but uses only $$\frac 1 4$$ of the internal rounds. Compute $$x_4$$ like above with using $$g$$ instead of $$f$$ and finalize by $$h=p(x_4)$$, where $$p$$ is a pseudorandom function that doesn't allow to compute $$x_4$$ from the hash $$h$$.

I reckon this might be secure against preimage but not collision attacks, because there is too much correlation between $$x_i$$ and $$x_{i+1}$$, allowing to construct message blocks $$m_i, \overline m_i, m_{i+1}, \overline m_{i+1}$$ so that $$g(g(x_i\|m_i)\|m_{i+1})=g(g(x_i\|\overline m_i)\|\overline m_{i+1})$$ The idea is now to insert each message block twice:

$$x_{i+1} = g(x_i \| m_{i \bmod 4}); \; i=0,...,7$$ $$h = x_8$$ Now there are at least five calls to $$g$$ between the injections of two different blocks $$m_i, m_j$$. For example $$m_2$$ is hashed when $$i=2$$ and $$m_3$$ when $$i=7$$, thus there shouldn't be exploitable correlation between $$x_2$$ and $$x_7$$. Yet this scheme uses only $$\frac 1 2$$ the rounds in total, compared with the ordinary method.

Would this be secure, given the round number of $$f$$ is just sufficient to make the ordinary method secure?

Here is one obvious approach to try to find a collison:

• Search for a pair $$m_1, \overline{m_1}$$ with the property that $$g(x \| m_1) = g(x \| \overline{m_1})$$ for a nontrivial fraction of $$x$$. Given that $$g$$ has a reduced number of rounds, this may be do-able.

• Now, start with a fixed $$x_i$$ (corresponding to a known message prefix), and search for an $$m_0$$ s.t. $$g(x_i \| m_0)$$ is one of the colliding preimages for $$m_1, \overline{m_1}$$.

• Call $$g(g(x_0 \| m_0) \| m_1)$$ the value $$x_2$$; search for an $$m_2, m_3$$ pair such that $$g(g(g(x_2 \| m_2) \| m_3) \| m_0)$$ is also a colliding pair.

If we can find that, then the message blocks $$(m_0, m_1, m_2, m_3)$$ and $$(m_0, \overline{m_1}, m_2, m_3$$) collide when added to the message prefix.

How doable is this? That depends on how feasible the first step is (and how probable a random $$x$$ value is a colliding preimage) - if we can get the probability of a colliding preimage up to $$2^{-N}$$, then the amount of effort used by the remaining steps is an expected $$2^{N+1}$$ work...

• This attack can be hampered by entering the iteration number into each compression step: $x_{i+1}=g(x_i \| m_{i \bmod 4}, i)$. Apr 8, 2022 at 13:03