Chance in cryptography

Question

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,

Answer 1

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.

Answer 2

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.

Answer 3

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

1. Use SSL and make your cookies HTTPS only.
2. Fix your cross site scripting vulnerabilities in your code.
3. Find a good random number generator so you can get a output with high entropy. It can be used to generate the session ID.