Comment by f154hfds | Hacker News Reader

Comment by f154hfds | Hacker News Reader

Parent Full thread

For a hash function to be mathematically secure, it needs to have a formal proof that the computational complexity of a preimage or collision attack (depending on the threat) meets some criteria. For example, [1]. As far as I'm aware, no such formalism exists for anything in the SHA family. This means in theory someday someone could discover a way to short circuit the desired complexity by taking advantage of some weakness in the algorithm, as they did to MD5 and SHA1 already.

In principal, these attacks are getting to the complexity where any new discovery will probably be aided by some form of AI (using a pretty loose definition of AI, computer aided search through an attack space). I only comment because the OP seemed rather flippant about 'math' protecting SHA256 where unless I'm mistaken there is no such protection.

[1] https://en.wikipedia.org/wiki/Security_of_cryptographic_hash...

You’re correct that there is no proof of the security of SHA1. The existence of any one-way function would imply that P != NP.

And if it turns out that P = NP then it will turn out that most of the cryptographic guarantees we rely on today will be unrealizable on classical computers.

Quantum computers may not help us as it is currently unknown if quantum computers are more powerful than classical computers in terms of time complexity (it’s strongly suspected that this is the case though).

What relationship do any SHA family hashes have to do with P vs NP? I'm not aware of any. If there is some proof that subset sum reduces to constructing a preimage of anything in the SHA family then I would count that 'mathematically' secure but I don't think any such reduction exists.

The relationship is that computing the SHA hashes takes polynomial time. One way you can think of NP is that it is the set of problems whose solutions that can be deterministically verified in polynomial time. So for any hash computable in polynomial time, the pre-image problem is in NP.

Note that this doesn’t prove the security of SHA256, it just says that to prove it secure would be to prove P != NP. You could still prove SHA256 insecure and that proof could be totally separate from P =? NP.

Reply on news.ycombinator.com