# If the hash of the multiplication is equal to the multiplication of the hash, how can this be used to leverage an attack?

Assume a hash function $H:\left\{0,1\right\}^*\to G$ where $G$ is a group and assume that finding an inverse in $G$ is easy.

How can a preimage efficiently be found using the fact that $H(M_1\cdot M_2)=H(M_1)\cdot H(M_2)$ for $M_1,M_2\neq0$?

I've tried playing around with the group properties but I haven't gotten very far. Any direction would be appreciated.

• How do you define multiplication in $\{0,1\}^*$? Dec 20, 2015 at 20:03
• @IlmariKaronen Integer multiplication. Dec 20, 2015 at 20:06
• OK, and how do you map bitstrings to integers (and back)? Just by treating the bits as base-2 digits? If so, note that this map is not one-to-one, because it ignores leading zeros. Does your hash also ignore leading zeros? If so, that's a second-preimage attack right there. Of course, you seem to be asking for a first preimage, so it's not quite enough, but still... Dec 20, 2015 at 20:22
• @IlmariKaronen I'm indeed asking for a first preimage Dec 20, 2015 at 20:24
• Technically, since $G$ is a group, all its elements must have inverses. In particular, $H(0)\in G$, so it has an inverse $H(0)^{-1}$. But since $0\cdot m=0$ for all $m$, it follows that $H(0)=H(0\cdot m)=H(0)\cdot H(m)$. Multiplying both sides by $H(0)^{-1}$ then yields $H(m)=1_G$, where $1_G$ is the identity element of $G$, for all $m$. Thus $H$ maps all inputs to $1_G$, and so finding preimages is either trivial (for $1_G$) or impossible (for any other elements of $G$). But I assume that's not the real answer; it seems more likely that your transcription of the exercise has a mistake. Dec 20, 2015 at 21:32

Given $y\in G$ we want to find $w\in \left\{ 0,1 \right\}^*$ such that $H\left(w\right)=y$.
Randomly choose $x\in \left\{ 0,1 \right\}^*$ and calculate $H\left(x\right)$ and $yH\left(x\right)^{-1}$. Wait until we find $a,b$ such that $H(a)$=$yH\left(b\right)^{-1}$.
Now $w=ab$: $H(w)=H(ab)=H(a)H(b)=yH\left(b\right)^{-1}H(b)=y$.