Cryptography-Digest Digest #319, Volume #9 Thu, 1 Apr 99 14:13:02 EST
Contents:
Re: Live from the Second AES Conference (John Savard)
Re: Is initial permutation in DES necessary? (John Savard)
Re: Newbie intro: what modern crypto systems assume the enemy knows (sb5309)
Re: FSE information anyone? (Thirteen)
Re: blind signatures (Ian Goldberg)
Re: True Randomness & The Law Of Large Numbers (Jim Felling)
GPS, encrypted data base and mushroom hunting ([EMAIL PROTECTED])
FSE information anyone? (David Crick)
Re: True Randomness & The Law Of Large Numbers (Dave Knapp)
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Re: True Randomness & The Law Of Large Numbers ("Franzen")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Live from the Second AES Conference
Date: Thu, 01 Apr 1999 17:22:15 GMT
[EMAIL PROTECTED] (wtshaw) wrote, in part:
>Let me get the title right, not Paint Your Wagon, but, The Hallelujah Trail.
Oh, dear; then the AES wasn't born under a wandering star...
John Savard (teneerf is spelled backwards)
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Is initial permutation in DES necessary?
Date: Thu, 01 Apr 1999 17:19:50 GMT
[EMAIL PROTECTED] wrote, in part:
>So does this mean that the NSA now has a general attack against block
>ciphers (AES candidates) which makes cracking them within the NSAs
>budget?
Not necessarily. Circumstances have changed. Triple-DES already exists.
IDEA already exists. Blowfish already exists.
Hence, the AES process isn't *really* making the situation any worse, even
if the final standard is not crackable by the NSA. At least, as a big block
cipher, it will be too unwieldy for use in many applications, especially by
technically less-privileged countries.
If others wish to suggest it was all a plot to distract everyone while the
U.S. pressed for changes to the Wassenaar agreement, they are free to do
so. As for me, I don't find it odd that NIST may seek one thing even if the
NSA might seek the opposite. Remember: the research that led to RSA being
openly discovered was partly funded by the U. S. Navy.
Thus, it is enough to note that the U. S. Government is a very big
organism, the left and right hands of which could well not know what the
other one is doing: no overarching conspiracy need be hypothesized.
John Savard (teneerf is spelled backwards)
http://members.xoom.com/quadibloc/index.html
------------------------------
From: sb5309 <[EMAIL PROTECTED]>
Subject: Re: Newbie intro: what modern crypto systems assume the enemy knows
Date: Fri, 02 Apr 1999 00:49:13 +0800
Hew, quite a change in mood, rather refreshing though !! :-)
>Sundial Services wrote:
> Suddenly that "home-grown" cryptosystem of yours might not sound so good
> after all. You're probably better off using, or even licensing, a
> cryptosystem that has known characteristics and is known to be (a) good
> enough for your application; and (b) known to be correctly implemented.
>
> This is similar to the advice to "look at your home as a burglar
> would." You assess the attacks that you need to defend against
> (possibly enlisting the help of a professional in the field), you select
> a well-made lock from a known manufacturer, AND you use it dilligently
> and correctly... and for legal purposes. Suddenly your home, your data,
> your messages, become unlikely to be broken into. Your data is
> reasonably secure... AND you are not merely speculating about this; you
> actually know.
------------------------------
From: Thirteen <[EMAIL PROTECTED]>
Subject: Re: FSE information anyone?
Date: Thu, 01 Apr 1999 08:29:00 -1000
Thirteen wrote:
>
> David Crick wrote:
> >
> > Does anyone who attended FSE (right after AES2) intend to compile
> > a brief report on it? (like we had for the two days of AES2)
> >
> > For instance I know there was a very interesting paper on Crypton
> > presented.
> >
> > David.
>
> FSE-6 : A Brief Report
>
> by number 13
>
> The Fast Software Encryption conference in Rome last week
> A Challenge to Create a CONSTRUCTIVE Computational Goal
>
> RC6 with constant rotation amounts
>
> Scramble All, Encrypt Small: sharing work with a smart card
>
> Miss In the Middle Attack
>
> Slide Attacks
Simplified Variants of RC6
The RC6 algorithm normally uses data dependent rotations but
these weere changed to constant rotations to investigate the
affect from the variable rotations. The probabilities for some
differential characteristics were evaluated and an interesting
case arose. A table of the 4 words in a block is given showing
how a differential in A and B words are preserved as rounds are
executed through seven rounds, and it is cyclic, so after 7
rounds the differential is the same as at the start. Lemma 1 says
that if the case in that table occurs, then certain subkey
conditions hold. But the real RC6 fixes that problem.
The diffusive properties of the quadratic function also were shown
to be useful compared to a variant lacking it. A table of probablities
for the variants shows that after 4 rounds the RC6 looks like random
noise, but weakened versions need 8 or more rounds to achieve that.
> To be continued...13
------------------------------
From: [EMAIL PROTECTED] (Ian Goldberg)
Subject: Re: blind signatures
Date: 1 Apr 1999 17:36:56 GMT
In article <01be7c5b$8e518d50$89097283@cirano>,
Gianluca Dini <[EMAIL PROTECTED]> wrote:
>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?
Yes.
>If the answer is yes, how difficult is this problem?
Totally trivial. Pick _any_ value for B1. Calculate
R1 = t * (B1^e)^(-1) (mod n).
>furthermore, is there any countermeasure?
Countermeasure? What for? This is the whole _point_ of a blinded signature:
the person doing the signature sees only t, not R and B. The idea is that
it's impossible for him to figure out what R was, since _any_ value of R
could have been used (note that I only showed above that any value of B
could have been used; the other statement is left as an exercise for the
reader). Further, if B is chosen uniformly at random from Zn*, then
the distribution of R given t is the _same_ as the distribution for R;
i.e. knowledge of t gives exactly zero help (in the information-theoretic
sense, not just computationally) in figuring out what R was.
- Ian
------------------------------
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Thu, 01 Apr 1999 09:58:42 -0600
"R. Knauer" wrote:
> On 31 Mar 1999 21:22:47 GMT, [EMAIL PROTECTED] (Bryan G. Olson; CMSC (G))
> wrote:
>
> >: 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.
>
> Yes, that is indeed correct. The Gaussian falls off very slowly. But
> not so slowly that the perfume odor stays next to the bottle forever.
>
> >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.
>
> Yes, that is correct. n units measures the farthest extent of the
> random walk.
>
> >As others have pointed out, the two dimensional case yields
> >a binomial distribution, so the standard deviation is
> >sqrt(npq).
>
> The one dimensional case also yields a binomial distribution, because
> a UBP yields the binomial distribution.
>
> >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.
>
> But more than a negligible number of particles will be outside +- 5%
> of the mean
The mean is 500000 5% of that is 25000, so within 5% of the mean is
equivalent to between 475000 and 525000. The SD is 500
5% of the mean is equal to SD * 50 so anything outside of that interval is
more than 50 SD's off the mean.
In the ensemble view. A TRNG randomly 'picks' a sequence out of the pool of
all possible sequences. The odds of it picking such a biased sequence is so
vanishingly small that it would be much more likely that the device is bad
than that the sequence was legitimately produced by a working TRNG.( not
impossible, but vanishingly tiny odds)
>
>
>
> >: 10,000 units is only 1% of 1,000,000 units, so the probability is very
> >: small.
>
> >You've misinterpreted the numbers.
>
> How?
>
> >: 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.
>
> I do not recall ever confusing frequency for a finite process with
> probability.
>
> >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.
>
> Are you saying that a run of 100 zeros conclusively demonstrates that
> a TRNG is malfunctioning? How about a run of 100 zeros in a sequence
> of 10^9 bits?
>
I'd probably still kick it out. The odds of a TRNG picking such a sequence
'by chance' is roughly than 10^9 / 2^100 < 10^-27. It can happen, but I'll
still bet against it.
>
> And how do you account for the fact that in a large uniform random
> walk in one dimension, most of the paths rarely end at or near the
> origin?
Many do not. Most do.( it all depends on what is meant by 'near' I suppose)
>
>
> >Look at your 100 zeros out of 100 bits.
>
> I do not recall using that exact expression. But never mind.
>
> >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.
>
> Can you elaborate on each key point in that analysis by giving
> specifics of how you go from the beginning assumptions to the final
> conclusion.
>
> 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]
Subject: GPS, encrypted data base and mushroom hunting
Date: Thu, 01 Apr 1999 17:44:02 GMT
>From Guiding Troops to Picking Wild Mushrooms.
A surprising new application of GPS technology.
By Sergei Burkov.
>From aiming intercontinental ballistic missiles to picking wild
mushrooms -- such is the evolution path of one once classified defense
technology. A group of Silicon Valley geeks is combining their love of
high tech with their other passion -- hunting wild mushrooms in the pine
groves of Northern California. A group of enthusiast within San
Francisco Mycological Society is going to employ GPS (Global
Positioning System) technology to increase precision of determining
the location of wild mushrooms in the forests.
Until recently, mushroom hunting was virtually unknown in the U.S. In
other part of the world, including Italy, France, and China, it’s
extremely popular. In Russia, it’s a national pass-time, compared in
popularity only to playing ice hockey and drinking vodka. In fact, it were
Russians who first began using GPS technology for hunting
mushrooms in the thick forest surrounding Moscow. Now, Russian
programmers working in Silicon Valley are importing the technology
and share it with their new American colleagues.
Every experienced mushroom hunter knows that the mushrooms grow
in the same place year after year. This is because the mushrooms are
seasonal growths on vast underground structures, called mycelium. If
a picker finds a group of mushrooms one year there are very good
chances that there will be good bounty at the same location the next
year, and year after. Being able to locate the place year later greatly
improves the productivity of the hunter. In Russia, many babushkas
have their secret spots they revisit for decades. They pick lots of
premium mushrooms, to the envy of younger folks who are wandering
in the forest at random, returning home with empty baskets.
It is not easy to find one specific pine tree among thousands or virtually
identical ones in a thick forest. All trees look alike. And it’s harder to
navigate as you step off the trail with its signs and trail blazes. Old
ladies rely on their instincts. Impatient young geeks rely on cutting
edge technology.
With right technology, it works like 1-2-3. Find a good mushroom
(better a bunch of). Determine your position with a GPS device
connected to a Palm Pilot. Enter the coordinates into a database. Go
find next mushroom. Continue. Next year, load the map marked with
last year’s spots into your Pilot, or directly into the GPS device, and go
straight to the best secret spot. To the babushkas envy, the device will
help you find the very same tree you visited a year ago, in minutes.
High tech gives the techno-savvy even sharper edge over the
babushkas. Before the forage, in the comfort of your room, you
examine the map and determine the optimal path. You do not want to
wander too much back and forth, you want to visit your secret spots as
fast as possible.
Here is where the geeks have an edge. The problem of visiting a set of
given spots in minimal time is the well known travelling salesman
problem. It has been studied by thousands of computer scientists,
economists and mathematicians. It is almost as famous as recently
proven Fermat’s last theorem. The exact solution of the travelling
salesman problem is still not found, and many mathematicians believe
will never be, but there are thousands of approximate solutions that
give the paths that are only few percentage points longer than the
minimal ones. For all practical purposes, a good approximate solution
is as good as the absolutely minimal one.
With all this in mind, Alexander Shen and Fedor Sherstyuk, two
Russian outdoor enthusiasts, avid mushroom pickers and GPS buffs
have developed a software product, called Gribnik (Russian for
"mushroom hunter"). The program maintains a data base of the
promising spots and calculates the optimal path in seconds. The
results are superimposed on a local map and downloaded into a Pilot
or directly into a GPS device. The shareware program became so
popular in Moscow that the friends are now working on a commercial
version. An English language version of Gribnik will be available in the
fall of 1999, in time for the season.
The standard accuracy of a typical GPS is about 50 m (150 ft), which is
helpful but does not allow one to pinpoint the mushroom. A differential
GPS which relies on a fixed ground station along with the usual three
satellites could render the 10 cm (4') accuracy. This leads the hunter
straight to the mushroom. To take advantage of such an
unprecedented accuracy the friends climb a toll tree in the middle of
the forest and put a ground station there. Then they decent and search
the surrounding forest.
Unfortunately, even 10 cm precision does not guarantee the
mushroom is there. Even if the timing is right and the mushrooms grow
well there is a chance that somebody has already picked them up.
Knowing this fact in advance will be beneficial to the picker. He would
merely skip the spot and go straight to the next one. Gribnik Pro, a
soupped up version of the program, offers a solution even to this
problem. When one member of a group of hunters picks a mushroom,
or finds that the spot has been cleared by a low tech babushka, he
marks the spot on the map and shares his knowledge with the others.
The sharing has a drawback. If a persons posts the coordinates of the
spot he has just cleared all others become aware of the spot. A good
hunter keeps best spots secret. Messrs. Shen and Sherstyuk founded
a web site where the
users of Gribnik Pro could post the coordinates of their spots in an
encrypted form. (To be more precise, a so-called one-way hash
function of the coordinates is posted on the web.) This way, the
competitors cannot read the coordinates off the web. However, if two
people know about one spot, the program would compare the hash
function values of the coordinates from the data bases of the two
hunters. This allows one hunter to post a note that the spot has been
visited without revealing the coordinates of the spot. Those who also
happen to be aware of the same spot will be able to understand the
message. Others, who have not been to the spot will remain unaware
of it. This yet another example of how, with little help from modern
cryptography, one can eat a cake and still have it. The cryptographic
part of Gribnik was contributed by Roman Avdanin of Invincible Data
Systems, Inc. (http://www.incrypt.com)
What lies ahead? At a press conference on the 1st of April in Moscow
Alexander Shen, Professor at Moscow Center of Continued
Mathematical Education (http://www.mccme.ru), revealed his plans: "We are
going to port the entire Gribnik, including the travelling salesman part,
to Palm Pilot and Windows CE platforms and link it to a cell phone.
This will allow a group of pickers to exchange data about spots in real
time. When a spot is taken the program will remove it from the to-visit
list and recalculate a new optimal path, on the fly. You will receive a
brief phone call and your Palm Pilot will tell you to skip the birch 13 and
proceed straight to the pine 21, across Pereplyujka river, 50 m south
west of an abandoned tiny wooden church and log home, where at
time of Ivan the Terrible a single hermit might have lived and picked his
mushrooms from the same spot."
Sergei Burkov, Ph.D.,
INVINCIBLE DATA SYSTEMS, INC.
Military grade encryption for Internet security.
1290 Oakmead Parkway, #118 phone: (408) 522-4980
Sunnyvale, CA 94086 fax: (408) 736-6083
http://www.incrypt.com e-mail: [EMAIL PROTECTED]
Public keys posted at http://www.incrypt.com/idspubk.html
PGP fingerprint: 5E 7C A8 D5 45 2E 18 D3 29 04 40 12 15 53 8E 2B
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
Date: Wed, 31 Mar 1999 19:34:57 +0000
From: David Crick <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: FSE information anyone?
Does anyone who attended FSE (right after AES2) intend to compile
a brief report on it? (like we had for the two days of AES2)
For instance I know there was a very interesting paper on Crypton
presented.
David.
--
+---------------------------------------------------------------------+
| David Crick [EMAIL PROTECTED] http://members.tripod.com/~vidcad/ |
| Damon Hill WC '96 Tribute: http://www.geocities.com/MotorCity/4236/ |
| Brundle Quotes Page: http://members.tripod.com/~vidcad/martin_b.htm |
| PGP Public Key: (RSA) 0x22D5C7A9 00252D3E4FDECAB3 F9842264F64303EC |
+---------------------------------------------------------------------+
------------------------------
From: Dave Knapp <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Thu, 01 Apr 1999 18:14:47 GMT
"R. Knauer" wrote:
>
> On Thu, 01 Apr 1999 02:57:14 GMT, Dave Knapp <[EMAIL PROTECTED]> wrote:
>
> >Thus, the repeated measurement of
> >the position of a particle undergoing a random walk has a very different
> >statistical distribution than would measurements of independent
> >particles undergoing the walk.
>
> That is the same as saying that the time average of one particle has
> nothing to do with the ensemble average of all particles.
No, it's saying that the time average of a single particle has different
properties than the ensemble average, which, by the way, is the point.
Aw, forget it. I have better things to do than attempt to educate
someone who refuses to educate themselves.
One more time, with feeling:
Please try to learn _something_ about statistics before criticizing it.
-- Dave
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Thu, 01 Apr 1999 18:44:46 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 01 Apr 1999 18:14:47 GMT, Dave Knapp <[EMAIL PROTECTED]> wrote:
>> That is the same as saying that the time average of one particle has
>> nothing to do with the ensemble average of all particles.
>No, it's saying that the time average of a single particle has different
>properties than the ensemble average, which, by the way, is the point.
Duh, I thought that is just what I said.
Perhaps you are objecting to the term "nothing to do with", which is
admittedly a but strong. OK, I will accept the fact that they are
somehow related, and change the statement to "has little to do with".
But for the record I will once again quote Feller directly:
+++++
"Thus, contrary to widespread belief, the time average for any
individual game has nothing to do with the ensemble average at any
given moment."
+++++
Notice that he uses the strong term "nothing to do with".
>Aw, forget it. I have better things to do than attempt to educate
>someone who refuses to educate themselves.
Aw, does that mean we won't be seeing you anymore on these posts?
Make sure you fully appreciate that I will shed no tears at your
demise.
>One more time, with feeling:
>Please try to learn _something_ about statistics before criticizing it.
Interestingly I have advised you to learn something about probability
theory, and you defiantly refuse to do so.
At least I am willing to study Trivola's book. I am certain that you
will never consult Li & Vitanyi or Feller in your entire lifetime. You
are afraid they will shake up your false notions on pseudorandomness
and its inadequacy in characterizing true randomness.
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: "Franzen" <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Thu, 1 Apr 1999 12:46:36 -0600
Bob Knauer <[EMAIL PROTECTED]> wrote approximately the following
Wed, Mar 31, 1999 at 2:06 PM. I edited and formatted his actual
writing for my clarity. I am responsible for any possible meaning
changes.
>I believe that statistical tests cannot be used to determine either
>TRNG randomness or non-randomness. The best the tests can be used
>for is diagnostic warning.
As I understand the hypothetical TRNG concept, it cannot generate
non-randomness. Since it is hypothetical, it cannot suffer process
failure either.
>The reason is that statistical tests are based on the notion of
>"pseudorandomness". A TRNG is based on the notion of "true randomness".
Chi-square is not a measurement which is limited to only measuring
pseudo-randomness; at least not in any literature I am aware of. I
understand it to be a yardstick which will yield differing results to
me when measuring fundamentally differing processes.
If a particular PRNG produces a sequence which is characteristically
different from a TRNG sequence, complete Chi-square test results will
differ also. The alternative is the incomplete Gamma function is an
invalid measurement concept.
>If you could use statistical tests to decide that a keystream was
>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 cannot generate true
>random sequences
With the present dearth of knowledge about uniform randomness, who can
say that a particular subset sequence from a PRNG which turns out to be
indistinguishable from an equal length TRNG subset is any less
uniformly random. Does uniform randomness have to have a pedigree to go
with its other inate characteristics?
>(although some can get mighty close to it).
First you state statistical tests cannot distinguish uniform randomness
from pseudo-randomness (first paragraph above). Now you parenthetically
state some PRNG's can generate "close to" uniformly random sequences.
How can you possibly know? Not only would you have to be able to
distinguish between the two randomness potentials, but you would also
have to have a way to measure them with some degree(s) of precision.
======
Douglas McLean
------------------------------
** 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
******************************
