In the very early days of online poker (late 90′s), a group of people did exactly that.
A number of factors combined to make it possible:
The site published the code for its shuffler, supposedly to demonstrate its competence.
The RNG was seeded by the number of milliseconds since midnight, a range laughably smaller than the range of possible poker hands.
Online poker was played for sufficiently low stakes that nobody thought either of the above would be a real problem.
Nowadays, sites keep their algorithms secret, and the even distribution of hands is constantly being verified by third parties with large data sets. They also harvest large sources of entropy, from user mouse gestures and physical RNGs. See PokerStars’ write-up on security.
If the hash function is strong, it doesn’t help—though as far as I know there’s no good formal definition of the properties the hash function has to have.
One of the properties a cryptographic hash function should have is indeed that, if you add known plaintext to an unknown plaintext in any way, you still can’t predict any property of the output that you couldn’t without this—you get no additional information.
Of course, we still don’t have a clue how to prove this for any interesting hash function. They frequently get broken, because there’s basically no mathematical framework behind them.
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.
How hard is it to “crack” a pseudorandom number generator? Say, one used to generate cards in an online poker game?
In the very early days of online poker (late 90′s), a group of people did exactly that.
A number of factors combined to make it possible:
The site published the code for its shuffler, supposedly to demonstrate its competence.
The RNG was seeded by the number of milliseconds since midnight, a range laughably smaller than the range of possible poker hands.
Online poker was played for sufficiently low stakes that nobody thought either of the above would be a real problem.
Nowadays, sites keep their algorithms secret, and the even distribution of hands is constantly being verified by third parties with large data sets. They also harvest large sources of entropy, from user mouse gestures and physical RNGs. See PokerStars’ write-up on security.
So, at least in theory, one could a bit manipulate their RNG, sending them some “mouse moving signals back”.
One would also need to know the other inputs and their hash function in order to control what the manipulation did. Otherwise, it would be “random”.
Needn’t to be a perfect manipulation, to get something already useful.
If the hash function is strong, it doesn’t help—though as far as I know there’s no good formal definition of the properties the hash function has to have.
One of the properties a cryptographic hash function should have is indeed that, if you add known plaintext to an unknown plaintext in any way, you still can’t predict any property of the output that you couldn’t without this—you get no additional information.
Of course, we still don’t have a clue how to prove this for any interesting hash function. They frequently get broken, because there’s basically no mathematical framework behind them.
This is a long, long, long way from the truth.
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.
Another word for a strong pseudorandom number generator is a “stream cipher”.
(This isn’t strictly true, but close enough)
Depends on the generator. Obviously hardware ones cannot be cracked, and even some software ones are thought to be cryptographically secure.
A lot harder than it would be to prove that the random number generator is rigged. ;)