No need to worry, cipher is right. I’m being horribly inaccurate, as usual. Voted him up for correctness. :-)
What I should have said is that there are no correctness proofs, of the style you’d get for RSA. No guarantees, in other words. There is plenty of math, just no math that lets you prove they have the properties you want them to have; this is doubly annoying because, historically, they will almost certainly turn out later to not have them.
There’s plenty of math that guarantees they lack specific vulnerabilities, and far more that attempts to exploit vulnerabilities, just nothing that says there are no vulnerabilities; at least, nothing I’ve heard of. Different hash functions have different levels of security; for example, most block ciphers can technically be used for hashing, hopefully with less chance of trouble than the faster MD5 or SHA hashes.
The fact of the matter is still that, outside of the annoyingly slow RSA family of ciphers, nothing I’ve heard of in cryptography that’s practically usable also has a strong mathematical proof; a problem that is borne out by a long string of theoretical and sometimes practical attacks on the algorithms. It’s easy to get disillusioned, but at least we get amusing attack names like “miss-in-the-middle”, and SHA-2 is still mostly intact.
And lest someone calls me on it, I should probably point out that RSA does not, strictly speaking, have a security proof either. Its security hinges on a single open question, namely whether prime factorization is slow or not; that’s a lot better than the attack surface of other ciphers, but not quite no surface at all, and that’s even ignoring the existence of Shor’s algorithm. If you have a quantum computer, RSA is broken.
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.
Anyone care to post evidence either way?
No need to worry, cipher is right. I’m being horribly inaccurate, as usual. Voted him up for correctness. :-)
What I should have said is that there are no correctness proofs, of the style you’d get for RSA. No guarantees, in other words. There is plenty of math, just no math that lets you prove they have the properties you want them to have; this is doubly annoying because, historically, they will almost certainly turn out later to not have them.
There’s plenty of math that guarantees they lack specific vulnerabilities, and far more that attempts to exploit vulnerabilities, just nothing that says there are no vulnerabilities; at least, nothing I’ve heard of. Different hash functions have different levels of security; for example, most block ciphers can technically be used for hashing, hopefully with less chance of trouble than the faster MD5 or SHA hashes.
The fact of the matter is still that, outside of the annoyingly slow RSA family of ciphers, nothing I’ve heard of in cryptography that’s practically usable also has a strong mathematical proof; a problem that is borne out by a long string of theoretical and sometimes practical attacks on the algorithms. It’s easy to get disillusioned, but at least we get amusing attack names like “miss-in-the-middle”, and SHA-2 is still mostly intact.
And lest someone calls me on it, I should probably point out that RSA does not, strictly speaking, have a security proof either. Its security hinges on a single open question, namely whether prime factorization is slow or not; that’s a lot better than the attack surface of other ciphers, but not quite no surface at all, and that’s even ignoring the existence of Shor’s algorithm. If you have a quantum computer, RSA is broken.
Well, there are still elliptic curves.
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.