The Hardware Random Number Generator

A Ciphers By Ritter Page

The conversation starts with a particular prescription for a physically-random generator. It then breaks into mostly theory, with a few comments on alternate approaches.

Contents

• 1999-01-22 .·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·.: "Those who seek to capture random numbers in their natural habitats often are faced with two difficult paths: to wait quietly for the small whispers of thermal noise or to become immersed in the dazzling thrashes of large signal sources."
• 1999-01-24 Terry Ritter: "Doing low-level analog in a digital environment is tough, there is no doubt about that. Presumably we would employ appropriate techniques to pull it off."
• 1999-01-24 .·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·.: "A digital ring oscillator composed of Schmitt Triggers (with hysteresis) can be designed to have a slow rise time of ten microseconds, but they respond to an input transition in 100ps, to use round numbers."
• 1999-01-24 Terry Ritter: "...this 'large signal' design is probably sensitive to even tiny power and ground transients." "What I see is a huge complexity-based increase in signal transitions (a frequency increase) which will be hard to distinguish from heat-based noise. And if we cannot distinguish operation *with* noise from operation *without* noise, we have no way to prove that noise is involved at all." "Even PSEUDO-random RNG's pass statistical tests. Those tests have nothing to do with cryptographic unpredictability or 'strength.'"
• 1999-01-24 R. Knauer: "That statement needs to be added to the FAQ on Crypto-Grade Randomness."
• 1999-01-02 jsavard@ecn.ab.ca: "Many people have heard this, but because they have not understood, they did not believe."
• 1999-01-25 R. Knauer: "Here is a post from Patrick Juola that expands on this in a way that can be understood by all."
• 1999-01-25 .·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·.: "The major source of randomness of this RNG is the unsynchronized nature of multiple oscillators with randomly changing frequencies. This is a large signal phenomenon, which cannot be accurately described mathematically."
• 1999-01-25 Trevor Jackson, III: "Since the (intermediate) output of the system is driving the changes to the oscillators there is a full feedback loop present. This kind of system may pass statistical tests for randomness, but it may not be unpredictable."
• 1999-01-26 handWave: "We ran mathematical auto-correlation tests looking exactly for this, and got good results."
• 1999-01-26 Mok-Kong Shen: "If I have two sources of randomness, one software and one hardware, both passing all statistical tests I apply equally well, why should I choose one source in preference to the other?"
• 1999-01-26 Trevor Jackson, III: "We cannot re-run the hardware and get the same output. Thus the hardware is superior" "Everyone alive in 1980 knew that software was the 'plastic' of the decade and that the market for software was going to grow quickly. But no other person alive in 1980 forsaw just how big the market would be for really bad software."
• 1999-01-26 R. Knauer: "...the auto industry knew that way before Gates used it in the S/W industry."
• 1999-01-27 Mok-Kong Shen: "If you produce some sequence with a sufficiently good algorithm with a sufficiently long key and later forget that key, even you wouldn't be able to reproduce the sequence."
• 1999-01-26 R. Knauer: "Why do you persist in believing that statistical tests have anything to do with randomness in cryptography?"
• 1999-01-26 Mok-Kong Shen: "Tell me what other (better) tools are available for me to make the decision."
• 1999-01-26 R. Knauer: "If I told you that there are none, would you believe me?" "The key to understanding is that randomness depends on the generation process, not the numbers themselves."
• 1999-01-27 Mok-Kong Shen: "Then tell me HOW to get such a physical device that PROVABLY is capable of generating all possible sequences of a given finite length equiprobalbly."
• 1999-01-27 Patrick Juola: "You can't. Tell me how you can build a plane that will *provably* fly equally stably in any direction."
• 1999-01-27 Mok-Kong Shen: "Since there can't be an good answer, one can't claim hardware sequences are always to be preferred to software sequences."
• 1999-01-27 Patrick Juola: "I can prove that there can't be a good s/w sequence running on a deterministic machine. But I can't do that merely by inspecting any finite sample of outputs -- I have to look at the generators to do it." "...one can't claim hardware sequences are always to be preferred to software sequences *on the basis of a statistical analysis of a finite set of output sequences.*"
• 1999-01-27 Mok-Kong Shen: "Are there other sound scientific basis to claim the said preference."
• 1999-01-27 Patrick Juola: "...yes, if your goal is to provide unbounded degrees of security for messages of unbounded length."
• 1999-01-27 Mok-Kong Shen: "Could you provide the requested sound scientific basis?"
• 1999-01-27 Patrick Juola: "If the key is 'as random as' the message, then Shannon's proof of secrecy goes through." "The difficulty is in *proving* that a given sequence of N bits is contains N bits of randomness...."
• 1999-01-27 R. Knauer: "You once said that such a system was vulnerable to a Bayesian attack. Have you changed your mind?"
• 1999-01-28 Patrick Juola: "No. The key point here is that the key is as large as -- larger than, in fact -- the plaintext."
• 1999-01-28 R. Knauer: "Please elaborate on the concepts of 'bounded', 'unbounded'...."
• 1999-01-29 Patrick Juola: "The difference between bounded and finite is simple -- with finite, plaintexts, I know that my articles will eventually end, but I don't know when beforehand. With a bounded plantext, I set myself a rule beforehand that I won't go over 30 lines, or 300, or 3 million, whatever *and stick to that rule.*"
• 1999-01-28 Mok-Kong Shen: "We must be realistic, since theoretical stuffs may not be realizable in the real world and since 'absulute' security is never required.... Incidentally, in another thread I also suggested distiling bit sequences out of natural language texts as raw materials."
• 1999-01-27 R. Knauer:
• 1999-01-27 R. Knauer:
• 1999-01-27 R. Knauer: "The answer that the poster wants to hear is: Because TRNGs are not Perfect, PRNGs are just as good."
• 1999-01-27 Mok-Kong Shen: "Where is the proof...?"
• 1999-01-27 R. Knauer: "The proof of the second part comes from an analysis of what makes a PRNG behave the way it does."
• 1999-01-27 Mok-Kong Shen: "Please note I don't claim PRNGs are good. I simply doubt that hardward generators are good because I have no tools to determine that they are good, except by using statistical tools."
• 1999-01-27 R. Knauer: "You must be skilled at designing a TRNG. Statistical tools are worthless."
• 1999-01-27 Mok-Kong Shen: "...how do you show through a test of skill that the resulting TRNG designed by that person has a certain 'crypto-grade'...?"
• 1999-01-27 Patrick Juola: "The same way you test the skill of the architect who designed your building."
• 1999-01-27 R. Knauer: "Get several skilled people to check the design and the actual TRNG."
• 1999-01-27 Patrick Juola: "...if the generation process is purely software running on a deterministic routine, then the randomness of the resulting pad is bounded by the randomness of the starting conditions."
• 1999-01-27 Mok-Kong Shen: "...that cetainly doesn't imply that any hardware generator can offer absolute security."
• 1999-01-27 R. Knauer: "The OTP cryptosystem is proveably secure."
• 1999-01-27 Mok-Kong Shen: "Simply saying that a hardware generator offers high security is NO convincing argument...."
• 1999-01-27 R. Knauer: "Fine - let him seek a meaningful demonstration then."
• 1999-01-28 Mok-Kong Shen: "After having built a hardware generator, do you test it or simply 'believe' that it is o.k.?" "'If two objects are indistinguishable, in what sense are they different?'"
• 1999-01-28 R. Knauer:
• 1999-01-27 R. Knauer: "With correct design one can make a TRNG random to within an arbitrarily high level of precision."
• 1999-01-27 Mok-Kong Shen: "You have to define that 'precision' in scientific terms, in particular establish a 'unit' and provide a precise method to measure that 'precision' in that unit. Before that, you have nothing."
• 1999-01-27 R. Knauer: "You do that by analyzing the design, and performing certain tests on the actual equipment to make sure it meets the design specifications."
• 1999-01-27 Mok-Kong Shen: "Now what are the specifications that ensures a crypto-grade TRNG?"
• 1999-01-27 R. Knauer: "Check out the Hotbits radioactive decay TRNG...."
• 1999-01-27 Patrick Juola: "Well, broadly speaking, you need a source of randomness...." "Then, I need to sample those events in a manner that preserves the randomness." "The resulting number streams can be certified as "random," subject to the same (standard) assumptions that any other engineering project uses."
• 1999-01-27 Trevor Jackson, III: "Now this is an issue worthy of intense thought and debate.... I believe this breaks into two subtopics, one fundamentally describing the unit of measure and the other describing the measurement methodology."
• 1999-01-27 Medical Electronics Lab: "The "unit" is expectation value. Precision isn't a good term, what you want is "uniformity". A TRNG should have expectation values for *all* imaginable tests, i.e. it should be uniformly random no matter how you look at it."
• 1999-01-27 Patrick Juola: "Mr. Knauer's criterion...: "For all (finite) lengths, all possible sequences of that length are outputted equiprobable."
• 1999-01-27 R. Knauer: "...I see no problem with using the sequence...."
• 1999-01-29 Kurt Wismer: "this is the definition i've used for years...."
• 1999-01-29 Patrick Juola: "...it also looks suspiciously like the result of an incompetent engineer *trying* to build a RNG."
• 1999-01-30 Kurt Wismer: "i don't see any foolproof method of verifying that the trng is indeed a trng...."
• 1999-01-31 R. Knauer: "I believe that a radioactive decay TRNG can be verified to within a known level of precision."
• 1999-02-01 Patrick Juola: "But this is yet another example of a statistical test."
• 1999-02-03 R. Knauer: "The tests, statistical or otherwise, would be of a diagnostic nature applied to the sybsystems of the TRNG."
• 1999-02-03 Trevor Jackson, III: "So a properly designed RNG is not permitted to fails in an unknown way? Is this design methodology documented anywhere? It sounds like it avoids Murphy the way perpetual motion machines avoid friction."
• 1999-01-27 Patrick Juola: "You are going to have to open the hood and look at the engine and see how it's put together."
• 1999-01-27 R. Knauer: "Assuming that you could use such a Bayesian Test to characterize randomness, how does that differ from statistical tests for randomness?"
• 1999-01-27 Mok-Kong Shen: "What is a 'probability survey'?"
• 1999-01-27 R. Knauer: "I used the term to describe the process whereby one surveyed a large number of ciphers using probability techniques...."
• 1999-01-27 Patrick Juola: "By the time you get up to the upper reaches of what we can do with PRNGs, the information leak over reasonably-sizes samples is pretty infinitesimal." "Bayes' Theorem lets you refine hypotheses about biases that you've already made. Conventional statistics just let you test for the presence or absence of a visible bias."
• 1999-01-27 R. Knauer: "So, the Bayesian attack is not all that powerful against stream ciphers *in general*. You have to provide the first hypothesis to get it started."
• 1999-01-27 Trevor Jackson, III: "One can change keys arbitrarily. Once cannot change code so often...."
• 1999-01-27 R. Knauer: "How about making your algorithm (code) part of the key?"
• 1999-01-27 Patrick Juola: "The larger the key, the more difficulty you have in changing/exchanging it."
• 1999-01-27 R. Knauer: "The question was theoretical."
• 1999-01-27 Trevor Jackson, III: "...you need a clever encoding scheme such that all key values translate to valid algoirhms. In addition, you need to show that all such encoded algorithms are 'secure'."
• 1999-01-27 R. Knauer: "A daunting task."
• 1999-01-27 Patrick Juola: "...the NSA does *NOT* have infinite resources. Far from it."
• 1999-01-27 Trevor Jackson, III: "...analysis of the generation process is more efficient than analysis of the generator output."
• 1999-01-27 R. Knauer: "Algorithmic analysis of the generated output itself is completely worthless if that output is finite in length."
• 1999-01-27 Trevor Jackson, III: "Analysis of output is insufficient to prove the entropy density is 100%, but it can easily provide useful information."
• 1999-01-27 Patrick Juola: "...you *NEED* to define the tests you're going to run and the rejection threshhold before you power up the generator."
• 1999-01-28 Trevor Jackson, III: "Absolutely. Any other arrangement produces a man-in-the-loop situation."
• 1999-01-27 R. Knauer:
• 1999-01-28 Patrick Juola: "In terms of finite length numbers, a finite number is not statistically random if I can predict it (or something about it)."
• 1999-01-28 R. Knauer: "You throw out the suspect bad generators and argue that such a practice is safe. But what is your argument for the generators that you do not throw out?"
• 1999-01-29 Patrick Juola: "That the amount of the bias *that I measured* is less than some threshhold. If I can live with that threshhold and I believe that no other (untested) source of bias is likely to be present, then the cypher is safe to use."
• 1999-01-30 R. Knauer: "Then you accept bad generators and reject good ones."
• 1999-02-01 Patrick Juola: "Absolutely. With a particular, known, measured probability."
• 1999-02-03 R. Knauer: "...your tests will eventually reject every TRNG you test long enough...."
• 1999-02-03 Patrick Juola: "I 'know' that a given TRNG will fail 1/20 of the tests at a 5% level, so if I get an approximate failure rate of 1 in 20, then I keep that one...." "Statistics -- nor engineering practice, for that matter -- will never allow you to get a probability all the way down to zero."
• 1999-02-05 R. Knauer: "Just how much testing do you need to do to convince yourself that a given RNG is crypto-grade (either proveably secure or secure in terms of work effort)?"
• 1999-02-04 Herman Rubin: "If one can assume independence between generated sets, one can make both of these errors quite small...."
• 1999-02-04 R. Knauer: "I am interested in seeing how much testing is involved for a given level of confidence, and how that testing effort increases with decreasing levels of confidence."
• 1999-02-05 Patrick Juola: "Well, one starts out by making a questionable assumption, in most cases...."
• 1999-02-07 Herman Rubin: "...the sample size needed would increase as 1/d^2...." "Now if we XOR independent files, say run on different days, the deviations from randomness multiply."
• 1999-02-07 R. Knauer: "If your tests are probabilistic with only a 'good chance' of being correct, then how can they be relied on?"
• 1999-02-08 Patrick Juola: "What is your acceptable degree of uncertainty? "
• 1999-02-09 R. Knauer: "The only way to get a "minimal good chance" of characterizing the TRNG itself is to do a complete audit on it."
• 1999-02-09 Trevor Jackson, III: "...any judgement or decision is going to be based on some evidence gathered by observation and/or experiment." "Have you ever audited a system for side effects? Like exhaustive logic tests or provable software design, this kind of analysis is only useful for toy systems."
• 1999-02-08 Herman Rubin: "...the type of TRNG you think you have does not exist, only approximations of it can exist. And it is necessary to test if the approximations are good enough."
• 1999-02-08 R. Knauer: "...the very thing you are testing the RNG for, namely its suitability for use with the OTP system, is not determinable."
• 1999-02-08 Patrick Juola: "There are two things you need to do to produce a certifiable TRNG." "One is to confirm that the device is, in fact, a 'random number generator' in the sense that it produces random bits." "The other is to confirm that the outputs are bias-free -- or more accuratley as bias-free as possible...."
• 1999-02-09 R. Knauer: "We speak of the ills of bit-bias in terms of random number generation, but what if the generator were designed with a deliberate bias?"
• 1999-02-10 Trevor Jackson, III: "Any tests you would use to prove QM indeterminate can be used t prove a non QM RNG indeterminate. naturally, these would be statistical tests."
• 1999-02-10 R. Knauer:
• 1999-02-10 Patrick Juola: "If it's a really good generator with a known bias, there are mathematical techniques that will allow me to strip out the bias and produced an unbiased stream."
• 1999-02-11 Tony T. Warnock: "..."random" bits are quite expensive to get."
• 1999-02-11 R. Knauer: "This brings up the question of whether anti-skewing changes the equiprobability of the generator." "Anti-skewing procedures do not generate those sequences that under-representted because of the bias."
• 1999-02-11 Patrick Juola: "That's *exactly* what anti-skewing procedures do."
• 1999-02-13 R. Knauer: "Can that anti-skewing technique above generate all possible sequences including 111...1 and 000...0 with their expected probability based on their length?"
• 1999-02-13 karl malbrain: "What you're missing here is INDUCTION."
• 1999-02-15 Patrick Juola: "As to proof that the expected probability is based on the length; do it by case analysis and induction."
• 1999-02-15 Trevor Jackson, III: "In electronics I believe this is called 'edge detection' instead of 'level detection'."
• 1999-02-13 R. Knauer: "You may be able to anti-skew a sequence, but that won't remove correlation."
• 1999-02-15 Patrick Juola: "This method produces perfectly unbiased numbers *IF* the underlying bit sequence is independent."
• 1999-02-15 R. Knauer: "One advantage is that if the output is shorted or pulled up, there will be no final output since there will be no dibits of the kind 01 or 10."
• 1999-02-15 Patrick Juola: "...this is an engineering question, and not a formal requirement."
• 1999-02-15 R. Knauer: "Until another proveably secure anti-skewing technique can be identified, it has the advantage that it works."
• 1999-02-08 Terry Ritter: "...a 'bad' generator (one with a measurable error) will fail very badly virtually all of the time." "We seek to certify, to high probability, using statistical tests, that a complex physical process is producing the results we expect. In this way we certify the detection machinery, and then depend upon the assumed characteristics of the physical source as the generator of randomness."
• 1999-02-08 R. Knauer: "I do not understand what you have just said wrt the LSB's. Why would using larger character representations be preferably to using LSBs?"
• 1999-02-09 Terry Ritter: "Even when characters have an overall 'entropy' of less than a bit, there is no particular reason to expect to find the entropy concentrated in the LSB's. The LSB represents part of the coding; it has nothing to do with the entropy transported by the variation in usage of that coding."
• 1999-02-09 R. Knauer: "I suppose the problem I am having is that if you include all the bits of the text characters, you will be introducing bias into the stream."
• 1999-02-09 Mok-Kong Shen: "I believe lots of people would be very happy if you could tell them how to obtain a fair coin! Isn't evident now that one can never get an ideal OTP?"
• 1999-02-09 R. Knauer: "I meant that coin toss system as an analogy."
• 1999-02-09 Tony T. Warnock: "If you bounce a die hard enough, it acts random."
• 1999-02-08 Terry Ritter: "...as I see it, 'the' important quality for a cryptographic sequence is the independence of each value."
• 1999-01-29 Mok-Kong Shen: "...people doing statistical tests are very prudent and very modest ones. They never say anything categorically ('for sure', IS or IS NOT) but rather say 'something is fairly unlikely to be true' or 'there is not enough evidence to believe that it is false'."
• 1999-01-26 handWave: "If you are in the college dorm with enemies who may interfere remotely, then a thermal noise generator from an avalanche diode with a high gain amplifier breadboared using wire-wrapped, unshielded circuits is a bad implementation."
• 1999-01-26 Mok-Kong Shen: "Some one offers me two sequences generated from two different sources (I am not told which is which). I want to decide which one to use." "How am I going to make the decision?"
• 1999-01-26 Terry Ritter: "...as a very basic first step, we must be very sure that we actually are measuring and reporting molecular-level randomness, rather than some other signal." "Ideally, a randomness machine will allow us to conduct statistical experiments on the randomness source itself...."
• 1999-01-27 Mok-Kong Shen: "I like however to associate that 'known' with some degree of subjectivity (unless that 'known' can be shown to be the same as 'proved')"
• 1999-01-26 Trevor Jackson, III: "I doubt an average person could control a roulette wheel that well after a year of practice. OTOH, I think an average person could reach that level of skill with a silver dollar after a few days or a week."
• 1999-01-25 Medical Electronics Lab: "Using a smoke detector it's a mighty damn weak signal. It takes about 1e5 amplification to see the radiation noise and that involves lots of shielding from outside sources as well as preventing feedback."
• 1999-01-26 handWave: "Or take your smoke detector and place the vitals in contact with the surface of a modern DRAM: Large Random Signals would result in the big memory array."
• 1999-01-26 burt: "Have you done any Frequency domain analysis...?"
• 1999-01-26 handWave: "As I recall, the two faster oscillators ran at about 5Mhz to 50Mhz as their frequencies were randomly modulated."
• 1999-01-26 Terry Ritter: "I have never heard IC designers claim that it is 'not possible to tell' whether their design works. In fact, if we can't tell whether a design works or not, we generally consider that a design *failure*: If we can't test it, we can't trust it." "...it is in the nature of this sort of oscillator to synchronize to tiny transients as may occur from nearby state changes. So just how do we *know* that our oscillators *are* "unsynchronized"?" "I argue that an RNG as you describe not only has digital state, it also has analog thermal state, direct electrical coupling from other power-using circuits (including each stage), and indirect coupling from nearby circuits. Once we account for all this state and interaction, I expect that we can largely predict the result."
• 1999-01-26 Kazak, Boris: "Consider such a simple system... where HH is a... bottle, OO are Objects, MM is a Microphone. Now if we start rotating the Housing around its horizontal axis, the Objects will produce a loud Random Rattle, and the Microphone will transmit this rattle to the sound card."
• 1999-01-27 handWave: "Your sound card and software will need to comprehend the natural resonant frequencies of the bottle and filter out that repeating soundwave."
• 1999-01-27 R. Knauer: "I suspect that all classical processes, even chaotic ones, suffer from some kind of flaw as you describe. That's why I would only use quantum processes for a TRNG."
• 1999-01-27 handWave: "Your messages are beginning to repeat themselves, so I am not responding to these repeated comments."
• 1999-01-31 Bo Dömstedt: "As for random number generation, we sell them for $170...."
• 1999-01-31 Kazak, Boris: "In all the hype that is there on the WWW page you mentioned, there is not a single word about the underlying physical phenomena which produces 'high level signal random output'."
• 1999-02-01 Bo Dömstedt: "We use a noisy diode as our noise source. It has been extensively checked, and works well in practice."
• 1999-01-31 handWave: "You will be sipping your coffee while your lonely RNG will be under hostile attack by Martians."

Subject: hardRandNumbGen
Date: Fri, 22 Jan 1999 23:24:52 -1000
From: ".·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·." <fermion@false.net>
Message-ID: <36A99564.D20@false.net>
Newsgroups: sci.crypt
Lines: 66

hardRandNumbGen

Those who seek to capture random numbers in their natural
habitats often are faced with two difficult paths: to wait
quietly for the small whispers of thermal noise or to 
become immersed in the dazzling thrashes of large signal
sources. Both ways may lead to success, or to a failure
so desperate, that every adversary may be seen as a
stalker in the night. The story you are about to read is
true: "The Hardware Random Number Generator!"

Our story starts in the late 1940's with a Bell Labs 
researcher in his Ivory Tower setting. Dusting off an old
book on physics, a young researcher reads about noise from 
resistors:

 "Thermal noise is produced as a result of thermally 
  excited random motion of free electrons in a conducting 
  medium, such as a resistor". 

This is the old wisdom of Kirchhoff and Kelvin. Randomness
may be gathered from an RMS voltage of about 4kTRB, where
B is the bandwidth, R is the resistance, T is temperature, 
and k is Boltzman's constant. Faced with adversaries, the 
researcher knows he must use small resistors which are more 
immune to remote interference. But if 300 ohms are used, 
the voltage will only be two microvolts! An amplifier with
a gain of a million will be needed to make the noise useable
for his secret cryptographic purposes. Then the amplifier
itself will become susceptible to outside influences. 

Millions of people are depending on his team to find a better
source of random numbers, when he has an inspiration. Like
a collection of atoms whose motion so hard to predict, if
he can use variable oscillators, or gyrators, as he likes to
call them, then their combined signals would be hard to predict.
Small variations in conditions would change the "large signal"
outputs from his circuits, which he could sample at regular 
intervals. That was the beginning. Today, my friends, we are
ready to receive the benefits of Large Signal Random Sources.
No longer will we wait, with a hope and a prayer, that the 
microvolt sources of randomness will not fall victum to the
beamed manipulations of deviant hackers, NO, digital large
signals have brought us immunity from such a fate.

But it is not just the hacker who would mug our chaotic joy, 
it is the very regularity of our clock cycles and the very 
power of our conforming buses which threaten to impart a
hideous regularity to our nonces, our IVs, our keys. The 
heartbeat of a computer is its clock, and a powerful hammerblow
it is to any mere analog circuit which would dare to reside 
on our motherboards. This is why we cannot use sensitive
amplifiers to boost the whispers of thermal noise. This is why
Large Signal Sources are our refuge, our bounty, our provider
of Hardware Random Number Generators. Oscillators, I tell you, 
OSCILLATORS, they are our main hope, and the pride modern
civilization. I cannot exaggerate too much, the importance of
avoiding the mistakes of past designers, who, through wishful
thinking, risked it all, and lost, to the whims of a tiny hiss.

So go now, brash young designers of tomorrows crytosystems, go
to your keyboards and your mice, and always remember: It is 
better to have thrashed and lost some quality, than to never 
have thrashed at all.

.·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·. 1999/1/22


Subject: Re: hardRandNumbGen
Date: Sun, 24 Jan 1999 05:08:35 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <36aaaacf.5602532@news.io.com>
References: <36A99564.D20@false.net>
Newsgroups: sci.crypt
Lines: 53


On Fri, 22 Jan 1999 23:24:52 -1000, in <36A99564.D20@false.net>, in
sci.crypt ".·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·."
<fermion@false.net> wrote:

>[...]
>it is the very regularity of our clock cycles and the very 
>power of our conforming buses which threaten to impart a
>hideous regularity to our nonces, our IVs, our keys. The 
>heartbeat of a computer is its clock, and a powerful hammerblow
>it is to any mere analog circuit which would dare to reside 
>on our motherboards. This is why we cannot use sensitive
>amplifiers to boost the whispers of thermal noise. 

"Cannot" may be a bit of a stretch.  Doing low-level analog in a
digital environment is tough, there is no doubt about that.
Presumably we would employ appropriate techniques to pull it off.
Probably this would involve some form of power isolation and
filtering, perhaps even shielding.  Once the signal is large enough,
it can compete with digital its own terms. 

We note that the output of a CD player is supposed to be low-noise,
yet is produced in a digital environment.  And sound-card inputs
amplify relatively low analog levels.  Certainly, disk-drive magnetic
read heads produce very low-level signals, yet are made to work well
in a highly-digital environment.  


>This is why
>Large Signal Sources are our refuge, our bounty, our provider
>of Hardware Random Number Generators. Oscillators, I tell you, 
>OSCILLATORS, they are our main hope, and the pride modern
>civilization. 

Unfortunately "oscillation" inherently seems to imply some amount of
saved and time-delayed energy.  It is this accumulation of energy that
makes it difficult to change the oscillation, and that is normally an
advantage.  Normally, an oscillator cannot detect quantum or molecular
phenomena, and we would not want it to do so.  

A signal composed of many oscillators, each doing their own thing, is
admittedly complex.  But complex relationships are not, by themselves,
cryptographically secure.  We could even think to simulate such a
system numerically, in which case the system is clearly no more than
yet another pseudorandom state machine waiting to be exposed.  And
while any such simulation might not be exact, it could be close, and
we could continually adjust the simulation to the reality we do see.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM



Subject: Re: hardRandNumbGen
Date: Sun, 24 Jan 1999 03:53:40 -1000
From: ".·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·." <real@complex.net>
Message-ID: <36AB25E4.2E7E@complex.net>
References: <36aaaacf.5602532@news.io.com>
Newsgroups: sci.crypt
Lines: 130

Terry Ritter wrote:
> 
> On Fri, 22 Jan 1999 23:24:52 -1000, in <36A99564.D20@false.net>, in
> sci.crypt ".·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·."
> <fermion@false.net> wrote:
> 
> >[...]
> >it is the very regularity of our clock cycles and the very
> >power of our conforming buses which threaten to impart a
> >hideous regularity to our nonces, our IVs, our keys. The
> >heartbeat of a computer is its clock, and a powerful hammerblow
> >it is to any mere analog circuit which would dare to reside
> >on our motherboards. This is why we cannot use sensitive
> >amplifiers to boost the whispers of thermal noise.

>"Cannot" may be a bit of a stretch.  

Yes, my prose were intended to be didactic to troll for responses. 
Thank you for your polite and rational response.

>Doing low-level analog in a
>digital environment is tough, there is no doubt about that.
>Presumably we would employ appropriate techniques to pull it off.
>Probably this would involve some form of power isolation and
>filtering, perhaps even shielding.  Once the signal is large enough,
>it can compete with digital its own terms.

On a single chip product, like a mainstream microprocessor that is 
employing appropriate techniques to push the limits of speed, you 
may find that large signals for a random number generator are 
preferable to millivolt signals. The substrate junction with p+ and 
n- wells have a capacitive noise for which it is hard to provide 
accurate cancellation. 

>We note that the output of a CD player is supposed to be low-noise,
>yet is produced in a digital environment.  And sound-card inputs
>amplify relatively low analog levels.  Certainly, disk-drive magnetic
>read heads produce very low-level signals, yet are made to work well
>in a highly-digital environment.

The inputs to a CD player are large signal, digital inputs from light 
relections. The digital codes are reproduced from a recording studio
which spent millions to get way from periodic noise. I have not done 
the following experiment: put a spectrum analyser on the output of a CD 
player during quiet passages. Look for the noise outside of the human 
hearing range. I expect that the digital electronics in a CD player
produce ordinary levels of periodic noise that we cannot hear. And 
that includes non-random noise BELOW 40 hz.

CD players are not 400 Mhz microprocessors that are going as fast
as possible driving motherboard capacitances on 400 pins. They are 
slow, dedicated chips with few pins being driven, and with small
load capacitances. They are self-contained assemblies that are 
shielded from other components in a home stereo system. The kind of
RNG I am interested in is one that is robust. One that is prepared
to exist in a hostile electrical environment, not some pampered
little dog of a processor.

Hard drives are limited to 5 zeros in a row. Consider : Why?

>>This is why
>>Large Signal Sources are our refuge, our bounty, our provider
>>of Hardware Random Number Generators. Oscillators, I tell you,
>>OSCILLATORS, they are our main hope, and the pride of modern
>>civilization.

>Unfortunately "oscillation" inherently seems to imply some amount of
>saved and time-delayed energy.  It is this accumulation of energy that
>makes it difficult to change the oscillation, and that is normally an
>advantage.  Normally, an oscillator cannot detect quantum or molecular
>phenomena, and we would not want it to do so.

A digital ring oscillator composed of Schmitt Triggers (with 
hysteresis) can be designed to have a slow rise time of ten 
microseconds, but they respond to an input transition in 100ps, to
use round numbers. To illustrate the powerful effect that these 
facts have on  the recording of thermal noise, I will give the 
details of it operation. Assume there is a +/- 1 millivolt thermal
noise present on the output of an inverter. Assume a Schmitt trigger
will switch when its input rises above 1v for a system using 2v
power supplies. The oscillator runs at 100khz. How long will it take 
for the input to rise 2mV? That is 2mV divided by 1V/10us or 50ns.
So on every cycle of the oscillator there is a 50ns time when 
uncertainty exists. This is a half percent on each cycle.

Since multiple oscillators will be involved, each with a half percent
uncertainty, one can see that by using 200 such oscillators XORed 
together, the output would be quite random. But in practice, 200 
oscillators are not needed because there are several sources of
uncertainty in a well designed Large Signal Random Number Generator
such as the one I designed at a large semiconductor company. It was 
fabricated and tested by a team of engineers. It worked well. It was 
evaluated by the CIA and they sent us a report on its 
characteristics. Have you built any hardware random number 
generators using large signals? Small signals?

Mr. Ritter says, "It is this accumulation of energy that makes it 
difficult to change the oscillation....". It is easy to change the
oscillation period using capacitors that are connected or 
disconnected from the oscillator by switches that are 
controlled by signals from the random string.
This arrangement amplifies any thermal noise that is captured.
To be more detailed, when a 1mV noise does affect a bit value that 
is shifted into a register, that bit value changes the frequency 
of oscillation of one or more oscillators. The XOR combines these
changes for a while until the combined bitstream is sampled. I 
contend that this is not just illusory complexity, it is an
amplification of a thermal noise into a large product.

>A signal composed of many oscillators, each doing their own thing, is
>admittedly complex.  But complex relationships are not, by themselves,
>cryptographically secure.  We could even think to simulate such a
>system numerically, in which case the system is clearly no more than
>yet another pseudorandom state machine waiting to be exposed.  And
>while any such simulation might not be exact, it could be close, and
>we could continually adjust the simulation to the reality we do see.

I hope that you would simulate the 200 oscillator example I gave. Yes, 
you can add the +/- 1mV noise and adjust to make it as accurate as you
care to invest time for. I have read your pat statement above several 
times recently, and I disagree with it. It is possible to design a 
complex circuit that is poorly done and which therefore would fail 
tests for randomness. But you should not get hung up on poor designs
that fit your expectation. You should open your mind to the 
possibility that talented design engineers might do a good job using
techniques you wish did not exist. You can change your opinion.
I will send you a relevent patent number through private email so
you can see the drawings.

.·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·.


Subject: Re: hardRandNumbGen
Date: Sun, 24 Jan 1999 17:48:24 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <36ab5cde.5814163@news.io.com>
References: <36AB25E4.2E7E@complex.net>
Newsgroups: sci.crypt
Lines: 171


On Sun, 24 Jan 1999 03:53:40 -1000, in <36AB25E4.2E7E@complex.net>, in
sci.crypt ".·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·."
<real@complex.net> wrote:

>Terry Ritter wrote:
>[...]
>>Unfortunately "oscillation" inherently seems to imply some amount of
>>saved and time-delayed energy.  It is this accumulation of energy that
>>makes it difficult to change the oscillation, and that is normally an
>>advantage.  Normally, an oscillator cannot detect quantum or molecular
>>phenomena, and we would not want it to do so.
>
>A digital ring oscillator composed of Schmitt Triggers (with 
>hysteresis) can be designed to have a slow rise time of ten 
>microseconds, 

Presumably this means that the effective source resistance is large
compared to the input capacitance, and the source of the delay is an
R-C ramp to the next stage.

>but they respond to an input transition in 100ps, to
>use round numbers. To illustrate the powerful effect that these 
>facts have on  the recording of thermal noise, I will give the 
>details of it operation. Assume there is a +/- 1 millivolt thermal
>noise present on the output of an inverter. 

That means that this "large signal" design is probably sensitive to
even tiny power and ground transients.  It is going to be very hard to
distinguish the effects of "real" thermal noise from transient
feedback due to the structure of the circuit.  So how can we have
confidence in the result?  Statistical testing cannot distinguish
between "physical" and "pseudo" randomness.  

>Assume a Schmitt trigger
>will switch when its input rises above 1v for a system using 2v
>power supplies. The oscillator runs at 100khz. How long will it take 
>for the input to rise 2mV? That is 2mV divided by 1V/10us or 50ns.
>So on every cycle of the oscillator there is a 50ns time when 
>uncertainty exists. This is a half percent on each cycle.

As a rare peak value, presumably.  

>Since multiple oscillators will be involved, each with a half percent
>uncertainty, one can see that by using 200 such oscillators XORed 
>together, the output would be quite random. 

What I see is a huge complexity-based increase in signal transitions
(a frequency increase) which will be hard to distinguish from
heat-based noise.  And if we cannot distinguish operation *with* noise
from operation *without* noise, we have no way to prove that noise is
involved at all.  Other than claims and handwaves, of course.  

>But in practice, 200 
>oscillators are not needed because there are several sources of
>uncertainty in a well designed Large Signal Random Number Generator
>such as the one I designed at a large semiconductor company. It was 
>fabricated and tested by a team of engineers. It worked well. 

I have looked at the published results a number of times.  They were
in fact part of the basis for my investigation of the numerical
relationship between repeats in sampling and the overall population. 

Easy calculations using the publushed results show that the effective
population of values is 1/4 the claimed ideal, which shows that the
design was not as good as you thought.  

>It was 
>evaluated by the CIA and they sent us a report on its 
>characteristics. 

The published (admittedly meager) experimental evidence says
otherwise.  

>Have you built any hardware random number 
>generators using large signals?   

The claimed basis for your generator is thermal noise, which is NOT
large-signal.  A large-signal digital system is a PSEUDO-random
digital RNG, and can be implemented in software as well as hardware.
So, yes, certainly I have implemented and tested many large signal
(software) RNG's.  

Some software computations are hard to reverse.  But few if any of the
conventional statistical RNG's have stood up to attack.  Just giving a
hardware design and claiming "nobody can break this" is the sort of
thing we see on sci.crypt all the time.  

The reasoning about this design is contradictory:  Supposedly the
large signal design is "random" because it senses low-level noise.
Yet the circuit is supposedly suitable for a noisy digital chip
because it is a "large-signal" design.  There is a fundamental problem
in making both claims at the same time.  

>Small signals?

Yes.

>Mr. Ritter says, "It is this accumulation of energy that makes it 
>difficult to change the oscillation...CRYPHTML.HTM". It is easy to change the 
>oscillation period using capacitors that are connected or 
>disconnected from the oscillator by switches that are 
>controlled by signals from the random string.

But that approach is digital complexity, and not thermal randomness.
It can be simulated in software.  It is PSEUDO-random.  Maybe it is
strong, maybe not, but there is certainly no proof.  

>This arrangement amplifies any thermal noise that is captured.
>To be more detailed, when a 1mV noise does affect a bit value that 
>is shifted into a register, that bit value changes the frequency 
>of oscillation of one or more oscillators. The XOR combines these
>changes for a while until the combined bitstream is sampled. I 
>contend that this is not just illusory complexity, it is an
>amplification of a thermal noise into a large product.

The obvious experiment, then, is to take the device to cryogenic
temperatures and see how it performs.  If the output still has good
statistics, we can suspect that the output does not represent thermal
noise at all, but is just a complex digital system.  Was such an
experiment performed?


>>A signal composed of many oscillators, each doing their own thing, is
>>admittedly complex.  But complex relationships are not, by themselves,
>>cryptographically secure.  We could even think to simulate such a
>>system numerically, in which case the system is clearly no more than
>>yet another pseudorandom state machine waiting to be exposed.  And
>>while any such simulation might not be exact, it could be close, and
>>we could continually adjust the simulation to the reality we do see.
>
>I hope that you would simulate the 200 oscillator example I gave. 

But your design does not use 200 oscillators, does it?  

>Yes, 
>you can add the +/- 1mV noise and adjust to make it as accurate as you
>care to invest time for. I have read your pat statement above several 
>times recently, and I disagree with it. It is possible to design a 
>complex circuit that is poorly done and which therefore would fail 
>tests for randomness. 

Even PSEUDO-random RNG's pass statistical tests.  Those tests have
nothing to do with cryptographic unpredictability or "strength."  Yet
strength is what you claim.  


>But you should not get hung up on poor designs
>that fit your expectation. You should open your mind to the 
>possibility that talented design engineers might do a good job using
>techniques you wish did not exist. 

I have no such wish.


>You can change your opinion.

I think you have missed the distinction between unpredictable
randomness for cryptography, and ordinary statistical randomness.  


>I will send you a relevent patent number through private email so
>you can see the drawings.

I have seen the technical article.  

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM



Subject: Re: hardRandNumbGen
Date: Sun, 24 Jan 1999 18:45:25 GMT
From: rcktexas@ix.netcom.com (R. Knauer)
Message-ID: <36ab69fd.16112067@nntp.ix.netcom.com>
References: <36ab5cde.5814163@news.io.com>
Newsgroups: sci.crypt
Lines: 17

On Sun, 24 Jan 1999 17:48:24 GMT, ritter@io.com (Terry Ritter) wrote:

>Even PSEUDO-random RNG's pass statistical tests.  Those tests have
>nothing to do with cryptographic unpredictability or "strength."  

That statement needs to be added to the FAQ on Crypto-Grade
Randomness.

It says it all.

Bob Knauer

"It is not the function of our government to keep the citizen from
falling into error; it is the function of the citizen to keep the
government from falling into error."
--Justice Robert H. Jackson



Subject: Re: hardRandNumbGen
Date: 25 Jan 99 02:37:29 GMT
From: jsavard@ecn.ab.ca ()
Message-ID: <36abd8e9.0@ecn.ab.ca>
References: <36ab69fd.16112067@nntp.ix.netcom.com>
Newsgroups: sci.crypt
Lines: 17

R. Knauer (rcktexas@ix.netcom.com) wrote:
: On Sun, 24 Jan 1999 17:48:24 GMT, ritter@io.com (Terry Ritter) wrote:

: >Even PSEUDO-random RNG's pass statistical tests.  Those tests have
: >nothing to do with cryptographic unpredictability or "strength."  

: That statement needs to be added to the FAQ on Crypto-Grade
: Randomness.

: It says it all.

It does indeed, but it will probably have to be expanded and commented
upon before it will "say it all" clearly enough so that everyone
understands what it means. Many people have heard this, but because they
have not understood, they did not believe.

John Savard


Subject: Re: hardRandNumbGen
Date: Mon, 25 Jan 1999 11:55:36 GMT
From: rcktexas@ix.netcom.com (R. Knauer)
Message-ID: <36ac5b28.1691712@nntp.ix.netcom.com>
References: <36abd8e9.0@ecn.ab.ca>
Newsgroups: sci.crypt
Lines: 73

On 25 Jan 99 02:37:29 GMT, jsavard@ecn.ab.ca () wrote:

>: >Even PSEUDO-random RNG's pass statistical tests.  Those tests have
>: >nothing to do with cryptographic unpredictability or "strength."  

>: That statement needs to be added to the FAQ on Crypto-Grade
>: Randomness.
>: It says it all.

>It does indeed, but it will probably have to be expanded and commented
>upon before it will "say it all" clearly enough so that everyone
>understands what it means. Many people have heard this, but because they
>have not understood, they did not believe.

I agree. Here is a post from Patrick Juola that expands on this in a
way that can be understood by all.

+++++
On 21 Jan 1999 08:23:54 -0500, juola@mathcs.duq.edu (Patrick Juola)
wrote:

You're not seeing the fundamnental distinction between "irrationality"
and "randomness" in that randomness is a function, not of a number,
but of a process.

Just for clarification :  *Any* number/string can be the result of
a uniformly random process.  In fact, a uniformly random process will
always produce all numbers equiprobably, by construction.

Any number can also be produced as the result of a non-random process,
although for many numbers this will be a very uninteresting process
such as a simple table-lookup and copy.

The closest relative for irrationality is not the properties such
as "non-repeating fraction" (which is a thoroughly bogus definition,
by the way), but the method by which you GET a rational number.

To wit, a rational number can be generated as the ratio of two
integers p and q (q != 0 for the formalists, pthththththth).  An
irrational number is a number that cannot be so generated.

Now, it so happens (lucky us) that any number that can be generated
as the ratio of two integers can also be written as a terminating
and/or repeating continued decimal string.  This is an independent
property, first proved in the year <mumble> by someone no doubt too
famous for me to remember offhand.  But the fact that you can
characterize a number as rational or irrational by inspection is,
strictly speaking, a lucky fluke.

There's a similar definition for, e.g., transcendentals -- a
transcendental number, of course, is a number that cannot be produced
as the solution to a polynomial equation.  Transcendentals are a
strict subset of irrationals -- sqrt(2), for instance, is irrational
but not transcendental. However, there's no way to characterize *by
inspection* whether or not a given irrational number is
transcendental.  I can easily prove a given number is *NOT*
transcendental by showing a polynomial to which &c., but
I can't go the other way.

So the point is that the characterization of both irrationals and
transcendentals is a) strictly process-driven, and b) defined in the
negative sense -- "no possible way to...CRYPHTML.HTM"  That irrationals can be
cleanly defined in typographic properties should *not* lead you to
believe that randomness can also be defined in typographic
properties or that it can be defined in positive terms.
+++++

Bob Knauer

"An honest man can feel no pleasure in the exercise of power over
his fellow citizens."
--Thomas Jefferson



Subject: Re: hardRandNumbGen
Date: Mon, 25 Jan 1999 04:44:51 -1000
From: ".·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·." <real@complex.net>
Message-ID: <36AC8363.6D55@complex.net>
References: <36abd8e9.0@ecn.ab.ca>
Newsgroups: sci.crypt
Lines: 240

On Sun, 24 Jan 1999 03:53:40 -1000, in <36AB25E4.2E7E@complex.net>, in
sci.crypt <real@complex.net> sinewave wrote:

>Terry Ritter wrote:

sinewave:
>>A digital ring oscillator composed of Schmitt Triggers (with 
>>hysteresis) can be designed to have a slow rise time of ten 
>>microseconds, 

Terry:
>Presumably this means that the effective source resistance is large
>compared to the input capacitance, and the source of the delay is an
>R-C ramp to the next stage.

Yes.

>>but they respond to an input transition in 100ps, to
>>use round numbers. To illustrate the powerful effect that these 
>>facts have on  the recording of thermal noise, I will give the 
>>details of it operation. Assume there is a +/- 1 millivolt thermal
>>noise present on the output of an inverter. 

>That means that this "large signal" design is probably sensitive to
>even tiny power and ground transients.  It is going to be very hard to
>distinguish the effects of "real" thermal noise from transient
>feedback due to the structure of the circuit.  So how can we have
>confidence in the result?  Statistical testing cannot distinguish
>between "physical" and "pseudo" randomness.  

In the real world, it is not always possible to tell. Integrating 
a random number generator (RNG) on a commodity IC is similar to
a manned expedition to MARS: they must take everything with them
into that harsh environment that they will need. If the craft is 
buffeted by periodic winds, they do not have the luxury of calling 
back to base and saying, "Houston, you told us this was a vacuum, 
please make it a perfect vacuum, over". The RNG will encounter
non-ideal electrical environments. It should have redundant systems
which are combined to give the final random number the best shot at
being unpredictable, not perfect, but unpredictable. The multiple 
ring oscillator design described here should be a part of the 
on-chip subsystem: it is an unpredictable seed generator. One can 
also add a differential amplifier RNG with power supply noise 
rejection capabilities, a PRNG, a counter, a hash, and storage for 
the previous random number to use for initialization and for
checking firmware. The RNG described above is a Large Signal
Random Number Generator, to be described in more detail, below.

>>Assume a Schmitt trigger
>>will switch when its input rises above 1v for a system using 2v
>>power supplies. The oscillator runs at 100khz. How long will it take 
>>for the input to rise 2mV? That is 2mV divided by 1V/10us or 50ns.
>>So on every cycle of the oscillator there is a 50ns time when 
>>uncertainty exists. This is a half percent on each cycle.

>As a rare peak value, presumably.  

Yes, I am using round numbers.

>>Since multiple oscillators will be involved, each with a half percent
>>uncertainty, one can see that by using 200 such oscillators XORed 
>>together, the output would be quite random. 

>What I see is a huge complexity-based increase in signal transitions
>(a frequency increase) which will be hard to distinguish from
>heat-based noise.  And if we cannot distinguish operation *with* noise
>from operation *without* noise, we have no way to prove that noise is
>involved at all.  Other than claims and handwaves, of course.  

I am glad you raised the "handwaves" metaphore, because handwaves are
what toss coins. A complex person tosses a coin and you might think it 
is random. The oscillator RNG in this discussion is directly analogous
to a coin toss in many ways. If a coin is not rotating (oscillating)
it will fall back into the hand in the same position that it stated from.
It is the rotation that helps the randomness, not only the complexity 
of the nervous system, the elasticity of the skin, and the trembling of 
the muscles. The rotation should be fast for best results. A juggler 
could become skilled at non-random coin tosses for one coin that 
rotates slowly. But if she tosses three coins with rapid rotation than
it is likely that random results will occur. If a periodic wind is
present in a coin toss, yes, it will influence the outcome, but the 
result will often be recognizable as a useful random throw, or a throw
that was blown away. The same with this RNG.

The major source of randomness of this RNG is the unsynchronized 
nature of multiple oscillators with randomly changing frequencies. This
is a large signal phenomenon, which cannot be accurately described 
mathematically. Similar to a coin toss, many analog variables are 
involved. These continuous variations of many influences cause seeming
randomness. If you can mathematically describe a human coin toss, then
so you can with this RNG. But you cannot, and I cannot. That does not
invalidate the usefulness of these seed generators, not in this 
century.

>>But in practice, 200 
>>oscillators are not needed because there are several sources of
>>uncertainty in a well designed Large Signal Random Number Generator
>>such as the one I designed at a large semiconductor company. It was 
>>fabricated and tested by a team of engineers. It worked well. 

>I have looked at the published results a number of times.  They were
>in fact part of the basis for my investigation of the numerical
>relationship between repeats in sampling and the overall population. 

>Easy calculations using the publushed results show that the effective
>population of values is 1/4 the claimed ideal, which shows that the
>design was not as good as you thought.  

Correct, that first version in that report had an XOR gate placed in 
a bad position, causing twice as many ones as zeros. The CIA alerted 
us to my mistake with that one gate. When removed, the results are 
much better. I still regret my mistake in that one gate placement.

>>It was 
>>evaluated by the CIA and they sent us a report on its 
>>characteristics. 

>The published (admittedly meager) experimental evidence says
>otherwise.  

Single reports do not tell all of the facts.

>>Have you built any hardware random number 
>>generators using large signals?   

>The claimed basis for your generator is thermal noise, which is NOT
>large-signal.  A large-signal digital system is a PSEUDO-random
>digital RNG, and can be implemented in software as well as hardware.
>So, yes, certainly I have implemented and tested many large signal
>(software) RNG's.  

The ealier description was an illustration for some readers to examine.
It was not an exhaustive explanation of the theory behind the design.
I have now expanded upon the description, explaining the large 
signals as being analogous to coin tosses which must rotate due to
a complex had waving motion. The complexity of my circuit design 
mimics, on a small scale, the complexities of the human hand wave
and coin toss. The frequency changes in the design are the analogy
of the hand motion. Thermal irregularities power supply variations
also contribute to this hand motion.

Radioactive decay is also a large signal RNG. It may be considered
to be both digital and analog, as this RNG may be.

>Some software computations are hard to reverse.  But few if any of the
>conventional statistical RNG's have stood up to attack.  Just giving a
>hardware design and claiming "nobody can break this" is the sort of
>thing we see on sci.crypt all the time.

I do not claim nobody can break this. I am presenting concepts to a
wide reading audience. Some of these concepts are less sound than 
others, so the readers have the opportunity to judge various attepts
to produce randomness in a harsh environment. I hope that they  will
fare better than I did.

>The reasoning about this design is contradictory:  Supposedly the
>large signal design is "random" because it senses low-level noise.
>Yet the circuit is supposedly suitable for a noisy digital chip
>because it is a "large-signal" design.  There is a fundamental problem
>in making both claims at the same time.  

I have addressed this above. A large signal, digital oscillator has
small noise on top of that. The randomness is primarily based on the
coin toss analogy. The thermal noise calculation first given is a
secondary source of randomness. The periodic power supply noise
will affect this design more in some ways than it would affect an 
analog circuit with well designed differential and common mode 
considerations. But the ways periodic noise affects these circuits
do not ruin the unpredictability of the resulting numbers. I leave
that discussion for another day.

snip...

>>Mr. Ritter says, "It is this accumulation of energy that makes it 
>>difficult to change the oscillation...CRYPHTML.HTM". It is easy to change the 
>>oscillation period using capacitors that are connected or 
>>disconnected from the oscillator by switches that are 
>>controlled by signals from the random string.

>But that approach is digital complexity, and not thermal randomness.
>It can be simulated in software.  It is PSEUDO-random.  Maybe it is
>strong, maybe not, but there is certainly no proof.  

It is analog complexity. I will give no proof today. Give me proof
of coin tossing that does not involve complexity or strength..

snip..

>The obvious experiment, then, is to take the device to cryogenic
>temperatures and see how it performs.  If the output still has good
>statistics, we can suspect that the output does not represent thermal
>noise at all, but is just a complex digital system.  Was such an
>experiment performed?

No. The circuit depends on many complex factors for randomness, as a
coin toss does. In some imagined laboratory experiment, it is feasible
to control all factors, causing non-random results. In commodity 
applications, Large Signal Random Number Generators are sometimes 
superior to small signal based generators and both may appear on a 
single IC.

>>>A signal composed of many oscillators, each doing their own thing, is
>>>admittedly complex.  But complex relationships are not, by themselves,
>>>cryptographically secure.  We could even think to simulate such a
>>>system numerically, in which case the system is clearly no more than
>>>yet another pseudorandom state machine waiting to be exposed.  And
>>>while any such simulation might not be exact, it could be close, and
>>>we could continually adjust the simulation to the reality we do see.
>>
>>I hope that you would simulate the 200 oscillator example I gave. 

>But your design does not use 200 oscillators, does it?  

No it had 3. The 200 oscillator example is for a simplified explanation
of one source of randomness.

>>Yes, 
>>you can add the +/- 1mV noise and adjust to make it as accurate as you
>>care to invest time for. I have read your pat statement above several 
>>times recently, and I disagree with it. It is possible to design a 
>>complex circuit that is poorly done and which therefore would fail 
>>tests for randomness. 

>Even PSEUDO-random RNG's pass statistical tests.  Those tests have
>nothing to do with cryptographic unpredictability or "strength."  Yet
>strength is what you claim.  

Yes it is a strong source, as upcoming product releases are expected to 
show. Just because old PRNGs pass some tests does not mean that new 
designs are bad, as you imply.

>I think you have missed the distinction between unpredictable
>randomness for cryptography, and ordinary statistical randomness.  

A PSRG may be depended upon to produce the same string under certain
easy to arrange conditions. This RNG does the opposite of that. Two 
sequential random numbers from this circuit would prove that to 
anyone who tests it, most of the time.

Thank you for this polite discussion.


Subject: Re: hardRandNumbGen
Date: Mon, 25 Jan 1999 13:23:11 -0500
From: "Trevor Jackson, III" <fullmoon@aspi.net>
Message-ID: <36ACB68D.34FA34A4@aspi.net>
References: <36AC8363.6D55@complex.net>
Newsgroups: sci.crypt
Lines: 290

Two points, in context below...

.·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·..·´¯`·. wrote:

> On Sun, 24 Jan 1999 03:53:40 -1000, in <36AB25E4.2E7E@complex.net>, in
> sci.crypt <real@complex.net> sinewave wrote:
>
> >Terry Ritter wrote:
>
> sinewave:
> >>A digital ring oscillator composed of Schmitt Triggers (with
> >>hysteresis) can be designed to have a slow rise time of ten
> >>microseconds,
>
> Terry:
> >Presumably this means that the effective source resistance is large
> >compared to the input capacitance, and the source of the delay is an
> >R-C ramp to the next stage.
>
> Yes.
>
> >>but they respond to an input transition in 100ps, to
> >>use round numbers. To illustrate the powerful effect that these
> >>facts have on  the recording of thermal noise, I will give the
> >>details of it operation. Assume there is a +/- 1 millivolt thermal
> >>noise present on the output of an inverter.
>
> >That means that this "large signal" design is probably sensitive to
> >even tiny power and ground transients.  It is going to be very hard to
> >distinguish the effects of "real" thermal noise from transient
> >feedback due to the structure of the circuit.  So how can we have
> >confidence in the result?  Statistical testing cannot distinguish
> >between "physical" and "pseudo" randomness.
>
> In the real world, it is not always possible to tell. Integrating
> a random number generator (RNG) on a commodity IC is similar to
> a manned expedition to MARS: they must take everything with them
> into that harsh environment that they will need. If the craft is
> buffeted by periodic winds, they do not have the luxury of calling
> back to base and saying, "Houston, you told us this was a vacuum,
> please make it a perfect vacuum, over". The RNG will encounter
> non-ideal electrical environments. It should have redundant systems
> which are combined to give the final random number the best shot at
> being unpredictable, not perfect, but unpredictable. The multiple
> ring oscillator design described here should be a part of the
> on-chip subsystem: it is an unpredictable seed generator. One can
> also add a differential amplifier RNG with power supply noise
> rejection capabilities, a PRNG, a counter, a hash, and storage for
> the previous random number to use for initialization and for
> checking firmware. The RNG described above is a Large Signal
> Random Number Generator, to be described in more detail, below.
>
> >>Assume a Schmitt trigger
> >>will switch when its input rises above 1v for a system using 2v
> >>power supplies. The oscillator runs at 100khz. How long will it take
> >>for the input to rise 2mV? That is 2mV divided by 1V/10us or 50ns.
> >>So on every cycle of the oscillator there is a 50ns time when
> >>uncertainty exists. This is a half percent on each cycle.
>
> >As a rare peak value, presumably.
>
> Yes, I am using round numbers.
>
> >>Since multiple oscillators will be involved, each with a half percent
> >>uncertainty, one can see that by using 200 such oscillators XORed
> >>together, the output would be quite random.
>
> >What I see is a huge complexity-based increase in signal transitions
> >(a frequency increase) which will be hard to distinguish from
> >heat-based noise.  And if we cannot distinguish operation *with* noise
> >from operation *without* noise, we have no way to prove that noise is
> >involved at all.  Other than claims and handwaves, of course.
>
> I am glad you raised the "handwaves" metaphore, because handwaves are
> what toss coins. A complex person tosses a coin and you might think it
> is random. The oscillator RNG in this discussion is directly analogous
> to a coin toss in many ways. If a coin is not rotating (oscillating)
> it will fall back into the hand in the same position that it stated from.
> It is the rotation that helps the randomness, not only the complexity
> of the nervous system, the elasticity of the skin, and the trembling of
> the muscles. The rotation should be fast for best results. A juggler
> could become skilled at non-random coin tosses for one coin that
> rotates slowly. But if she tosses three coins with rapid rotation than
> it is likely that random results will occur. If a periodic wind is
> present in a coin toss, yes, it will influence the outcome, but the
> result will often be recognizable as a useful random throw, or a throw
> that was blown away. The same with this RNG.

Human gestures are not a good foundation for system design.  There are large,
industrial concerns that rely upon human-gesture-generated unpredictability.
Their interest is *not* statistical randomness as we find in simulations,
games, and Monte Carlo tests (in spite of the latter name).  Their interest
is the same as ours: unpredicability.  They are called casinos.

In spite of the fantastic efforts taken to eliminate predictability in games
of chance human gestures can still dominate the outcomes completely.  I'm not
referring to shuffling cards systematically, but to rolling a roulette ball
against the wheel so precisely that out of 20 tries a human can obtain a
predicted outcome (slot 17) 10 times.  50% success.  I think that constitutes
predictability.

The hand-eye coordination involved is of an extreme level, requiring decades
of practice to achieve.  But it is real.  The complexity of controlling a
roulette wheel appears to me to be far larger than that of a coin toss.  Even
a fast one.

Without detailed scrutiny of your design I cannot tell whether it is robust.
No inspection of the outcome will convince me it is.  However, the design
philosophy you have expressed leads me to believe there will be weaknesses in
the system.

> The major source of randomness of this RNG is the unsynchronized
> nature of multiple oscillators with randomly changing frequencies. This
> is a large signal phenomenon, which cannot be accurately described
> mathematically. Similar to a coin toss, many analog variables are
> involved. These continuous variations of many influences cause seeming
> randomness. If you can mathematically describe a human coin toss, then
> so you can with this RNG. But you cannot, and I cannot. That does not
> invalidate the usefulness of these seed generators, not in this
> century.

The phrase "randomly changing oscillators" is key to the paragrph above.  I
would like to question the use of the term random in the sense of
unpredictable.  Since the (intermediate) output of the system is driving the
changes to the oscillators there is a full feedback loop present.  This kind
of system may pass statistical tests for randomness, but it may not be
unpredictable.  The result may "cause seeming randomness", but this is far
from unpredictability.  For instance, how much correlation would you expect
from a set of such devices initialized identically?

Even the presmption that the output would pass statistical tests is
questionable.  One famous gafffe in PRNG design was Knuth's composite
generator, which he called superrandom.  Unfortunately it was a closed loop
design.  He did not forsee the possibility of cycles so short as to be
degenerate.  All closed loop designs contain this danger.  If the hardware
output is driving the hardware configuration, it is avidly searching for a
configuration that represents a local minima in its volatility.

Now, given initialization in a configuration near such a local minima, how
much divergence would we find in the output of a set of these devices?

> >>But in practice, 200
> >>oscillators are not needed because there are several sources of
> >>uncertainty in a well designed Large Signal Random Number Generator
> >>such as the one I designed at a large semiconductor company. It was
> >>fabricated and tested by a team of engineers. It worked well.
>
> >I have looked at the published results a number of times.  They were
> >in fact part of the basis for my investigation of the numerical
> >relationship between repeats in sampling and the overall population.
>
> >Easy calculations using the publushed results show that the effective
> >population of values is 1/4 the claimed ideal, which shows that the
> >design was not as good as you thought.
>
> Correct, that first version in that report had an XOR gate placed in
> a bad position, causing twice as many ones as zeros. The CIA alerted
> us to my mistake with that one gate. When removed, the results are
> much better. I still regret my mistake in that one gate placement.
>
> >>It was
> >>evaluated by the CIA and they sent us a report on its
> >>characteristics.
>
> >The published (admittedly meager) experimental evidence says
> >otherwise.
>
> Single reports do not tell all of the facts.
>
> >>Have you built any hardware random number
> >>generators using large signals?
>
> >The claimed basis for your generator is thermal noise, which is NOT
> >large-signal.  A large-signal digital system is a PSEUDO-random
> >digital RNG, and can be implemented in software as well as hardware.
> >So, yes, certainly I have implemented and tested many large signal
> >(software) RNG's.
>
> The ealier description was an illustration for some readers to examine.
> It was not an exhaustive explanation of the theory behind the design.
> I have now expanded upon the description, explaining the large
> signals as being analogous to coin tosses which must rotate due to
> a complex had waving motion. The complexity of my circuit design
> mimics, on a small scale, the complexities of the human hand wave
> and coin toss. The frequency changes in the design are the analogy
> of the hand motion. Thermal irregularities power supply variations
> also contribute to this hand motion.
>
> Radioactive decay is also a large signal RNG. It may be considered
> to be both digital and analog, as this RNG may be.
>
> >Some software computations are hard to reverse.  But few if any of the
> >conventional statistical RNG's have stood up to attack.  Just giving a
> >hardware design and claiming "nobody can break this" is the sort of
> >thing we see on sci.crypt all the time.
>
> I do not claim nobody can break this. I am presenting concepts to a
> wide reading audience. Some of these concepts are less sound than
> others, so the readers have the opportunity to judge various attepts
> to produce randomness in a harsh environment. I hope that they  will
> fare better than I did.
>
> >The reasoning about this design is contradictory:  Supposedly the
> >large signal design is "random" because it senses low-level noise.
> >Yet the circuit is supposedly suitable for a noisy digital chip
> >because it is a "large-signal" design.  There is a fundamental problem
> >in making both claims at the same time.
>
> I have addressed this above. A large signal, digital oscillator has
> small noise on top of that. The randomness is primarily based on the
> coin toss analogy. The thermal noise calculation first given is a
> secondary source of randomness. The periodic power supply noise
> will affect this design more in some ways than it would affect an
> analog circuit with well designed differential and common mode
> considerations. But the ways periodic noise affects these circuits
> do not ruin the unpredictability of the resulting numbers. I leave
> that discussion for another day.
>
> snip...
>
> >>Mr. Ritter says, "It is this accumulation of energy that makes it
> >>difficult to change the oscillation...CRYPHTML.HTM". It is easy to change the
> >>oscillation period using capacitors that are connected or
> >>disconnected from the oscillator by switches that are
> >>controlled by signals from the random string.
>
> >But that approach is digital complexity, and not thermal randomness.
> >It can be simulated in software.  It is PSEUDO-random.  Maybe it is
> >strong, maybe not, but there is certainly no proof.
>
> It is analog complexity. I will give no proof today. Give me proof
> of coin tossing that does not involve complexity or strength..
>
> snip..
>
> >The obvious experiment, then, is to take the device to cryogenic
> >temperatures and see how it performs.  If the output still has good
> >statistics, we can suspect that the output does not represent thermal
> >noise at all, but is just a complex digital system.  Was such an
> >experiment performed?
>
> No. The circuit depends on many complex factors for randomness, as a
> coin toss does. In some imagined laboratory experiment, it is feasible
> to control all factors, causing non-random results. In commodity
> applications, Large Signal Random Number Generators are sometimes
> superior to small signal based generators and both may appear on a
> single IC.
>
> >>>A signal composed of many oscillators, each doing their own thing, is
> >>>admittedly complex.  But complex relationships are not, by themselves,
> >>>cryptographically secure.  We could even think to simulate such a
> >>>system numerically, in which case the system is clearly no more than
> >>>yet another pseudorandom state machine waiting to be exposed.  And
> >>>while any such simulation might not be exact, it could be close, and
> >>>we could continually adjust the simulation to the reality we do see.
> >>
> >>I hope that you would simulate the 200 oscillator example I gave.
>
> >But your design does not use 200 oscillators, does it?
>
> No it had 3. The 200 oscillator example is for a simplified explanation
> of one source of randomness.
>
> >>Yes,
> >>you can add the +/- 1mV noise and adjust to make it as accurate as you
> >>care to invest time for. I have read your pat statement above several
> >>times recently, and I disagree with it. It is possible to design a
> >>complex circuit that is poorly done and which therefore would fail
> >>tests for randomness.
>
> >Even PSEUDO-random RNG's pass statistical tests.  Those tests have
> >nothing to do with cryptographic unpredictability or "strength."  Yet
> >strength is what you claim.
>
> Yes it is a strong source, as upcoming product releases are expected to
> show. Just because old PRNGs pass some tests does not mean that new
> designs are bad, as you imply.
>
> >I think you have missed the distinction between unpredictable
> >randomness for cryptography, and ordinary statistical randomness.
>
> A PSRG may be depended upon to produce the same string under certain
> easy to arrange conditions. This RNG does the opposite of that. Two
> sequential random numbers from this circuit would prove that to
> anyone who tests it, most of the time.
>
> Thank you for this polite discussion.





Subject: Re: hardRandNumbGen
Date: Tue, 26 Jan 1999 03:24:11 -1000
From: handWave <real9@complex9.net>
Message-ID: <36ADC1FB.4212@complex9.net>
References: <36ACB68D.34FA34A4@aspi.net>
Newsgroups: sci.crypt
Lines: 116

Trevor Jackson, III wrote:

handWave wrote:
> > I am glad you raised the "handwaves" metaphore, because handwaves are
> > what toss coins. A complex person tosses a coin and you might think it
> > is random. The oscillator RNG in this discussion is directly analogous
> > to a coin toss in many ways. If a coin is not rotating (oscillating)
> > it will fall back into the hand in the same position that it stated from.
> > It is the rotation that helps the randomness, not only the complexity
> > of the nervous system, the elasticity of the skin, and the trembling of
> > the muscles. The rotation should be fast for best results. A juggler
> > could become skilled at non-random coin tosses for one coin that
> > rotates slowly. But if she tosses three coins with rapid rotation than
> > it is likely that random results will occur. If a periodic wind is
> > present in a coin toss, yes, it will influence the outcome, but the
> > result will often be recognizable as a useful random throw, or a throw
> > that was blown away. The same with this RNG.
> 
> Human gestures are not a good foundation for system design.  There are large,
> industrial concerns that rely upon human-gesture-generated unpredictability.
> Their interest is *not* statistical randomness as we find in simulations,
> games, and Monte Carlo tests (in spite of the latter name).  Their interest
> is the same as ours: unpredicability.  They are called casinos.

The product I designed was evaluated for casinos by Bally, a potential 
customer.

> 
> In spite of the fantastic efforts taken to eliminate predictability in games
> of chance human gestures can still dominate the outcomes completely.  I'm not
> referring to shuffling cards systematically, but to rolling a roulette ball
> against the wheel so precisely that out of 20 tries a human can obtain a
> predicted outcome (slot 17) 10 times.  50% success.  I think that constitutes
> predictability.

Yes, this is like the skilled juggler I described above. The analogy to a 
hardRandNumbGen is a skilled hacker who controls the power supply noise, 
the clock glitches, the radio beams so that the RNG becomes under his 
control. The chip designer must anticipate such antics, and prepare the 
module for lunar insertion.

> The hand-eye coordination involved is of an extreme level, requiring decades
> of practice to achieve.  But it is real.  The complexity of controlling a
> roulette wheel appears to me to be far larger than that of a coin toss.  Even
> a fast one.

I dispute this. A coin has one bit of output, a wheel has many bits in 
one toss. A wheel is a big target with a smaller bandwidth for RPMs. A 
coin has a wider bandwidth, perhaps 1hz to 50 hz, a wheel, from .1 hz to 
.5 hz on the initial spin. A coin may be tossed from a rooftop. Wheels 
would fracture under such conditions.
> 
> Without detailed scrutiny of your design I cannot tell whether it is robust.

I can send you the patent number by private email, upon request posted 
here in sci.crypt.

> No inspection of the outcome will convince me it is.  However, the design
> philosophy you have expressed leads me to believe there will be weaknesses in
> the system.

Yes there are weaknesses. A moonshot too has weaknesses, and people do 
their best to prepare a module for its harsh environment. The payoff is 
so sweet, though. It is better to have thrashed and lost some entropy, 
than never to have thrashed at all.

> 
> > The major source of randomness of this RNG is the unsynchronized
> > nature of multiple oscillators with randomly changing frequencies. This
> > is a large signal phenomenon, which cannot be accurately described
> > mathematically. Similar to a coin toss, many analog variables are
> > involved. These continuous variations of many influences cause seeming
> > randomness. If you can mathematically describe a human coin toss, then
> > so you can with this RNG. But you cannot, and I cannot. That does not
> > invalidate the usefulness of these seed generators, not in this
> > century.
> 
> The phrase "randomly changing oscillators" is key to the paragrph above.  I
> would like to question the use of the term random in the sense of
> unpredictable.  Since the (intermediate) output of the system is driving the
> changes to the oscillators there is a full feedback loop present.  This kind
> of system may pass statistical tests for randomness, but it may not be
> unpredictable.  The result may "cause seeming randomness", but this is far
> from unpredictability.  For instance, how much correlation would you expect
> from a set of such devices initialized identically?

We ran mathematical auto-correlation tests looking exactly for this, and 
got good results. This type of multi-oscillator, frequency modulated, 
unsynchronized circuit is part analog and part digits. It is susceptible 
to realities as a hand exists in realities during a toss. Many subtle 
influences come into play, including the capacitance between the moon and 
the IC.

> 
> Even the presmption that the output would pass statistical tests is
> questionable.  One famous gafffe in PRNG design was Knuth's composite
> generator, which he called superrandom.  Unfortunately it was a closed loop
> design. 

It was a computer program.

 >He did not forsee the possibility of cycles so short as to be
> degenerate.  All closed loop designs contain this danger.  If the hardware
> output is driving the hardware configuration, it is avidly searching for a
> configuration that represents a local minima in its volatility.
> 
> Now, given initialization in a configuration near such a local minima, how
> much divergence would we find in the output of a set of these devices?

Good point. This is exactly what we were looking for. The results were 
excellent. I wave my hands vigorously at this point to emphasize that 
this type of circuit exists in the real world as we do. It is in the 
school of hard knocks. It can be defeated. But it has some value as a 
commodity product in certain well chosen scenarios.

handWave


Subject: Re: hardRandNumbGen
Date: Tue, 26 Jan 1999 13:33:49 +0100
From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de>
Message-ID: <36ADB62D.E681674F@stud.uni-muenchen.de>
References: <36ADC1FB.4212@complex9.net>
Newsgroups: sci.crypt
Lines: 31

handWave wrote:
> 

> > Even the presmption that the output would pass statistical tests is
> > questionable.  One famous gafffe in PRNG design was Knuth's composite
> > generator, which he called superrandom.  Unfortunately it was a closed loop
> > design.
> 
> It was a computer program.

Having previously taken part in discussions in several threads of 
this group on random number generations, I doubt nevertheless that
I have really known an answer to the following question:

If I have two sources of randomness, one software and one hardware,
both passing all statistical tests I apply equally well, why should 
I choose one source in preference to the other? And if additionally 
I don't know which sequence I get is from software and which is from 
hardware? (Compare the Turing test.) How does the origin of the
sequence affect the workload of the analyst, if the software
generation process involves so many parameters that for combinatorical
reasons he has no chance of directly dealing with them but has
to try to look instead for possible regularities/irregularities in 
the sequence itself and, by assumption, the sequences from the
two sources are of equal statistical quality? (Note that the
hardware source is (in my humble opinion) unpredictable simply 
because there are so many participating 'parameters' that the 
'summation' (the end product) becomes unpredictable, cf. the casting 
of a dice.)

M. K. Shen


Subject: Re: hardRandNumbGen
Date: Tue, 26 Jan 1999 12:28:17 -0500
From: "Trevor Jackson, III" <fullmoon@aspi.net>
Message-ID: <36ADFB30.BB4B07FD@aspi.net>
References: <36ADB62D.E681674F@stud.uni-muenchen.de>
Newsgroups: sci.crypt
Lines: 60

Mok-Kong Shen wrote:

> handWave wrote:
> >
>
> > > Even the presmption that the output would pass statistical tests is
> > > questionable.  One famous gafffe in PRNG design was Knuth's composite
> > > generator, which he called superrandom.  Unfortunately it was a closed loop
> > > design.
> >
> > It was a computer program.
>
> Having previously taken part in discussions in several threads of
> this group on random number generations, I doubt nevertheless that
> I have really known an answer to the following question:
>
> If I have two sources of randomness, one software and one hardware,
> both passing all statistical tests I apply equally well, why should
> I choose one source in preference to the other? And if additionally
> I don't know which sequence I get is from software and which is from
> hardware? (Compare the Turing test.) How does the origin of the
> sequence affect the workload of the analyst, if the software
> generation process involves so many parameters that for combinatorical
> reasons he has no chance of directly dealing with them but has
> to try to look instead for possible regularities/irregularities in
> the sequence itself and, by assumption, the sequences from the
> two sources are of equal statistical quality? (Note that the
> hardware source is (in my humble opinion) unpredictable simply
> because there are so many participating 'parameters' that the
> 'summation' (the end product) becomes unpredictable, cf. the casting
> of a dice.)

The fundamental reason is that, for security purposes, we have to assume that our
opponent can do anything we can do.  We can re-run the software and obtain the
identical output.  We cannot re-run the hardware and get the same output.  Thus the
hardware is superior.

The deceptive provision in your question is the fact that the sources are hidden.
This amounts to security via obscurity.  Obscurity fails catastrophicaly when it is
breached.  A bad thing because the opponent can steal a copy of the software and
get every output we will every get.  He cannot steal a copy of the machine and get
identical outputs to ours.

This line of thought identifies a possible opportunity for Bill Gates; a true
marketing genius if  there ever was one.  Everyone alive in 1980 knew that software
was the "plastic" of the decade and that the market for software was going to grow
quickly.  But no other person alive in 1980 forsaw just how big the market would be
for really bad software.  Everyone else was concentrating on reasonably good
software. This is why Gates is a multi-deca-billionaire.

Now, in crypto, you have identified another case in which people cannot tell
whether someone is selling Good Stuff or Really Bad Crap.  Since it is not
reasonable to distinguish the two, we need an organization to produce a tiny amount
of Good Stuff and massive quantities of Really Bad Crap, and sell it all as the
former.  No one could tell the difference, and, in theory, no one would care.

Bill, are you listening?





Subject: Re: hardRandNumbGen
Date: Tue, 26 Jan 1999 19:25:23 GMT
From: rcktexas@ix.netcom.com (R. Knauer)
Message-ID: <36ae1411.29221428@nntp.ix.netcom.com>
References: <36ADFB30.BB4B07FD@aspi.net>
Newsgroups: sci.crypt
Lines: 45

On Tue, 26 Jan 1999 12:28:17 -0500, "Trevor Jackson, III"
<fullmoon@aspi.net> wrote:

>This line of thought identifies a possible opportunity for Bill Gates; a true
>marketing genius if  there ever was one.

I guess you consider Attila the Hun to be a military genius too. :-)

>But no other person alive in 1980 forsaw just how big the market would be
>for really bad software.

Hell, the auto industry knew that way before Gates used it in the S/W
industry. He just took the same marketing concepts used by Henry Ford
and built the same kind of fortune.

"You can have any color Model T you want as long as it runs on
Windows."

>Now, in crypto, you have identified another case in which people cannot tell
>whether someone is selling Good Stuff or Really Bad Crap.  Since it is not
>reasonable to distinguish the two, we need an organization to produce a tiny amount
>of Good Stuff and massive quantities of Really Bad Crap, and sell it all as the
>former.  No one could tell the difference, and, in theory, no one would care.

Soon Gates is gonna retire all his programmers at MicroShaft and
install a TRNG to produce code. And now that his beta test force is
big enough, he can partition the outputs and see what runs
experimentally.

Depending on which beta test group(s) order the next "revision", he
can decide what to put in shrinkwrap. If it gets to the Windows Logo,
it is good enough for the consuming public.

If they don't like it, let them run UNIX.

>Bill, are you listening?

HA! Unka Bill is too busy working on his new TRNG.

Bob Knauer

"An honest man can feel no pleasure in the exercise of power over
his fellow citizens."
--Thomas Jefferson



Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 15:30:05 +0100
From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de>
Message-ID: <36AF22ED.9D0E25B0@stud.uni-muenchen.de>
References: <36ADFB30.BB4B07FD@aspi.net>
Newsgroups: sci.crypt
Lines: 21

Trevor Jackson, III wrote:
> 

> The fundamental reason is that, for security purposes, we have to assume that our
> opponent can do anything we can do.  We can re-run the software and obtain the
> identical output.  We cannot re-run the hardware and get the same output.  Thus the
> hardware is superior.
> 
> The deceptive provision in your question is the fact that the sources are hidden.
> This amounts to security via obscurity.  Obscurity fails catastrophicaly when it is
> breached.  A bad thing because the opponent can steal a copy of the software and
> get every output we will every get.  He cannot steal a copy of the machine and get
> identical outputs to ours.

If you produce some sequence with a sufficiently good algorithm with 
a sufficiently long key and later forget that key, even you wouldn't 
be able to reproduce the sequence. As to stealing I suppose it is 
irrelevant in the present context. (If you have a one-time pad and
that got stolen (copied), then what?)

M. K. Shen


Subject: Re: hardRandNumbGen
Date: Tue, 26 Jan 1999 17:56:39 GMT
From: rcktexas@ix.netcom.com (R. Knauer)
Message-ID: <36ae019b.24495482@nntp.ix.netcom.com>
References: <36ADB62D.E681674F@stud.uni-muenchen.de>
Newsgroups: sci.crypt
Lines: 16

On Tue, 26 Jan 1999 13:33:49 +0100, Mok-Kong Shen
<mok-kong.shen@stud.uni-muenchen.de> wrote:

>If I have two sources of randomness, one software and one hardware,
>both passing all statistical tests I apply equally well, why should 
>I choose one source in preference to the other?

Why do you persist in believing that statistical tests have anything
to do with randomness in cryptography?

Bob Knauer

"An honest man can feel no pleasure in the exercise of power over
his fellow citizens."
--Thomas Jefferson



Subject: Re: hardRandNumbGen
Date: Tue, 26 Jan 1999 19:24:18 +0100
From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de>
Message-ID: <36AE0852.16B9A95F@stud.uni-muenchen.de>
References: <36ae019b.24495482@nntp.ix.netcom.com>
Newsgroups: sci.crypt
Lines: 18

R. Knauer wrote:
> 
> On Tue, 26 Jan 1999 13:33:49 +0100, Mok-Kong Shen
> <mok-kong.shen@stud.uni-muenchen.de> wrote:
> 
> >If I have two sources of randomness, one software and one hardware,
> >both passing all statistical tests I apply equally well, why should
> >I choose one source in preference to the other?
> 
> Why do you persist in believing that statistical tests have anything
> to do with randomness in cryptography?

Tell me what other (better) tools are available for me to make
the decision. These are simply easy to obtain, as far as my
humble knowledge goes. Please kindly give your recipe to cope with 
the situation I described. Thanks in advance.

M. K. Shen


Subject: Re: hardRandNumbGen
Date: Tue, 26 Jan 1999 19:33:24 GMT
From: rcktexas@ix.netcom.com (R. Knauer)
Message-ID: <36ae16a8.29884341@nntp.ix.netcom.com>
References: <36AE0852.16B9A95F@stud.uni-muenchen.de>
Newsgroups: sci.crypt
Lines: 41

On Tue, 26 Jan 1999 19:24:18 +0100, Mok-Kong Shen
<mok-kong.shen@stud.uni-muenchen.de> wrote:

>> Why do you persist in believing that statistical tests have anything
>> to do with randomness in cryptography?

>Tell me what other (better) tools are available for me to make
>the decision.

If I told you that there are none, would you believe me?

>These are simply easy to obtain, as far as my
>humble knowledge goes.

So is snake oil.

>Please kindly give your recipe to cope with 
>the situation I described. Thanks in advance.

Learn what crypto-grade randomness is. The concept is deceptively
simple once you understand it. But first you have to give up all other
definitions of randomness from other fields like statistics.

The key to understanding is that randomness depends on the generation
process, not the numbers themselves. The number 000...0 fails all
sorts of statistical tests, but can be a random number if it is
generated by a TRNG. Until you analyze the method of generation, you
cannot know.

A TRNG is a physical device that is capable of generating all possible
sequences of a given finite length equiprobably. If you understand
that, then you will understand crypto-grade randomness - and, as
another poster pointed out yesterday, you will also understand
cryptography.

Bob Knauer

"An honest man can feel no pleasure in the exercise of power over
his fellow citizens."
--Thomas Jefferson



Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 15:38:29 +0100
From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de>
Message-ID: <36AF24E5.95D5D7F9@stud.uni-muenchen.de>
References: <36ae16a8.29884341@nntp.ix.netcom.com>
Newsgroups: sci.crypt
Lines: 17

R. Knauer wrote:

> A TRNG is a physical device that is capable of generating all possible
> sequences of a given finite length equiprobably. If you understand
> that, then you will understand crypto-grade randomness - and, as
> another poster pointed out yesterday, you will also understand
> cryptography.

Excellent! Then tell me HOW to get such a physical device that 
PROVABLY is capable of generating all possible sequences of a given 
finite length equiprobalbly.

Secondly, your equiprobability is not at all sufficient. If
the said given finite length is 2, is a physical divice outputting
0001101100011011..... a TRNG?????

M. K. Shen


Subject: Re: hardRandNumbGen
Date: 27 Jan 1999 09:51:46 -0500
From: juola@mathcs.duq.edu (Patrick Juola)
Message-ID: <78n962$lii$1@quine.mathcs.duq.edu>
References: <36AF24E5.95D5D7F9@stud.uni-muenchen.de>
Newsgroups: sci.crypt
Lines: 40

In article <36AF24E5.95D5D7F9@stud.uni-muenchen.de>,
Mok-Kong Shen  <mok-kong.shen@stud.uni-muenchen.de> wrote:
>R. Knauer wrote:
>
>> A TRNG is a physical device that is capable of generating all possible
>> sequences of a given finite length equiprobably. If you understand
>> that, then you will understand crypto-grade randomness - and, as
>> another poster pointed out yesterday, you will also understand
>> cryptography.
>
>Excellent! Then tell me HOW to get such a physical device that 
>PROVABLY is capable of generating all possible sequences of a given 
>finite length equiprobalbly.

You can't.  Tell me how you can build a plane that will *provably*
fly equally stably in any direction.

>Secondly, your equiprobability is not at all sufficient. If
>the said given finite length is 2, is a physical divice outputting
>0001101100011011..... a TRNG?????

You can't tell.  You've framed the question such that it's
unanswerable due to insufficient information :

There is a coffee cup on the southeast corner of my desk.  If
it is approximately 1/3 full, what is written on the outside
of the cup?

What kind of mileage does a blue car get?

However, the fact that you've asked a dumb question doesn't mean that
the concepts aren't useful -- both paint color and mileage are
important in describing and evaluating cars.  But they're not connected
the way you think they are.

The fact that you're repeatedly asking the same dumb question does,
however, suggest that you're not really interested in the answer.

	-kitten



Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 16:12:44 +0100
From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de>
Message-ID: <36AF2CEC.B5684684@stud.uni-muenchen.de>
References: <78n962$lii$1@quine.mathcs.duq.edu>
Newsgroups: sci.crypt
Lines: 11

Patrick Juola wrote:
> 

> The fact that you're repeatedly asking the same dumb question does,
> however, suggest that you're not really interested in the answer.

The origninal purpose is evidently: Since there can't be an good
answer, one can't claim hardware sequences are always to be preferred 
to software sequences.

M. K. Shen


Subject: Re: hardRandNumbGen
Date: 27 Jan 1999 10:30:16 -0500
From: juola@mathcs.duq.edu (Patrick Juola)
Message-ID: <78nbe8$llm$1@quine.mathcs.duq.edu>
References: <36AF2CEC.B5684684@stud.uni-muenchen.de>
Newsgroups: sci.crypt
Lines: 27

In article <36AF2CEC.B5684684@stud.uni-muenchen.de>,
Mok-Kong Shen  <mok-kong.shen@stud.uni-muenchen.de> wrote:
>Patrick Juola wrote:
>> 
>
>> The fact that you're repeatedly asking the same dumb question does,
>> however, suggest that you're not really interested in the answer.
>
>The origninal purpose is evidently: Since there can't be an good
>answer, one can't claim hardware sequences are always to be preferred 
>to software sequences.

Your claim above is untrue.  I can prove that there can't be a good
s/w sequence running on a deterministic machine.  But I can't do that
merely by inspecting any finite sample of outputs -- I have to look
at the generators to do it.  Of course, any bad PRNG can be implemented
either in h/w or s/w, so just because something is in h/w doesn't make
it good.

More accurately : one can't claim hardware sequences are always to 
be preferred to software sequences *on the basis of a statistical
analysis of a finite set of output sequences.*   

But this is unsurprising.  I can't tell you the gas mileage by looking
at the color of the paint, either.

	-kitten


Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 16:48:46 +0100
From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de>
Message-ID: <36AF355E.DA6A3DBC@stud.uni-muenchen.de>
References: <78nbe8$llm$1@quine.mathcs.duq.edu>
Newsgroups: sci.crypt
Lines: 11

Patrick Juola wrote:
> 

> More accurately : one can't claim hardware sequences are always to
> be preferred to software sequences *on the basis of a statistical
> analysis of a finite set of output sequences.*

The issue is: Are there other sound scientific basis to claim the 
said preference.

M. K. Shen


Subject: Re: hardRandNumbGen
Date: 27 Jan 1999 12:04:02 -0500
From: juola@mathcs.duq.edu (Patrick Juola)
Message-ID: <78ngu3$lsg$1@quine.mathcs.duq.edu>
References: <36AF355E.DA6A3DBC@stud.uni-muenchen.de>
Newsgroups: sci.crypt
Lines: 16

In article <36AF355E.DA6A3DBC@stud.uni-muenchen.de>,
Mok-Kong Shen  <mok-kong.shen@stud.uni-muenchen.de> wrote:
>Patrick Juola wrote:
>> 
>
>> More accurately : one can't claim hardware sequences are always to
>> be preferred to software sequences *on the basis of a statistical
>> analysis of a finite set of output sequences.*
>
>The issue is: Are there other sound scientific basis to claim the 
>said preference.

And the answer is : yes, if your goal is to provide unbounded
degrees of security for messages of unbounded length.

	-kitten


Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 18:20:22 +0100
From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de>
Message-ID: <36AF4AD6.1EC74EF0@stud.uni-muenchen.de>
References: <78ngu3$lsg$1@quine.mathcs.duq.edu>
Newsgroups: sci.crypt
Lines: 27

Patrick Juola wrote:
> 
> In article <36AF355E.DA6A3DBC@stud.uni-muenchen.de>,
> Mok-Kong Shen  <mok-kong.shen@stud.uni-muenchen.de> wrote:
> >Patrick Juola wrote:
> >>
> >
> >> More accurately : one can't claim hardware sequences are always to
> >> be preferred to software sequences *on the basis of a statistical
> >> analysis of a finite set of output sequences.*
> >
> >The issue is: Are there other sound scientific basis to claim the
> >said preference.
> 
> And the answer is : yes, if your goal is to provide unbounded
> degrees of security for messages of unbounded length.

I would be happy with a weaker goal, i.e. for messages of a
certain finite length. Could you provide the requested sound
scientific basis? Note that I am going to use the sequences
in practical applications. So any claimed degree of security
has be shown with a practical algorithm. I am also prepared to
weaken the goal further to 'bounded degree of security' if you
can give a precise definition of 'degree of security' that is 
satisfactory for the practice.

M. K. Shen


Subject: Re: hardRandNumbGen
Date: 27 Jan 1999 14:27:50 -0500
From: juola@mathcs.duq.edu (Patrick Juola)
Message-ID: <78npbm$m42$1@quine.mathcs.duq.edu>
References: <36AF4AD6.1EC74EF0@stud.uni-muenchen.de>
Newsgroups: sci.crypt
Lines: 67

In article <36AF4AD6.1EC74EF0@stud.uni-muenchen.de>,
Mok-Kong Shen  <mok-kong.shen@stud.uni-muenchen.de> wrote:
>Patrick Juola wrote:
>> 
>> In article <36AF355E.DA6A3DBC@stud.uni-muenchen.de>,
>> Mok-Kong Shen  <mok-kong.shen@stud.uni-muenchen.de> wrote:
>> >Patrick Juola wrote:
>> >>
>> >
>> >> More accurately : one can't claim hardware sequences are always to
>> >> be preferred to software sequences *on the basis of a statistical
>> >> analysis of a finite set of output sequences.*
>> >
>> >The issue is: Are there other sound scientific basis to claim the
>> >said preference.
>> 
>> And the answer is : yes, if your goal is to provide unbounded
>> degrees of security for messages of unbounded length.
>
>I would be happy with a weaker goal, i.e. for messages of a
>certain finite length. Could you provide the requested sound
>scientific basis?

Sure.  If the key is "as random as" the message, then Shannon's
proof of secrecy goes through.  In particular, if your messages
are bounded by a given length N, then if you can get N bits of
randomness, from whatever source, hardware or software, then
you can achieve perfect secrecy.

How you get them is, of course, your problem.  The difficulty is
in *proving* that a given sequence of N bits is contains N bits
of randomness (or more formally that a given generator produces
exactly random bits).  But it's fairly easy to gather *MORE* than
N bits -- as much more as you feel confident that it is unlikely
to be more less than N bits of randomness in the resulting sample.

Furthermore, I note that "sound scientific basis" doesn't necessarily
rely on a formal, mathematical proof.  We use the acceleration of
gravity g = 9.8 m/sec on the basis of experiment rather than any
first-principle analysis.  Similar experiments show that, for instance,
English text contains just over one bit of randomness per character.
If you need a thousand bits of randomness, get a thousand characters
of English text from a secure source, distill them appropriately with
a trusted hashing function.  Better yet, get 1500 characters to allow
for sloppy engineering -- you'd never run a wire at its rated wattage,
would you?  Take the resulting 1000 bit string, XOR it with the plaintext,
and voila.  A scientifically sound method of securing 1000 bit secrets.

>I am also prepared to
>weaken the goal further to 'bounded degree of security' if you
>can give a precise definition of 'degree of security' that is 
>satisfactory for the practice.

Well, the usual definition is "work factor" -- the ratio of work
necessary to read a message without the key vs. with the key.
Again, "sound scientific basis" does not necessarily rely on proof;
if you are willing to accept (as many scientists do) that RSA is
as secure as factoring, then the work factor to crack an RSA code
can be made as large as you like by raising the modulus appropriately.
If you don't believe that RSA is as secure as factoring.... well, there
are other methods out there with various conjectures about their
difficulty of solution.  If you don't believe *any* conjectures, you're
arguably in the same camp as people who don't really believe that 
the force of gravity is constant just because it's always been constant
so far....

	-kitten


Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 23:54:24 GMT
From: rcktexas@ix.netcom.com (R. Knauer)
Message-ID: <36afa6cd.50106439@nntp.ix.netcom.com>
References: <78npbm$m42$1@quine.mathcs.duq.edu>
Newsgroups: sci.crypt
Lines: 21

On 27 Jan 1999 14:27:50 -0500, juola@mathcs.duq.edu (Patrick Juola)
wrote:

>English text contains just over one bit of randomness per character.
>If you need a thousand bits of randomness, get a thousand characters
>of English text from a secure source, distill them appropriately with
>a trusted hashing function.  Better yet, get 1500 characters to allow
>for sloppy engineering -- you'd never run a wire at its rated wattage,
>would you?  Take the resulting 1000 bit string, XOR it with the plaintext,
>and voila.  A scientifically sound method of securing 1000 bit secrets.

You once said that such a system was vulnerable to a Bayesian attack.
Have you changed your mind?

Bob Knauer

"No Freeman shall ever be debarred the use of arms. The strongest
reason for the people to retain the right to keep and bear arms is,
as a last resort, to protect themselves against tyranny in government."
--Thomas Jefferson



Subject: Re: hardRandNumbGen
Date: 28 Jan 1999 11:25:33 -0500
From: juola@mathcs.duq.edu (Patrick Juola)
Message-ID: <78q31t$ngq$1@quine.mathcs.duq.edu>
References: <36afa6cd.50106439@nntp.ix.netcom.com>
Newsgroups: sci.crypt
Lines: 25

In article <36afa6cd.50106439@nntp.ix.netcom.com>,
R. Knauer <rcktexas@ix.netcom.com> wrote:
>On 27 Jan 1999 14:27:50 -0500, juola@mathcs.duq.edu (Patrick Juola)
>wrote:
>
>>English text contains just over one bit of randomness per character.
>>If you need a thousand bits of randomness, get a thousand characters
>>of English text from a secure source, distill them appropriately with
>>a trusted hashing function.  Better yet, get 1500 characters to allow
>>for sloppy engineering -- you'd never run a wire at its rated wattage,
>>would you?  Take the resulting 1000 bit string, XOR it with the plaintext,
>>and voila.  A scientifically sound method of securing 1000 bit secrets.
>
>You once said that such a system was vulnerable to a Bayesian attack.
>Have you changed your mind?

No.  The key point here is that the key is as large as -- larger than,
in fact -- the plaintext.  Such a system *would* be vulnerable if you
were using it to secure secrets larger than 1000 bits.  But as long
as the plaintext is finite *AND BOUNDED*, if you can get key material
to exceed that bound, you can get perfect secrecy.

But few of us have bounded secrets.

	-kitten


Subject: Re: hardRandNumbGen
Date: Thu, 28 Jan 1999 23:40:37 GMT
From: rcktexas@ix.netcom.com (R. Knauer)
Message-ID: <36b0f4c7.11366854@nntp.ix.netcom.com>
References: <78q31t$ngq$1@quine.mathcs.duq.edu>
Newsgroups: sci.crypt
Lines: 22

On 28 Jan 1999 11:25:33 -0500, juola@mathcs.duq.edu (Patrick Juola)
wrote:

>as long
>as the plaintext is finite *AND BOUNDED*, if you can get key material
>to exceed that bound, you can get perfect secrecy.

>But few of us have bounded secrets.

You are being uncharacteristically obscure.

Please elaborate on the concepts of "bounded", "unbounded" and how
they apply to a "bounded secret". And just how is a plaintext
"bounded", given that it is finite in length?

Bob Knauer

"No Freeman shall ever be debarred the use of arms. The strongest
reason for the people to retain the right to keep and bear arms is,
as a last resort, to protect themselves against tyranny in government."
--Thomas Jefferson



Subject: Re: hardRandNumbGen
Date: 29 Jan 1999 08:56:25 -0500
From: juola@mathcs.duq.edu (Patrick Juola)
Message-ID: <78sem9$ori$1@quine.mathcs.duq.edu>
References: <36b0f4c7.11366854@nntp.ix.netcom.com>
Newsgroups: sci.crypt
Lines: 37

In article <36b0f4c7.11366854@nntp.ix.netcom.com>,
R. Knauer <rcktexas@ix.netcom.com> wrote:
>On 28 Jan 1999 11:25:33 -0500, juola@mathcs.duq.edu (Patrick Juola)
>wrote:
>
>>as long
>>as the plaintext is finite *AND BOUNDED*, if you can get key material
>>to exceed that bound, you can get perfect secrecy.
>
>>But few of us have bounded secrets.
>
>You are being uncharacteristically obscure.
>
>Please elaborate on the concepts of "bounded", "unbounded" and how
>they apply to a "bounded secret". And just how is a plaintext
>"bounded", given that it is finite in length?

The idea behind a bounded plaintext is fairly simple.  Just say
to yourself that you will never, EVER, in your entire life,
encrypt a document larger than X with a single key.  Splitting
a big document into two into order to make it smaller doesn't
count, as you need two different keys in that case.

X is, then, "the bound."  And it's a measure of how much work you
need to generate the key for each and every message you send --
so make it low.

The difference between bounded and finite is simple -- with finite,
plaintexts, I know that my articles will eventually end, but I don't
know when beforehand.  With a bounded plantext, I set myself a rule
beforehand that I won't go over 30 lines, or 300, or 3 million, whatever
*and stick to that rule.*

Can you promise yourself that you'll never want to Email yourself a
copy of Microsoft Word?

	-kitten


Subject: Re: hardRandNumbGen
Date: Thu, 28 Jan 1999 16:10:36 +0100
From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de>
Message-ID: <36B07DEC.7D4DE9EE@stud.uni-muenchen.de>
References: <78npbm$m42$1@quine.mathcs.duq.edu>
Newsgroups: sci.crypt
Lines: 59

Patrick Juola wrote:

> Sure.  If the key is "as random as" the message, then Shannon's
> proof of secrecy goes through.  In particular, if your messages
> are bounded by a given length N, then if you can get N bits of
> randomness, from whatever source, hardware or software, then
> you can achieve perfect secrecy.
> 
> How you get them is, of course, your problem.  The difficulty is
> in *proving* that a given sequence of N bits is contains N bits
> of randomness (or more formally that a given generator produces
> exactly random bits).  But it's fairly easy to gather *MORE* than
> N bits -- as much more as you feel confident that it is unlikely
> to be more less than N bits of randomness in the resulting sample.
> 
> Furthermore, I note that "sound scientific basis" doesn't necessarily
> rely on a formal, mathematical proof.  We use the acceleration of
> gravity g = 9.8 m/sec on the basis of experiment rather than any
> first-principle analysis.  Similar experiments show that, for instance,
> English text contains just over one bit of randomness per character.
> If you need a thousand bits of randomness, get a thousand characters
> of English text from a secure source, distill them appropriately with
> a trusted hashing function.  Better yet, get 1500 characters to allow
> for sloppy engineering -- you'd never run a wire at its rated wattage,
> would you?  Take the resulting 1000 bit string, XOR it with the plaintext,
> and voila.  A scientifically sound method of securing 1000 bit secrets.

Thank you for the very lucid description of a sound standpoint in
practice ('applied' cryptography as against 'theoretical' cryptography).
We must be realistic, since theoretical stuffs may not be realizable
in the real world and since 'absulute' security is never required
(does it matter if a cipher is cracked after 100 years?) Incidentally,
in another thread I also suggested distiling bit sequences out of
natural language texts as raw materials.

> 
> Well, the usual definition is "work factor" -- the ratio of work
> necessary to read a message without the key vs. with the key.
> Again, "sound scientific basis" does not necessarily rely on proof;
> if you are willing to accept (as many scientists do) that RSA is
> as secure as factoring, then the work factor to crack an RSA code
> can be made as large as you like by raising the modulus appropriately.
> If you don't believe that RSA is as secure as factoring.... well, there
> are other methods out there with various conjectures about their
> difficulty of solution.  If you don't believe *any* conjectures, you're
> arguably in the same camp as people who don't really believe that
> the force of gravity is constant just because it's always been constant
> so far....

I appreciate your opinions and in particular agree with you that
formal proofs are not always needed but can be substituted with
'practical' yet scientifically sound procedures. One should never
be pedantic but one certainly should not be on the other hand
a 'believer' of 'religious assertions' (totally unfounded big
words of someone).

M. K. Shen

M. K. Shen


Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 16:17:41 GMT
From: rcktexas@ix.netcom.com (R. Knauer)
Message-ID: <36af3bd0.22717926@nntp.ix.netcom.com>
References: <78nbe8$llm$1@quine.mathcs.duq.edu>
Newsgroups: sci.crypt
Lines: 17

On 27 Jan 1999 10:30:16 -0500, juola@mathcs.duq.edu (Patrick Juola)
wrote:

>But this is unsurprising.  I can't tell you the gas mileage by looking
>at the color of the paint, either.

There were certain colors that were used exclusively on the Volkswagen
Beetle. That would have given you a strong enough clue to infer the
gas mileage, assuming standard operating conditions.

Bob Knauer

"No Freeman shall ever be debarred the use of arms. The strongest
reason for the people to retain the right to keep and bear arms is,
as a last resort, to protect themselves against tyranny in government."
--Thomas Jefferson



Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 15:43:43 GMT
From: rcktexas@ix.netcom.com (R. Knauer)
Message-ID: <36af340c.20729677@nntp.ix.netcom.com>
References: <36AF2CEC.B5684684@stud.uni-muenchen.de>
Newsgroups: sci.crypt
Lines: 19

On Wed, 27 Jan 1999 16:12:44 +0100, Mok-Kong Shen
<mok-kong.shen@stud.uni-muenchen.de> wrote:

>> The fact that you're repeatedly asking the same dumb question does,
>> however, suggest that you're not really interested in the answer.

>The origninal purpose is evidently: Since there can't be an good
>answer, one can't claim hardware sequences are always to be preferred 
>to software sequences.

See! What did I tell you.

Bob Knauer

"No Freeman shall ever be debarred the use of arms. The strongest
reason for the people to retain the right to keep and bear arms is,
as a last resort, to protect themselves against tyranny in government."
--Thomas Jefferson



Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 15:40:53 GMT
From: rcktexas@ix.netcom.com (R. Knauer)
Message-ID: <36af31b5.20130325@nntp.ix.netcom.com>
References: <78n962$lii$1@quine.mathcs.duq.edu>
Newsgroups: sci.crypt
Lines: 36

On 27 Jan 1999 09:51:46 -0500, juola@mathcs.duq.edu (Patrick Juola)
wrote:

>In article <36AF24E5.95D5D7F9@stud.uni-muenchen.de>,
>Mok-Kong Shen  <mok-kong.shen@stud.uni-muenchen.de> wrote:

>>Secondly, your equiprobability is not at all sufficient. If
>>the said given finite length is 2, is a physical divice outputting
>>0001101100011011..... a TRNG?????

>The fact that you're repeatedly asking the same dumb question does,
>however, suggest that you're not really interested in the answer.

The answer that the poster wants to hear is: Because TRNGs are not
Perfect, PRNGs are just as good.

What he fails to appreciate is that there is a fundamental difference
between a TRNG and a PRNG. That is because he fails to realize that a
crypto-grade random number is characterized by the generation process,
not the number itself.

IOW, according to the poster, regardless of whether a number is
generated by a TRNG or a PRNG, if it passes some statistical tests
(that only work on infinite numbers), then it makes no difference what
the method of generation is.

Maybe there needs to be a law that a student must take cryptography
before statistics. :-)

Bob Knauer

"No Freeman shall ever be debarred the use of arms. The strongest
reason for the people to retain the right to keep and bear arms is,
as a last resort, to protect themselves against tyranny in government."
--Thomas Jefferson



Subject: Re: hardRandNumbGen
Date: Wed, 27 Jan 1999 16:52:30 +0100
From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de>
Message-ID: <36AF363E.45670214@stud.uni-muenchen.de>
References: <36af31b5.20130325@nntp.ix.netcom.com>
Newsgroups: sci.crypt
Lines: 12

R. Knauer wrote:
> 

> What he fails to appreciate is that there is a fundamental difference
> between a TRNG and a PRNG. That is because he fails to realize that a
> crypto-grade random number is characterized by the generation process,
> not the number itself.

Where is the proof of 'if the generation process is hardware then
it is crypto-grade, otherwise it is not'??

M. K. Shen


Subject: Re: hardRandNumbG