Cryptography-Digest Digest #129, Volume #9 Wed, 24 Feb 99 04:13:04 EST
Contents:
Re: Unicity of English, was Re: New high-security 56-bit DES: Less-DES
([EMAIL PROTECTED])
Re: Define Randomness (Anthony Stephen Szopa)
Re: Where to publish hashes? (wtshaw)
Re: Another extension to CipherSaber (wtshaw)
A Tale of Two Bases (wtshaw)
Re: Randomness of coin flips (Michael Sierchio)
Re: Pentium III Hardware Random Numbers (Terry Ritter)
Re: New high-security 56-bit DES: Less-DES (Bryan Olson)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Unicity of English, was Re: New high-security 56-bit DES: Less-DES
Date: Wed, 24 Feb 1999 02:38:05 GMT
In article <[EMAIL PROTECTED]>,
Bryan Olson <[EMAIL PROTECTED]> wrote:
> With no key there is no equivocation.
"Equivocation" (better, conditional entropy) applies not only to the key but
also to the message -- two different and quite independent concepts, which of
course do not have to be zero at the same length of received text (otherwise,
they would be dependent in that sense).
This has been one of your continuing equivocations on this matter ;-).. but,
you need not only to qualify "equivocation" above. You must also change the
wording from "no key" to "one key of unity probability" -- your phrase is
thus wrong in two counts. The correct phrase would be:
"With one key of unity probablity the conditional key entropy is zero."
So, you again seem not to know what you are talking about... since that
phrase of yours is far too short to contain two technical mistakes. And yet
you keep making assertions upon assertions, "examples" as that one for DES
which was simply misleading, and repeating quotations from good ol'
Shannon...however, out of context as I show above and next.
But, as I said in my very first reply, I find such "hollier than thou"
attitudes of yours quite amusing. So, I will continue to help lint this
message of yours. Perhaps, will help you in future messages. Lint count so
far: 2.
> This is the
> "degenerate type of secrecy system" described by Shannon at the
> bottom of page 663.
As I quoted, yes. As you quoted, no. Lint count so far: 3.
>Since there is only one key,
Good! Now, you change from "no key" to "only one key" ...
>we can uniquely determine it
You can uniquely determine *nothing* ...since that key is already known. You
are beating a dead horse. That key entropy is zero by hypothesis. Lint count
so far: 4.
> without intercepting any ciphertext, yielding a unicity
> distance of zero.
Non sequitur. Without intercepting any character, the message's conditional
entropy is not zero. Lint count so far: 5.
Oh, but why, you may ask. Well, I would suggest you simply write down the
formula!!! As often said, surprise and information are synonymous ;-)
Cheers,
Ed Gerck
______________________________________________________________________
Dr.rer.nat. E. Gerck [EMAIL PROTECTED]
http://novaware.cps.softex.br
--- Meta-Certificate Group member -- http://www.mcg.org.br ---
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Subject: Re: Define Randomness
Date: Tue, 23 Feb 1999 20:40:53 -0800
Reply-To: [EMAIL PROTECTED]
"Trevor Jackson, III" wrote:
> Anthony Stephen Szopa wrote:
>
> > Define Randomness
> >
>
> [big snip]
>
> > So the argument is twofold: first randomness is relative. What is
> > random for some is predictable and non random for others. And secondly,
> > computer programs can produce genuinely true random numbers.
> >
> > I rest my case.
> >
> > And may you rest in peace trying to refute what I have described and
> > concluded because you will surely die trying.
>
> What you have described is just an extremely large hash function applied to
> the initial conditions and parameters of the simulation. One flaw in this
> reasoning is that the perfect imaginary keno game is reversible. Another is
> that you have not considered the limits to the resolution of the simulator.
>
> Otherwise I agree that randomness is a measure of ignorance and that there
> are many examples of imperfect systems that are practically secure without
> being provably secure.
I don't mean to jump up and defend myself but only to further explain:
the imaginary ideal keno game example was used to demonstrate that a
computer simulation of such could be done, and that such a simulation
could be programmed to approach a real imperfect system.
It is this latter case that I think not reversible because there would
just be too many parameters or degrees of freedom to make computation
feasible.
Now, regarding limits to the resolution, I think you mean how detailed
or minute the detail, or in other words, the number of degrees of
freedom must be defined. I alluded to this but did not describe it
thoroughly.
Imagine each ping pong ball to have 1000 tiny bumps spread non uniformly
over its surface with each ball having no single common bump in the same
location. The velocity of the compressed air flow could change to over
1000 different values. The friction on the inner surface of the plastic
spherical container varies over 10,000 times non uniformly. Etc.
This should qualify for a certain level of resolution.
But I like the general agreement on some crucial points by yourself and
others:
"I agree that randomness is a measure of ignorance and that there are
many examples of imperfect systems that are practically secure without
being provably secure."
"But when all is said and done, cryptographers only need crypto-grade
random numbers which are produced by a TRNG, even one that is not
perfect, as long as the ciphers are not breakable. " ( A TRNG that is
not perfect is not a TRNG?? Might it be a PRNG??)
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Where to publish hashes?
Date: Tue, 23 Feb 1999 23:13:34 -0600
In article <7aumt1$l0h$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Helger
Lipmaa) wrote:
> dan schwartz ([EMAIL PROTECTED]) wrote:
> : Let's say I want to publish a secure hash of a document, so I can
> : later prove that I possessed that document on or before the date
> : that the hash was published.
>
> : Any ideas for the best places to publish the hash? The publishing
> : method should have the following characteristics:
>
> : 1 - Visible to the public.
> : 2 - Not subject to manipulation after publication.
> : 3 - Available for viewing for a long time after publication.
> : 4 - Inexpensive.
> : 5 - Convenient.
>
> : Placing an ad in a major newspaper satisfies 1 - 3, but probably
> : not 4 and 5. Is there a method that satisfies all of them?
>
> : Dan Schwartz
>
> This is one of the non-mathematical parts of the general time-stamping
> problem (I'd suggest to look at http://home.cyber.ee/helger/cuculus for
> information about time-stamping). Being a non-mathematical part, there are
> no optimal solutions. All depends on the requirements you place on the
> system. If the hashes are _really_ of great importance (as in the case of
> time-stamping), I would personally publish them on several different media
> at the same time, including:
>
Proliferation and preservation are the names of the game, producing many
copies and associating them with something that is apt to be preserved.
The associated item should be individually valued for some utilitarian
use, but not of great intrinsic value, nor distributed nor preserved in a
highly documented or predictable way.
--
A much too common philosophy:
It's no fun to have power....unless you can abuse it.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Another extension to CipherSaber
Date: Tue, 23 Feb 1999 23:05:55 -0600
> > Also, regarding the earlier suggestion of ASCII armoring, we already have
> > universal standards (like binhex or UUEncode) which accomplish this.
>
> Neither of which is actually universal. Stick with base64 or just hex if
> you want guaranteed-to-work or trivial-to-implement, respectively. There
> are lots of versions of binhex and uuencode which are incompatible and
> which don't go thru gateways like you'd like.
>
Trying to narrow design standards for crypto to meet ever more-restrictive
criteria results in the ultimate end of having only one crypto algorithm
that can meet them; this is exactly what some want to happen, and to be
sure that it is a appropriately crippled product to boot.
No, better to encourage the use of as many divergent methods as possible,
not only to increase the numbers of algorithms, but to stimulate designs
that are heretofore not even known. And, as wide as the range of
purposes, show should be that of crypto; one, or even a few cannot do it
all.
It strikes me funny that so many paper mavericks are all to willing to
show themselves as dumb stinking sheep, a term which is learned through
experience. Keep your options open as well as your eyes and ears to new
ideas, and explore.
--
A much too common philosophy:
It's no fun to have power....unless you can abuse it.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: A Tale of Two Bases
Date: Wed, 24 Feb 1999 00:10:14 -0600
No surprise, this posting is an extension of my base translation cipher
series. I have been converting plaintexts in base 100 to various other
bases, lower ones. These simple block ciphers include a transposition key
and a substitution key of appropriate sizes.
One of the past efforts was Granville, transposes 14, 28, 42, or 56
digits, substitutes and outputs in a 57 character set. The most recent
effort is MapleLeaf, which also substitutes and outputs in a 57 characters
set; but, the transposition in MapleLeaf is 18 or 36 hexits.
With minimum default keys, input in each is 7 character groups and output
is in 8 character groups. In fact, as anticipated, the default ciphertext
with the default keys is identical. At the second available sized
ciphers, this also is the case since the I/O characters sized blocks are
14/16. Of course, Granville has 2 more sizes in these implementations
with no corresponding ones available in MapleLeaf. With actual
transposition, the outputs are widely varied as expected.
Default keys for MapleLeaf are as follows:
Subs(ML): abcdefghijklmnopqrstuvwxyz/123456789.,?!:;()'"-=*+~#%$&@|
Trans(ML): abcdefghijklmnopqrstuvwxyz/123456789
Note that instead of using the 36 character set with a zero instead of a
/, it is better to use a subset for convenience in implementation. To
give a flavor of the ciphertext, Here is this paragraph done with the
simple default keys:
zpw6* .!v95 /#u/a ~,8$% err/- t&~=b *2!or t+'-6 !ns.4 ,)p'q gs$h, g!+%2
d3ff, :mfd| gs";* /)n(: auav1 .~*"u .vqnx 7"-1u k*k1a /x#*. e'"p| |t@sm
?nevd ,?u-- z4t@i +,o&6 )n6r) 8#z;6 r895! :%-73 22-jj wh@au a1eh$ ~)f)m
%v5%! ory;' ?,,:n e$w3% am4ao 3@p'- ~#o'- u)55; 4~az) 7/i=2 +7a1a pz1'2
!or/u kzf;x x@-&* f-r=~ ee|3' &*du5 =l
As before, the keys use the THF, so ksy can be easily generated or entered
as needed.
To name the application, I was lead to the same area in Canada, and found
near Lake Granville, a town with Leaf in its name. Now, Leaf would be a
regretable name for a cipher with negative connotations, so it is not hard
to get an appropriate type of leaf for the location in the midst of
Canada, the Maple Leaf. Strangely, the application was largely built on
another previous one, Canadian, which as some might remember is because of
a River and Town found in Texas...an strange relationship for sure.
The next application will also do a previous pair of bases, with bits
instead of digits used for transposition.
--
A much too common philosophy:
It's no fun to have power....unless you can abuse it.
------------------------------
From: Michael Sierchio <[EMAIL PROTECTED]>
Subject: Re: Randomness of coin flips
Date: Tue, 23 Feb 1999 23:10:04 -0800
Reply-To: [EMAIL PROTECTED]
"R. Knauer" wrote:
> What on God's Green Earth (tm) is a "quincunx"?
It's in the heavens and not on the Earth (it is a mildly favorable
aspect of two planets).
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Pentium III Hardware Random Numbers
Date: Wed, 24 Feb 1999 08:10:08 GMT
On 24 Feb 99 03:30:02 GMT, in <[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] () wrote:
>Earlier, there was a post speculating that the Pentium III might use a
>technique described in a recent Intel patent to generate random numbers,
Note that the RNG may be on the Pentium III "platform": the support
chips, and not on the CPU chip itself. This is also where we can
expect to find the public-key engine they talk about.
>based on oscillator drift, which would not be good.
>
>I recently saw an item (was it in Wired? Computerworld?) that says that
>Intel is going to use thermal noise in the chip. This, of course, is a
>much better technique for quality randomness.
If we look at the abstract for US Patent 5706218, issued 1998 Jan 06
to Eric Hoffman and assigned to Intel, we see:
"A random number generator using a single, slow, voltage controlled
oscillator which receives a noise input and a plurality of high
frequency ring oscillators."
The patent shows two 50K resistors taking the same source voltage into
both sides of a differential amplifier, and it is claimed that the
diff amp may see +/- 500 uv from resistor noise (presumably, Johnson
thermal noise). The diff amp drives a VCO running at about 450 kHz.
The VCO digital output directly latches the state of a different 600
MHz oscillator per output bit. (There is also a special design for a
D flop which is intended to latch either a 0 or 1 without bias.)
>From my point of view, there are two problems with the design:
1) The ring oscillators on each chip may vary slightly, and will be
affected by temperature, but this should happen similarly on every
run-up. So, for a particular chip, we have oscillators which will
each have their own relatively-constant frequency. This may mean
that, over multiple latch events (which we expect to be normally
distributed around the average VCO period), not every combination of
oscillator phases is equally likely, even if the output values are
apparently random.
2) The other problem is the absence of any attempt to turn off the
noise (e.g., short the resistors). There is thus no way to
demonstrate that the RNG is using unpredictable noise as opposed to
complex but reproducible near-by switching transients. Unless we have
a way to turn off the noise and see a fundamental change in output
statistics, we have no way to know whether the design is really using
noise or not. We can seek to analyze the results, but even
PSEUDO-random RNG's pass such tests.
>And it confirms that this
>feature is to be present - until this report, I had seen nothing about
>this feature except in Usenet posts, which could be rumors.
Unfortunately, if the patent reflects what they are really doing, it
is not the usual comforting noise-based RNG.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: New high-security 56-bit DES: Less-DES
Date: Wed, 24 Feb 1999 00:33:39 -0800
[EMAIL PROTECTED] wrote:
> Bryan Olson wrote:
> > Ed Gerck wrote:
> > > Bryan had written:
> > > > You say that a zero unicity distance would mean a message is known
> > > > before it's written. Does that mean a unicity distance of 8 means
> > > > any message is known after the first 8 letters are written?
> > >
> > > Yes, but pls exchange "intercepted" for "written" when the unicity > 0,
> >
> > You had it as "written" when you made the claim for a unicity
> > (distance) of 0, so I asked if the analogous
>
> ;-) the analogous case is as I wrote, Bryan.
>
> >held for 8. If you can't answer, fine, but I asked the question I meant.
>
> which had no meaning Bryan, as I pointed out.
It means does one know an entire message after being
given the first 8 bytes? (even if the rest is not yet
written). The answer is of course not.
Why is it analogous? If we require that at the unicity
point the message is uniquely determined, then unicity
distance would have to depend on message length. We cannot
uniquely determine a 1000 letter English message given eight
letters. Neither zero nor eight would make sense without
specifying the length of the message. Shannon's definition
does not depend on message length, only the cipher and
plaintext language.
> In fact, I just see a repeat performance for the lack of dialogue that has
> characterized this rather dull exchange from your side.
See:
http://x7.dejanews.com/[ST_rn=qs]/getdoc.xp?AN=446372808&CONTEXT=919570827.958005461&hitnum=2
where I tried to respond to the outstanding issues.
> I must again recall
> that completely misleading "example" for DES that you wrote here and never
> recalled.
It was you, not I, who said it was for DES. I regret that the
initial presentation confused a reader on that point, but later
I specifically clarified that I was not assuming DES.
> You tried to call it "contrived" and everything else but not what
> it is: a tentative to fudge the discussion -- which is neither useful nor
> acceptable in a technical discussion.
It was neither of those. See the post cited above for
references to the actual history as recorded in the
archives.
> > > do NOT use the word "distance" since it is NOT a "distance" as I have
> > > commented before and in the paper.
> >
> > Again I must decline. "Unicity distance" is a term of art in the
> > discipline.
>
> :-) which I point out is incorrect.
Terms of art are not correct or incorrect; they are simply
words with meanings. Blackjack dealers do not in fact
"burn" the first card off the deck. If a doctor prescribes
two medications known to have harmful interactions, it is
not in fact a "contradiction". Only a minuscule fraction
of "balloon payments" apply toward financing lighter-than-air
craft. Terms of art. You may note that I have not criticized
you for not using the accepted technical term; I merely
declined to stop using it myself.
> > Maybe Shannon could change it, but he retired from the
> > field a long time ago.
>
> I see you know nothing about the scientific method. And that would be a
> dialogue pre-requisite -- another one which you obviously miss.
Terminology is established by usage within the discipline
and especially usage by the prominent leaders. The scientific
method does not define words for us.
Your "I see" is quite similar to a previous observation.
When I wrote:
> > The unicity distance estimate for a
> > random cipher H(K)/D is a lower bound, not an upper bound on
> > unicity distance.
You replied:
> I see that you are not used to mathematical terminology.
And yet if we look at Shannon page 699, he does explain
why the unicity distance estimate from the random cipher
model is the lowest it could be.
Both of your "I sees" were phrased as personal insults,
and believe me it was tempting to respond in kind. I
decided to simply present the case for my assertions.
> > In my previous post (linked above) I asked if you think your
> > definition is equivalent to Shannon's. You snipped the questions.
>
> It is written in my paper and repeated by myself ad nauseam here: I did not
> redefine unicity
The snipped questions then asked how you justify a
three-letter unicity (distance) for DES given that your
explanation of how to break it required 16 intercepted
letters. The count of intercepted letters required for
unique solution is how Shannon defines unicity distance.
Where is the break that uses three intercepted letters?
> Regarding Shannon's unicity formula I do call attention to its current wrong
> use for block ciphers -- when the formula is used beyond its validity range,
> which can NEVER exceed one cipher block
As I previously granted, DES block cipher does not a good
approximate a random cipher for more than one block, and I'd
grant the same for other block ciphers. But after presenting
the formula for the random cipher, Shannon goes on to show it
is a reasonable approximation method for other ciphers.
> and can be even less as in the case
> of DES (which is a random cipher over 7 bytes, not 8 bytes).
So you found nothing you could use in:
| Look at the description of the random cipher. It has both a number
| of messages, Shannon calls it 'T', and a number of keys, called 'k'.
| DES approximates a random cipher where T=2^64 and k=2^56. If you're
| talking about the key space over which DES approximates a random
| cipher, then it's 7 bytes. If you're talking about the message space,
| then it's 8 bytes.
> But .. all this has nothing to do with this thread subject's -- so I will
> stop here.
>
> This thread deals with [...]
It has wandered, and I have never criticized you for changing
a thread's subject header.
--Bryan
------------------------------
** 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
******************************
