Brute Force is infeasible for just about every algorithm we use today. Yet, attacks are feasible. This is because weaknesses keep coming up in our algorithms. Why?

We have proven lower bounds for things like sorts, the information security of things like OTP and Shamir's Secret Sharing, proven many problems as hard as any that can be checked in polynomial time (NP-complete), yet we haven't proven anything computationally secure.

Like, we can say that "if this assumption holds, this is secure" but the assumptions are obvious or definitional, like you would expect from axioms, but conjectures that are introduced just so they can be used to prove stuff, and are not in anyway self-evident. Are trust for them goes as far as "a bunch of people have tried to break it, but haven't." As far as I know, we don't even have many cryptographic algorithms for which breaking is NP-Complete.

Why is computational security so hard to prove? Why don't we have any, say, public-private key system that is NP complete to break?