Does this proof sketch show that finding a SHA-1 preimage is NP-hard? Jutla &amp; 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 &amp; Khovratovich ; Rechberger; and Aoki &amp; 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?
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)