Analog Random Character Generator

I've been giving away little decks of cards with the following write-up since 2007. I figured it was time to make them publicly and freely available for non-commercial use. This presentation as well as a Microsoft Word document that will print on Avery 5877 business card stock are checked into my project on GitHub.

Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.
- John von Neumann 1951

Computers are deterministic state machines - totally incapable of producing anything random. They employ pseudorandom number generators: functions that appear to produce random output with respect to their input. Good pseudorandom number generators (PRNGs) can produce thousands of values a second with a surprising degree of entropy. But even the best PRNG is limited by the variability of its “seed” or input values, and none have perfectly even distribution or an absence of patterns in their output.

Cards are much slower than PRNGs, but a deck can be shuffled in such a way that no-one can predict the order. This deck contains 52 letters (26 uppercase and 26 lower), 10 numbers (0-9), and 33 other symbols for a total of 95 cards. It was designed to create truly random passwords, keys, and other security tokens for use with computers.

Instructions

Always shuffle well before dealing a new key to ensure a highly random deck. Shuffling between each draw will yield the most random results, but a very high degree of entropy can be obtained by shuffling after every 5 to 9 characters. Vary the number of characters between shuffles to avoid dividing your key into n-character blocks and providing a (small) foothold for attackers. It’s a good idea to shuffle at least once mid-key to allow the possibility of a repeated character. If you occasionally deal yourself a real word, place, or person, throw it out and start over. When you are done, shuffle your deck so that you don’t leave the top or bottom cards in the order of your password.

Remember to keep your keys electronically encrypted and/or physically secured. Remember that the 32 symbols in this deck can cause problems in certain contexts (the * at the command prompt, for instance) so make sure to encode or discard any characters that would be troublesome for your application.

Bits of Entropy

In cryptography, key size, measured in bits (or powers of 2), represents the number of keys which must be tested to break an encrypted message by brute force. But encryption algorithms are generally “lossy” because, being deterministic, they have some degree of predictability and/or collisions of different keys producing the same output values. Some algorithms are “lossier” than others and there are many statements in the literature to the effect that a 1024-bit key using one algorithm is just as secure as an 80-bit key using another. That means one algorithm is 1.49×10284 times more secure than the other! Despite common misuse in advertising claims, bits are the “standard” unit of entropy. In this writing, they represent a mathematically derived number of equally likely possible combinations, expressed in powers of 2 - not the computer space used to store a value generated with a PRNG.

Using the 95 standard ASCII characters printed on these cards, there are 10148 possible deck orderings (that’s 492 bits of precision). By shuffling every few characters, any desired level of entropy can be achieved. There are 79 bits of entropy in a 12-character key (that’s 5.40×1023 possible keys) which is about 33,000 times the precision of the most theoretically random 64-bit value a computer could possibly generate. Even a 5-character key has 7.73×109 possible values, which is almost twice the precision of a 32-bit number.

Dirty Secrets of PRNGs

"We guarantee that each number is random individually, but we don't guarantee that more than one of them is random." Figure that out.
- Press, William H., et al. 1992 referring to RANDU

Given the same initial input, a PRNG will not only produce the same output value, but will produce the same sequence of values every time, and that sequence is generally your cryptographic key, password, or hash. The “moving parts” inside most PRNGs are 64-bit and 32-bit registers and this limits their entropy. But PRNGs are often more limited by the precision of their input or seed. Since the few somewhat random processes in the computer tend to produce clusters of values, they are unsuitable as random number seeds. The only part of the computer that produces an even dispersion of values is the system clock, which measures milliseconds.

There are only 8.64×107 milliseconds in a day. That’s about 26 bits of entropy. Without shuffling, you can deal yourself a stronger key in only 5 cards! So why not use a longer time frame? There are 3.1×1011 milliseconds in 10 years which is only 38 bits of entropy – and who has a password older than 10 years? Most people generate their keys at work, between the hours of 9-5 M-F which is only ¼ of the hours in the week, so you might be loosing about 2 bits of entropy there.

So even if you have a 64-bit random number generator, unless you can get a seed with more than 36 bits of entropy, you only get 36 bits of entropy in your key. That’s the same number of significant digits in a truly random 6-character key (956). How many significant digits of randomness does any computer generated encryption key contain? No more than the significant digits of entropy used to create it times the number of PRNG algorithms that could have been used. In 2008, that often means the time and the process ID (a number generally between 1 and 32,767) combined which yields 9.9×1015 likely combinations or 54 bits of entropy. If process IDs were truly random (they are not), you can deal yourself more entropy in 9 cards than state-of-the art automatic password generators on consumer operating systems can generate.

PRNGs that accept mouse or keyboard input, hardware PRNGs, and entropy-gathering daemons are significant improvements, but without an exhaustive analysis, it is difficult to judge their true effectiveness. Playing cards have been reliably generating entropy since they were invented in 12th century China.

Analysis: Shuffling Every Card

Random numbers should not be generated with a method chosen at random.
- Donald E. Knuth

Assuming you shuffle between each card, the table below shows the number of possible combinations for each length of key. The column headings have the following meanings:

• n: length of key
• 95n: Number of possible keys of the given length (n). Repeated characters are allowed.
• log2(95n): This is an approximate value corresponding to the nearest number of bits of entropy.
• Crack: the time a 3Ghz processor would take to brute-force generate half the keys of this length. Most encryption algorithms would slow this down significantly, but serious crackers would use much more horsepower. YMMV.
• Relevant Numbers: Real world examples with the same magnitude as the number of possible keys.

n	95n	log2(95n)	Crack	Relevant numbers
1	95	7	0
2	9025	13	5 ms.
3	857,375	20	½ sec.
4	81,450,625	26	15 sec.	Number of milliseconds in a day.
5	7.73×109	33	30 min	Number of milliseconds in 4 months.
6	7.35×1011	39	2 days	Trillions (125 Gigabytes). Number of milliseconds in 20 years.
7	6.98×1013	46	1 year
8	6.63×1015	53	70 years	256 The original key length for DES encryption.
9	6.30×1017	59	7,000 years	Quintillions. The age of the universe in seconds.
10	5.98×1019	66	600,000 years
11	5.68×1021	72		Number of stars in the universe
12	5.40×1023	79		Septillions. Avogadro’s number – the number of atoms in 12 grams of carbon-12
13	5.13×1025	85
14	4.87×1027	92
15	4.63×1029	99
16	4.40×1031	105
17	4.18×1033	112
18	3.97×1035	118
19	3.77×1037	125
20	3.58×1039	131

Analysis: Without Shuffling

If you deal a key without shuffling, the number of possible next-characters decreases every time one is dealt. The formula for possible combinations of each card dealt is: 95 × (95 - 1) × (95 - 2) × ... × (95 - (n - 1)) where n is the length of the key (number of cards dealt). The table below is meant for comparison against the table above for the purpose of deciding how often you want to shuffle when you deal a key. The formula column just shows how the Number of Combinations was derived, since it’s a little different for each card dealt. A mathematician might write the formula using capital pi notation to represent the product of a sequence, in this case the sequence of numbers, from 95 down to 95 - (n - 1) multiplied by each other:

Or, using permutation notation:

n	# combinations	log2(95n)	Formula
1	95	7	95
2	8,930	13	95×94
3	830,490	20	95×94×93
4	76,405,080	26	95×94×93×92
5	6.95×109	33	95×94×93×92×91
6	6.26×1011	39	95×94×93×92×91×90
7	5.57×1013	46	95×94×93×92×91×90×89
8	4.90×1015	52	95×94×93×92×91×90×89×88
9	4.26×1017	59	95×94×93×92×91×90×89×88×87
10	3.67×1019	65	95×94×93×92×91×90×89×88×87×86
11	3.12×1021	71	95×94×93×92×91×90×89×88×87×86×85
12	2.62×1023	78	95×94×93×92×91×90×89×88×87×86×85×84
13	2.17×1025	84	95×94×93×92×91×90×89×88×87×86×85×84×83
14	1.78×1027	91	95×94×93×92×91×90×89×88×87×86×85×84×83×82
15	1.44×1029	97	95×94×93×92×91×90×89×88×87×86×85×84×83×82×81
16	1.15×1031	103	95×94×93×92×91×90×89×88×87×86×85×84×83×82...×80
17	9.12×1032	109	95×94×93×92×91×90×89×88×87×86×85×84×83×82...×79
18	7.12×1034	116	95×94×93×92×91×90×89×88×87×86×85×84×83×82...×78
19	5.48×1036	122	95×94×93×92×91×90×89×88×87×86×85×84×83×82...×77
20	4.16×1038	128	95×94×93×92×91×90×89×88×87×86×85×84×83×82...×76

The benefit of adding characters without shuffling drops off dramatically as the number of characters nears 94. For example:

• By the 9th character, you loose one bit of precision (half as many combinations without shuffling as you would with shuffling). This should not make a difference for most applications.
• By the 15th character you have about ¼ as many combinations (2 bits). But ¼ of a really big number is still a really big number.
• By the 18th character, 3 bits of precision are lost (1/8 the combinations).
• By the 32nd character, at least one more bit of precision is lost for each additional character (there are only 64 or 26 characters left providing 6 bits of entropy instead of 7)
• The 80th character provides only 4 bits of entropy (there are 16 characters left unaccounted for)
• The 94th character provides only 1 bit of entropy (only 2 possibilities)
• The 95th character provides no additional entropy (The only card left is totally determined by the 94 that came before it).