# Does this proof sketch show that finding a SHA-1 preimage is NP-hard?

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?

• 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. – Rhyme Aug 30 '16 at 17:19
• @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. – poncho Aug 30 '16 at 17:37