3
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ How do you define multiplication in $\{0,1\}^*$? $\endgroup$ Dec 20, 2015 at 20:03
  • $\begingroup$ @IlmariKaronen Integer multiplication. $\endgroup$
    – Michael
    Dec 20, 2015 at 20:06
  • $\begingroup$ 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... $\endgroup$ Dec 20, 2015 at 20:22
  • $\begingroup$ @IlmariKaronen I'm indeed asking for a first preimage $\endgroup$
    – Michael
    Dec 20, 2015 at 20:24
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 20, 2015 at 21:32

1 Answer 1

1
$\begingroup$

Perform a birthday attack:

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

$\endgroup$
1
  • $\begingroup$ do you think birthday complexity is the lowest complexity possible for this problem? $\endgroup$
    – kodlu
    Dec 23, 2015 at 21:35

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.