Cryptography-Digest Digest #889, Volume #8 Tue, 12 Jan 99 10:13:04 EST
Contents:
Re: On the Generation of Pseudo-OTP (Mok-Kong Shen)
Re: On the Generation of Pseudo-OTP ("Trevor Jackson, III")
Re: On the Generation of Pseudo-OTP ("Trevor Jackson, III")
a^x mod n question (Rx Video)
Re: On the Generation of Pseudo-OTP ("Trevor Jackson, III")
Re: Birthday Attack calculations. ("Trevor Jackson, III")
Re: On the Generation of Pseudo-OTP (Mok-Kong Shen)
Re: Practical True Random Number Generator (R. Knauer)
Re: Practical True Random Number Generator (R. Knauer)
Re: On the Generation of Pseudo-OTP (Patrick Juola)
Re: Practical True Random Number Generator (Mok-Kong Shen)
Re: On the Generation of Pseudo-OTP (R. Knauer)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Tue, 12 Jan 1999 12:54:42 +0100
R. Knauer wrote:
>
> On Mon, 11 Jan 1999 17:35:45 +0100, Mok-Kong Shen
> <[EMAIL PROTECTED]> wrote:
>
> >> Does that convince you that I can PROVE what I said?
>
> >It is NOT a rigorous proof in the mathematical sense.
>
> Who says that only mathematical proofs are valid?
I only employ mathematics to illustrate the type of 'rigor'.
On the other hand, all rigorous proofs are ultimately reduced
to proofs in mathematical logic. And mathematical logic is
a subfield of mathematics.
>
> >It is a 'plausible' proof.
>
> No, it is a rigorous proof.
>
> If the physcial process, such as radioactive decay, is completely
> random, and the TRGN is properly constructed, then the output is
> suitable for a totally secure OTP.
But if that phrase 'If the .... random' cannot be true in the real
world, then your assertion has no practical meaning. It's like
'If there are plants on the moon'.
>
> Of course the designer has to certify that the TRNG behaves as
> advertised, but that can be done. The radioactive source can be
> certified to follow a first order rate law to within an arbirtary
> level of precision. The electronics can be designed to withstand any
> single point of failure. The entire system can be subjected to
> multiple Bayesian Attacks.
So long that you accept 'non-perfectness' (through your 'arbitrary
level of precision') everything is o.k. You verify that with some
tests and these give you confidence level of whether a given
sequence from radioactive source satisfy certain advertised merits.
But so can appropriately done 'intended approximation to an ideal OTP'
be subject to such tests. If the tests happen to be o.k., these
can be used in the practice.
>
> >I never argued that hardware noises were bad.
>
> And I have never considered using them for a TRNG.
By hardware noises I mean noises (randomness) from physical processes.
If you exclude these, where do you obtain your 'TRNG'?
>
> >I believe they are mostly excellent.
>
> On what do you base that assertion?
This is only a 'belief' and hence subjective. I get the impression
from the amount of works people have expended in trying to remove
bias from hardware noises. It's like trusting a well-sold household
device is o.k. One may err, of course, with such subjective
(non-rational) belief.
>
> >But perfect are they NOT, nonetheless.
>
> So what? They can be certified to meet a certain level of practical
> perfomance which for all effects and purposes is the same as total
> security. Just because a TRNG creates a pad that leaks a bit or two of
> information now and then isn't going to detract from their practical
> value as generators of totally secure pads.
Covered above.
>
> >But we don't (never) need perfectness in practice, so
> >they (assuming that bias are sufficiently reduced) can for all
> >practical purposes be substitutes for the (practically unobtainable)
> >ideal OTP.
>
> Each case must be considered separately. I have proven that from
> direct experimentation certain kinds of radioactive decay meet the
> specifications for a TRNG. I have not seen an analysis for electronic
> noise in general. I would expect that the analysis would depend
> crucially on the source of the noise.
>
> The problem I forsee with electronic noise generators is that they
> have a finite spectral response, which in principle could limit them
> as TRNGs, in the sense that not all possible sequences would be
> capable of being output equiprobably. That is not a problem with a
> digital device like a properly designed radioactive decay TRNG.
As I said, if one accepts certain approximation and does not
(irrationally) demand perfectness, then everything is o.k.
>
> >But the justification of using these has ultimately to come
> >from a risk and cost analysis of the user.
>
> Not if it is being used for the OTP. In that instance, only the best
> TRNG will suffice - best in the practical sense.
Hardware noise may indeed be the best source in the practical sense.
But that anyway doesn't preclude 'intended approximation to an ideal
OPT' from being, say, the second best source and thus have utility in
practice because of cost advantages, etc.
>
> >Since software made
> >'intended approximations of ideal OTP' presumably can also attain
> >negligible correlations,
>
> That is what remains to be shown. Can one construct a procedure to
> remove correlation from calculated or natural language or music
> bitstreams?
I indicated certain viable techniques in the original article.
Whether they are good have ultimately to be verified by experiment.
But I thought that there is certainly value to know what merits the
individual techniques (or additional proposals) may possibly have
according to experts' evaluations before doing extensive experiments,
which could be expensive without guidance of experts' opinions.
That's why I initiated the the present thread.
>
> >they have also a chance of substituting
> >the hardware noises in certain applications, IF this can be
> >justified from a risk and cost analysis.
>
> There is no risk with the OTP system. It either works or it doesn't.
> And cost is irrelevant if you must have a proveably (in the practical
> sense) secure system.
Covered by what is said about 'approximation' above.
M. K. Shen
------------------------------
Date: Tue, 12 Jan 1999 07:55:06 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
R. Knauer wrote:
> On Sun, 10 Jan 1999 22:08:29 -0500, "Trevor Jackson, III"
> <[EMAIL PROTECTED]> wrote:
>
> >Right. The quality of the key was certinaly "good enough" to qualify that system
> >and a true OTP in spite of what we would judge as low-quality key material.
>
> I never knew that Venona concluded that the key material was of low
> quality. In fact, I don't even know what you mean by such a term.
>
> How does one characterize a key as low quality, unless it can be show
> to be susceptible to a successful Bayesian Attack, which was certainly
> not the case with those Russian ciphers. Instead it took pad reuse to
> break them.
Such an attack is one method of showing weakness. It is not the only method. We do
not
need to attack a system using weak keys to prove the keys are weak. You have been
stating that text-based keys are weak. This conclusion is undoubtedly based on
analytic
considerations rather than experimental ones.
In the instance of the Russian cipher the key generation process could not have
produced
fully independent key elements (this from human factors considerations). However, it
may
have produced keys good enough to make an attack infeasible without making it
impossible.
------------------------------
Date: Tue, 12 Jan 1999 08:26:02 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
R. Knauer wrote:
> RFC 1750 is available on the Web. Here is one source that seems to be
> stable over the last year:
>
> http://andrew2.andrew.cmu.edu/rfc/rfc1750.html
Please review the following sections of RFC1750:
4.4 Selecting keys from large databases; why this is a bad idea. N.B., a
transcendental
number is a compressible form of lage database.
5.2.3 Removal of correlation via FFT
6.1.2 Strong mixing functions.
These sections address the major issues you've raised recently.
------------------------------
From: Rx Video <[EMAIL PROTECTED]>
Subject: a^x mod n question
Date: Tue, 12 Jan 1999 08:17:50 -0500
Hello,
In his book B.Schneider shows how to efficiently calculate a^x mod n by
splitting the whole statement into multiplications (modulo) of squares
of (a*a mod n).
a^x mod n = a*a*...*a mod n=(((a^2 mod n)^2 mod n)...^2) mod n
I wanted to ask why not do this in the following manner.
a=k*n+r, r being the rest
a^x mod n=((a mod n)^x) mod n - calculate a mod n first, and then raise
it to power x and calculate modulo from this result. It gives the same
result.
There are probably some good reasons for doing things the way
B.Schneider described, still, I would like to know why is it that way.
Sincerely yours,
Martin
------------------------------
Date: Tue, 12 Jan 1999 07:45:43 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
John H Meyers wrote:
> Patrick Juola wrote:
>
> > For most trancendental numbers and most bases, it takes time and effort
> > to calculate increasingly long strings of digits. So for engineering
> > reasons, it's a lot faster to calculate the first thousand digits
> > than the second thousand (and so forth, progressively).
>
> > for generating successive digits of
> > a trancendental numbers -- each digit costs marginally more than the
> > last, which means that there's one digit that costs more to generate
> > than it would cost to generate and distribute random pages. At this
> > point, it is no longer cost-effective to consider trancendental-based
> > computation. You might as well print the pads and be done with it.
>
> Nonetheless, any *hexadecimal* digit of pi can be calculated (yes,
> at slightly increasing cost) without calculating *any* previous digit:
> <http://www.mathsoft.com/asolve/plouffe/plouffe.html>
>
> The following claims to have calculated over 50 *billion* (50*10^9)
> digits of pi: <ftp://www.cc.u-tokyo.ac.jp/README.our_latest_record>
> (many statistics included)
>
> This brings up the question of whether some set of selected offsets
> into this "pad" (XOR'ing all pads together) can constitute an effective
> key and pad (no need to store the pad, since the digits at any offset
> can be generated, as above, without knowing any prior digits);
> cryptanalysis of this one might seem difficult :)
The commentary surrounding these announcements indicates that the results may
be compressible. If so transcendental numbers are probably not appropriate
sources of entropy.
------------------------------
Date: Tue, 12 Jan 1999 08:34:48 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Birthday Attack calculations.
Thanks for the background exposition. I think I am slightly confused over the odds of
finding the first collision and the odds of finding no or any collisions.
For the purposes of the original issue we want the odds of finding the first collision.
I.e., the expected wait. The series formula I described indicates the probability of
finding no collisions, which also gives (by 1-p) the probability of finding any number
of collisions.
Presumably even odds of finding a single collision should take less work than even odds
of finding all collisions. Is this correct?
Fred Van Andel wrote:
> "Trevor Jackson, III" <[EMAIL PROTECTED]> wrote:
>
> >Fred Van Andel wrote:
> >
> >> A birthday attack would require > 2^128 calculation while an
> >> exhaustive search would need 2^255. There is a big difference. When
> >> you are dealing with large hashes even a birthday attack becomes
> >> impossible to do. Its the birthday attach that dictates the size of
> >> hash required, not the exhaustive search.
> >
> >I agree with your last statement above. But I an confused by your first statement
> >above. Is there a closed-form equation for the figure 2^128 you quoted? I am only
> >familiar with the probability series summation.
>
> You quoted the formula yourself in a earlier message
>
> > odds = 1;
> > for i=0 to N-1
> > odds = odds * (M-i)/M
>
> For any gives value of M the location of the 50% mark will be roughly
> the square root of M. The square root of 2^256 is 2^128.
>
> Unless I am misunderstanding you again.
>
> Some closed forms of the equations were given in the earlier posts of
> this thread.
>
> This method was posted by David Broughton
>
> > w = n^g + 0.29 - e
> >
> >where:
> >w = the number of documents to get 50% probability of a collision
> >n = number of different hash codes, all equiprobable
> >g = 0.5 + 1/(6.13 * ln(n))
> >ln() is the natural logarithm function
> >e is a small error that can be ignored in practice, usually < +- 1.
> >
> >This is an empirical formula that I worked out many years ago and
> >filed away in a notebook.
> >
> >The exact formula is the value of w in this equation:
> >
> > ( product from k = 1 to k = w-1 of (n-k)/n ) = 0.5
> >
> >but this is not a practical calculation for large n.
> >
> >As you can see, w is a bit larger than the square root of n. For
> >n = 10^6, for example, w = 1177.68 (e = -0.197).
> >
> >If your formula is meant to be 1.2 * n^0.5, then w = 1200 for n =
> >10^6 which is getting there.
>
> Or this one by Peter Pearson
>
> >To derive your own approximation formula from the above, exact
> >formula, rewrite it as follows:
> >
> > n (n-1) (n-2) ... (n+1-w) n!
> >product = -------------------------- = ----------
> > n^w (n-w)! n^w
> >
> >Then, use Stirling's approximation to make the factorials more
> >manageable. Stirling's approximation (see, for example, Knuth,
> >Art of Computer Programming, Volume 1) is:
> >
> > ln( n! ) = (n+1/2) ln(n) - n + ln( 2*pi )/2 + 1/(12*n) - ...
> >
> >You'll have to experiment with the number of terms required to
> >get meaningful results. Overimplifying to n*ln(n)-n gives conspicuously
> >nonsensical results. If memory serves, (n+1/2) ln(n) - n + ln( 2*pi )/2
> >is a good level of approximation, and one needs the approximation
> >ln(1+x) = x (for small x) as well.
>
> Or this one by Terry Ritter
>
> > s(N,p) = (1 + SQRT(1 - 8N ln(p))) / 2
> >
> >where s is the expected number of samples needed, N the size of the
> >population being sampled, and p the given probability.
> >
> >For N = 10**6 and p = 0.5 (so ln(p) = -0.693) we get 1177.9 instead of
> >the usual handwave SQRT(N) = 1000, or the stated approximation, 1.2 *
> >SQRT(N) = 1200.
> >
> >For N = 2**20 and p = 0.5, we get 1206.2 instead of 1.2 * 1024 =
> >1228.8 for the stated approximation.
> >
> >The formula basically comes out of my article on population
> >estimation:
> >
> > http://www.io.com/~ritter/ARTS/BIRTHDAY.HTM
> >
>
> Fred Van Andel
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Tue, 12 Jan 1999 11:52:16 +0100
R. Knauer wrote:
>
> On Mon, 11 Jan 1999 16:46:50 +0100, Mok-Kong Shen
> <[EMAIL PROTECTED]> wrote:
>
> >Yes. These are plain texts. Here I use these as given, i.e. applying
> >no techniques of removing correlations, only that I XOR the given
> >plain texts and use the resulting sequence as a 'pseudo-OTP' to
> >encrypt the message 'Attack at noon' through an XOR.
>
> What do you hope to accomplish by doing that?
The analyst can't decide which of the three is the real message.
A true OTP is thought to obtain the same undecidability.
> Oh, you can rest assured that physicists have indeed proven both
> experimentally and theoretically that certain forms of radioactive
> decay are truly random.
Even there is a truly random physical process (I 'assume' that a
certain defition of true randomness can be verified, though I
doubt that), the actual registration of the process, i.e. the
obtaining of data, needs measuring appratus. Since no man-made
apparatus is perfect, if follows that the sequence obtained is
subject to errors, hence not perfect. Hence one can at best accept
the sequence as truly random with a certain statistical confidence
level.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Practical True Random Number Generator
Date: Tue, 12 Jan 1999 14:20:55 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 11 Jan 1999 21:45:17 -0500, Nicko van Someren
<[EMAIL PROTECTED]> wrote:
>> >Another method is to time the two intervals between three decay
>> >events. If the first interval is longer than the second then emit a
>> >zero and if the second is longer than the first emit a one. If your timer
>> >says that they are the same do it again. This has as little bias as
>> >you can get.
>> That is the preferred method because it cancels any slowly varying
>> systematic errors, such as clock errors or detector errors - as long
>> as the the interval lengths are shorter in duration than the time
>> constants for the errors.
>> It was my understanding that you needed to measure each interval
>> independently, that is, you need to time the two intervals between 4
>> decay events, not 3.
>No. This is not necessary. In radioactive decay the decay events
>are independant (give or take some cascade effect which is extreemly
>short lived). In fact you don't even need three events, you can
>say to yourself "Now" and then time until the first event and then
>time until the second event, or even you can just pick a second
>random starting point and time until the next event. Irrespective
>of the starting time the probability distribution for the time until the
>next event is the same. (The astute reader will see that this means
>the distribution is an exponential curve).
I think you may have missed the point why it is necessary to time two
intervals. It has nothing to do with randomness of the decay process
per se, but everything to do with removing bias and systematic error.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Practical True Random Number Generator
Date: Tue, 12 Jan 1999 14:22:12 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 11 Jan 1999 22:48:40 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>Matter of fact, I think we're trying to remove the president 'cause
>his statements contained over 200% entropy!
LOL
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: On the Generation of Pseudo-OTP
Date: 12 Jan 1999 09:18:42 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On Mon, 11 Jan 1999 21:03:31 +0000, [EMAIL PROTECTED] (Paul L.
>Allen) wrote:
>
>>> There is something about your entropy that is not quite right here. In
>>> one of his papers, Chaitin dismisses such "low-entropy" sequences as
>>> being "non-random" for purposes of his algorithmic information theory,
>>> of which his algorithmic complexity theory is a subset. He dismisses
>>> such sequences because they are reducible.
>
>>Then his algorithmic information theory appears to have flaws.
>
>To be fair to Greg Chaitin, you should read his papers for yourself
>and not trust my evaluation. I am not trained in this field (although
>I am not a complete neophyte either), so it is entirely possible I
>misconstrued what he was saying.
>
>His papers are at:
>
>http://www.umcs.maine.edu/~chaitin/
>http://www.cs.auckland.ac.nz/CDMTCS/chaitin/
>
>>Any sequence
>>you like to specify in advance is reducible and, with the right input data,
>>will result in good compression.
>
>I don't understand what you just said. Are you saying that ANY
>sequence can be compressed further to a significant extent? Small
>reductions are not of significance in algorithmic complexity theory.
I don't know if he's saying that.... but, yes, he's correct. That's
why the compression theorists measure, not the size of the compressed
data, but the size of the compressed data plus the size of the
compression program. To keep people from simply memo-izing the
benchmark data and putting that particular data into the code as
a special case.
-kitten
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Practical True Random Number Generator
Date: Tue, 12 Jan 1999 15:26:03 +0100
Medical Electronics Lab wrote:
>
> It isn't just theory, but it's pretty damn hard for a real random
> number generator to pass something like DIEHARD without using a
> hash function.
I just want to recall that the Diehard package as supplied by its
designer is buggy. Sometime ago some person did a new implementation
in C without the known bugs and announced it in this group. But his
URL appears to be no longer accessible.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Tue, 12 Jan 1999 14:27:15 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 11 Jan 1999 21:41:59 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>Now my sub-atomic physics was never great, but it appears that there will
>always be a way to mess up "perfectly random" events.
Proper design would take all that into account, byshielding for
example.
>Now the key question:
>Do we know for a fact, or can we prove, that no *natural* phenomena can
>influence our TRNG in such a manner as to induce regularities.
Nope. But stay tuned because I hear that hidden variable theories are
making a comeback.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
** 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
******************************
