Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Let $H$ be a sponge hash with rate $r$ and capacity $c$, built from a permutation $\pi: \{0, 1\}^n \rightarrow \{0, 1\}^n$, where $n = r + c$.
Assuming $r \ge 2c$, how can I find a collision with probability at least $0.5$ in time $O(2^{c/2})$. The colliding messages can be $2r$ bits each.
I'm pretty sure I have to use birthday paradox, but I still don't know how to apply it.
The hash function, by definition of rate, processes messages in $r$ bit long blocks. Generate about $2^{c/2}$ ($r$ bit) message blocks until you a pair of messages, say $m$ and $m'$ such that you get a collision in the $c$ bits associated with capacity. That is $T_c(\pi(iv \oplus (0^c \| m)) = T_c(\pi(iv \oplus (0^c \| m'))$ where $T_c$ is a function that truncates* the $n$ bit output of $\pi$ to $c$ bits, $iv$ is the internal state of the hash function prior to absorbing any message, $0^c$ is a string of c zero bits, and $\|$ is the concatenation operator.
The internal state of two instances of the hash function after one absorbs $m$ and the other $m'$ now have identical capacity bits, but $\pi(iv \oplus (0^c \| m)) \neq \pi(iv \oplus (0^c \| m'))$ because $m \neq m'$ and $\pi$ is a permutation. Select any value $m_2$ for the second message block for the first instance of the hash function. Then select $m_2'$ for the second block of the second hash such that $m_2 \oplus m_2' = \pi(iv \oplus (0^c \| m)) \oplus \pi(iv \oplus (0^c \| m'))$.
Prior to absorbing the second message block both instances have just their capacity bits identical. You select the second message block to cancel the remaining $r$ unequal bits before the second time $\pi$ gets applied. Since the inputs to $\pi$ are the same, so are the outputs. Now you have a full internal collision. For this reason, just requesting the output of the hash function at this point will yield an output collision. But a collision in a hash function's internal state is more powerful than just a collision between outputs. You can keep generating collisions by choosing a different $m_2$ or by extending the input to both hash functions with new identical message blocks.
The reason you (may) need $2r$ bits of input is so you can cancel the difference in the non-capacity part of the sponge's state. A sponge based hash can be defined such that the last step isn't necessary. Note that once you have a collision in the capacity bits it's trivial to choose the next message block values such that you have a collision.
The algorithm can be defined such that instead of remembering all $n$ bits of output from $\pi$ it only stores the capacity bits. This changes the algorithm. The outputs of two hash functions that differ only by this detail will be different, but the collision resistance of the two is the same.
It may be defined such that performs state updates as in $h_{i} = \pi(h_{i-1} \oplus (0^c \| m_i))$. Where $h$ is the $n$ bit state of the hash function, $m_i$ is the $i$th r-bit long message block, and $0^c \| m_i$ is n bits because $|0^c| + |m_i| = c + r = n$.
Or it could also be defined to do updates as in $h_i = T_c(\pi((h_{i-1} \| m_i))$. Where $h_i$ is instead $c$ bits long.
Intuitively the difference is that the latter definition overwrites the new message block bits into the sponge state and the former XORs bits into the sponge state. Whether a sponge based hash function is defined one way or the other has no affect on its collision resistance.
TLDR: Just brute force the first message block such that the capacity bits match. Then just pick the second message block to cancel out the remaining r-bit difference.
* In this case discarding the last $r$ bits. I chose to assume in this answer that the hash function was defined such that the rate bits of the sponger were the last $r$ bits and the capacity bits were the first $c$ bits)
