Cryptography-Digest Digest #974, Volume #8 Tue, 26 Jan 99 16:13:03 EST
Contents:
Re: hardRandNumbGen (Terry Ritter)
Re: Random numbers from a sound card? (R. Knauer)
Top 14 Sayings Of Classified Military Systems Designers {funnybit, no spam}
([EMAIL PROTECTED])
Re: Idea for plaintext steganography (Patrick Juola)
Re: Random numbers from a sound card? ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: hardRandNumbGen
Date: Tue, 26 Jan 1999 19:35:40 GMT
On Mon, 25 Jan 1999 04:44:51 -1000, in <[EMAIL PROTECTED]>, in
sci.crypt ".���`�..���`�..���`�..���`�..���`�..���`�."
<[EMAIL PROTECTED]> wrote:
>On Sun, 24 Jan 1999 03:53:40 -1000, in <[EMAIL PROTECTED]>, in
>sci.crypt <[EMAIL PROTECTED]> sinewave wrote:
>
>>Terry Ritter wrote:
>[...]
>>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.
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.
>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.
*Every* electronic circuit has requirements; we specify those
requirements and then demand that the larger system achieve them if it
expects the circuit to work. Conceivably, a low-noise section might
have its own filtered analog power with a single-point ground, and
separate digital power.
>It should have redundant systems
Yet we don't have, say, redundant adders on a processor. Why? One
reason is that the result can be even *less* reliable. What we do is
*test* the part, and if it doesn't work, we don't ship it. Which
means we have to be able to test it.
>which are combined to give the final random number the best shot at
>being unpredictable, not perfect, but unpredictable.
If one is going to claim that a design achieves its goals due to
thermal noise, one must at the very least be able to show a
performance change between noise and no-noise. Combining the thermal
noise detection with RNG feedback complexity generally prevents this,
which means we can't test the very thing we claim to do.
>[...]
>The major source of randomness of this RNG is the unsynchronized
>nature of multiple oscillators with randomly changing frequencies.
First, 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"?
Next, the idea that the oscillators have "randomly changing
frequencies" is what we need to prove or demonstrate, and not just
assume. Even chaotic oscillators can follow predictable patterns.
>This
>is a large signal phenomenon, which cannot be accurately described
>mathematically.
Large signal phenomena are precisely those which are best described
mathematically. It is the tiny signals (which must compete with
thermal noise and transients from capacitive, inductive, and
electromagnetic coupling) which are difficult to model well.
>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.
So I guess this is not a machine which provably detects random
molecular events and conveys them to us in the larger world. It is
instead something which looks quite a lot like yet another complex
software PRNG.
>[...]
>>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.
Thank you for the confirmation. Usually I hear about my mistakes.
Apparently I was able to detect a problem in the design which your
team and famous consultant did not, but which the CIA apparently also
detected.
In other words, my analysis was contrary to your beliefs and those of
your crypto expert, but was also correct.
So why are you not listening to me now?
>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.
That is a very unsatisfying explanation for an on-chip device composed
of extremely-well-understood physical components and techniques.
>[...]
>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.
And that is the same reason I confront those claims. Someday I may
have to trust one of those systems.
>>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.
And, to the extent that it is sensitive to "small noise," that part of
its operation is no longer "large signal."
>The randomness is primarily based on the
>coin toss analogy.
Every binary sequence has 1's and 0's, but that does not make the
generator physically random, or even pseudorandom.
>The thermal noise calculation first given is a
>secondary source of randomness.
And the first source would be?
>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.
I would say so, yes.
>But the ways periodic noise affects these circuits
>do not ruin the unpredictability of the resulting numbers.
If these stages are switching not based on thermal noise, but instead
from nearby power transients from digital switching, they could appear
to work, and yet be absolutely correlated to some apparently unrelated
but physically-close device. And that could be predictable, if we are
willing to invest the effort in finding the relationship. And once we
do, of course, we can apply that knowledge to all examples of the
device.
>I leave
>that discussion for another day.
Well :)
>[...]
>>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..
This is the same sort of argument we very often hear from crypto
newbies.
Unfortunately, it is not possible to prove -- or even measure --
cryptographic strength. It *is* possible to prove weakness by finding
"breaks," but typically at great cost. That leaves the rather
unsatisfying task of arguing strength, which is not working here.
>[...]
>>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.
But what would make you think "Large Signal Random Number Generators"
are superior? Even the name is a deception which hides the fact that
switching depends upon tiny noise-level values. The more you discuss
this, the more it sounds like the sort of snake oil we see around her
all the time.
>[...]
>>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.
A press release shows us cryptographic strength?
If these circuits cannot demonstrate that they are detecting the
thermal randomness they are said to use, there is no set of tests in
the world which would be sufficient to show "strength."
>Just because old PRNGs pass some tests does not mean that new
>designs are bad, as you imply.
I imply no such thing. Perhaps you missed the point.
>>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.
That is what you need to prove, or to argue in a convincing way.
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.
The worst case would be that some stages trigger from some unexpected
power transient, or even trigger off each other by unexpected
coupling. In this case, prediction becomes much easier. Most
dangerously, such a device might well seem "random" to all tests not
specifically aware of the unexpected transient or coupling.
>Two
>sequential random numbers from this circuit would prove that to
>anyone who tests it, most of the time.
Testing the output cannot be sufficient to test the design. The
engineering in circuit design is not about handwaves, it is about the
attempt to absolutely understand and control device operation. So if
we can't test it, we can't trust it.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random numbers from a sound card?
Date: Tue, 26 Jan 1999 19:11:42 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 26 Jan 1999 14:19:59 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>> Not really. The OTP system is proveably secure.
>Once again I assert that this is a (for all practical purposes)
>useless fact,
Sorry, but that's nonsense.
For all practical purposes the OTP is proveably secure. That means
that you can build an OTP system that is secure to within a level of
precision can be made arbitrarily small.
To do that you must build a physical device which can generate all
possible sequences of a given finite length equiprobably. That is
possible using quantum mechanical processes and good electronic
design.
The hot line between Washington and Moscow is (supposedly) protected
by an OTP. Conversations on that line can be tapped and interfered
with in principle by anyone close enough to the equipment. Do you
think the two most dangerous govts in the world would trust the fate
of Planet Earth to an insecure communications link? Hardly.
Nothing we humans build is Perfect, but we are able to build things
that are very damn close to Perfect. We can build TRNGs that are
perfect enough to send messages which would take more energy to
analyze than is available in the Universe.
How much more Perfect do you want, even in a practical sense?
>because OTP presuppose (absolutely) true randomness
>and there is no way of determining that in practice.
Sure there is. Just look at how the numbers are being generated. That
will tell you if they are random.
>I suppose
>(with my meager knowledge of physics) this is almost the same as
>saying at at at 0 Kelvin you can halt the motions of all atoms
You are not aware of the so-called "zero point" vacuum fluctuations
which persist even at 0 Kelvin. If all motion stopped at 0 Kelvin, the
Universe would cease to exist - no photons, no particles, no forces -
nothing.
>(but you can't get to 0 Kelvin, only very close to it).
You can get exceedingly close to it, like one milli-degree close to
it. That's one thousandth of a degree close to it. How much closer
would you want to get to be closer than very close to it?
Is calculus impossible because numbers can never actually reach the
limit required to calculate a derivative or an integral? People in the
17th century, when Newton and Leibnitz invented calculus, thought
calculus was wrong because those limits could never be reached in a
"practical" sense. Yet calculus went on being correct despite them.
And crypto-grade randomness goes on being correct in a very practical
sense too, despite the lack of perfection in a practical sense.
Bob Knauer
"An honest man can feel no pleasure in the exercise of power over
his fellow citizens."
--Thomas Jefferson
------------------------------
From: [EMAIL PROTECTED]
Subject: Top 14 Sayings Of Classified Military Systems Designers {funnybit, no spam}
Date: Tue, 26 Jan 1999 20:30:06 GMT
Click on the link below to visit my newest slightly arcane and esoteric but
still funny funnybit, "Top 14 Funny Sayings Found Taped To The Cubicle Walls
Of Classified Military System Designers"...please go to:
http://hkentcraig.com/Top14Classified.html
NO spam, no harvestbots, non-commercial, no money, just funny!~~~Kent
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Idea for plaintext steganography
Date: 26 Jan 1999 14:20:07 -0500
In article <[EMAIL PROTECTED]>,
Christopher <[EMAIL PROTECTED]> wrote:
>As a simple example, suppose each byte of data were expanded to a simple
>english sentence. 'A(n)'/'The' gives one bit, one of eight nouns would
>give three bits, 'is'/'was' gives one bit, and one of eight adjectives
>gives three bits. So an example would be 'The car is black.'
>Admittedly not very efficient, but improvements can be made with a larger
>dictionary and better ways of packing the information into the rules for
>different sentence structures and such.
>Also, it may look like junk to a human, but shouldn't get the attention of
>any automated systems - any comments?
How smart is your automated system? A lot of the reasons that this
will look like junk to a human are quantifiable and detectable by an
appropriate AI system. For example, topic continuity is something
that can be measured; see Marti Hearst's work on paragraph and section
breaks. Even something as simple as counting the number of different
nouns used in a given document or discourse would reveal a big difference
between your set (one of eight) and the set of a real human (one of
40,000+). I could also look for unusual word pairings -- any document
containing the word "protozoan" probably has a lot of other biological
terms and not many sports-related terms.
On the other hand, I think there's a lot of stuff that could be applied.
I'd be inclined to use some compression-like technology to infer
a model for English text and then run the model backwards, decompressing
the (random) plaintext to see what it looked it. There might be enough
here to work with, especially if what you used for stego purposes was
samples of abstract art....
-kitten
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Random numbers from a sound card?
Date: Tue, 26 Jan 1999 20:12:38 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David Ross) wrote:
> Has anyone had success using a sound card (like a Sound Blaster) to
> generate streams of random numbers?
Yes.
> What sort of audio source would you suspect would be the best to use
> in generating random numbers?
I used an old radio shack mono fm radio, with antenna removed,
tuned to hiss, at high volume, fed into the sound card.
Later I got a video/radio digitizer, which I can tune to
FM hiss, which is more self contained.
This produces an apparently uniformly distributed noise spectrum,
using a pc-based spectrum analyzer.
But this doesn't have full entropy, and you have to distill (see
RFC 1750) the bits. I experimented with parity-of-N bits,
and used Maurer's Universal statistical test for RNGs to measure
the entropy. When you distill enough, the entropy reaches its
expected value.
Some people might recommend a strong hashing function (e.g., a thousand
raw bits hashed with MD5 down to a fixed output size). This is
complex and I found unnecessary; simple parity works, though it
may waste more bits than a serious hash would. But bits are cheap,
and xor is fast.
> How would you test the 'quality' of the generated random number
> stream?
1. Marsaglia's Diehard suite of statistical (structure) tests.
This suite goes far beyond the FIPS suggestions.
2. Maurer's Universal statistical test, which approximates
the entropy of a sample using a formally motivated,
compression-like algorithm.
As "calibration standards" I used the "RAND million normal digits and their
deviant friends", and also block ciphers run in feedback modes (ie,
as PRNGs).
I've also got a parallel-port compatible geiger counter and a
microcurie of americium, but i haven't careful studies on these yet.
But they are cool toys :-)
You will learn that you *always* have to distill raw bits.
And you may observe that very few hardware RNGs actually monitor their output
quality (especially on-line), though it seems to me you should.
Also note that a 'loud' source of hiss is preferable. Were I using
an acoustic microphone as my raw input, I would locate it next
to the frother on my espresso machine and blow steam out of it,
rather than counting on the wind or ambient brownian effects.
Note that even using a highly structured signal (e.g., digitized
video program including your local receiver noise) you could generate
good bits, but you'd have to distill bushels of them.
Have fun,
randombit
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
