# Chance in cryptography

I was just thinking about my own chance and the way chance can defeat even the most advanced algorithm.

My thought was : you can make a strong session id, but what if by chance, a hacker set this exact match up ?

hypothetical : 454{à"_çé89)hjdsHHKZmdsjYds"#

just try to imagine that someone, by typing a nonsense makes it happen.

You could say, the chances it happens is subminimal. And you may be right.

But what can we do against it ? Ip lock is impossible since the ip is ever changing for some users. Geographical checks, if possible, will lead to severe performance hits (checks), dynamic session may or may not add an interesting enough layer of security since you could take another people session id.

So what can crypto propose against chance ?

Thanks,

-
Why do you feel that it is a problem? The solution crypto gives to this issue is simply lowering the probability enough (in a measurable and concrete way) to be deemed negligible. Again, just because a probability is not zero doesn't mean it's going to happen. –  Thomas Jan 13 at 11:38
This is the reasoning behind the notion of indistinguishability. In short, if an attacker has "negligible" advantage over a purely random system, the system can be said to be semantically secure. So modern cryptography tries to ensure that secrets are overwhelmingly improbable to be guessed at random — it would take so many attempts at guessing that under ideal conditions, one would require more energy than exists in the galaxy to have a decent chance at correctly finding the secret. –  Stephen Touset Jan 13 at 21:14

The probability of someone 'getting lucky' with a guess at a key for a decent cryptosystem is crazily low, but yes: it is possible. However, there are methods that can 'survive' even this.

For example, consider the one time pad. In this system the key and plaintext are xor'd together to form the ciphertext, and to decrypt you xor the ciphertext and key.
So, what happens if the attacker guesses the correct key? Well, he can xor it with the ciphertext, and will be left with the plaintext. However, what happens if he guesses a different key? This will also leave him with a possible plaintext, which to the best of his knowledge could have been the intended message. Thus even if he guesses the correct key, he won't have any way of knowing that he was right.

This is called information theoretical security: If the ciphertext does not contain any information (in the formal sense) about the plaintext, there is no way that an attacker could possibly know when he has correctly found the key.

eg: Suppose the message $m=11111111$ and the key is $k=10101010$. Then we have the ciphertext $c=m\oplus k = 01010101$.

An attacker intercepts $c$, and starts guessing keys. He guesses two possible keys: $k_1=10101010$ and $k_2=01010101$, leading to him reaching two candidate messages: \begin{aligned} m_1 &= c \oplus k_1 = 01010101 \oplus 10101010 = 11111111 \\ m_2 &= c \oplus k_2 = 01010101 \oplus 01010101 = 00000000 \end{aligned}

He has no way of knowing if either of these guesses was correct, even though we (as the original sender) know that in fact he was correct with his guess $k_1$. To him, each possible message $m_i$ is equally likely, so he can conclude nothing. In our example, he has no way of knowing if every bit is set, no bit is set, or indeed something in between.

As an interesting corollary to this, one can (by guessing the wrong OTP key) come up with a possible plaintext that might contain more sensitive data than the original plaintext! For example, if I encrypt $m=\text{I'm just going to buy some milk}$ with key $k$, if the attacker guessed key $k'=k\oplus m \oplus \text{Nuclear launch code=4923...}$ (where 4923... is replaced with the actual launch codes), when they try to decrypt my innocuous message, they would be left with a plaintext telling them the nuclear launch codes. Pretty cool really.

-
It is possible also with AES or 3DES and short messages that it is not possible to distinguish between actual decryption of the ciphertext and other same length alternatives. Basically, this is commonly a feature of the encryption use where the key size is equal or larger than the length of the message. –  user4982 Jan 13 at 16:10
Your explanation and last example got my love :) –  Larry Jan 13 at 19:37

So what can crypto propose against chance ?

Nothing, an infinite number of monkeys typing at random at a keyboard in infinite time will retrieve any password. See http://en.wikipedia.org/wiki/Infinite_monkey_theorem. So surely there's a chance, practically negligible but not impossible.

-

The question is bit absurd. Suppose if someone randomly finds an encryption key in a dream, there is not much cryptography can do against it. Because cryptography relies on secrecy of the keys. You are imagining a similar occasion. Here attacker has somehow found the correct session ID. But you can do few things to stop this