Score:2

More efficient way of iterative hashing

sk flag

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?

Score:2
my flag

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

ThomasM avatar
sk flag
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)$.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.