Friday, March 2, 2012

Practical sources of randomness for key generation

As promised, here are some suggestions about sources of randomness suitable for use on systems that allow entropy input to their random number generator via external typing. 

Dice
This is the Diceware™ blog, after all, so it's appropriate to start with this ancient but highly dependable source of entropy. Each roll of a die has six possible outcomes, yielding 2.58 bits of entropy [log2 (6)]. To get 128 bit of entropy, you'll need to type in the outcomes of 50 rolls. Putting 10 dice in a box with enough room to shake them up would let you enter the required number of rolls in 5 operations.

Type the outcomes of the dice rolls into whatever program you are using to generate keys, assuming it allows such input. If not, and you are using Unix-like operating system, such as Linux or Mac OS X, you can enter the entropy into its /dev/random generator.  Bring up a terminal window and type at the prompt: 

    cat >/dev/random 

followed by return. Then enter the dice rolls or one of the random string generated by other methods described below. Type Control-D when your done.

Mistakes when you're typing in these random strings just add more randomness, so if you type something wrong, don't go back, just type in the correct value and continue. 


Playing cards
Paying card are another good source of randomness, assuming they have been properly shuffled.  Seven through riffle shuffles are needed for full randomness; do a couple more for good measure. Wikipedia has a nice article on various shuffling techniques.  http://en.wikipedia.org/wiki/Shuffling A fully shuffled deck has 225 bits of entropy [log2(52!)].  The first card dealt has 5.7 bits of entropy, [log2(52)] and the amount per card decreases slowly as more cards are dealt. To get 128 bits of entropy, you should deal out 25 cards. Type in the cards including the suit, for example, you'd type

    3djs10hac …

for the 3 of Diamonds, Jack of Spades, 10 of Hearts, Ace of Clubs, and so on. There's no need to put spaces delimiters between the card values. Here is a full example that took me about 80 seconds to type in:

     4d3s4c10s2hqc5c10c3dqs6hah2dkd3hjs10dqd7s3c9s8c7c6s8h

If you need more entropy, say 256 bits, shuffle the deck again and type in another 25 cards. The deck should be shuffled again after you are done so no one can reproduce what you typed in.

Video camera 
Another way to generate randomness is to take a picture with a computer's webcam and "digest it" with a cryptographic hash function. The old saying, "a picture is worth a 1000 words" is an understatement in the computer world. Camera images typically take half a million bytes of memory or more. 

There are two sources of randomness in a digital photograph: randomness inherent in the image content and electrical noise generated by the image capture hardware. The later is likely more than enough for our purposes, but since it is not feasible to test every camera and lighting situation that my occurs, we might as well use both sources.

Here are instructions for doing this on a Mac:

1. Find and and and open Photo Booth, then take a picture. Save the snapshot file on the desktop using an uncompressed format such as TIFF.

2. Open a terminal window and type the following at the prompt (don't hit return yet):

       $ openssl dgst -sha512 

3. Drag the picture from Photo Booth picture file onto the terminal window. The Terminal program will add the file path to  the command string.

4. now type:  > /dev/random

5. Finally delete the Photo Booth picture using Finder -> Secure Empty Trash

It probably doesn't matter what you point the camera at--there should be enough noise in any camera image--but here are some suggestions:

o Trees outside your window

o Your head, especially if you had a bad hair day

o A cluttered (physical) desktop

o The screen of an old analog TV tuned to a nonexistent station. 

The last is a good choice if you want to set up a webcam as a permanent resource, say for initializing virtual machines. You'll need to write a script that mounts the camera device, takes a photo, hashes it into the randomness generator and then releases the camera for the next virtual machine.
Sound input
Even if your computer does not have a camera, you can grab random data using its audio input or microphone.  If your computer does not have a sound capture utility, you can download a free one for Windows,  Mac or Linux at http://audacity.sourceforge.net (Mac's with ILife already have GarageBand, though it's a bit complicated for this task.)

For a sound source, use a radio tuned between stations. An AM radio is preferable because FM sets tend to lock on to the nearest strong signal. If your in a noisy computer room, that might do in itself. Record 15 seconds or so of noise and save the file to the desktop, preferably using an uncompressed format (choose Export from the Audacity file menu). Then follow the steps for camera input, above. Don't forget to clean up by securely erasing the sound file when your done.

4 comments:

  1. Very nice summary. I found your blog while working on a post about pseudo-random number generators. I added a link to your article in the footnotes, I hope you don't mind.

    I like the incorrectly tuned TV idea, though I suppose you would get some (partly) predictable patterns from neighbouring channels.
    Another source of entropy (used in particular y TrueCrypt when generating new key pairs) is mouse motion: they ask you to move your mouse "as randomly as possible", and record the motion.

    ReplyDelete
  2. You would get some predictable signal, but if there is enough noise, hashing should produce good quality entropy.

    ReplyDelete
  3. Two dice have 36 possible outcomes, supposing the two dice to be distinguished. By chance, the total number of possibilities in an alphanumeric code, assuming a single case is used, is 36 – i.e. twenty-six letters (A-Z) plus ten numbers (0-9).

    If two dice are thrown together, using a simple conversion table, the result can be recorded as a letter or number, thus halving the length of the passcode without any loss of entropy. The fifty dice throws you recommend can be reduced to an alphanumeric code of twenty-five.

    ReplyDelete
  4. If you are trying to generate a password to memorize, then your conversion to a letter/digit makes sense and I mention this on my diceware.com FAQ. But if you are just entering random data to, say, create a GPG key, then typing in the 50 numbers from 1 to 6, instead of converting pairs to letters/digits, may be easier. It's a matter of taste, the security is the same.

    ReplyDelete