# How hard is it to recover $p$ if I can get $h(p) \oplus h(p^*) \oplus r$ and $h(r)$?

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?

• 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. – poncho Jun 10 '15 at 3:47
• 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? – phan Jun 10 '15 at 4:11
• 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. – D.W. Jul 10 '15 at 5:43
• I have to agree. If $p^*$ was a guess, the attacker should be able to just calculate $H(p^*)$. – 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^*$.
• 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. – phan Jun 10 '15 at 4:58
• 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? – phan Jun 10 '15 at 5:14
• 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')$. – pxdnr Jun 10 '15 at 5:30
• In my assumption, $x = h(p) \oplus h(p^*) \oplus r$ is the out-of-control thing. – phan Jun 10 '15 at 5:43