2
$\begingroup$

Jutla & Patthak wrote "Is SHA-1 conceptually sound?" back in 2005, in which they provide a proof sketch (Appendix A) to show that finding a preimage for SHA-1 is NP-hard. Now, there are some issues with the proof sketch (as far as I can see). It does not take into account the additional constraints introduced by linear message-expansion; and it does not handle the CHOICE function and is therefore applicable to rounds >20. At a somewhat more pedantic level, the constructions look a bit artificial, but perhaps that's just aesthetics.

Nevertheless, it seems that if the proof sketch does hold true, then this provides a NP-hard model for two-thirds of SHA-1 preimage-finding, which seems like it should be a big deal. The paper has never been published in conference proceedings or journals, nor is it cited by the most significant SHA-1 preimage work in recent years (i.e., Knellwolf & Khovratovich ; Rechberger; and Aoki & Sasaki). I assume that there's something more important that's wrong with the proof as a whole, but I'm not sure what it could be.

So my questions is: what's wrong with it?

$\endgroup$
3
$\begingroup$

they provide a proof sketch (Appendix A) to show that finding a preimage for SHA-1 is NP-hard

No, they don't. The definition of a problem being NP-hard is "if you have an Oracle that can solve instances of this problem in polynomial time, you can solve any problem in NP in polynomial time"; as we can quickly find SHA-1 preimages using a huge lookup table, we can easily see that finding SHA-1 preimages is not NP-hard (unless P=NP, in which case every problem is NP-hard)

What they do (at best) is show is a class of problems that are jointly NP-hard (of which finding SHA-1 preimages may be an instance). However, that doesn't tell us anything about the concrete difficulty of SHA-1; NP-hard problems can have easy instances (trivial example: travelling salesman problem over every city in the world; is there a circuit that's at most 1 kilometer total distance? Even though the traveling salesman problem is NP-hard, this is a trivially solved instance)

$\endgroup$
  • 1
    $\begingroup$ If you have a 10-input 3SAT problem and the time to test $2^{10}$ input variations, can't you also make a huge lookup table to "solve" that 3SAT problem? But that doesn't mean that 3SAT is not NP-complete. I'm not sure how having a LUT changes the difficulty of the problem. $\endgroup$ – Rhyme Aug 30 '16 at 17:19
  • 1
    $\begingroup$ @Rhyme: indeed, 3SAT problems restricted to 10 bits inputs is also not NP-complete; you need to allow the problem to scale to arbitrary size before NP-complete/NP-hard becomes a possibility. You can have a LUT to solve the problem for 10 bits of inputs; you can't (or, at least, it's not obvious how) to apply a LUT to quickly solve an arbitrary sized input (and, remember, you're not allowed to precompute different LUTs as the input grows) $\endgroup$ – poncho Aug 30 '16 at 17:25
  • 2
    $\begingroup$ Aren't they basically saying: "There is this problem which is (probably?) NP hard. If we could solve it, we could also construct collisions/preimages for SHA-1." I.e. finding SHA-1 images can be much easier in other ways. $\endgroup$ – otus Aug 30 '16 at 17:28
  • 2
    $\begingroup$ @otus: essentially, that's what they are saying. Now, this is true of any NP-complete problem; however the problem they give is "close" to the SHA-1 preimage problem (unlike, say traveling salesman), and it's not obviously generic (unlike, say, SAT problem). $\endgroup$ – poncho Aug 30 '16 at 17:34
  • 2
    $\begingroup$ @Rhyme: actually, from a complexity theoretical view (and the terms "NP-hard" and "NP-complete" are complexity theoretical terms), there's no problem with precomputing $2^{447}$ solutions (or $2^{160}$ preimages for the $2^{160}$ possible outputs); yes, that's impractical, but complexity theory doesn't care about that. In contrast, with 3SAT, you have a potentially unbounded number of possible solutions (as the problem size grows without limit), and so it's not only infeasible, but impossible to have a finite table that lists the solutions. $\endgroup$ – poncho Aug 30 '16 at 17:37

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.