Table of contents
Open Table of contents
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 and that expresses the likelihood of an event occurring. The higher the value, the more likely it is that the event happens.
A value expresses that “the event never happens”, whereas a value of indicates that “the event always happens”.
This implies that a 50% chance of an event taking place can be expressed through the value .
Probability in Cryptography
In Cryptography, we’re often interested in the likelihood of an attacker breaking a construction.
This probability can be expressed via a calculation where the number of successful events is divided by the total number of possible events.
If we want to calculate the likelihood of an event not happening, we need to subtract the probability that the event happens from .
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 key that was used and we also know that there are possible keys we need to try. Using the formula from above we can calculate the success probability of such an attack as follows.
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.
As we can see, it’s very likely that the key we picked randomly is the wrong one.