Cryptography-Digest Digest #905, Volume #8 Thu, 14 Jan 99 09:13:05 EST
Contents:
Re: Practical True Random Number Generator (R. Knauer)
Re: Metaphysics Of Randomness (R. Knauer)
Re: a^x mod n question (Rx Video)
Re: On the Generation of Pseudo-OTP (Snowhare)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: Irish school kid encryption ("Sam Simpson")
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: Twofish vs DES? (Bruce Schneier)
Re: AES and diffusion with 128-bit block length (Bruce Schneier)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Practical True Random Number Generator
Date: Thu, 14 Jan 1999 12:12:41 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 14 Jan 1999 01:36:01 GMT, [EMAIL PROTECTED] wrote:
>You can obtain a parallel-port compatible geiger counter (with a mica window)
>for ~$170 from www.aw-el.com. I've been playing with one of these.
>Background in So Cal is about 16 microR/hr. A click every few seconds.
>NB: I've found smoke detectors for $5. They contain the same circuit
>board and microcurie as the $15 and up First Alerts. Placing the geiger
>tube next to the the Am source, I get over 20 milliR/hour, which is a
>count of over 300 per second. (An inch from the hot source, you see nothing:
>alphas don't penetrate air well.)
>The distribution of clicks/sec is of course a normally distributed function.
Hmm... I thought for low count rates it was a Poisson distribution.
From: http://www.io.com/~ritter/RES/RNGMACH.HTM
"A histogram shows that the random intervals are not uniformly
distributed; there is a definite peak around an 'average' value, but
you'll find all values between zero and huge." "From what little I
remember from my courses in probability theory, the curve resembles a
Poisson distribution."
[ For random sources which are slow enough to be detected as
individual pulses, the Poisson distribution is expected. ]
>You have to distill the entropy to get a uniform distribution.
Do you have a preferred technique for doing that which does not
introduce non-randomness algorithmically?
>As an entropy source, this is inferior to a soundcard digitizing amplified
>FM hiss due to the lower bandwidth, even with the Am source. Since you
>have to distill the entropy anyway, there is little to be gained by
>using radioactivity, except that it can't be interfered with as readily.
The one advantage of the radioactive decay TRNG is you can prove that
it satisfies the TRNG specification. I am not so sure about electronic
noise devices - it appears that one would need to make some
assumptions which have no fundamental physics behind them.
Chaos does not imply randomness, for a TRNG anyway. The weather is
chaotic, but hardly random. I suspect the same for electronic noise in
general, although there must be a few instances where one could use
first principles to prove randomness due to quantum effects.
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Thu, 14 Jan 1999 12:27:02 GMT
Reply-To: [EMAIL PROTECTED]
On 13 Jan 1999 15:46:01 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
R. Knauer <[EMAIL PROTECTED]> writes
>>>One conclusion from these considerations is that a number that is
>>>generated algorithmically, no matter what the algorithm might be, is
>>>not a true random number - because such a number always has some
>>>reason for its existence, a reason that you could possibly discover if
>>>you worked at it long enough or hard enough. That is why only the
>>>TRNG-based OTP cryptosystem is proveably secure - all other systems
>>>have an underlying calculable reason behind their encryption schemes.
>>>That means that almost all of classical cryptography (the OTP being
>>>the sole exception) is not about security but is about obscurity,
Douglas E.Denny. <[EMAIL PROTECTED]> writes:
>>There is an inbuilt falacy in this above statement.
>>If your proposition above about any random number generated is not a true
>>random number, (for whatever reason) then the OTP _cannot_ be an
>>exception as its (random) key is normally derived from an algorithm.
[EMAIL PROTECTED] (Patrick Juola) wrote:
>Mr. Knauer's statement is incorrect -- although not for the reason
>given.
Specifically which statement is that?
>I'm not familiar with *ANY* implementation of the OTP
>in which the random key is derived from an algorithm;
I have been saying that all along.
>the usual method by which the random key is chosen involves tapping
>into some non-algorithmic source of "randomness".
I have been saying that all along, too.
>The classic
>example is, of course the (Sperry-Rand) table of random numbers
>which actually involved a complex pinball-machine/roulette-wheel
>to develop the numbers.
I have been promoting the concept of a TRNG, which is a physical
device capable of outputting all possible sequences of a given finite
length equiprobably.
>Anyone who claims to have an algorithmic method of generating an OTP
>is selling snake oil.
I have been saying exactly that all along. Ask Mok-Kong Shen.
>But, on the other hand, the reason that the OTP is provably
>secure is *NOT* because of some mystical property involving
>''true randomness'', but by a simple assumption of statistical
>equiprobability and uncertainty
I have been saying that all along.
I have been saying that the proveable security of the OTP is not based
on the "true randomness" of the pad per se - but the way in which the
pad is generated, namley by a TRNG which satisfies the properties of
equiprobability and uncertainty.
>If the key is at least as uncertain as the message, then it's
>possible to develop a provably perfect encryption method based
>on that key.
If the key is generated by a TRNG, it will possess that property.
>The typical problem is that messages are usually
>very long (and hence exceed the uncertainty of most keys rather
>quickly).
I don' understand that statement. If the pad is generated from a TRNG,
it can be arbitrarily long - and what you describe is not a problem.
I fail to see from anything you have just said that anything I have
said is in error. Please point out what makes you think my statement
is incorrect.
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: Rx Video <[EMAIL PROTECTED]>
Subject: Re: a^x mod n question
Date: Thu, 14 Jan 1999 07:49:12 -0500
Hello,
Thank you for the answer. I didn't realize that a is already less than n. In that
case an additional mod operation is obviously not necessary. I thought that a can
be any number.
Sincerely yours,
Martin
Man-Sik Choi wrote:
> John Enright wrote:
> >
> > Rx Video wrote in message
> > <[EMAIL PROTECTED]
> > t>...
> > >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
>
> It is done the way The Book says because it take less wurk to do it that
> way then to do x multiplications. Also, as someone said a is less than n
> already, so your approach INCREASES the wurk needed. Take an example.
>
> 101^513 mod 1009 == c
>
> 101 mod 1009 == 101 = 0*1009 + 101 (your methud)
>
> 101*101 =10201
>
> 10201 mod 1009 == 898
>
> (((898^2 mod 1009)^2 mod 1009)^2 mod 1009)*101 == c
>
> That is easier than doing 513 multiplications and mods
------------------------------
Subject: Re: On the Generation of Pseudo-OTP
From: [EMAIL PROTECTED] (Snowhare)
Date: Wed, 13 Jan 1999 17:51:26 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Nothing above this line is part of the signed message.
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>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.
Or by monitoring the environment. You don't have to make it _directly_
immune to tampering - you just have to be able to _detect_ tampering.
Neutrino beams? By the time you crank one up high enough to measurably
affect a TRNG you would have so much secondary radiation that *it* would
be detectable (not to mention directional effects would also be
detectable). Ditto for neutron beams, gamma rays, etc. Proper isolation
and environmental monitoring could produce a TRNG that could be trusted
to any limit you care to specify.
Benjamin Franz
=====BEGIN PGP SIGNATURE=====
Version: 2.6.2
iQCVAwUBNpzdfujpikN3V52xAQFdRgQAl3+aZwWNY9ms3VARPbvQFVPXf+nTeeyb
6rVDIX0IAqekJa8Wfhs1fD9d781XoCQr8yBpwv37VQ7LnI8c+Fet6GapGKApT3XP
ajbCe8NXEDiyqKNg7v9rAnusNEXqkEvAqZ2TpVZkjpKZkTGc6Y1YU/0Y27p+58Yb
ImQMsATADyU=
=TcOH
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 14 Jan 1999 12:52:03 GMT
Reply-To: [EMAIL PROTECTED]
On 13 Jan 1999 14:37:11 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>Now, note that the function Y above yields a method for generating
>the string x. Simply concatenate two programs -- one that outputs
>the number 1, and then the function Y' that converts 1 into x.
>*IF* x is a very complex string, then the function Y' will not
>be smaller than the KC-complexity of the string x. So the size
>Y' is bounded from below, even while x can be compressed to an
>arbitrary degree by a sufficiently complex program.
This discussion began when I asked a question about Chaitin's
algorithmic irreducibility theorem, namely:
If I present you with a sequence (the ciphertext) which is the optimal
compression of some other sequence (the plaintext) and it is the
minimal algorithm based on Chaitin's theory, then according to his
theory it is "random". Yet it is not crypto-grade random, because if
you run the algorithm on a computer it will reproduce the original
plaintext trivially.
Later one poster commented that the algorithm was not the minimal size
- and that is what you seem to be saying - but I question if that is
what Chaitin had in mind by algorithmic reducibility.
Regardless, Chaitin claims that algorithmic complexity has a strong
connection with randomness (the bits of his Omega are each random in
the crypto sense, namely completely unpredictable) and I question that
to some extent as I did above, and because some of the output
sequences from a TRNG can be algorithmically reduced, and it is not
possible to exclude those from an OTP without messing up the OTP.
The whole point of this discussion was, as I originally intended it,
to decide if Kolmogorov-Chaitin complexity is a proper measure of
crypto-grade randomness. I think it is not considered in its entirety.
But I do believe there are some useful concepts contained therein that
apply to crypto.
Chaitin himself goes one step further and says that his theories have
no applicablilty to crypto whatsoever (private communication), but I
do not agree fully with that - see the thread entitled "Metaphysics of
Randomness".
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 14 Jan 1999 13:13:21 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 14 Jan 1999 03:07:24 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>I don't think quench time *can* be taken into account. If another
>event occurs during the quench time, it will not be detected, and may
>affect the quench time itself. And when an event is *not* detected,
>it can hardly be taken into account. Quench time will introduce an
>uncertainty of the time between event pulses, which would otherwise be
>"perfectly" Poisson-distributed.
By "taken into account" I should have said that one must not use a
detector that has an unacceptable quench time. I did not mean to imply
that one could doctor the data to get around that problem.
But you bring up an interesting point. Let's say that the detector
does not count some events because of failure to quench the gases in
the tube. Imagine instead that those events went off in another
direction and would not have been detected anyway.
There is nothing magical about the event that should have been counted
but was not counted - either because it did not enter the detector or
because it did enter the detector but was not counted because the
detector gases were not quenched.
The randomness being measured by the radioactive decay TRNG is the
result of the source-detector system, not the source alone. That
source-detector system is not 100% efficient by any means - most
events escape detection, regardless of quenching. Yet the timing
intervals occur on a completely random basis.
The reason is that any event occurs at a random time whether you
detect it or not. Those events that are not counted because the
detector gases were not quenched do not in any way influence the
ramdomness of the decay time of other events. Each decay event is
completely independent of all other decay events - that is required
for them to be random in the first place.
So quench times are not of fundamental significance.
>Fine. Provide some references to serious articles by serious
>experimenters who seriously state that they have a random number
>machine which is "provably random."
I cannot do that. Do you have evidence to the contrary?
>It is easy for a handwave to meet that specification. But only real
>machines actually produce sequences, and real machines neither measure
>nor report reality precisely, especially at quantum levels. Nor is it
>clear that we can ever know the full story of the distortions in our
>measurements.
Your pessimism could be seen as so much handwaving, too.
>If the values from physical measurements must be a flat, unbiased
>distribution, I doubt we will every have such a machine. If we can
>accept post-processing, we don't need such precision, but then of
>course we have less of an argument for "absolute" randomness.
Don't you believe that one can make a TRNG that outputs crypto-grade
random sequneces to within an arbtrary level of practical precision
without post processing?
>I guess not everyone listens.
How can one listen unless you tell them?
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: Irish school kid encryption
Date: Thu, 14 Jan 1999 09:25:21 -0000
This systems seems to be be based upon the RSA problem - is it also covered
by US Patents? Could the scheme be extended to use Discrete Logs (e.g.
ElGamal / Diffie-Hellman) ?
Cheers,.
Sam Simpson
Comms Analyst
-- http://www.hertreg.ac.uk/ss/ for ScramDisk hard-drive encryption & Delphi
Crypto Components. PGP Keys available at the same site.
Anthony Lineham wrote in message
<[EMAIL PROTECTED]>...
>I read a brief news article today about a 16 year
>old Irish school girl who recently won a prize at
>a science fair for designing an encryption
>algorithm for internet use that is reported to be
>10 times faster than algorithms currently in use.
>she is apparently being hailed as a mathematical
>genius.
>
>Does anyone have any more specific details about
>this or know where they may be found?
>
>Thanks
>
>Anthony.
>
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 14 Jan 1999 13:28:12 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 14 Jan 1999 03:07:30 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>RFC 1750 describes fairly well-known techniques, and there is
>remarkably little "proof" argument there.
It does describe hashing too.
>I claim that any good hash should be a good randomness mixer,
>especially when more goes into it than comes out. While RFC 1750 does
>not mention CRC mixing, I often argue that a linear CRC hash
I trust you mean CRC 16. If so, its implementation via lookup table is
very easy.
>provides a fine mixing for really random streams.
I am confused. If the streams are random to begin with, why would they
need to be combined by a hash? DO you mean "almost random streams"
except they have corrrelation that needs to be removed - like the LSBs
of text or the bit expansion of pi might be, or the output of a
well-designed LFSR?
>We could use a keyed Latin square combiner, or the combiner-based
>ciphering structures I have been promoting for the past few years.
Which are? I have never heard of those things.
Remember that the original objective here is to remove correlation
from a bitstream such as the LSBs of text or the bit expansion of pi.
It is assumed that those streams have been antiskewed before hand.
>I take no such an implication. I would say that one probably would
>not expect a mathematical proof of the "strength" of mixing techniques
>(indeed, if such a term applies) unless they are, in some sense,
>perfect.
How would one test for such perfection? How does one quantify the
extent of that, like 99.9% perfect?
>Such as a Latin square.
Which is?
>"Algorithmic decorrelation" certainly *could* be impossible if you
>define it that way. That seems rather unuseful, however.
What other way is there to decorrelate a bitstream in a useful manner
other than to do it by some algorithmic procedure, either on a
computer or in dedicated hardware?
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 14 Jan 1999 13:32:38 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 14 Jan 1999 03:10:31 GMT, [EMAIL PROTECTED] (John Nagle) wrote:
> Pure XOR is safe only with truly random keying material.
>Otherwise, it's a weak cypher, and any nonrandomness in the keying
>material can potentially be exploited. Historically, it has been, too.
>Witness Venona, etc.
I thought the weakness exploited in Venona had to do solely with the
reuse of the pads, and not from some intrinsic weakness in the pads
themselves. IOW, if the Russians had not reused the pads, their
ciphers would be secure even to this day.
> The big trouble with one-time pads is that not only do you need
>large amounts of keying material, you need unique keying material
>for each pair of stations that communicate. This tends to restrict
>its use to hierarchical situations like embassy-to-capital, spy
>to HQ, and military unit to higher headquarters where the central
>station is highly secure.
Or the Washington to Moscow hotline.
I can see it now - a new doomsday movie about how the President calls
Boris in a nuclear crisis and tries to send him an OTP cipher but his
dog ate the pad.
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 14 Jan 1999 13:40:07 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 14 Jan 1999 03:53:08 GMT, [EMAIL PROTECTED] (Snowhare)
wrote:
>Would you believe there is now a project to map the interior of the
>Earth using neutrinos?
When it comes to spending OPM, I can believe anything. Fermi suggested
building a cyclotron that circled the earth in orbit.
What I cannot understand was shutting down the Supercollider project -
and I followed that saga from beginning to end, since I live in Texas.
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Twofish vs DES?
Date: Thu, 14 Jan 1999 13:46:24 GMT
On Sat, 9 Jan 1999 15:07:17 -0700, "TERACytE"
<[EMAIL PROTECTED]> wrote:
>Which is better? Twofish or DES?
Depends on how you define the term.
Trust: DES is far older and has been analyzed far more extensively.
It is much more trusted than Twofish.
Security: DES has a 56-bit key length; the best security it can
possibly offer is 2^56. Twofish has a key length up to 256 bits.
Even if it were horribly flawed, the odds of it being less secure than
2^56 are pretty slim. Twofish is more secure.
Advertised security: DES only offers 56-bit security, and it seems to
deliver. Twofish advertises 1238-, 192-, and 256-bit security. The
jury is still out as to whether it delivers.
Speed: Twofish is faster.
Gate Count: DES is smaller.
Name: DES has a "three letter acronym." Twofish has a cooler name.
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
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: AES and diffusion with 128-bit block length
Date: Thu, 14 Jan 1999 13:47:56 GMT
>What I will report soon in my paper
>that is being submitted, is how many rounds each algorithm takes to get
>substantial avalanche and diffusion. For example Frog takes 32 rounds and HPC
>takes 1 round to get avalanche that is near its final distribution. But then,
>those 2 algorithms have very different numbers of rounds to complete their
>algorithms. You will need to wait for the whole report, but for now you
>should know that there is a noticeable difference between the algorithms for
>how much excess avalanche is produced beyond the point at which a near-ideal
>result is acheived.
Good. I had been hoping that someone was doing an analysis like this.
If you wish, I would be interested in commenting on your methodology.
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
------------------------------
** 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
******************************
