2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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...

$\endgroup$
1
  • $\begingroup$ 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)$. $\endgroup$
    – ThomasM
    Apr 8, 2022 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.