15
$\begingroup$

Let's assume we have an $n$-bit hash function and a $b$-bit partial preimage attack that is faster than brute force. Does this imply a faster than brute force preimage attack on the whole hash?

It seems that it does, because if you run the $t<2^b$ time partial preimage attack on an input you have a $2^{b-n}$ chance of finding a full preimage, which is better than the chance with a brute force attack in that time.

On the other hand, if you run it on $2^{n-b}$ inputs you expect one of them to find a full preimage and this takes $t \cdot 2^{n-b} < 2^n$ time. However, with that many inputs a brute force attack would find one of them in just $2^b$ time, which is better unless $b>\frac{n}{2}$ and the partial preimage attack is very fast. (Complicating matters further, some of the inputs may have the same partial hash, not sure how to take that into account.)

I am trying to figure out what assumptions can be made about preimage attacks when considering the truncation of an arbitrary $n$-bit secure $n$-bit hash.

Improve this question
$\endgroup$
6
  • $\begingroup$ Just to understand: are you saying that the hash function, that once given some input, it outputs $n$ many hash bits, and you found a method to identify $b$ bits of the original input, without performing a $2^b$ bruteforce? $\endgroup$
    – caveman
    Commented Aug 8, 2016 at 15:10
  • 1
    $\begingroup$ @caveman suppose I have a function that given a hash $H(x)$ for an unknown $x$ quickly outputs a value $y$ whose hash $H(y)$ matches the first $b$ bits of $H(x)$. ("Quickly" being in significantly less than the $2^b$ time a brute force attack would take to find one.) $\endgroup$
    – otus
    Commented Aug 8, 2016 at 15:27
  • $\begingroup$ @otus I was just wondering about this very same topic myself today. Did you ever get an answer to this old question by some other means? $\endgroup$
    – Luis Casillas
    Commented Feb 25, 2017 at 2:20
  • $\begingroup$ @LuisCasillas, no I did not. $\endgroup$
    – otus
    Commented Feb 25, 2017 at 7:20
  • 1
    $\begingroup$ @fgrieu, thinking about it again a year later, I think my confusion was because I was conflating a single-target preimage attack and a multi-target attack. A partial preimage attack seems to help with the former, but not necessarily with the latter. $\endgroup$
    – otus
    Commented May 17, 2017 at 19:22

3 Answers 3

Reset to default
2
$\begingroup$

It depend on what notion of preimage resistance you mean, and on whether the preimage attack applies to only a tiny class of images or whether it works uniformly on all of them.

Fix a random hash family $H\colon \{0,1\}^{4b} \to \{0,1\}^{2b}$. Define

\begin{equation*} H'(x) = \begin{cases} 0^b \mathbin\Vert H_b(x), & \text{if $x$ starts with $1^{2b}$;} \\ H(x), & \text{otherwise.} \end{cases} \end{equation*}

Here $H_b(x)$ is some $b$-bit truncation of $H(x)$. How does the obvious cheap preimage attack on $H'_b$ translate to the cost of a preimage attack on $H'$?

  • The everywhere preimage resistance (ePre) of $H'$ is at most half the bits of that of $H$, because there exists an image $y$—namely, any string starting with $0^{b}$—such that there is a known random algorithm $A_y(H')$ making $q$ queries that can find a preimage with probability $O(2^{-b} q)$ much higher than the generic $O(2^{-2b} q)$.

    That is, we have an extremely cheap preimage attack on $H'_b$ for the image $0^b$ which translates to a cheaper-than-generic everywhere preimage attack on $H'$ because there exist images, namely those starting with $0^b$, for which we can find preimages at substantially lower cost than generic.

  • But this has negligible impact on the always preimage resistance (aPre), or just unqualified preimage resistance (Pre). There are random algorithms $A_{H'}(y)$, for always preimage-resistance, or $A(H', y)$, for (unqualified) preimage-resistance, with conditional probability $O(2^{-b} q)$ of finding preimages given that $y$ lies in a certain class of image—but the probability of being challenged with such an image $y$ is about $2^{-b}$.

    That is, although we have an extremely cheap preimage attack on $H'_b$ for the image $0^b$, it doesn't help us to find a preimage for a uniform random challenge image because the probability of being challenged with an image that starts with $0^b$ is negligible.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I'm not sure how this applies to my question. You've constructed a $H'$ that is weaker than $H$ due to it being easier to brute force a partial preimage than a full one. You've not said anything about how this applies to an attack on $H$ if you have a faster-than-brute-force attack on $H_b$. $\endgroup$
    – otus
    Commented May 12, 2018 at 9:44
  • 1
    $\begingroup$ @otus I do have a cheaper-than-brute-force attack on $H'_b$ and does imply a cheaper-than-brute-force attack on $H'$, for certain images. I'm not sure I understand your objection to this example. My point is that it depends on the notion of preimage resistance and on the nature of the partial preimage attack. Does the partial preimage attack work on any image, or only on a tiny class of them? If only a tiny class of them, then it only breaks ePre, not aPre or Pre; if it works uniformly on all images, then it breaks aPre and Pre too. $\endgroup$
    – Squeamish Ossifrage
    Commented May 12, 2018 at 12:47
1
$\begingroup$

The question assumes hat a $b$-bit preimage attack randomly produces b bit preimages. This is not a realistic assumption.

We could imagine a $b$-bit preimage oracle which deterministically produces just a single $b$-bit preimage - never more never less. Running it multiple times will not give us any additional advantage than running it the first time.

Access to a partial preimage oracle does not seem to help at all in solving the full preimage problem.

Improve this answer
$\endgroup$
0
$\begingroup$

No it doesn't.

Consider this example from Katz' book: "let $g$ be a one-way function and define $f(x_1, x_2) = (x_1, g(x_2))$, where $|x1|=|x2|$. It is easy to show that $f$ is also a one-way function, even though it reveals half its input."

So, despite finding half part of its preimage, it is not possible to find the inverse of $f$ by a polynomial-time algorithm.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ While this answer is interesting it doesn't really answer the original question. It seems to be formulated for fixed length input fixed length output functions and the strength of the one way function $g$ is the same as that of $f$ whose output is much shorter. $\endgroup$
    – kodlu
    Commented Jul 22, 2017 at 4:41
  • $\begingroup$ But there is a faster than brute force attack on f. It can be attacked in about $2^{|x1|}$ instead of $2^{2|x1|}$. $\endgroup$
    – otus
    Commented Jul 22, 2017 at 6:22
  • 2
    $\begingroup$ Although it is faster than brute-force attack but it still needs an exponential-time to run. The problem of finding preimage is that you cannot find it by a polynomial-time algorithm, not by an algorithm better than brute-force attack. $\endgroup$
    – ssss1
    Commented Jul 28, 2017 at 8:12

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.