Cryptography-Digest Digest #340, Volume #9 Sun, 4 Apr 99 19:13:03 EDT
Contents:
Re: Norton diskreet (JPeschel)
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Re: Random Walk (R. Knauer)
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Re: Random Walk (R. Knauer)
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Scott19u Solution (JPeschel)
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
chosen-plaintext attack ("news.compassnet.com")
Re: How does one start cracking ciphers? (Sandy Harris)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Norton diskreet
Date: 4 Apr 1999 21:52:56 GMT
>[EMAIL PROTECTED] writes:
>Unfortunately its DES but from what i've heard it is possible to break it.
>
>
You'll find some code and also Peter Guttman's remarks here.
http://members.aol.com/jpeschel/diskreet.zip
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sun, 04 Apr 1999 21:54:36 GMT
Reply-To: [EMAIL PROTECTED]
On 4 Apr 1999 14:02:31 -0500, [EMAIL PROTECTED] (Herman
Rubin) wrote:
>Fourier transforms of distributions ALWAYS exist; it is not QUITE
>necessary to have second moments for the CLT to be valid. However,
>even if the CLT is valid, the approach is not that fast.
What "approach"?
>For the
>sum of n independent, identically distributed random variables with
>THIRD moments, the rate of convergence in O(1/sqrt(n)).
Are you saying that such a uniform distribution permits the use of the
CLT?
>However, the abuse of the normal distribution is so great that
>it should be questioned whether it belongs in a first course as
>something to be relied on. Often, it is not of much importance,
>and few introductory books even point out where it is and where
>it is not.
Triola makes the point that one cannot use parametric distributions
for determining randomness. That includes the pseudo-random
distributions that come from the uniform Bernoulli process, because
those distributions are necessarily parametric.
>>It is a *model* of the population
>>that is tested via statistical computation on the sample.
That standard model is based on the distribution for an infinite
population.
>In most problems, one is not sampling from a finite population.
That seems to contradict earlier statements. Is it a typo?
>>Too bad for you that I did just give the parameters of the
>>distribution (actually, just the first two moments,
>>but the others are readily calculable) for your "true
>>random process".
>This is quite correct.
Those parameters were for a pseudo-random process. The assumption is
that the pseudo-random model is valid for true randomness, even if
only as a necessary condition - and I am challenging that assumption.
You need to prove that those parameters are "quite correct". What if
one or the other of those moments does not exist?
>But now we have the real problem; is the actual process
>close enough to the non-existent TRNG that, for the current
>purpose, one should go ahead and use it. It is not a
>question of "statistical significance"; it may be that one
>should use something for which a typical significance test
>would reject by using fixed significance levels, and it may
>be that one should not use something which is accepted by
>the usual significance level.
What if this "non-existent TRNG" actually became existent in the form
of a quantum computer programmed to calculate truly random numbers?
>It is the balancing of the risks which is needed.
There are no risks with a quantum computer - it is proveably truly
random.
Bob Knauer
"The brave men who died in Vietnam, more than 100% of which were
black, were the ultimate sacrifice."
- Marion Barry, Mayor of Washington, DC
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Sun, 04 Apr 1999 21:54:43 GMT
Reply-To: [EMAIL PROTECTED]
On 4 Apr 1999 11:22:54 -0500, [EMAIL PROTECTED] (Herman
Rubin) wrote:
>>What is that model and why is it assumed that its properties at
>>infinity have any validity for an infinitesimally small sample of
>>finite sequences. The law of large numbers makes a number of
>>assumptions which I do not believe apply to true randomness on an a
>>priori basis.
>Statistics deals with what to do with a finite sample. Probability
>discusses quite a bit about infinite samples, but this is also not
>relevant to the problem.
What I meant is that the rules of inference for finite samples are
derived from considerations of infinite populations.
In particular, the Central Limit Theorem (CLT), which serves as the
fundamental basis for statitical inferences for finite samples,
requires considerations about the data distribution at infinity. For
example, the CLT is not valid if the distribution is not square
integrable out to infinity.
IOW, the distribution must behave in a certain way as the population
grows infinitely large, even though it does not have to in practice be
infinitely large. One of the consequences of that is that the actual
population can be any size - it is only the sample size that
determines statistical significance when the CLT is valid.
Requiring the distribution to have certain properties derived for an
infinite population means that the distribution maximally represent
any population size - it serves as the "standard" distribution for the
actual population. Therefore small samples can be drawn from this
"standard" distribution in accordance with the CLT, namely the means
of the samples are themselves distributed normally.
If the data distribution did not have those required properties for an
infinite population, then the CLT would not produce a normal
distribution for the means of a finite number of samples.
You have to ask the question: "What happens to the data distribution
if the population goes to infinity?" in order for the CLT to be valid
for finite populations. If you do not know what the data distribution
does when the population goes to infinity, then you can't assume the
validity of the CLT, because the data distribution could behave in
such a way that the CLT would not be valid for larger and larger
populations. The infinite population distribution serves as the
standard for all finite populations and is the reason for the validity
of the CLT.
I feel confident that if I pursued this further there would be
numerous examples of how data distributions misbehave in the limit of
infinite populations such that the CLT is not valid. In fact perhaps
someone could point out a book out that discusses these matters.
Bob Knauer
"The brave men who died in Vietnam, more than 100% of which were
black, were the ultimate sacrifice."
- Marion Barry, Mayor of Washington, DC
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sun, 04 Apr 1999 21:54:44 GMT
Reply-To: [EMAIL PROTECTED]
On 4 Apr 1999 13:35:52 -0500, [EMAIL PROTECTED] (Herman
Rubin) wrote:
>To certify a random device takes more than the square of the
>accuracy needed, unless one makes VERY strong assumptions.
I am not relying on any measurements to certify the intrinsic
randomness of the source of randomness itself. I am relying on the
fact that it is quantum mechanically random for that. Since all other
subsystems are deterministic, there are no accuracy requirements just
diagnostic requirements.
>It is from those who work with the physical devices that I
>question the possibility of getting the desired accuracy.
>There are hopefully ways that one can improve things.
A quantum computer can calculate true random numbers with no accuracy
issues involved whatsoever.
But who needs a TRNG when we already have a quantum cryptosystem that
is not only proveably secure but is also proveably private. If anyone
tries to intercept the stream, the device knows it immediately and can
stop transmitting.
Bob Knauer
"The brave men who died in Vietnam, more than 100% of which were
black, were the ultimate sacrifice."
- Marion Barry, Mayor of Washington, DC
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Sun, 04 Apr 1999 21:54:41 GMT
Reply-To: [EMAIL PROTECTED]
On Sun, 04 Apr 1999 14:00:07 -0400, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>You model this mathematically as zero information.
>You model this physically as 100% entropy. (lack of order on which a
>prediction could be based).
I agree with you for the classical case, but what about in the quantum
case? Cerf & Adami model QM measurement and come up with negative
entropy, which is classically forbidden. They call it
"supercorrelation".
>The brightest minds of multiple millenia thtought the earth was flat in
>spite of observations over a thousand years old that indicated
>otherwise.
Those minds did not have physics and mathematics at their disposal.
BTW, I am not convinced that the brightest minds believed in a flat
earth. In the first place, the number of bright minds was severly
limited, and there is evidence that the few there were did know that
the earth was not flat. For one thing all they had to do was look up
in the sky and see the eclipses case a circular shadow on the moon.
Also, the spherical shape of the sun and planets (the Moon is a
planet) was prima facie evidence that the earth was not flat.
>QM is young.
Not in terms of the cumulative effort put into it. If you use the
number of pages of published articles, I would guess that QM has
received more attention from bright minds than all the scientific
issues preceding it.
>The modern foundations are only half a century
>old (Feynman's history integration cirra '47-48 I think).
Questions of the random nature of QM goes back to the earliest days.
De Broglie was the first proponent of hidden varialbles.
>Yes there would. Hashing increases the entropy density, a desirable
>quality.
Can you prove that hashing actually does increase entropy density? And
is entropy density still a suitable measure of unpredictability if it
is not maximal?
>No. Hashing is a Good Thing.
I am still waiting for the discussions which will prove that.
>We do not care that there are patterns in the data. We do not care that
>some of the data is biased, correlated, or predictable. We only care
>that some measurable aspect of the system's behavior is *not*
>predictable. Given that, we can distill it to complete
>unpredictability.
Here are some of my problems with that:
1) First you are using an algorithmic method to create randomness. We
know better than that.
2) Secondly, if the RNG cannot generate randomness, that means that it
is flawed, so hashing it is not a good idea. The correct idea is to
fix the RNG.
3) Third, if hashing could create randomness by distilling whatever
randomness is present in the RNG, why not just apply it to a PRNG?
>I believe this is provable.
Then by all means show us.
>*REALLY*? Before you post again please review the history of OTP usage
>and catalog the failures due to inadequate RNGs and all the rest.
>Keystream flaws are lost in the rounding of that summary.
Are you saying that a quantum random number generator is not adequate
for use with the (proveably secure) OTP system?
Key management is not an analytical issue, so it does not qualify as a
reason for the failure of the OTP system.
Bob Knauer
"The brave men who died in Vietnam, more than 100% of which were
black, were the ultimate sacrifice."
- Marion Barry, Mayor of Washington, DC
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sun, 04 Apr 1999 22:04:32 GMT
Reply-To: [EMAIL PROTECTED]
On Sun, 04 Apr 1999 20:59:50 GMT, Dave Knapp <[EMAIL PROTECTED]> wrote:
>Incredible! You not only don't understand statistics, but you don't
>understand decision theory even better!
At least I know what correlation means.
Bob Knauer
"The brave men who died in Vietnam, more than 100% of which were
black, were the ultimate sacrifice."
- Marion Barry, Mayor of Washington, DC
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Scott19u Solution
Date: 4 Apr 1999 22:40:14 GMT
You'll find a partial solution, in the form
of a second clue, to DScott's "gloat contest"
on my site in the "Contests" page.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sun, 04 Apr 1999 22:35:11 GMT
Reply-To: [EMAIL PROTECTED]
On Sun, 04 Apr 1999 17:32:38 -0400, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>Sadly, most of this is not relevant.
Even more sadly, you are wrong.
>Consider that an independent,
>equiprobable, single-bit generator is all we need, why worry about
>multi-bit sequences?
That is an assumption that must be proven. A single-bit generator like
the uniform Bernoulli process results in parametric distributions, and
according to Triola that cannot be used to model a true random
process.
>IFF you have a generator that produces
>independent, equiprobable bits, you have everything you need.
I never said anything against that. I was trying to point out that the
distribution of keys is not binomial in an ensemble of all possible
keys.
>The whole point of testing the output of an RNG is to evaluate whether
>indeed the RNG does produce individual bits correctly.
BUT... the model for determining that evaluation is the pseudo-random
model and it has not been proven that the pseudo-random model actually
models true randomness properly.
What do the production of bit-grouped sequences that are distributed
according to a binomial distribution have to do with truly random
processes?
If I put 1000 unique items in a jar and select one at random, what
does that process have to do with the binomial distribution? For that
matter, if I put two unique balls in the jar and select one, what does
that have to do with the binomial distribution? The answer in both
cases is that those processes have absolutely nothing to do with the
binomial distribution.
It's only when you group the sequences into bit-groups that the
binomial distribution comes into play. But that is not allowed for
cryptographic keys - each one is unique, so bit-grouping gives a false
measure of true randomness.
The assumption that distribution for bit-groups models a true random
process is totally incorrect. There is no connection whatsoever
between the distribution for bit-groups and a true random process.
>Even a quantum source has to be evaluated, TESTED, to see if it really
>produces what it is supposed to produce.
Yes, but not tested statistically on the very things it is being asked
to calculate, namely a true random number. There are no analytic
properties of that number, so there is no way to know if it is being
calculated correctly. That's why it is truly random. If there were
some property of that true random number that would tell you that it
was truly random, then it would not be truly random. There is no
property of the ensemble either - the distribution is completely flat.
Therefore there is no analytic property of the ensemble that will tell
you that the process is either truly random or not truly random.
Just because a pseudo-random process like a UBP has the *appearance*
of being random for infinite sequences does not make it a correct
model for the generation of true random numbers, even for very large
sequences. Bit-group distributions have nothing to do with true
randomness - they just look random in the limit of infinitely large
sequences where every number is both truly random and Borel normal.
But for finite sequences, every one of them is unique - so they cannot
be modeled by infinitely large Borel random numbers.
Bob Knauer
"The brave men who died in Vietnam, more than 100% of which were
black, were the ultimate sacrifice."
- Marion Barry, Mayor of Washington, DC
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sun, 04 Apr 1999 22:49:11 GMT
Reply-To: [EMAIL PROTECTED]
On Sun, 04 Apr 1999 17:35:14 -0400, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>Garbage.
Just re-read your weasel wording below and see what garbage really is.
>No one here has said that there exists a perfect or
>comprehensive set of statistical tests.
I was referring to statistical tests that have high levels of
confidence. Because the law of the distribution of the mean is normal,
it does not take all that large a sample to get extremely high levels
of confidence for data distributions which have a reasonable value for
the second moment.
Consider "reasonably correct" to mean a confidence level of 99%. Now,
given that level of significance, re-read what I said:
I claim that there are only two valid sets for randomness:
Set #1: Reasonable certainty that the process is not random;
Set #2: Processed which do not exist in set #1.
Put into the language of statistics:
Null Hypothesis: A particular RNG is not random.
Alternate Hypothesis: That particular RNG is random.
There is no middle set of RNGs that are maybe random, maybe not random
on the basis of reasonable certainty. There is a definite area outside
the Z-score and a definite related area inside the Z-score. There is
no gray zone where things may be or may not be simultanously.
>In fact I among other have
>argued that there *cannot* be such a set of tests. Thus your "Alternate
>Hypothesis" is flawed. C.F., the problem of "the excluded middle".
If there cannot be such as set of tests, then we are in agreement.
The whole issue comes down to whether a distribution for bit-grouped
numbers can serve as a model for a true random process involving
finite sequences. I claim that it cannot, because such a pseudo-random
distribution only gives the appearance of true randomness by
attempting incorrectly to map the bit-group property of zero bias from
infinite sequences onto finite sequences. Once a sequence goes from
infinite to finite size, it loses all of its Borel normality imposed
on it by its infinite size.
Pseudo-randomness only pertains to infinite sequences, and fails as a
model to account for finite true random number generation.
Bob Knauer
"The brave men who died in Vietnam, more than 100% of which were
black, were the ultimate sacrifice."
- Marion Barry, Mayor of Washington, DC
------------------------------
From: "news.compassnet.com" <[EMAIL PROTECTED]>
Subject: chosen-plaintext attack
Date: Sun, 4 Apr 1999 17:41:40 -0500
Hi, thanks for reading this post!
Why are public-key systems vulnerable to chosen-plaintext attacks? What
does a cryptanalyst have to do deduce the private key (if necessory at all)
or the algorithm to infer further plaintext? I failed to find an example on
the Internet. How does it help since public keys are known to everyone.
Why are symmetric cryptosystems not vulnerable to this attack?
------------------------------
From: [EMAIL PROTECTED] (Sandy Harris)
Subject: Re: How does one start cracking ciphers?
Date: Sun, 04 Apr 1999 22:16:05 GMT
consalus <[EMAIL PROTECTED]> writes:
>This may be a silly question, but I cannot remember seeing it covered in
>
>anything I've read thus far.
>
>How does one crack ciphers?
Read Kahn's "The Codebreakers". It has fairly detailed descriptions of
cracking methods for older ciphers.
Check Schneier's company's site;
http://www.counterpane.com
He has a self-study cryptanalysis course there.
------------------------------
** 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
******************************
