Cryptography-Digest Digest #24, Volume #9 Tue, 2 Feb 99 17:13:04 EST
Contents:
Re: Random numbers generator and Pentium III (John Briggs)
Re: *** Where Does The Randomness Come From ?!? *** (John Savard)
Re: Historical basis for BLOWFISH (Bruce Schneier)
Re: Random numbers generator and Pentium III ("Trevor Jackson, III")
Re: Truth, theoremhood, & their distinction (R. Knauer)
Re: RNG Product Feature Poll (John Savard)
Re: *** Where Does The Randomness Come From ?!? *** (R. Knauer)
Re: Encryption for telemedicine (John Savard)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Briggs)
Subject: Re: Random numbers generator and Pentium III
Date: 2 Feb 1999 20:15:43 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (R. Knauer)
writes:
>On Tue, 02 Feb 1999 05:49:44 -0500, "Trevor Jackson, III"
><[EMAIL PROTECTED]> wrote:
>
>>> So if a finite number fails your test, does that mean it isn't random?
>
>>It means that we have some confidence (probability) that it is not random. The
>>confidence is defined statistically.
>
>This statement is yet another prime example of the kind of sophistry
>that comes from people who attempt to characterize randomness from
>statistical tests of the output of a number generator.
>
>Let's say you want to buy a TRNG but first you require that it be
>certified proveably secure. So the person selling you the TRNG tells
>you that he will perform statisitcal tests. Let's call that test T1.
Note well, we're pre-certifying the TRNG. We're not filtering output.
We're precertifying.
And Trevor is being quite clear that this can provide confidence. Not
proof.
>In T1 he claims to have found random strings and non-random strings.
>Let's call them "bad" strings and "good" strings respectively.
>According to the sophistry of statistical testing of the output, you
>want as many "good" strings and as few "bad" strings as possible from
>your TRNG .
Yep. Since the set of "good" strings vastly outnumbers the set of
"bad" strings (for any reasonable test) and since the generator is
supposed to output all possible strings equiprobably, we expect that
good generators will output "good" strings and not "bad" strings.
Most of the time.
>In T1 we find a certain number of strings that are bad because they
>failed the statistical tests and a certain number of strings that are
>good because they passed the statistical tests. Let that ratio be:
>
>(bad/good) = r1.
OK. Sample ratio for trial 1 = r1.
>Since you are still skeptical about this whole procedure, you requre a
>second test T2 to be performed which yields the ratio:
>
>(bad/good) = r2.
OK. Sample ratio for trial 2 = r2.
>Because r2 is not equal to r2, you get suspicious and require a third
>test T3:
>
>(bad/good) = r3
OK. Sample ratio for trial 2 = r2.
>
>....
>
>(bad/good) = r_n
>
Yeah, I see the pattern.
>After n such tests you begin to see that the ratio (bad/good) is
>bounded on the lower and upper extremes by RL = min (r_i) and RU = max
>(r_i), so you have a high degree of confidence that:
>
>RL <= (bad/good) <= RU.
Ok. We've got sample measures that are a reliable bound on an
underlying statistical value.
>
>Let's say you are SO confident that you assign a probability of one to
>that confidence. IOW, that range above has probability one of being
>correct:
>
>Pr (RL <= (bad/good) <= RU)) = 1
>
>where Pr (x) is the probability of x.
You can't ever get that confident. You can approach it. But you
can't get there. But no matter. Let's see where you're going with this...
(As it turns out, this confidence stuff was indeed a red herring,
irrelevant to the faulty assumptions below.)
>
>Since you know nothing about how the numbers are being generated, you
>just as well assume that the distribution of ratios is symmetric
>around the mean of the bounds.
>
>That implies that
>
>Pr (Rl <= (bad/good) <= 1/2(RL+RU)) = 1/2
>
>and
>
>Pr (1/2(RU+RL)<= (bad/good) <= RU)) = 1/2
>
>where 1/2(RU+RL) is the mean of the bounds RL and RU.
Unsupported assumption.
For the record, you're assuming that the sample ratio of bad/good is
a random variable that is uniformly distributed about its mean.
And then you're assuming that this means that 1/2(RU+RL) is also
a random variable that is uniformly distributed about its mean.
(Which, by symmetry, would indeed be a valid conclusion, given the
above assumption).
First, let's fix the divide by zero problem. Add n to both numerator
and denominator. If you want to fix it some other way, feel free.
Please specify.
Now, assume a TRNG that outputs elements chosen from {1,2,3,4} equiprobably.
Let good = {2,3,4} and bad = {1}.
Run a test with one trial.
How is the ratio (bad+1)/(good+1) distributed?
R1 = Rn = RU = RL = 2/1 with probability 1/4
R1 = Rn = RU = RL = 1/2 with probability 3/4
(RU+RL)/2 is distributed identically to this.
The mean is 7/8.
Is the distribution uniform about the mean? No.
Assumption falsified.
>Now you take the RNG to another person and he submits it to
>statistical tests in the same manner as above and he gets identical
>results to those above, but this time he considers the ratio
>(good/bad) instead of (bad/good).
>
>Using the distribution above, namely
>
>1/RU <= (good/bad) <= 1/RL
>
>we get
>
>Pr (1/RU <= (good/bad) <= 1/2(1/RU+1/RL)) = 1/2
>
>and
>
>Pr (1/2(1/RU+1/RL) <= (good/bad) <= 1/RL)) = 1/2
>
With the implicit assumption that the sample ratio good/bad is
a random variable that is _also_ uniformly distributed about its mean.
Another false assumption. Try it against the same TRNG, good and bad
sets and test procedure given above. It fails.
>But this contradicts the results obtained earlier from the ratio
>(bad/good) since the means are not the same when you go back to the
>original ratio (*). Clearly something is wrong here.
Yep. Your assumptions are both wrong.
Note too that estimating the mean of a distribution as the mean of the
extreme sample values is pretty unconventional. And pretty damned
unreliable. And not necessarily unbiased.
Most folks estimate the distribution mean as the sample mean. That is,
as I recall, unbiased.
>This is known as Bertrand's Paradox (see Li and Vitanyi, op. cit), and
>illustrates what can happen when you attempt to infer the distribution
>of the generator from probablistic tests of the output.
Presumably Li and Vitanyi analyzed a slightly different problem that
did not suffer from divide by zero issues. It is difficult to
accept the notion that what was described above actually appears in any
useful reference.
>Probability only tells you about an event *after it happens*. It
>cannot tell you about the generation process.
On the contrary. In my view, probability is about events *before they
happen*. After the fact, you've got uncertainty. The outcome is
determined, but you don't know what the determination was. Before
the fact, you've got probability. The outcome isn't even determined
yet. I've heard of "subjective probability". But what I've heard
isn't flattering.
That's the way I keep it straight anyway. My own metaphysics.
The mathematical formalism for probability has nothing to do with
"before", "after" or "generators". It's all about distributions.
>proveably secure (not just probablistically secure) you must do an
>analysis on the generator itself. If you try to infer the
>characteristics of the generator from statistical tests of the output,
>you can get contradictory results depending on how the measurements
>are conducted.
I suspect this depends on what you mean by contradictory results.
>One of the things that is wrong with statistical testing of the output
>is that it assumes that there are so-called "bad" strings. But that is
>not possible, since for a TRNG to be proveably secure it must be
>capable of generating *ALL* possible strings of a given finite length
>equiprobably.
In the real world, the notion that there are "bad" strings is not
incompatible with that all strings must be generated equiprobably.
The probability of encountering a "bad" string by accident can be
made vanishingly small.
If my real world TRNG outputs 4096 zero bits in a row, the smart money
is on "broken", not "accident".
>If *ALL* strings must be "good" for a TRNG to be proveably secure,
>then none of them can be "bad".
"Provably secure". Now you're ringing in an additional assumption. You
want _proof_ that a TRNG is _perfect_. Can't be done in the real world.
Real world theories aren't proven. They're validated. And statistical
validation is a useful test.
Read the post to which you're responding. It's not about proof. It's
about confidence. There is a difference.
>DUH! Tests which purport to uncover
>"bad" strings in the output are of nonsense tests. Statistical tests
>for randomness ("good") and non-randomness ("bad") of the output
>strings do not pertain to crypto-grade random number generation for
>the (proveably secure) OTP cryptosystem.
If we were talking about a mathematically ideal OTP cryptosystem then
you are correct. Statistical tests for randomness are pointless
at best and broken at worst.
Since we are talking about real world tests for real world, crypto
quality hardware random number generators, statistical measures are
not only useful, they are indispensible.
>If you allow someone to sell you a TRNG based on statistical testing
>of the output, you just bought a Snake Oil Generator.
If you allow someone to sell you a TRNG that produces all zeroes all
the time, allow me to sell you an open circuit for the same fee.
John Briggs [EMAIL PROTECTED]
Thank God that R. Knauer has *plonk*ed me. Saves a lot of
effort writing replies to his replies that completely miss my points.
I should probably *plonk* him too and save even more effort.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.skeptic,sci.philosophy.meta
Subject: Re: *** Where Does The Randomness Come From ?!? ***
Date: Tue, 02 Feb 1999 21:12:02 GMT
[EMAIL PROTECTED] (Ron Cecchini) wrote, in part:
>[EMAIL PROTECTED] (Bart Lidofsky) wrote:
someone else wrote:
>> > *** Either Randomness does not exist OR the Universe is an Open System.
>> You have not adequately covered the possibility of true randomness
>> in a closed Universe. This is a major topic in scientific philosophy,
>> where the tide of opinion is in almost continuous flux.
>The first step is to try to *define* "true randomness"!
Well, for the purpose of utterances like the one which began this,
"true randomness" presumably means independence of all that preceded
it in the state of the Universe.
And, of course, the proper response is:
Quantum mechanical randomness is true - and implies the Universe is an
"open system", but only to a limited extent not corresponding to the
usual meaning of the term "open system", since nothing but randomness
can be accessed quantum mechanically, there is really no way of truly
knowing that this randomness is coming from somewhere else.
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Historical basis for BLOWFISH
Date: Tue, 02 Feb 1999 21:16:19 GMT
On Tue, 02 Feb 1999 18:29:35 GMT, karl_m <[EMAIL PROTECTED]>
wrote:
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Bruce Schneier) wrote:
>>
>> Wow. Where did this Blowfish history come from? It has nothing to do
>> with reality (as I know it).
>
>The history came from my <<understanding>> of the process by which you came to
>include REDOC II in your book. Your presentation did not reference Biham and
>Samir's work on it, you merely re-published Michael_W's revised REDOC III,
>which he created in response. Granted LINEAR analysis, e.g. the solution to a
>system of simultaneous linear equations, was not widely known in 1993, nor
>covered by Biham and Shamir -- I'm not trying to attack here.
Fascinating. As far as I know (as the inventor of Blowfish), the
algorithm has nothing to do with REDOC II or REDOC III. I'm not sure
where you get your history as to the process by which I included REDOC
II in my book, as I believe I was alone at the time and never recorded
that process.
For the record, I decided to include it because it was presented at a
Crypto conference. I also references Biham and Shamir's differential
attack. Biham and Shamir never looked at REDOC III; I chose to
publish it because I was asked to (back then, block ciphers were
scarce). Again, this has nothing to do with Blowfish.
>Your statement "The algorithm (REDOC III) is deceptively simple, even though
>it looks fairly weak" was the indicator of the reality (or lack thereof).
>
>Does you answer mean that we are all doomed to some form of advanced LINEAR
>analysis???
No.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
Date: Tue, 02 Feb 1999 16:21:37 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Random numbers generator and Pentium III
John Briggs wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (R. Knauer)
>writes:
>
> >Probability only tells you about an event *after it happens*. It
> >cannot tell you about the generation process.
>
> On the contrary. In my view, probability is about events *before they
> happen*. After the fact, you've got uncertainty. The outcome is
> determined, but you don't know what the determination was. Before
> the fact, you've got probability. The outcome isn't even determined
> yet. I've heard of "subjective probability". But what I've heard
> isn't flattering.
This is precisely the fundamental issue. We utilize statistical mechanism to provide
predictions. We bound the strength of those predictions with the confidence we have
in them.
Of course the analysis of the *samples taken* occurs after the fact, but we use the
results of
that post-processing as predictive of similar *future samples*.
>
>
> That's the way I keep it straight anyway. My own metaphysics.
>
> The mathematical formalism for probability has nothing to do with
> "before", "after" or "generators". It's all about distributions.
>
> >proveably secure (not just probablistically secure) you must do an
> >analysis on the generator itself. If you try to infer the
> >characteristics of the generator from statistical tests of the output,
> >you can get contradictory results depending on how the measurements
> >are conducted.
>
> I suspect this depends on what you mean by contradictory results.
>
> >One of the things that is wrong with statistical testing of the output
> >is that it assumes that there are so-called "bad" strings. But that is
> >not possible, since for a TRNG to be proveably secure it must be
> >capable of generating *ALL* possible strings of a given finite length
> >equiprobably.
>
> In the real world, the notion that there are "bad" strings is not
> incompatible with that all strings must be generated equiprobably.
>
> The probability of encountering a "bad" string by accident can be
> made vanishingly small.
>
> If my real world TRNG outputs 4096 zero bits in a row, the smart money
> is on "broken", not "accident".
>
> >If *ALL* strings must be "good" for a TRNG to be proveably secure,
> >then none of them can be "bad".
>
> "Provably secure". Now you're ringing in an additional assumption. You
> want _proof_ that a TRNG is _perfect_. Can't be done in the real world.
>
> Real world theories aren't proven. They're validated. And statistical
> validation is a useful test.
>
> Read the post to which you're responding. It's not about proof. It's
> about confidence. There is a difference.
>
> >DUH! Tests which purport to uncover
> >"bad" strings in the output are of nonsense tests. Statistical tests
> >for randomness ("good") and non-randomness ("bad") of the output
> >strings do not pertain to crypto-grade random number generation for
> >the (proveably secure) OTP cryptosystem.
>
> If we were talking about a mathematically ideal OTP cryptosystem then
> you are correct. Statistical tests for randomness are pointless
> at best and broken at worst.
>
> Since we are talking about real world tests for real world, crypto
> quality hardware random number generators, statistical measures are
> not only useful, they are indispensible.
>
> >If you allow someone to sell you a TRNG based on statistical testing
> >of the output, you just bought a Snake Oil Generator.
>
> If you allow someone to sell you a TRNG that produces all zeroes all
> the time, allow me to sell you an open circuit for the same fee.
>
> John Briggs [EMAIL PROTECTED]
>
> Thank God that R. Knauer has *plonk*ed me. Saves a lot of
> effort writing replies to his replies that completely miss my points.
>
> I should probably *plonk* him too and save even more effort.
Nah, the correlative side effects of those plaonked are worth the effort. One might
even brag
about it. ;-)
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Crossposted-To: sci.math,comp.theory
Subject: Re: Truth, theoremhood, & their distinction
Date: Tue, 02 Feb 1999 21:34:59 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 02 Feb 1999 13:37:25 -0500, Nicol So <[EMAIL PROTECTED]>
wrote:
>There is no technical definition for correctness of interpretation,
I would ask you to comment on Solomonoff's induction model. I am
working my way towards an exposition of that in Li and Vitanyi's book
on Kolmogorov Complexity, and the authors have hinted that they will
show that Solomonoff's system of inference yields "correct"
interpretations (hypotheses), much more correct than those obtained by
by other systems of inductive reasoning, like Occam's Razor or
Bayesian inference.
>Hopefully in the light of my clarification, the answer to the question
>becomes obvious.
I got into this late and missed out on a lot of the preliminary stuff,
and to join in I apparently assumed something that was not there.
Bob Knauer
"Sometimes it is said that man cannot be trusted with the government
of himself. Can he, then, be trusted with the government of others?"
--Thomas Jefferson
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: RNG Product Feature Poll
Date: Tue, 02 Feb 1999 21:15:47 GMT
[EMAIL PROTECTED] (Dan S. Camper) wrote, in part:
>1) Don't add a hash. (This is the easy one!)
The best idea. If we don't trust you, and imagine that these hardware
random numbers are "really" generated by some tricky NSA stream cipher
that will let them guess all our session keys, we can hash those
random bits ourselves to be on the safe side.
Obviously, if we don't trust your random bits, we won't trust your
hash.
And why would anyone be using encryption, if he wasn't already
paranoid? :)
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Crossposted-To: sci.skeptic,sci.philosophy.meta
Subject: Re: *** Where Does The Randomness Come From ?!? ***
Date: Tue, 02 Feb 1999 21:36:49 GMT
Reply-To: [EMAIL PROTECTED]
On 2 Feb 1999 18:51:28 GMT, [EMAIL PROTECTED] (Seisei Yamaguchi) wrote:
>Randomness and unforeseeableness are not identical.
Why not?
There are several different types of randomness. Not all kinds of
randomness are statisitcal in nature.
Bob Knauer
"Sometimes it is said that man cannot be trusted with the government
of himself. Can he, then, be trusted with the government of others?"
--Thomas Jefferson
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Encryption for telemedicine
Date: Tue, 02 Feb 1999 21:26:07 GMT
Themos Dassis <[EMAIL PROTECTED]> wrote, in part:
>I am working in a European project in telemedicine and trying to
>identify the security components that will be needed.
>The system consists of LAN's connected with ISDN reserved lines.
>The LAN's will be Ethernets, while on the ISDN the EURO-ISDN protocol
>will be used. The data communicated is sensitive data related to
>the patient, and quite big (around 70Mbytes). The project is not
>concentrated in security, but we have to implement some kind of
>encryption.
>I was thinking of an ISDN modem with a symmetric encryption hardware
>incorporated to it, but I was told that such a solution is out of the
>trend and that a public key solution with a TTP suits best to my
>problem.
>What kind of a solution would you propose me?
It is true that a solution involving _no_ use of public-key methods is
not common these days. Usually, though, public-key methods are used to
facilitate key distribution. Most data will still be encrypted with
symmetric encryption.
A simplistic use of public-key methods, however, only protects against
passive eavesdropping. For this type of project, if you give up having
someone go around and give the key to every authorized site, you must
have some other means of authenticating the sites in the network.
So one is talking about certificates authenticating public keys,
signed by a central authority.
But it should be possible to obtain a public-key solution like that
which supports a modem with hardware symmetric encryption, instead of
requiring everything to be encrypted on PCs. It is more likely that
the modem manufacturer will have public-key key management software
than that a public-key software company will support other companies'
modems of this type.
Thus, I don't think the conflict is too great between your original
plan and the other vision presented to you.
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
** 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
******************************
