outer@utcsri.UUCP (Richard Outerbridge) (03/12/85)
Looking over the various schemes proposed for key generation and management it seems that one of the basic, really fundamental, requirements is a source of truly random numbers. All the master keys these schemes use are assumed to be truly random (generated off-line using die or lima beans, whatever) and much of the subsequent effort is devoted to constructing pseudo-random shadows of these original truly-random seeds. I also seem to recall that one of the specifications that Alan Turing made for the ACE computer way back when is that it include a hardware device capable of generating truly random numbers. Such a facility would doubtless be useful in other areas besides cryptography. Davies&Price advise that hardware random number generation is indeed practicable, albeit fraught with as many statistical pratfalls as ordinary pseudo-random number generation. It can't be that hard though. So, why do so few supposedly modern computers include a hardware random number generator? I mean really, every decent library includes at least one flawed-in- one-way-or-another pseudo-random generator so its not as though its an esoteric application. Why no hardware random numbers? -- Richard Outerbridge <outer@utcsri.UUCP> (416) 961-4757 Payload Deliveries: N 41 39'36", W 79 23'42", Elev. 106.47m.
henry@utzoo.UUCP (Henry Spencer) (03/12/85)
> ... Why no hardware random numbers?
Because it's hard to build a hardware random-number generator that
will be unbiased and STAY unbiased. There are any number of things
you can use as a source of random analog garbage -- I seem to recall
that thermal noise in a suitable semiconductor is a reasonable choice --
but converting them into bits that are reasonably evenly distributed
(and will stay that way without constant readjustment) is harder.
Plus, there is minimal demand. The reproducibility of pseudorandom-
number generators is a feature, not a bug, for most purposes.
--
Henry Spencer @ U of Toronto Zoology
{allegra,ihnp4,linus,decvax}!utzoo!henrypdbain@wateng.UUCP (Peter Bain) (03/13/85)
In article <868@utcsri.UUCP> outer@utcsri.UUCP (Richard Outerbridge) writes: > >So, why do so few supposedly modern computers include a hardware random number >generator? I mean really, every decent library includes at least one flawed-in >one-way-or-another pseudo-random generator so its not as though its an esoteric >application. Why no hardware random numbers? >-- The Ferranti Ferret (I believe), one of the very early machines (made in Canada) had a hardwired random number generator, specifically a gas tube in a magnetic field. The problem with this type of random number generator is that the sequence of values you get is irreproducible, which can be a real drag if you are doing simulations and want to check your results, or you want to try two different algorithms on the same sequence of numbers. The problem of software random number generation has been well studied, it's just that a lot of people go off and do it themselves without knowing what they are doing... -peter -- - peter bain ...!{allegra|decvax|clyde|ihnp4 }!watmath!wateng!pdbain hard mail: CCNG, CPH-2369A, University of Waterloo, Waterloo, Ont. Canada N2M 5G4 telephone: (519) 885-1211 x2810
lauren@vortex.UUCP (Lauren Weinstein) (03/13/85)
People who are REALLY concerned about security have ways of generating random numbers via hardware. That's how the coding sequences for "one time pads" (the most secure encoding system) are generated. There are a number of ways to design the hardware, but one of the best is to use the decay rate of a radioactive element (that is, count and time the geiger ticks) and use that as the "random" source. This is supposed to be one of the most random events known. --Lauren--
gnu@sun.uucp (John Gilmore) (03/13/85)
Intel's new secure EPROM has a supposedly good hardware source of random numbers built in. I don't think you can get at them yourself though, it generates one, encrypts it, and sends it out to be sure you really know the decoding key. I think it's based on random thermal variations but don't remember exactly how.
david@iwu1a.UUCP (scheibelhut) (03/13/85)
In the past hardware random number generators were hard to implement and unreliable because they were based on measuring noise. However, in this era of VLSI chips a hardware random number generator should be easy to build: one could just send the set of integers into an encryption chip and return the result. No one will be able to find any regularity (except perhaps the NSA). David Scheibelhut
jewett@hplabs.UUCP (Bob Jewett) (03/13/85)
> Looking over the various schemes proposed for key generation and management > it seems that one of the basic, really fundamental, requirements is a source > of truly random numbers. ... > So, why do so few supposedly modern computers include a hardware random number > generator? > Why no hardware random numbers? > Richard Outerbridge <outer@utcsri.UUCP> (416) 961-4757 Hardware random number generators exist. You can, for example, amplify thermal noise and count the number of zero crossings in a fixed time interval and throw away the MSB's. One reason PRN generators are preferred is that they will always give the same sequence for a given seed, which can be useful for debugging a program. Bob Jewett hplabs!jewett
jbn@wdl1.UUCP (03/14/85)
One way to build a hardware random number generator is to
get a small radiation source and detector and use the pulses to drive a
counter. Then use the following algorithm to generate one random bit.
1. Count pulses for a time T. Call this count A.
2. Count pulses for a time T. Call this count B.
3. If A=B, start over.
4. If A>B, emit a 1, else emit a 0.
If T is too small, no bits will emerge, but the randomness of the
generator is not affected by the choice of T.
A friend of mine who was developing commodity speculation software
once reached the point of designing an S-100 bus random number generator
using the above technique, but he got out of the S-100 card business before
building it. His problem was that he tested his commodity speculation programs
against a random walk; the ideas is that if they practice good money management
they should not lose badly against a random walk. They were winning. This
is impossible with a true random walk; however, his analysis programs were
picking up patterns in the random number generator and were able to extract
some pattern from the noise.
True random number generators are available commercially for key
generation, from
HAGELIN CRYPTO AG
P.O. Box A-163
CH-6301 Zug/Switzerland
John Naglebrooks@lll-crg.ARPA (Eugene D. Brooks III) (03/16/85)
> So, why do so few supposedly modern computers include a hardware random number > generator? I mean really, every decent library includes at least one flawed-in- In the heaviest users of random numbers, Monte Carlo programs, repeatability is very important. When tracking down a bug being able to generate the same sequence is very useful. Making a REAL random number generator is not very easy. Bias in the hardware can creep in and be very difficult to detect. GEE, did I discover a new effect with my Monte Carlo program or was the random number generator a little off last tuesday. I can't find out because I can't generate the same sequence again.
hugh@hcrvx1.UUCP (Hugh Redelmeier) (03/19/85)
In article <2139@wateng.UUCP> pdbain@wateng.UUCP (Peter Bain) writes: >The Ferranti Ferret (I believe), one of the very early machines (made in >Canada) had a hardwired random number generator. Ther name was Ferrut (Ferranti at U of T). It was actually mostly a British machine (a commercialized version of one of the Manchester machines, if I remember correctly).
rbt@sftig.UUCP (R.Thomas) (03/21/85)
> In article <868@utcsri.UUCP> outer@utcsri.UUCP (Richard Outerbridge) writes: > > > >So, why do so few supposedly modern computers include a hardware random number > >generator? I mean really, every decent library includes at least one flawed-in > >one-way-or-another pseudo-random generator so its not as though its an esoteric > >application. Why no hardware random numbers? > >-- > > The Ferranti Ferret (I believe), one of the very early machines (made in > Canada) had a hardwired random number generator, specifically a gas tube > in a magnetic field. The problem with this type of random number generator > is that the sequence of values you get is irreproducible, which can be > a real drag if you are doing simulations and want to check your results, > or you want to try two different algorithms on the same sequence of > numbers. The problem of software random number generation has been well > studied, it's just that a lot of people go off and do it themselves without > knowing what they are doing... > -peter > -- The Applesoft BASIC system for the Apple II personal computer has a rather poor pseudo random number generator, but a great way of acquiring a truely random seed if the user requests it. None of this 'start from the clock' stuff for them (The Apple II doesn't *have* a hardware clock -- so that wouldn't work.) The routine that reads user keypresses (and waits for the user to press one if need be) increments a cell while it waits for input to become available. That cell is specificly for seeding the random number generator. Is that 'truely random' enough for you? Rick Thomas
herbie@watdcsu.UUCP (Herb Chong [DCS]) (03/21/85)
In article <1139@hcrvx1.UUCP> hugh@unix.UUCP (Hugh Redelmeier) writes: >In article <2139@wateng.UUCP> pdbain@wateng.UUCP (Peter Bain) writes: >>The Ferranti Ferret (I believe), one of the very early machines (made in >>Canada) had a hardwired random number generator. >Ther name was Ferrut (Ferranti at U of T). It was actually mostly a >British machine (a commercialized version of one of the Manchester >machines, if I remember correctly). it was the commercial version of the Manchester Mark I. it's architecture is outlined in a CACM special issue on computer architecture about 1979. Herb...
ed@mtxinu.UUCP (Ed Gould) (03/21/85)
> The problem with this type of random number generator > is that the sequence of values you get is irreproducible, which can be > a real drag if you are doing simulations and want to check your results, > or you want to try two different algorithms on the same sequence of > numbers. > -- > - peter bain It seems, then, that we really need both. A good software PRN generator for testing, reproducing, and debugging, and a hardware RN generator (I don't say pseudo-random, because I'm willing to define certain natural phenomena as truely random) for better randomness. -- Ed Gould mt Xinu, 739 Allston Way, Berkeley, CA 94710 USA {ucbvax,decvax}!mtxinu!ed +1 415 644 0146
karn@petrus.UUCP (03/23/85)
Intel has just announced a "secure eprom" ("Keprom") which incorporates
a hardware random number generator and encryption to supposedly guard the
ROM against copying. The basic idea is that the ROM cannot be read until
it has completed a two-way cryptographic handshake with another of its
kind. In an actual system, one ROM would be permanently attached to the
system board (potted, say) while the other would be on an optional board
and contain the software to be protected.
Despite Intel's glowing writeups ("46 billion years to try every
combination!"), the scheme seems just as doomed to failure as various
attempts over the years to prevent videotape piracy. The basic problem
is that if I grant a legitimate user access to the information (which
I have to do in order for him to pay me) then there is nothing to prevent
him from recording it. If I can get at the data bus of the machine, I can
copy the ROM in one of two ways:
1. Passively watch the address and data busses of the device as it executes
normally in the machine, recording each location as it appears on the bus.
2. If the microprocessor supports DMA, build a bus peripheral that waits
until the ROM handshake has completed and then grabs the bus to do a
DMA dump to an external device.
Oh yes. Their random number generator has a patent pending. They claim
their statistical tests for random showed it to have "practically ideal
randomness."
Philjohn@x.UUCP (John Woods) (03/25/85)
>GEE,did I discover a new effect with my Monte Carlo program or was the random >number generator a little off last tuesday. I can't find out because I can't > generate the same sequence again. > To quote someone truly famous, "GAAAAAAAAAH!" Take the hardware random number generator and dump a few million numbers out to disk. You have a repeatable sequence (and if you have good buffering, it might be a faster repeatable sequence than the RANDU you're probably tempted to use instead). If this seems silly to you, check out the Table of 10,000 Random Digits in your Rubber Bible (you *do* have the CRC Handbook of Mathmatics, don't you?). A few months back, a talk was given at MIT about 'correcting' biased random number generators, but I wasn't interested at the time and didn't attend. Maybe I'll try to dig up someone who knows about it. -- John Woods, Charles River Data Systems, Framingham MA, (617) 626-1101 ...!decvax!frog!john, ...!mit-eddie!jfw, jfw%mit-ccc@MIT-XX.ARPA
franka@hercules.UUCP (Frank Adrian) (03/26/85)
In article <321@mtxinu.UUCP> ed@mtxinu.UUCP (Ed Gould) writes: >> The problem with this type of random number generator >> is that the sequence of values you get is irreproducible, which can be >> a real drag if you are doing simulations and want to check your results, >> or you want to try two different algorithms on the same sequence of >> numbers. >> -- >> - peter bain > >It seems, then, that we really need both. A good software PRN >generator for testing, reproducing, and debugging, and a hardware RN >generator (I don't say pseudo-random, because I'm willing to define >certain natural phenomena as truely random) for better randomness. > Not really. If you want reproducability on a machine with ONLY a hardware RN generator, write a program which samples the generator, puting the results into a file. Then read the file sequentially for a reproducable set of random numbers. This gives both repeatability and "true" randomness. Frank Adrian
mmt@dciem.UUCP (Martin Taylor) (03/27/85)
>> ... Why no hardware random numbers? > >Because it's hard to build a hardware random-number generator that >will be unbiased and STAY unbiased. There are any number of things >you can use as a source of random analog garbage -- I seem to recall >that thermal noise in a suitable semiconductor is a reasonable choice -- >but converting them into bits that are reasonably evenly distributed >(and will stay that way without constant readjustment) is harder. >Plus, there is minimal demand. The reproducibility of pseudorandom- >number generators is a feature, not a bug, for most purposes. >-- > Henry Spencer @ U of Toronto Zoology A long time ago, when Flip-Chips (DEC trademark) were a nice new toy, we built a hardware random-number generator to run psychophysical experiments. We even had a knob to control the bit probability, because we figured that would be a nice way to change the probability of targets for people to look or listen for; and we had a big old meter that told us the current probability (averaged over several thousand bits, by mechanical inertia). It worked pretty well, but we never made another or moved it to a different experiment. Pseudo-random numbers are easier to deal with, as Henry says. -- Martin Taylor {allegra,linus,ihnp4,floyd,ubc-vision}!utzoo!dciem!mmt {uw-beaver,qucis,watmath}!utcsri!dciem!mmt
brooks@lll-crg.ARPA (Eugene D. Brooks III) (03/30/85)
> seems silly to you, check out the Table of 10,000 Random Digits in your > Rubber Bible (you *do* have the CRC Handbook of Mathmatics, don't you?). Yes, I do have one. Along with a half a dozen other mathematics reference books that are as outdated in the stuff they present. These random number lists were put in reference books for the times when computers barely existed and monte carlo was done by hand. The last thing I would do in my monte carlo program would be to enter the random numbers by hand from the CRC table. (I admit to using the table to get lists of seeds.) The same goes for using disk to read a random number list from. The disk is a bit faster but not quite fast enough.
jc@mit-athena.UUCP (John Chambers) (04/01/85)
>>GEE,did I discover a new effect with my Monte Carlo program or was the random >>number generator a little off last tuesday. I can't find out because I can't >> generate the same sequence again. > > ... Take the hardware random number >generator and dump a few million numbers out to disk. You have a repeatable >sequence (and if you have good buffering, it might be a faster repeatable >sequence than the RANDU you're probably tempted to use instead). This does give you the same sequence of random numbers, but fail to solve one important aspect of the original suggestion: It can't be used to test the original program. Note that the original program called the random-number generator; it didn't read from a file. To use the file, you have to write a new "random-number reader" routine, compile it, and relink the program to include the new routine. You now have a new program whose behaviour will probably not show the same set of bugs as the original. This approach would be a good one for producing a reproducible, truly random sequence. But to be useful for debugging purposes, it would have to be incorporated into the library routine from the start, so that when his bug pops up some Tuesday, he can test it on the same sequence without changing any of the code. (Yes, I am truly paranoid. It comes from years of trying to debug programs, many of which worked just fine with the debugging output enabled.) -- John Chambers [...!decvax!mit-athena] If you're not part of the solution, then you're part of the precipitate.
john@x.UUCP (John Woods) (04/04/85)
> > seems silly to you, check out the Table of 10,000 Random Digits in your > > Rubber Bible (you *do* have the CRC Handbook of Mathmatics, don't you?). > > to get lists of seeds.) The same goes for using disk to read a random > number list from. The disk is a bit faster but not quite fast enough. > I suppose I should have put a smiley on my CRC Handbook comment, I didn't intend it to be a serious suggestion for a Monte Carlo simulation (after all, it doesn't take long to go through 10,000 digits). However, the statement "The disk is a bit faster but not quite fast enough" is not necessarily always true. Consider the following C code: int fd; main() { int i,t; fd = open("randoms",0); for (i = 0; i < 50000; i++) Rand(); /* or just "rand()" */ rand(); } int buf[5000], nb; Rand() { if (nb == 0) nb = read(fd,buf,sizeof buf) >> 2; return buf[--nb]; } Thanks to the `huge' buffer I use (20Kb on my 68000), it turns out that this program runs marginally faster using the disk table than when using the "rand()" function directly. OBVIOUSLY, your mileage may vary, but if your system has good disk throughput and a computationally expensive rand(), then you will likely see similar results, if you can afford a big buffer. It will also help if you don't mind having several megabytes of random data on your disk (but if you have netnews...). @Begin[ :-) ] By the way, back in college, we discovered that the Rubber Bible bounces, when dropped on an appropriate carpet. @END[ :-) ] -- John Woods, Charles River Data Systems, Framingham MA, (617) 626-1101 ...!decvax!frog!john, ...!mit-eddie!jfw, jfw%mit-ccc@MIT-XX.ARPA You can't spell "vile" without "vi".
brooks@lll-crg.ARPA (Eugene D. Brooks III) (04/06/85)
> Thanks to the `huge' buffer I use (20Kb on my 68000), it turns out that this > program runs marginally faster using the disk table than when using the > "rand()" function directly. OBVIOUSLY, your mileage may vary, but if your Obviously, you don't have the correct perspective on this problem. First, I don't use a 68000 to do my Monte Carlo calculations, I use a Cray. Hence there is very large differnce between the subroutine call used for a 32 bit integer multiply on the 68000 and the multiply that happens every clock on the Cray. Then there is always the clock speed itself to account for. Adding up these orders of magnitude, there are quite a few of them, you have to consider just how long this Monte Carlo runs on the Cray. Take 10 cpu hours for a reasonable run. Now thats a lot of random numbers.... The disk falls quite short in throughput, the CRC table analogy is quite appropriate, and it doesn't have enough space to hold them all anyway.