[Courses] [security] Random number generators (was: Crypto Scientists Crack Prime Problem)

[Raven Alder]

Heya --

Quoth Megan Golding (Wed, Aug 14, 2002 at 04:00:46AM -0700):
> > what are the general sources of randomness people use to issue key
> > pairs?
> 
> I've seen a few techniques used: 
> 
> Take lots of mouse positions after instructing the user to move the
> mouse for some time. The positions wind up seeding the key
> generation.
> 
> Take keyboard input. Ask the user to type "random" stuff and use that
> to seed the key generation.

	These are generally not very random, though, since people will
actually type in semi-predictable patterns when asked to type randomly.
Ditto for mouse movement.  "Random" typing usually results in people
mashing the middle of the keyboard a lot, and in quick succession.  So
you get something like 

hdsfkjahsioduytseadnvmdv alshdlfhsidruidnfsdk fsdifjsoiad fjsiodfja

as input most of the time.  Note the absence of capitalized characters,
numbers, punctuation marks, anything like that.  The fingers don't move
more than they have to.

	I've not seen any attacks based on this in particular, but I am
reasonably convinced that it could be done.
 
> Tells developers (at a high level) how to obtain random seed data:
> http://download.baltimore.com/keytools/docs/v50/ssl/j-docs/html/ssljdevguide-11.html
> 
> Someone from Netscape proposes add'l ways to get random seeds:
> http://www.msg.net/utility/FWTK/netscape-random-seed.html

	Also, some Unixes have a device called /dev/random or something
similar that can be accessed to provide random seeding input from the
kernel.  Linux generally does -- /dev/random gets its random input from
unrelated device drivers, and will return as much randomness as it has.
/dev/urandom will return as much randomness as you've asked for -- so if
you have only 16 bits of randomness and you ask for 32, the last 16 may
not be truly random in the good-for-crypto sense.  FreeBSD also has a
/dev/random, and there are various workarounds for Solaris.  Sol 9 does
have a random number generator, and there's a patch available for 8, but
anything before that and you're probably out of luck.

	On your Linux system, you should be able to "man random" to read
all about it, or just read this:

http://nodevice.com/sections/ManIndex/man1271.html 

	If your crypto program uses a pseudorandom number generator,
there are also programs to test just how random (high in entropy) your
output is.  For example:

http://www.fourmilab.ch/random/

Ent is fairly often recommended for this from what I've seen.

Cheers,
Raven
 
"Do you know where the RSA t-shirt is?"
"No." 
"Well, I need the algorithm, so I'm doing laundry."
  -- me and RavenBlack