Cryptography-Digest Digest #315, Volume #9 Wed, 31 Mar 99 18:13:03 EST
Contents:
Re: "Biprime Cryptography" to replace RSA? (John Savard)
Re: Live from the Second AES Conference (wtshaw)
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Re: True Randomness & The Law Of Large Numbers (Bryan G. Olson; CMSC (G))
Re: Is initial permutation in DES necessary? (Paul Koning)
Re: Tripple DES key length. (Paul Koning)
Re: What is fast enough? (Paul Koning)
Re: Alert: "HAPPY99.EXE" e-mail/newsgroup virus (Markku Nevalainen)
Re: North Korean A3 code (Jim Dunnett)
Re: Random Walk (R. Knauer)
Re: Alert: "HAPPY99.EXE" e-mail/newsgroup virus ("Arvin Meyer")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: "Biprime Cryptography" to replace RSA?
Date: Wed, 31 Mar 1999 19:18:58 GMT
Jim Gillogly <[EMAIL PROTECTED]> wrote, in part:
>Since printed books aren't going to change easily, changing the
>ubiquitous common name of the algorithm would only lead to confusion.
All they want is for people (other than themselves) attempting to sell
implementations of the algorithm to be victims of confusion -
and it is more likely to be effective, than, say, lobbying for an amendment
to the patent law so that patents last for, say, 100 years from filing
instead of 20.
John Savard (teneerf is spelled backwards)
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Live from the Second AES Conference
Date: Wed, 31 Mar 1999 13:44:10 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
>
> I'm very glad the AES process is taking place, but I admit that if one
> looks really hard at it, there are reasons to fear that it hasn't just gone
> off track, but it was never on a track to begin with. It's much too late, I
> fear, to remedy this: it has produced a major advance in the state of the
> art, and this surely counts for more than any problems we may have with its
> ability to produce a good *direct* result.
>
In allusion to Paint Your Wagon, some the various forces have been moving
in a somewhat parallel direction in order to keep an eye on each other.
The climax of the process is apt to be as well organized as was in the
film, with the most important results tending to be lost in the mud for a
time, but available for those that know how to use patience.
--
Too much of a good thing can be much worse than none.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Wed, 31 Mar 1999 20:06:15 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 31 Mar 1999 20:27:21 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>I believe THE problem is the impossiblity of obtaining an algorithm
>(method) to determine a measure (quantity) of deviation of a given
>'real TRNG' from the 'idealized TRNG', if you do not accept
>the applicability of statistical tests
I fully agree.
The only way you can have any reasonable confidence in the performance
of a "real TRNG" is to audit the design carefully and run diagnostics
on each subsystem using methods that define its performance. And that
includes the quantum mechanical source of true randomness, like
radioactive decay. Even though statistical tests cannot be used on the
output, you can run definitive tests on the quantum system to make
sure it is performing properly. That's because you are not trying to
infer randomness from those tests.
IOW, those tests are confirming that the quantum system is passing the
randomness thru properly. That's especially troublesome for detecting
radioactive events because of deadtime errors. You want to run tests
to make sure that deadtime is not a problem. But that does not mean
you are testing the quantum system for randomness. You are relying on
the fact that the quantum system is truly random based on quantum
mechanics.
There is one exception to that is the Mossbauer spectrum of a truly
randomly decaying isotope. It's shape is Lorentzian if the decay
process is truly random. IOW, you can use the lineshape to demonstrate
the truly random nature of that particular isotope's decay process.
Truly random radioactive decay is the result of spontaneous emission
which is governed by second order perturbation theory in quantum
mechanics. That is where the true randomness comes from and that is
where the Lorentzian lineshape comes from. They are intimately related
to one another in quantum perturbation theory.
The Fourier transform of a Lorentzian is a simple exponential, which
is also the result of a truly random process in that it comes from a
first order rate equation with a constant probability per unit time -
which makes the time of decay independent and equidistributed, two
properties of a TRNG.
>(which as far as I understand
>is one of your positions concerning random number generations).
I do not believe that statistical tests can be used either to
determine the randomness or non-randomness of a TRNG. The best they
can be used for is a diagnostic warning. The reason is that
statistical tests are based on the notion of "pseudorandomness", where
a TRNG is based on the notion of "true randomness".
If you could use statistical tests to decide that a keystream were
random, then they could be used to filter sequences from a PRNG and
pass them along as truly random sequences. But we know that is not
correct, since PRNGs can't generate true random sequences (although
some can get mighty close to it).
Bob Knauer
"The laws in this city are clearly racist. All laws are racist.
The law of gravity is racist."
- Marion Barry, Mayor of Washington DC
------------------------------
From: [EMAIL PROTECTED] (Bryan G. Olson; CMSC (G))
Subject: Re: True Randomness & The Law Of Large Numbers
Date: 31 Mar 1999 21:22:47 GMT
R. Knauer ([EMAIL PROTECTED]) wrote:
: On 31 Mar 1999 02:16:01 GMT, [EMAIL PROTECTED] (Bryan G. Olson; CMSC (G))
: wrote:
: >Not so. As n grows large, a greater and greater fraction of
: >the ink molecules will be within 0.05*n of where they started.
: That defies physical intuition, as well as the rules for mixing
: entropy. Everyone knows that if I open a perfume bottle in the middle
: of the room, the odor will spread all over the room with time.
But by that time n units is far beyond the walls of the room.
: >Have you done that experiment?
: Actually, now that you asked - yes, I have done that experiment. I
: have done diffusion experiments in a scientific laboratory when I
: studied diffusion in dilute alloys.
So you know the velocity of particles of given mass at given
temperature. This velocity times time determines how far n
units really is. Compare that to how far your ink or perfume
has spread.
: But you do not need to be a scientist to conduct such an experiment -
: just open a perfume bottle in the middle of the room and check back
: later in different places in the room which are distant from the
: bottle.
Again, you've forgotten what n units means. It's how far a particle
would have traveled if every step were leftward or every step
rightward. It has nothing to do with where drywall is hung.
: >You could try simulating it
: >with a PRNG. Generate bits, and send a particle left for
: >each zero and right for each 1. After a million bits, what
: >do you think the chance is that the particle will be farther
: >than 10,000 units from the starting point?
: Feller (op. cit.) does these very calculations, but not using any
: PRNG. The probability for large n is a Gaussian, and it spreads out in
: time - like SQRT(n) / n = 1/SQRT(n). As n increases, 1/SQRT(n) gets
: smaller.
As others have pointed out, the two dimensional case yields
a binomial distribution, so the standard deviation is
sqrt(npq). Here n=1000000 p=q=0.5, so the standard deviation is
500 units. Very few particles will be 20 standard deviations
or more from the mean.
: 10,000 units is only 1% of 1,000,000 units, so the probability is very
: small.
You've misinterpreted the numbers.
: >Only a small fraction? I expect the vast majority to be within
: >10000 of the center.
: You are wrong. Just think about the diffusion experiment above. The
: perfume odor will spread throughout the room with time.
But nowhere near 0.05 n units, which is the issue.
: >The bias
: >is in the probability of generating a 1 vs a 0 bit. The number
: >of 1 and zero bits actually generated is the frequency.
: Yes. I know that. But others here are attempting to equate the
: frequency with the probability for finite sequences. Therein lies the
: error.
The only one I saw doing that was you.
: You cannot infer the non-randomness of a TRNG from a restricted sample
: of sequences, especially when all you do is measure the 1-bit bias of
: those few sequences.
You don't measure bias, you measure frequency. And if what
you find looking at 100 bits is 100 zeros, we can safely
reject the candidate RNG based on that test alone.
: There is a seemingly unendless stream of people on sci.crypt who claim
: that statistical testing is a valid way to determine the
: non-randomness of a RNG.
Hmm, you lost me with "unendless".
: I am the one (but not the only one) who has maintained that
: statistical tests are not valid in determining the non-randomness of a
: RNG. I am the one (but not the only one) who has maintained that the
: best one can hope for is to use statistical tests as a diagnostic
: warning.
Look at your 100 zeros out of 100 bits. If we make any
reasonable estimate of the probability our candidate RNG is
defective in such a way as to produce this outcome, say one in
a trillion, then Bayes' theorem tells us there's no significant
chance the RNG is in fact unbiased.
--Bryan
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Is initial permutation in DES necessary?
Date: Mon, 29 Mar 1999 10:32:39 -0500
Christoph Haenle wrote:
> The permutation is not done for security reasons. Rather, it is
> supposed to make DES implementation slower in software.
I've seen the claim that it's supposed to make the hardware
implementation more efficient. That claim has never been
accompanied by any specifics and I don't believe it for
a moment.
> However, when
> using 3DES, it could make a difference (in security) whether EDE or
> EEE is used, even when using three different keys (when using EDE, the
> permutations between E and D and between D and E won't disappear as
> opposed to the EEE scheme).
Not true. It goes away either way.
> As far as I know, nobody has ever proven
> whether of not the permutations strenghens 3DES.
Not so; it's entirely obvious that it does nothing useful
at all. Explaining why would be a good easy homework
problem for Cryptography 101.
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Tripple DES key length.
Date: Fri, 26 Mar 1999 14:02:45 -0500
OlafP wrote:
>
> Hi everyone,
>
> I've been looking through various websites and FAQ about DES encryption.
> Unfortunately, still something isn't quite clear to me regarding tripple-DES
> encryption. I know there are various modes, but what is considered to be
> (legally) the keylength when using tripple DES ? Is it considered as a
> specific key, tripple-DES-56 or is it considered as a 168 bit keylength ?
112 (2 x 56) if using 2-key mode, 168 (3 x 56) in 3-key mode.
Unless you're using manual keying and can't cope with the
notion of typing more bits, there's no sense in using 2-key
mode. IPSEC uses 3-key mode exclusively for that reason.
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: What is fast enough?
Date: Wed, 31 Mar 1999 15:52:40 -0500
Bruce Schneier wrote:
>
> On Wed, 31 Mar 1999 04:53:18 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
> wrote:
>
> >Bruce Schneier wrote:
> >> First off, don't calculate speed in MB/sec, count it in clock cycles
> >> per byte encrypted.
> >
> >All these implementation-specific measures are suspect.
> >For example, algorithm A might be able to exploit massive
> >parallelism, or a DSP, while algorithm B might not gain
> >any advantage from such architectures. Yet if alg. B is
> >somewhat faster than alg. A on a single-thread Pentium,
> >the rules seem to make it "preferred".
>
> Algorithms that stick to operations from the RISC instruction set tend
> to have similar performance across various CPUs. Algorithms that use
> complex instructions--multiplications, data-dependent rotates--are
> pretty much at the mercy of the CPU for performance.
I think you're making an unwarranted simplification.
There was a paper some time ago (forgot the details) that discussed
how various cypher designs fare in highly pipelined processors.
RC4, for example, has a lot of data dependency stalls; other
cyphers that superficially seem slower allow for a higher degree
of pipelining. You might not notice that on a Pentium, but if you
use high end Alphas that have several integer functional units, it
becomes an issue.
Similarly, not every chip has one cycle load/store even with cache
hits, and analyses that assume one cycle loads may be misleading.
Earlier in this thread there was a note about Merced performance
for various cyphers. One of them did quite poorly. That may
very well be related to the points I mentioned.
paul
--
!-----------------------------------------------------------------------
! Paul Koning, NI1D, D-20853
! Xedia Corporation, 119 Russell Street, Littleton, MA 01460, USA
! phone: +1 978 952 6000 ext 115, fax: +1 978 952 6090
! email: [EMAIL PROTECTED]
! Pgp: 27 81 A9 73 A6 0B B3 BE 18 A3 BF DD 1A 59 51 75
!-----------------------------------------------------------------------
! "Among the many misdeeds of the British rule in India, history
! will look upon the Act depriving a whole nation of Arms, as
! the blackest" --- Mahatma Gandhi
------------------------------
From: Markku Nevalainen <[EMAIL PROTECTED]>
Crossposted-To:
comp.lang.pascal.delphi.misc,comp.databases.paradox,comp.databases.ms-access
Subject: Re: Alert: "HAPPY99.EXE" e-mail/newsgroup virus
Date: Thu, 01 Apr 1999 00:52:22 +0200
Reply-To: [EMAIL PROTECTED]
Sundial Services wrote:
>
> There is a Win32 program circulating around the Net which contains a
> virus that will attach itself to every e-mail message and newsgroup post
> you happen to make. Or it will send a message shortly afterward. Tidy
> thing... it even keeps a log of its activities!
>
Isn't this a slightly outdated info? It's more than month ago when
Happy99 came in. And in the age of 30 days these new super viruses
are already worn with years.
The hottest new virus from last thursday/friday is Melissa (Word
macrovirus) and Papa (Excel macrovirus).
I heard that FBI has promised $350.000 to anyone who will point
out the writer of Melissa virus.
Markku Nevalainen
------------------------------
From: [EMAIL PROTECTED] (Jim Dunnett)
Subject: Re: North Korean A3 code
Date: Wed, 31 Mar 1999 20:05:55 GMT
Reply-To: Jim Dunnett
On Wed, 31 Mar 1999 13:08:58 +0900, Eric Hildum
<[EMAIL PROTECTED]> wrote:
>In today's Japan Times, there was a discussion of a 1978 kidnapping of a
>Japanese woman from Japan by North Korea [this is one of about a dozen suspected
>cases over the last twentyfive years]. The article discussed a North Korean code
>called "A3," described as a five digit number for each hangul (?) character.
>Given the recent discussion on this newsgroup, it would seem to me that such a
>code system would be relatively easy to break -- are there any references on the
>internet to this system? I assume that as so much is known about this code that
>it has in fact been broken....
The Chinese also have a system which codes a subset of the
ideograms of Mandarin into 5-figure (letter?) groups.
It's hardly a cipher, merely a means of telegraphing ideograms!
Perhaps the Korean system you refer to is no more than that.
--
Regards, Jim. | Da mihi castitatem et continentiam,
olympus%jimdee.prestel.co.uk | sed noli modo.
dynastic%cwcom.net |
nordland%aol.com | - St. Augustine, 354 - 430
marula%zdnetmail.com | (in Confessions, Book 8 Chap 7)
Pgp key: pgpkeys.mit.edu:11371
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Wed, 31 Mar 1999 22:34:55 GMT
Reply-To: [EMAIL PROTECTED]
On 31 Mar 1999 15:34:19 -0500, [EMAIL PROTECTED] (Herman
Rubin) wrote:
>The UBP, and related highly specific processes, only exist as
>theoretical abstractions. All that can be hoped for is a
>sufficiently close approximation. The laws of nature are not
>what we write down.
Are you implying that ideal models are worthless - that the ideal
model of the circle is not useful?
>The statistical properties are what they are. In using tests,
>do not jump to conclusions about what they are.
The only statistical measure of randomness that has been stated here
in the many debates we have had over two periods lasting a total of a
year is bit bias. There has been talk of correlation tests, but most
of the emphasis has been on determining 1-bit bias, since it is so
easy to do - just count bits and see if there is an excess of one over
the other.
So I focused my attention on learning about how bit bias could be used
to determine that a process was not truly random. In my search I came
across Li & Vitanyi's many comments about how bit bias can deviate
considerably for seemingly random processes like the UBP. Then I came
across Kolmogorov's warnings about the misapplication of statistical
measures such as bit bias for random processes. The authors referenced
Feller innumerable times, so I got his book and read all the sections
relating to true randomness. I also read a book on quantum computing
that has a whole chapter on true randomness and how to generate it
with a quantum computer. All these people have made the same claim,
each in their own way, namely that statistical tests cannot decide on
either true randomness or non-true-randomness. The best they can do is
indicate something called "pseudorandomness".
I hardly consider that "jumping to conclusions".
>Intuition can be quite dangerous.
Yeah, like the intuition that time averages are the same as ensemble
averages. Or the naive intuition that pseudorandomness is the same as
true randomness. Or how about the many instances where the law of
large numbers is misapplied. How about the so-called "law of averages"
which (falsely) indicates that the lead in a coin-tossing game should
change sides many times.
When confronted with direct evidence to the contrary people try to
avoid the result that their intuition was wrong. For example, Feller
found that most statiticians he surveyed were surprised that a random
walk of 10,000 steps only crossed the origin 8 times. Statiticians had
expected the path to cross the origin many more times than just 8.
Yep, I know fully well that intuition can be a dangerous thing. Try
convincing someone that a bullet drops just the same whether it is
spinning or not. It is literally impossible, because some people are
100% convinced that the spin of the bullet causes it to stay on a
flatter trajectory because a spinning gyroscope doesn't fall down.
True randomness is at the very essence of quantum mechanics, which
itself is very counter-intuitive. I can easily understand why so many
people have a false intuition about true randomness.
>To someone who works in probability, this idealization is extremely
>well known. Mathematics does not deal with idealizations of the
>real world, but with abstractions; its utility is the extent to
>which real world entities behave like the abstractions.
Would you put that in such a way that an Informed Layman (tm) can
understand it. I have absolutely no clue what you just said.
Bob Knauer
"The laws in this city are clearly racist. All laws are racist.
The law of gravity is racist."
- Marion Barry, Mayor of Washington DC
------------------------------
From: "Arvin Meyer" <[EMAIL PROTECTED]>
Crossposted-To:
comp.lang.pascal.delphi.misc,comp.databases.paradox,comp.databases.ms-access
Subject: Re: Alert: "HAPPY99.EXE" e-mail/newsgroup virus
Date: Wed, 31 Mar 1999 17:08:24 -0500
I don't know about the $350K, but I can tell you that both MS and Intel were
bit hard by Melissa last weekend. As a precaution I suggest you read the
following from Woody Leonhard's Windows Office Watch:
~~~~~~~~~Begin Post~~~~~~~~~~~~
THE NOT SO LOVELY MELISSA VIRUS ~~~~~~~~~~~~~~~~~~~~~~~
The bombshell for Friday afternoon (US time) was a new Word
97 and Word 2000 (currently being widely tested) virus that
uses Microsoft Outlook (not Outlook Express) to send itself
out to lots of people very fast and right under your nose.
As a result it's spread like wildfire in company email
systems and across the Internet - causing havoc in places
you would not expect like Microsoft and Intel among many.
See
http://chkpt.zdnet.com/chkpt/hud0007500a/www.zdnet.com/zdnn/stories/news/0,4
586,2233030,00.html
for Fridays report.
The virus is called 'Melissa' or more properly
W97M/Melissa.A (there's no official name and you'll also
see it called W97M_Melissa or W97M.Mailissa.A ) after the
name of class module that contains the macro virus. The
module is set to run each time an infected document is
opened and sometimes when closed too.
As usual there has been a lot of panicked and ill informed
reports about what this virus does so we've worked over the
weekend to see what it really does, how you can protect
yourself and what to do if you've already been infected by
the Melissa virus. We'll also squash some of the rumors
and misunderstandings that are out there.
THE MAIN WARNING - PLEASE READ THIS ~~~~~~~~~~~~~~~~~~~
First the main and important warning in brief ...
If you receive a message from ANYONE at all - it doesn't
matter who it might be:
* with the subject line 'Important Message from <name of sender>'
* and an Word document attached (of any name but probably LIST.DOC)
Then DELETE THE MESSAGE, do NOT open the Word document.
This simple advice will remove the virus infected document
and stop it spreading. If everyone would follow that
advice the Melissa virus will be stopped dead in its
tracks.
~~~~~~~~~~~End Post~~~~~~~~~~~~~
=====
Arvin Meyer
[EMAIL PROTECTED]
Markku Nevalainen wrote in message <[EMAIL PROTECTED]>...
>Sundial Services wrote:
>>
>> There is a Win32 program circulating around the Net which contains a
>> virus that will attach itself to every e-mail message and newsgroup post
>> you happen to make. Or it will send a message shortly afterward. Tidy
>> thing... it even keeps a log of its activities!
>>
>
>Isn't this a slightly outdated info? It's more than month ago when
>Happy99 came in. And in the age of 30 days these new super viruses
>are already worn with years.
>
>The hottest new virus from last thursday/friday is Melissa (Word
>macrovirus) and Papa (Excel macrovirus).
>
>I heard that FBI has promised $350.000 to anyone who will point
>out the writer of Melissa virus.
>
>Markku Nevalainen
------------------------------
** 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
******************************
