Probability

Open Table of contents

What it is
Ranges of probabilities
Probability in Cryptography
Brute-force key search
References

What it is

Probability is a very useful and important topic to study in the context of Cryptography as it’s closely related to randomness, which is the underpinning of most cryptographic constructions.

With the help of probability we can calculate the likelihood of an event happening / not happening and therefore estimate the security guarantees an algorithm based on randomness provides (e.g. a key generation algorithm).

Ranges of probabilities

The result of a probability calculation is a value between $0$ and $1$ that expresses the likelihood of an event occurring. The higher the value, the more likely it is that the event happens.

A value $0$ expresses that “the event never happens”, whereas a value of $1$ indicates that “the event always happens”.

This implies that a 50% chance of an event taking place can be expressed through the value $0.5$ .

Probability in Cryptography

In Cryptography, we’re often interested in the likelihood of an attacker breaking a construction.

This probability $p$ can be expressed via a calculation where the number of successful events is divided by the total number of possible events.

p = \frac{successful}{total}

If we want to calculate the likelihood of an event not happening, we need to subtract the probability $p$ that the event happens from $1$ .

1 - p = 1 - \frac{successful}{total}

Brute-force key search

As an example, let’s assume that we have a symmetric cipher that uses a 256-bit key for encryption. We know that the cipher itself doesn’t expose any design flaws that can be exploited to recover a plaintext given its corresponding ciphertext.

The only attack we can deploy is a brute-force key search in which we simply try every possible key and see if the key allows us to decrypt the ciphertext.

How likely is it that we’ll be successful using such an attack?

We know that there’s exactly $1$ key that was used and we also know that there are $2^{256}$ possible keys we need to try. Using the formula from above we can calculate the success probability of such an attack as follows.

\begin{aligned} p &= \frac{successful}{total} \\ p &= \frac{1}{2^{256}} \\ p &= 0.0000000000... \\ p &\approx 0 \end{aligned}

This shows that it’s highly unlikely that the key we’ve chosen at random is the correct one. Conversely we can also calculate the likelihood that the randomly chosen key is the wrong one.

\begin{aligned} 1 - p &= 1 - \frac{successful}{total} \\ 1 - p &= 1 - \frac{1}{2^{256}} \\ 1 - p &= 1.0000000000... \\ 1 - p &\approx 1 \end{aligned}

As we can see, it’s very likely that the key we picked randomly is the wrong one.

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.