Randomness: where keys come from
Think of a number between 1 and 10. Not out loud, just in your head. You thought of 7. Or else 3. Almost nobody picks 1 or 10, and 7 comes up far more often than the one time in ten you would expect. People are bad at randomness, and that is funny. Computers are bad at it too, and that is not: every lock in the rest of this site hangs on one number nobody must be able to guess.
Words you might need
- Key
- The secret number you will soon use to lock messages. You first use one in chapter 5. This chapter is only about where that number comes from.
- Randomness
- Something with no rule behind it. Roll a die and no amount of calculation gets you the next roll. That is exactly what you want from a key.
- Pseudorandomness
- Randomness that only looks the part. A formula spits out numbers that jump about wildly, but anyone who knows the formula knows all of them in advance. "Pseudo" is Greek for "fake".
- Seed
- The number such a formula starts from. Everything after it is fixed from that moment on. Same seed, same sequence. Always.
- Entropy
- A measure of how much there really is to guess, counted in bits. One coin toss is 1 bit. Eight coin tosses are 8 bits, which is 256 possibilities. The more bits, the more hopeless guessing becomes.
A formula that looks like chance
Just about every programming language has a button that promises "a random number". In most cases what sits behind it looks like this:
next = (previous × 1103515245 + 12345) mod 2147483648
That is all. Take the previous number, multiply it by a big number, add something, and keep the remainder after dividing by 231. The results jump all over the place and look nicely shuffled. They are, for a game or a splash of colour on the screen.
But look at that line again. There is nothing in it you do not know. Anyone who sees one number from the sequence can fill it in and has the next.
Predict the next number
Everything happens in your browser. Nothing is sent to the server.
- Click Five numbers. Look at them and try to work out the sixth yourself. You will not manage it.
- Click Predict the sixth. The demo fills the formula in with the fifth number and puts its prediction next to the real answer.
- Click Real randomness, then Predict the sixth again. Read what happens then.
Where real randomness comes from
A computer cannot invent anything by itself. What it can do is measure things
nobody can replay: how many microseconds passed between two of your
keystrokes, how warm the chip is right now, exactly when a packet arrived
from the network. That is messy, unrepeatable noise. The operating system
piles that noise up, stirs it, and hands you bytes out of it. In the browser
that tap is called crypto.getRandomValues(), and everything on
this site that makes a key uses it.
The difference with the formula above is not that one is better shuffled than the other. It is that with the tap there is no rule to fill in.
The key that came out of the clock
Now the mistake people really have made. You want a key, you have a formula, and you need a seed to start from. What do you take? Something always to hand that is different every time: the clock.
That sounds reasonable. Count along. A 128-bit key has 340 282 366 920 938 463 463 374 607 431 768 211 456 possibilities. But if it came out of the clock and the attacker knows within the hour when you made it, then 3600 possibilities are left. Not 2128. Three thousand six hundred.
Crack a key made from the clock
Everything happens in your browser. Nothing is sent to the server.
- Click Make a key. The demo picks a moment in the past hour and makes 16 bytes out of it. You get to see four.
- Click Find the rest. The demo tries every second of the past hour until the first four bytes match.
- Look at how many tries it took, and compare that with the 39-digit number above.
This has happened for real, twice. In 1995 Netscape, the browser of the day, seeded its keys with the time and the number of the running program. Two students at Berkeley, Ian Goldberg and David Wagner, needed less than a minute of computing time. And in 2008 it turned out that two years earlier someone had removed a line from the Debian build of OpenSSL that fed in the noise. What was left was the number of the running program: 32 768 possibilities. Every key made on such a machine in those two years had to go. In both cases the mathematics was fine. The seed was not.
Rolling a key yourself
You do not need a computer to get real randomness. A die will do, and you can work out how many times you need to roll. Every roll has six outcomes, and six possibilities are worth log2(6) = 2.585 bits. So for 128 bits you need 128 ÷ 2.585 ≈ 50 of them.
Fifty rolls
Everything happens in your browser. Nothing is sent to the server.
- Click Roll and watch the counter scrape bits together.
- Click Roll ten times a few times until you reach 128 bits.
- Look at the key that comes out. That is one you really could have made with a die on paper, and it comes in handy again in chapter 9.2.
This is not just a party trick. People who keep a key that something real depends on sometimes roll it exactly like this, on a computer that has never been near a network. A die has no manufacturer you have to trust.
What you take away from this
| Where the number comes from | Good for |
|---|---|
| A formula with a seed | games, shuffling a playlist, a splash of colour |
| A formula seeded with the clock | nothing with a secret hanging on it |
crypto.getRandomValues() | keys, passwords, everything on this site |
| A die, fifty times | keys, and you have to believe nobody |
From the next chapter on we start using keys, and then it is all about how strong they are: 128 bits, 256 bits, numbers with dozens of digits. Keep this chapter in the back of your mind. Such a number is exactly as strong as the randomness it came out of, and not one bit stronger.
This is math: information theory
The bits you watched adding up with the die are called entropy, and you work them out with a logarithm: a choice between n equally likely possibilities is worth log2(n) bits. That is why a coin toss counts for 1 and a die for 2.585. Claude Shannon wrote that formula down in 1948, in a single paper that opened the whole field of information theory. He did not come up with it for secret writing but for telephone lines: how much can you push down a wire before the noise wins? A year later he showed that the same measure tells you exactly when a cipher is unbreakable. You run into that result in chapter 9.2. Information theory sits today in every file format that compresses, in every photo you send, and in the question of how much you do not actually know.