of the style you'd get for RSA.

There are no such proofs for RSA either. The best you can hope for with public key crypto is a reduction to a problem believed hard; in the case of RSA, this is the "RSA problem" of finding roots modulo semiprimes of unknown factorization (which is not the integer factorization problem). I think in practice we have more faith in the security of our stronger symmetric primitives than we do that the hard problems in public key crypto are hard; this has things backwards.

Incidentally, as far as I can tell there's no good reason ever to use RSA; the Rabin family reduce to a strictly harder problem (factorization) and are faster too.

MD5 and SHA are built around custom block ciphers.

Against quantum computers lots of elliptic curve crypto is also broken. Look up "post-quantum cryptography" for a sampling of the algorithms that are not known to fall; none of the well-known ones.