Assume that $h:\{0,1\}^* \rightarrow \{0,1\}^\lambda$ is a cryptologic hash function, $r$ is taken randomly from $\{0,1\}^\lambda$, $p$ is a low-entropy password and $p^*$ is a guess. Now we get $h(p) \oplus h(p^*) \oplus r$ and $h(r)$ but don't know $h(p)$ or $h(p^*)$.

Then there are two problems is a problem:

  1. Can we get $\Delta{}h = h(p) \oplus h(p^*)$ by a brute-force cracking? (Yes.)

  2. Can we get $h(p)$ (and $p$, due to the low-entropy property)?

There may be a slight different problem to consider easily, what if we get $\mathsf{pad}(p) \oplus \mathsf{pad}(p^*) \oplus r$ and $h(r)$, where $\mathsf{pad} (x)$ simply pads x with zeros?

  • 1
    $\begingroup$ What is the data you're starting out with? It's unlikely that the system that you're attacking will actually provide $h(p^*)$, where $p^*$ is the value you're guessing. $\endgroup$ – poncho Jun 10 '15 at 3:47
  • $\begingroup$ Consider a system that records every login request, but for security it never stores the guess $h(p^*)$ directly? In my opinion it's common to send $h(p^*)$ instead of $p^*$ in a authentication system... Or do I misunderstand something? $\endgroup$ – phan Jun 10 '15 at 4:11
  • 1
    $\begingroup$ What's the motivation for this question? What's the context in which you ran into it? It seems rather strange: I can't imagine why such a system would return such a value to the attacker -- and I especially can't imagine a setting where the attacker would learn this value but wouldn't know $p^*$. What does that even mean? What's the distribution of $p^*$? What do you mean by a guess? Without that, I don't see how this question can be answered. $\endgroup$ – D.W. Jul 10 '15 at 5:43
  • $\begingroup$ I have to agree. If $p^*$ was a guess, the attacker should be able to just calculate $H(p^*)$. $\endgroup$ – otus Jul 10 '15 at 6:46

Let $x = h(p)\oplus h(p^*)\oplus r$. If $h(x) = h(r)$, then either $p = p^*$ or you've found a collision for $h$ (which happens with low probability). Since $p$ is generated from some low-entropy distribution, I assume it's feasible to brute-force over all possible values of $p$, allowing you to recover $p$ by checking whether $h(x) = h(r)$ for each guess $p^*$.

| improve this answer | |
  • $\begingroup$ How to do this brute-force? If we've known $h(p)$, we got $y = x \oplus h(p) = h(p^*) \oplus r$, and could try every possible guess to recover the original $p^*$. Similarly, if we've known $h(p^*)$, we got $y = x \oplus h(p^*) = h(p) \oplus r$, and could try every possible password to recover the original $p$. But we in facts know nothing about $h(p)$ or $h(p^*)$ directly. $\endgroup$ – phan Jun 10 '15 at 4:58
  • $\begingroup$ OK, if we try every possible value of $p$ and $p^*$ concurrently, we may find only one pair $(p’,p’^*)$ that makes $h(x \oplus h(p’) \oplus h(p’^*)) = h(r)$. Then we might consider the scene $ x = \mathsf{pad}(p) \oplus \mathsf{pad}(p^*) \oplus r$. In this scene, we may find many pairs $(p’,p’^*)$ that $h(x \oplus \mathsf{pad}(p’) \oplus \mathsf{pad}(p’^*)) = h(r)$ . Am I right? $\endgroup$ – phan Jun 10 '15 at 5:14
  • $\begingroup$ I assumed that you can receive $h(p)\oplus h(p^*)\oplus r$ for different values of $p^*$. Hence if you have guesses $p^*_1, p^*_2, \ldots, p^*_n$, you receive $x_1, x_2, \ldots, x_n$ and compare $h(x_i)$ with $h(r)$, where $x_i = h(p)\oplus h(p^*_i)\oplus r$. If you cannot make multiple guesses, then you can recover $p$ with probability at most $\max_{p'}\Pr(p = p')$. $\endgroup$ – pxdnr Jun 10 '15 at 5:30
  • $\begingroup$ In my assumption, $x = h(p) \oplus h(p^*) \oplus r$ is the out-of-control thing. $\endgroup$ – phan Jun 10 '15 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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