Hacker News Reader

Hacker News

Comment by kyruzic | Hacker News Reader

Parent Full thread

kyruzic

This is perhaps one of the most ill-informed comments of all time.

AI cannot magically make math not exist, but nice try.

View on HN

No, it’s perfectly valid for an AI break an algorithm where a human cannot. You’ll see

We already have SAT solvers and they're much better at algorithms than any future AI you can think of.

Respectfully what math exactly protects SHA256?

the same math that says without a map of my back yard, y'all aint finding the gold unless you grab a shovel for ten years

SHA256 uses "one way function" - "easy" to compute, but "hard" to reverse.

https://en.wikipedia.org/wiki/One-way_function

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