Understanding Entropy and Randomness (once and for all)

Introduction

This article explains entropy and randomness in the context of information security.

Both concepts are important, but they are not easy to understand. Many people need to study them more than once before the ideas become clear. This article gives a simple and correct explanation.

Randomness

What is randomness, and why do we need it?

In information security, we use randomness in many applications.

One application is the generation of secrets, such as passwords. A generated password must be truly random. If an attacker can guess a password (for example, a password for an online banking account), the attacker can use that guess to break in. For this reason, a password must be as random as possible. The only realistic attack on the password must be brute force. Brute force means the attacker tries every possible value, one after another.

An example of weak randomness

Consider a password that is generated from a 64-bit timestamp. This is a weak method, for the following reason.

Assume an attacker knows the password was generated during the last week. The attacker does not need to test every possible timestamp. The attacker needs to test only the timestamps from that week. This gives 604'800 possible values (60 × 60 × 24 × 7). A modern computer can test about one million values per second. At this rate, the attacker finds the correct password in less than one second.

An example of strong randomness

Now assume the full 64 bits of the password are generated at random, with no shortcut like a timestamp. In this case, the attacker faces far more than 600'000 possible values.

Assume each bit is generated by a fair coin flip: 1 for heads, 0 for tails. The attacker must now search the full key space, every possible combination of 64 bits. This gives 2⁶⁴ possible values, or 18'446'744'073'709'551'616 (about 18,4 quintillion). If the attacker uses the same computer as before, at one million guesses per second, the search takes about 1,8 × 10¹³ seconds. This is approximately 585'000 years.

How do we know a value is truly random?

A secret with X bits of length is secure only if the attacker must search the full 2ˣ space to find it. This raises a practical question: how do we confirm that a generated value is truly random, and not predictable? To answer this, we use the concept of entropy.

Entropy and Min-Entropy

Shannon Entropy

Entropy, in this context, is a measure of average uncertainty. It was introduced by Claude Shannon in his foundational work on information theory.

Shannon Entropy answers the following question: how many bits of information are needed, on average, to describe the outcome of a random process? Consider a fair coin flip. Heads and tails each have a probability of 50%. Before the flip, an observer cannot predict the result with certainty, because both outcomes are equally likely.

When every outcome in a set has equal probability, the distribution is called uniform. For a fair coin, the result space is {heads, tails}, with probabilities {0.5, 0.5}. A uniform distribution over two outcomes has an entropy of exactly 1 bit. This means one binary digit is enough, on average, to describe the result of one flip.

Shannon’s formula for entropy is:

H = −Σ p(x) · log₂ p(x)

Here, p(x) is the probability of each possible outcome x, and the sum is taken over all outcomes.

The limitation of Shannon Entropy

Shannon Entropy has one limitation for security purposes: it describes the average uncertainty across all outcomes, not the worst-case uncertainty for a specific attacker.

Consider an unfair coin: 90% probability of heads, 10% probability of tails. Applying Shannon’s formula gives an entropy of approximately 0.469 bits. This value is close to 0.5 bits, even though one outcome is nine times more likely than the other. For security analysis, this figure is misleading, because it does not reflect how easily an attacker can guess the outcome.

Min-Entropy

For this reason, information security uses Min-Entropy instead of Shannon Entropy. Min-Entropy measures the uncertainty that remains after an attacker makes their single best guess. It answers the question: how much resistance remains against the attacker’s most effective guessing strategy?

Consider the unfair coin again. A rational attacker will always guess heads, since heads occurs 90% of the time. This guess succeeds with 90% probability. The Min-Entropy measures the remaining 10% probability, the chance the attacker’s best guess is wrong.

Min-entropy is calculated as:

H_min = −log₂(p_max)

Here, p_max is the probability of the most likely outcome. For the unfair coin, p_max = 0.9, and H_min = −log₂(0.9) ≈ 0.152 bits.

This value is much lower than the Shannon Entropy value of 0.469 bits. It reflects the real-world risk more accurately, because it reflects the attacker’s actual best strategy, not an average across all outcomes.

Conclusion

A secure system forces an attacker to rely on brute force to recover a secret. This is only true if the secret is generated with sufficient randomness.

To generate secrets that resist brute force, we need a source of truly random bits. To confirm that a source produces truly random bits, we measure its entropy, specifically its min-entropy, since this reflects the worst case for a defender. In summary: entropy measures the degree of uncertainty in a value, and for security purposes, this uncertainty should be as high as possible.

Literature

• Randomness: https://en.wikipedia.org/wiki/Randomness
• Randomness Requirements for Security: https://www.rfc-editor.org/info/rfc4086/
• Entropy (information theory): https://en.wikipedia.org/wiki/Entropy_(information_theory)#References
• Min-Entropy: https://en.wikipedia.org/wiki/Min-entropy
• A Mathematical Theory of Communication by Claude Shannon: https://web.archive.org/web/19980715013250/http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf

Understanding Entropy and Randomness (once and for all) was originally published in Clear Byte on Medium, where people are continuing the conversation by highlighting and responding to this story.