02.18.04
 By
A.P. Lawrence
Random numbers are important for computers. Aside from making games
like Solitaire more interesting, the use of randomness in generating
passwords and encrypting data is critical to security.
Until fairly recently, cpu's had no direct way to generate random
numbers. Intel's Pentium III introduced a hardware random number generator
that uses thermal noise "to generate high-quality random and nondeterministic
numbers" , but prior to that systems that needed good random numbers
had to relay on add-on boards or other external input.
The problem, of course, is that the whole point of computer programming
is predicability: given the same input, a program will always follow
the same path to completion. That makes it impossible to generate
random numbers with an algorithm. |
For
all we know, it may be impossible, period. While thermal noise from
a semiconductor certainly seems random to us, if we really understood
the physics, it might not be at all. If string theory is real, then
the arrangement and orientation of these "strings" might affect their
vibration, which in turn affects the behavior of electrons, etc. It's
quite possible that the universe is deterministic - we really aren't
in any position to even guess right now.
The real question is, does it matter? And the answer is both "yes,
it does" and "no, it doesn't", depending on why you asked. On the
one hand, we have apparently non-deterministic events like how many
visitors this web site will have today. That's an apparently very
random number, determined by perhaps hundreds of conflicting factors
such as news events, advent of security challenges, the weather, Google
rankings: well beyond any ability to calculate. Yet, it's pretty easy
for me to guess within a few hundred what that number will be because
in large enough populations, the random behavior of individuals is
unimportant: statistics and other indicators can tell us what the
general group behaviour will be. From this point of view, it doesn't
matter if individuals are non-deterministic because group behavior
is not.
On the other side, things that really aren't random at all can be
quite random enough for a particular need. For example, if you had
to "randomly" select from a group of 60 items using a computer program,
a very simple way to do it would be to use seconds from the current
time: if your user runs the program at 23 seconds past the minute,
the program selects item 23. This isn't random at all; it's very deterministic.
If there was any reason for your users to care about which of the
sixy items were selected, they could find ways to "cheat" your program
fairly easily. But if it isn't important, the selection may in fact
be quite random enough for your needs. The underlying method isn't
random, but it appears to be for the expected use, so the algorithm
works. Apparent randomness from a very non-random source.
That is the problem with computer generated "random" numbers: they
may not be very random at all. Almost all computer languages have
some method of selecting a random number, but in fact it's not really
random. This Perl script will generate the same results every time
it is run:
If you saw that run once, you'd think it was giving you random numbers.
Run it again and you get the same ten numbers. The numbers will not
change no matter how many times you run it, so obviously they aren't
random at all. That's because it is really only pseudorandom. The
argument given to srand seeds the random number generator, and it
will always generate the same numbers in the same order for the same
starting seed. However if we seed "srand" with something more random
(or more apparently random), we get better results:
This has every appearance of generating random numbers. Yet, a cryptographer
would warn you not to rely on that for encrypting bank accounts, because
just like our simplistic selection from the sixty items, the seed
actually isn't random and given sufficient incentive, that flaw could
be very costly.
So how do you get more random? Linux and other operating systems may
provide a "/dev/random" and "/dev/urandom". Don't assume you know
how these work: Mac OS X and Linux both have these, but the man pages
are quite different. If your use is casual (you aren't protecting
Fort Knox), the differences are probably unimportant, but "man 4 random"
is interesting reading anyway.
Perl has a "TrulyRandom" module that uses interrupt timing discrepancies
to get random numbers; but do we know that the discrepancies are truly
non-deterministic? Like the thermal activity of a semiconductor, it
might actually be predictable. With sufficient knowledge and computing
power, any of these things might be as trivial as our "random second"
implementation.
Many systems have the PRNG
library - many versions of SSH use that. If you've ever generated
a GPG key, you
probably remember this:
We need to generate a lot of random bytes. It is a good idea
to perform some other action (type on the keyboard, move the mouse,
utilize the disks) during the prime generation; this gives the random
number generator a better chance to gain enough entropy.
These unpredicable actions on your part were used to seed the random
number generation.
Much attention is paid to the importance of avoiding predicability
in random numbers, and yet as we have seen from the most recent ssh
exploits, the random numbers used in encryption are only a very small
part of the total picture. It was other weaknesses in the ssh code
that were exploited, and the encrypted keys were not important at
all. The thickest deadbolts on your front door are useless if the
back door is wide open.
About the Author:
A.P. Lawrence provides SCO Unix and Linux consulting services http://www.pcunix.com
Read this newsletter at: http://www.securitypronews.com/2004/0218.html |
| | From the Forum: | | Cannot connect | I cannot connect to the internet. I previously have used juno and aol with no problems. I have quit aol and went to start using juno free but i cannot connect at all now. It connects and immediately hangs up. I have tried reinstalling dialup networking, and adjusting all modem settings to no avail. Can anyone suggest anything??
Thank you. |
 |
|
