Cryptography-Digest Digest #325, Volume #9 Fri, 2 Apr 99 07:13:03 EST
Contents:
Re: Random Walk (Shawn Willden)
Re: ---- Two very easy secret key Cryptosystems ("David Starr")
blind signatures ("Gianluca Dini")
Re: My Book "The Unknowable" ("David Starr")
SHA (Thomas Mehring)
Re: Random Walk (R. Knauer)
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Re: Random Walk (R. Knauer)
----------------------------------------------------------------------------
Date: Mon, 29 Mar 1999 21:31:39 -0700
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: Random Walk
"R. Knauer" wrote:
> Shawn Willden <[EMAIL PROTECTED]> wrote:
> >Someone who has thought a little about the properties of random
> >walks in particular would not be deceived by their intuition.
> Apparently the notion of true randomness is not commonly understood
> by people in the crypto industry, judging from the rather large
> amount of snake oil out there regarding the effectiveness of
> statistical tests.
You have not established the existence of snake oil in this
regard. I
refuted your argument supporting your judgment that
randomness is not
well understood, and you cannot use your conclusion to
support your
argument.
> >> The uniform one-dimensional random walk is the same as the
> >> uniform Bernoulli process in terms of how the bits of the
> >> sequence are generated.
> >Nonsense. The output of random walk looks nothing whatsoever like
> >the output of a UBP. A UBP can be used as the underlying random
> >process on which one builds a random walk, but the outputs of the
> >two processes are radically different. With this sort of
> >construction, you must think of the random walk as a sort of post
> >processing on the underlying process.
> Please re-read my statement above and tell me how it says anything
> that is different from what you just said. The operative part of the
> statement above is "in terms of how the bits of the sequence are
> generated" - and you are saying the same thing as I said, namely,
> that the random walk relies on the UBP for generation of the paths.
Actually, you said the random walk is the same as the UBP.
"The same
as" and "relies on" have quite different meanings. However,
I'll
assume that you really meant "relies on".
> >Certainly a non-uniform Bernoulli process seems like an excellent
> >model, since it is then not necessary that p==q.
> But a non-uniform Bernoulli process results in sequences that are
> not crypto-grade. IOW, the process is no longer equidistributed. If
> p > q, then the process will generate more sequences with a greater
> number of 1s versus 0s, and fewer sequences with the opposite
> property. In the case that p >> q, most sequences will be highly
> biased with 1s compared to 0s. That makes a very poor keystream for
> crypto.
Maybe. If |p-q| is very small, the keystream would be quite
good.
OTOH, since no physical device will produce p == q, the
non-uniform
model is probably a better one.
> >you are correct that it is impossible to define statistical tests
> >that will verify that a sequence is random.
> I think you mean to say: "it is impossible to define statistical
> tests that will verify that a sequence is generated by a random
> process."
Yes.
> The debate now is whether statistical tests can be used to
> characterize non-random processes.
No, the debate is about whether statistical tests can be
used to
verify statistical properties of the output of processes, be
they
random or deterministic.
> That is, if a process fails statistical tests for pseudorandomness,
> does that mean for certain that the process is not truly random?
What is a "test for pseudorandomeness"?
> If you draw balls from an urn filled with a very large number of
> balls of white and black color, can you validly conclude from a
> sample of all white balls, that there are only white balls in the
> urn? I think not. You have to proceed to examine all of them, and
> that entails an infinite number of samples.
No, you do not need an infinite number of samples. This is
precisely
the fundamental concept that makes probability and
statistics useful
in the real world. The result of examining a small sample
can be
extrapolated to cover the whole space. Further, the
probability that
the sample is representative can be calculated, and the
sample size
can be adjusted to provide whatever level of confidence is
required.
> >Obviously. One cannot use statistical tests to detect randomness.
> You know that, and I know that, and several other readers of
> sci.crypt know that. But if you were a regular here, you would be
> appalled at the number of people who do not know that.
I've read most of the posts in this thread, and I've yet to
find
someone who does believe that one can test for randomness.
> But that is not the issue I am raising now. The position I am taking
> in this debate is as stated above, namely that one cannot use
> statistical tests to detect non-true-randomness.
Again, I'll say it. Tests can show nothing about
randomness. They
can only address distributions, biases and correlations.
Your own
definition of a TRNG requires that any output sequence be
equally
likely, and while that is a difficult proposition to prove,
it is an
easy one to disprove, at least with a given error bound.
If, for
example, you were to perform a very simple analysis of the
output of
an RNG and you were to discover that in nearly every one of
10,000
sequences of 1 million bits each there were three times as
many 0s as
1s, you could safely conclude that the RNG is biased. There
would
remain, of course, a non-zero probability that the RNG is in
fact
unbiased and you just happened to get those sequences, but
it is a
very, very small probability. If you wanted, you could
calculate what
that probability is, and if it still weren't small enough
after 10,000
samples, you could perform as many experiments as necessary
to make
that probability as small as you desire.
> >The expansion of pi might make a perfectly good PRNG, other than
> >it's so much slower than other, equally good methods. However,
> >what does this have to do with cryptography?
> Beats me. Probably as much as your comment has to do with
> cryptography.
What? You were the one who brought up transcendental
expansions.
> >No I would not. I would consider them to uniformly distributed and
> >free of detectable bias. I might consider them to be
> >unpredictable, but I would have to believe that they may be
> >predictable by someone who knows more than I do.
> Some people would conclude that just because the digit expansion of pi
> passes statistical tests for pseudorandomness, that the process is
> therefore truly random. We know that to be incorrect.
Who would conclude that? (And could that person explain what
a test
for pseudorandomness is?)
> I concede that if a TRNG does not pass pseudorandom tests, that
> there is a certain (calculable) *possibility* that it is not truly
> random, but I also maintain that one must decide that on the basis
> of an analysis other than statistical testing of the output per se.
Why? Given that additional testing can raise that
calculated
probability to any desired degree, why bother with anything
else?
Note that I do believe that if the RNG passes all of our
statistical
tests (i.e. that our samples show that the output is uniform
and
unbiased with probability near 1), it is a good idea to
perform other
sorts of diagnostic testing, but only because of the
possibility that
the attacker has better statistical tests than we do. If we
could
truly be sure that our battery of tests were complete (we
can't), then
passing them (with high confidence) would be enough ensure
security.
OTOH, if *any* test reveals that the output is biased (with
high
confidence), we should consider the RNG broken.
> >Statistical tests do not and, as you pointed out, cannot
> >characterize randomness.
> Nor can they characterize non-randomness with absolute certainty.
But nothing is absolutely certain.
> >Statistical tests do precisely what they're designed to do, which
> >is compute the probability that a particular finite string is
> >produced by a random variable that is distributed according to a
> >particular model.
> And that probability is only an estimate of the possibility that the
> variable is truly random - or non-random. Possibility does not mean
> certainty for finite sized samples. Only in an infinitely large
> sample can one determine for certain the randomness or
> non-randomness of a process based on statisitcal measure. That is
> what the law of large numbers is trying to tell you - that you must
> go to the infinite limit to get certainty, otherwise all you can
> have is a calculable level of possibility.
And here, I believe, is the crux of the matter. You cannot
have
certainty. Ever. No amount of careful design, no amount of
diagnostic testing and tuning, no amount of statistical
testing, there
is *nothing* that will *ever* provide certainty.
Statistical tests
have one huge advantage over all other approaches, though,
and that is
that with the statistical tests one can, in fact, compute
the
possibility that the results of the test are in error, and,
further,
one can continue the testing until that possibility of error
is as
small as one desires. IOW, statistical testing allows you
to get as
close to certainty as you'd like.
Unfortunately, each statistical test only checks for a
certain (set
of) kind(s) of structure, so each test can only provide
arbitrarily
high confidence that the criteria defined by the test are
passed/failed.
This means, of course, that a test can only show that all
sequences
are *not* equiprobable.
> >If I have a noise-based RNG based on radioactive decay,
> >well-shielded to prevent an attacker from monitoring the output,
> >and I have not performed any statistical tests to look for, is this
> >stream random? Yes, it is.
> If the RNG meets the specification for a TRNG, then it is suitable
> for a proveable secure cryptosystem such as the OTP. You will have
> to do a design audit and run experimental tests on each subsystem to
> determine if the device is a TRNG or not.
Will I then have certainty?
> >If I do apply thorough statistical tests to my well-shielded,
> >radioisotope-based RNG and I discover that, with very high
> >confidence, the resulting bit streams fit a uniform distribution
> >and evidence no memory,
> Just out of curiosity, how do you propose to do that? Can you call
> out the battery of statistical tests and all the test conditions
> that you would use.
No. At least not without doing some research. Can you call
out the
battery of audit reviews and experimental tests you would
perform on
each subsystem of a TRNG? Further, can you quantify the
likelihood
that your specific reviews and tests will produce accurate
results?
Finally, can you say how you will ensure that your audits
and
experimental tests are complete as well as correct?
> >and I then cease testing and put the RNG into production, is this
> >stream random? Yes, it is.
> It is only because it meets the specification for a TRNG, and that
> is something you cannot determine from statistical testing alone?
Yes. It is because the machine appears to be a random
process that I
consider the output to be random. Note that this is
independent of the
question of the distribution of the output (which makes it
what you
would call "crypto-grade", and which the aforementioned
statistical
tests exist to falsify).
> >If I have my shielded, tested TRNG and while continuously
> >monitoring the output I notice a string of 100 consecutive zeros,
> >is this stream random? No, it is not.
> Why not?
> I agree that such an occurance has a large *possibility* of being
> the result of a malfunction, but it is not certain that it is the
> result of a malfunction.
Do you have any concept of just how small 1/2^100 is?
> If you stopped the TRNG and checked it out, and found out that it
> was not malfunctioning, would you use those 100 zeros as part of the
> keystream - or would you discard them because you are prejudiced
> against long runs?
Neither. I would suspect that the tests I used to determine
the TRNG
is not malfunctioning are in error. I would probably
discard not only
the 100 zeros, but all other unused output of the TRNG and
I'd
probably get a new machine.
It *is* possible that I'm in error, but if we assume my TRNG
produces
1,000,000,000 bits per second (a rather high data rate), on
average I
expect to legitimately see such a run once every 17 trillion
years, so
I'm willing to take that minisclue chance that I'm throwing
away a
perfectly good machine.
> Where in the specification of a TRNG does it mention anything about
> long runs of one bit or the other being prohibited?
Nothing, but really long runs are so hugely unlikely that
they must be
viewed as an indication of failure. It is so much more
probable that
the run is the result of a failure that the only sensible
thing is to
assume that it is.
What I'd like to know is what tests you are planning to
perform to
verify the correct operation of the machine that are
guaranteed to be
more accurate than statistical tests of the output.
Shawn.
------------------------------
From: "David Starr" <[EMAIL PROTECTED]>
Subject: Re: ---- Two very easy secret key Cryptosystems
Date: Fri, 2 Apr 1999 01:27:48 -0600
[EMAIL PROTECTED] wrote in message <7dtbuo$rq4$[EMAIL PROTECTED]>...
>In article <[EMAIL PROTECTED]>,
> kctang8 <[EMAIL PROTECTED]> wrote:
>> Fiji wrote:
>> > > kctang8 wrote:
>> > >>a,b,c and e denote positive integers.
>> > >>
>> > >> Please crack the following systems:
>> > >>
>> > >>(Q1)
>> > >>plaintext: [a,b,c]
>> > >>encryption: choose a secret number e,
>> > >> cyphertext = [A,B,C] = [e*a, e*b, e*c]
>> > >>decryption: the partner know e,
>> > >> get plaintext [a,b,c]= [A/e, B/e, C/e]
>> > >>
>>
>> > Well if this were english text, it would be nothing but a substitution
>> > cipher which would allow one to do frequency analysis. This is not
unlike
>> > the affine cipher.
>>
>> But the point of system (Q1) is that _A_ secret number is used for
>> _EACH_ three components. For more than 3 components, such as 9
>> components, 3 _different_ secret numbers will be used.
>
>Allow me to point out that this system is trivially breakable.
>e = GCD(e*a, e*b, e*c)
>
>enough said?
e is not necessarily GCD(A,B,C).
For instance:
a = 64
b = 16
c = 32
e = 2
Assuming e = 1 is illegal (otherwise ea=A), e will be a common factor of
(A,B,C) in { 2..GCD }.
-dave
------------------------------
From: "Gianluca Dini" <[EMAIL PROTECTED]>
Subject: blind signatures
Date: 1 Apr 1999 16:11:18 GMT
I have a problem with blind signatures and, surely, someone of you can help
me.
Assume a standard RSA setting, in which the public key is denoted as a
pair (e,n) and the private key is denoted as a number d. Here, the modulus
n is a product of two large (secret) primes p, q and the private key d is
the multiplicative inverse of e modulo (p-1)(q-1). For the security of the
RSA system it is assumed that both p and q are
sufficiently large (e.g., 100 digit numbers), such that it is infeasible to
either find the factorization of n or to find the private key d, given only
the public key (e,n).
Consider now the blind signature scheme.
Suppose that R and B are two random numbers between 0 and n and that B is
used to blind R. The blinding operation is performed by working out the
following equation:
t = R x B^e (mod n)
Now, the problem is: by the knowledge of t and e (and R and B if
necessary), is it possible to find anouther couple (R1, B1), different of
(R, B), such that t = R1 x B1^e?
If the answer is yes, how difficult is this problem? furthermore, is there
any countermeasure?
thanks.
all the best
gianluca
------------------------------
From: "David Starr" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.physics,sci.logic
Subject: Re: My Book "The Unknowable"
Date: Fri, 2 Apr 1999 02:18:06 -0600
karl malbrain wrote in message <7e1cvg$eti$[EMAIL PROTECTED]>...
[-snip-]
While I AM fascinated BY your USE of CAPITAL letters, this WHOLE thread IS
off-TOPIC
for sci.crypt. For that MATTER, the FOLKS over in sci.physics and sci.math
probably AREN'T
ALL that interested, EITHER.
Have a NICE day,
-dave
------------------------------
From: [EMAIL PROTECTED] (Thomas Mehring)
Subject: SHA
Date: Fri, 02 Apr 1999 11:10:15 +0200
Is SHA free?
bye
Thomas Mehring
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Fri, 02 Apr 1999 11:23:54 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 02 Apr 1999 00:04:17 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>Now, given a constant confidence level, how does the sample size
>required to reach that level of confidence grow as the size of the
>parent population grows? This is related to the sharpening of the
>central spike in a gaussian distribution as the size grows.
Then you do have a theoretical model for true randomness.
At medium
>large numbers (10e6) the spike is quite sharp. At really large numbers,
>like the moles of air in a room (10e25?) the spike is incredibly thin.
>Thus we never see any measurable pressure differential across a room,
>much less a segregation of air molecules.
>For truly huge numbers, such as 2^256, the spike is essentially
>everything. It is really very hard to get a sequence of that length
>that is at all far from the center. For numbers like those you
>mentioned, 2^1000, it is impossible in practice.
>Given this narrowing of expectations,
The "narrowing of expectations" is a presumption based on a
theoretical model, such as the uniform Bernoulli process. I am not
going to put words into your mouth by saying that you believe that a
UBP is a correct model for a TRNG - as many others have said in the
literature - but I am going to ask if you think it is.
>it does not take a large sample to
>give good confidence that the sample properly represents the parent
>population.
Just how large is a "large sample"? And what is the justification for
making that statement in general?
I do not believe either question can be answered unless you posit a
theoretical model, and make the assumption that is correctly models
the TRNG output. Can you provide us with that model, so we can see how
you can calculate such things as a "large sample" and see how such a
"large sample" actually allows us to make inferences.
>I have purposely left out any prescriptive reference,
>thinking that if you derive the actual forumla for the sample size
>necessary to reach a given level of confidence then you will have gained
>the insight necessary to comprehend the answer. Without that insight
>the answer will be counter-intuitive gobbledogook.
You cannot calculate amything until you have been given the
theoretical model. So, just exactly what is the theoretical model for
true randomness?
>Good luck.
Oh, cut it out - such calculations are taught in elementary
undergraduate courses. Don't evade the fundamental issues with
condescention.
>This is another reasonable question, but I'm not well-enough grounded in
>the axioms of statistics to answer it at all authoritatively. I am
>certain that the analyses I learned had nothing, zero, to do with
>infinite samples.
Then how come Triola says omp. 212:
"The mean of a discrete random variable is the theoretical mean
outcome for *infinitely* many trials."
How much more explicitly would you want someone to state that infinity
plays a large part in statistics than when that someone uses it to
discuss the calculation of such a fundamental quantity as the mean
value of a distribution?
I rest my case:
1) Statistical tests assume a theoretical probability distribution;
2) Statistical tests rely on the passage to infinity in the
calcualtions of expectations.
>I would guess your suspiscion is related to something
>like the central limit theorem in which the answers are approximations
>until the limit is reached. That is most certainly NOT true of
>statistics. All of the principles are founded in finite populations.
Not true according to Triola. He makes a big deal over distributions
(p. 202):
"Without a knowledge of probability distributions, users of statistics
would be severely limited in the inferences they could make. We intend
to develop the ability to work with discrete and continuous
probability distributions, and we begin with the discrete case because
it is simpler."
>They are several (probably more than I am aware of) shortcuts that can
>be taken because a sample may be shown to approximate a "perfect"
>distribution (based on an infinite collection), which makes it easier to
>manipulate. But AFAIK this are just Q&D techniques unrelated to
>fundamental statistical analysis.
I do not doubt what you said in the general case - I am challenging
that assertion as it applies to tests for true randomness of finite
sequences.
Bob Knauer
"First, it was not a strip bar, it was an erotic club. And second,
what can I say? I'm a night owl. Anyway the bitch set me up."
- Marion Barry, Mayor of Washington DC
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Fri, 02 Apr 1999 12:02:12 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 02 Apr 1999 03:19:02 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>I will let the readership judge for themselves whether I
>have been disingenuous, or a charlatan.
Then in that case, let's not forget to add "smug" and "condescending"
to the list.
Bob Knauer
"First, it was not a strip bar, it was an erotic club. And second,
what can I say? I'm a night owl. Anyway the bitch set me up."
- Marion Barry, Mayor of Washington DC
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Fri, 02 Apr 1999 12:00:35 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 02 Apr 1999 03:35:49 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>> >A point that is generally agreed is that whatever is going on at
>> >the quantum superposition level, it is inconsistent with standard
>> >probability theory (a la Feller, for example), although it is
>> >usually described in probabilistic terms.
>> Can you explain what you believe is inconsistent with standard
>> probability theory?
>That should be obvious,
Are you claiming that quantum mechanics is "obvious"?
Get outta here! Quantum mechanics is anything but obvious. Even the
classical one dimensional uniform random walk is anything but obvious.
Nothing worth considering is ever obvious, except to a sophomoric
mentality.
>but: Take the 2-slit experiment as the
>canonical example (and Feyman says this is appropriate);
Feynman is dead now, and much has happened since his death. Quantum
Entanglement is all the rage now. Entanglement attempts to explain in
probabilistic terms what is going on in the QM measurement process.
>So it is not even treatable using probability theory;
What you really mean is that quantum mechanics is not treatable with
*standard* probability theory. Quantum mechanics is its own
non-standard probability theory using complex numbers in Hilbert
space. It is a probability theory in its own right.
>No; in fact what I *think* you mean by "true randomness" you have
>attributed to a uniform Bernoulli process, and apparently also a
>static 0-order Markov chain, which are simple to model
>mathematically.
You still don't get it. Now, pay close attention so we don't have to
go thru this every time:
1) I did not invent the concept of "true randomness". It is based on
an inordinate number of discussions (easily in the thousands) we all
had 1 1/2 years ago here on sci.crypt when we were grappling with the
OTP cryptystem, trying to understand how it could be proveably secure,
how to make sure that the keystream would result in guaranteed
security, etc.
The specification for a true random number generation that I have
been stating was distilled from the prevailing consensus of people
here. I did not make anything up. That specification is:
+++++
A true random number is one that is produced by a True Random Number
Generator (TRNG), which is a process that generates all possible
fininte sequences equiprobably, namely in an independent and
equidistributed manner.
+++++
2) I am not claiming that any model, not even the uniform Bernoulli
process of coin tossing or its cousin the random walk or even a Markov
chain for that matter, is the correct theoretical model for a TRNG
process. I have been discussing the UBP and random walk only because
Feller discusses them as examples of how statistical considerations
can be incorrect for finite sequences.
I will point out that many people have used the UBP as an example of
how one might configure a TRNG, such as with a fair coin toss. But I
have never agreed that any classical theoretical model comes even
close to modeling true random number generation. I am of the belief
that true random number generation is quantum mechanical in nature,
and the only hope you have for producing it in the real world is to
tap off of a quantum process such as radioactive decay.
3) I claim (which is a reversal of my earlier position) that
statistical tests on finite sequences using infinitesimally small
samples, as is necessarily the case for keystreams with a large number
of bits, is not a valid way to determine non-true-randomness of a TRNG
process. Such tests only disclose a property called
"pseudo-randomness". I have never seen anyone succeed in showing that
statistical properties result in the collapse of the wave vector.
There has been nearly a century of investigation going into the search
for hidden variables, and nothing has been turned up. QM may be based
on statistical models, but the fundamentally random parts, such as
measurement, are not. There is something far more profound going on
than can be described by statistics alone.
>You might as well not bother, then. Triola was suggested as a
>way to learn enough about statistical testing to have an
>educated opinion on the subject. I don't recall that he ever
>brought up the issue of "true randomness" as such.
I never said he did. It is you who claimed that a reading of Triola
would enlighten me as to the validity of statistical tests in
determining that a process is not truly random.
>And in
>any event, nobody here (other than you) has suggested "that
>statistics has found the holy grail of true randomness".
You are absolutely wrong in that assertion. Just look at FIPS-140 to
see that several statistical tests are touted as the proper means to
determine the randomness of sequences for crypto. Nowhere was there
any warning given that in actuality these tests were really to
determine a property called "pseudo-randomness" and that therefore
they were limited to a diagnostic role.
>What we have stated is that properly applied and interpreted
>statistical testing of RNG output is a reasonable activity.
Yet you never give us any concrete examples. You did once mention the
Chi-Square Test, but never went anywhere with it. That's because that
test, and all other statistical tests, does 2 things which are
impossible to justify with regard to true randomness:
1) It assumes a classical theoretical model;
2) It relies on the passage to infinity for its expectations.
>One doesn't learn statistics by "focussing on specific issues"
>any more than one learns general mathematics by focussing on
>the properties of the number "ten".
I am not interested in learning statistics. I have more interesting
things to do with my time than that - such as determining what this
concept of "true randomness" is all about.
I am taking this side trip into the wonderland of statistics only
because people like you insist that it has a fundamental bearing on
true randomness.
Bob Knauer
"First, it was not a strip bar, it was an erotic club. And second,
what can I say? I'm a night owl. Anyway the bitch set me up."
- Marion Barry, Mayor of Washington DC
------------------------------
** 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
******************************
