Cryptography-Digest Digest #128, Volume #9 Wed, 24 Feb 99 00:13:04 EST
Contents:
Re: Unicity of English, was Re: New high-security 56-bit DES: Less-DES (Bryan Olson)
Re: Define Randomness ("D")
Re: Testing Algorithms ("Trevor Jackson, III")
Re: Interesting DES results (bill johnson)
Re: Unicity of English, was Re: New high-security 56-bit DES: Less-DES (Bryan Olson)
Re: What do you all think about the new cipher devised by a 16 year old? (Anthony
Naggs)
Re: Block cipher in the smallest PIC (Matthias Bruestle)
Re: Define Randomness ("Trevor Jackson, III")
Re: Define Randomness (Darren New)
Re: Testing Algorithms ("Trevor Jackson, III")
Re: Testing Algorithms ([EMAIL PROTECTED])
Re: Unicity of English, was Re: New high-security 56-bit DES: Less-DES (Dennis
Ritchie)
Re: Testing Algorithms [moving off-topic] ([EMAIL PROTECTED])
Re: Define Randomness (Nicol So)
Pentium III Hardware Random Numbers
Re: Define Randomness (Anthony Stephen Szopa)
Re: Define Randomness (Anthony Stephen Szopa)
----------------------------------------------------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Unicity of English, was Re: New high-security 56-bit DES: Less-DES
Date: Tue, 23 Feb 1999 15:05:07 -0800
[EMAIL PROTECTED] wrote:
>
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] () wrote:
> > [EMAIL PROTECTED] wrote:
> > : BTW, this further shows why unicity cannot
> > : defined by the condition of "zero key equivocation" alone -- here, we have
> > : zero key equivocation for one intercepted letter but not zero message
> > : equivocation and thus no unicity.
> >
> > There is indeed zero message equivocation. We know, for a fact, that the
> > message is the letter "C".
>
> That is why I noted that I was NOT talking about the *received* letters --
> which are trivially known and certain (as certain as the systems's
> reliability is). More interestingly -- I asked what can we predict the
> message will be if we receive n letters?
>
> > Certainly, we can define a concept *similar* to unicity, which tells us
> > how much unenciphered English text we need, on average, to identify words
> > unambiguously, and get the sense of the text we see.
>
> The concept is not similar but the same. And, it does NOT involve sense or
> meaning -- just syntax. Pls note that Shannon's Information Theory does not
> concern itself with sense.
My reading of the quote of John Savard is that the "which tells us..."
is meant to describe the concept hypothetical concept "similar" to
unicity, not Shannon's unicity point and unicity distance. The
placement of the clause leaves it somewhat ambiguous. John, am I
reading that correctly?
John is right. With no key there is no equivocation. This is the
"degenerate type of secrecy system" described by Shannon at the
bottom of page 663. Since there is only one key, we can uniquely
determine it without intercepting any ciphertext, yielding a unicity
distance of zero. Note that there is no implication that we can
tell what a message is without intercepting the ciphertext.
The single transform case has, strange as this may seem, ceased to
be degenerate. All public key ciphers disclose to attackers the actual
transform induced by the key, and therefore have a unicity distance of
zero for any plaintext language.
--Bryan
------------------------------
From: "D" <[EMAIL PROTECTED]>
Subject: Re: Define Randomness
Date: Tue, 23 Feb 1999 19:06:30 -0500
You know, I was reading this thread and I had an interesting thought. If
naturally occurring phenomenon are random, and they repeat periodically,
such as in the adage about history, then shouldn't 'crypto-grade randomness'
actually be something completely different than randomness?
------------------------------
Date: Tue, 23 Feb 1999 20:34:49 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithms
Steven Runyeard wrote:
> >There's no garantee that this growth rate will continue. In fact
> >everything points to the opposite.
>
> No, there is no quarantee of this. There is also no quarantee that the
> speed of light will be a barrier.
>
> You are basing your calculations on the assumption that CPU speeds
> will stop increasting. So far the trend has been a doubling around
> every 1.5 years. I remember back in 1985 being told that my 1 MIP CPU
> is about as fast as we can possible get because of 'physical
> barriers'. Today we have CPUs that can run 2,000 times faster. Have we
> got to that barrier yet? No, I don't think so.
>
> This whole thing comes down to speculation. As far as you're concerned
> we are going to reach a ceiling in computer performance. I, on the
> other hand think we will not. If there is money in it Intel will find
> a way of making a faster CPU.
>
> It's your guess that we won't crack a 256 bit key. It's my guess that
> we will. Each guess is just as valid.
No. The guess is only as valid as the assumptions it is based upon.
Since you have based yours on nothing concrete, your guess is pretty
useless. If you specify any level of technology less than divine you will
find limits. Those limits will control the size of a key that can be
broken with that technology in a reasonable amount of time.
It takes an outrageous set of technology assumption to make breaking
256-bit keys possible. Outrageous not by the standard of current
technology, but by the wildest standard you can think of. Do the math.
Try to count that high.
------------------------------
Date: Tue, 23 Feb 1999 21:22:50 -0800
From: bill johnson <[EMAIL PROTECTED]>
Reply-To: same
Subject: Re: Interesting DES results
Thanks for the input guys. I'll check further, but it sounds like most
of you are saying this is normal.
Bill Johnson
bill johnson wrote:
>
> Hello,
>
> I'm new to this news group but I found something interesting. I was
> interested in random numbers so I tried encrypting a file to produce
> another file of random numbers. The encryption was done with a standard
> DES engine with a single key, encrypting 8 bytes in sucession and
> writing the values to a data file.
>
> I then ran two tests on the data file (about 1.5MB). The first was to
> count the number of different byte values (0 through 255) and as I
> expected the results were very uniform with little deviation.
>
> The second test was to measure the + or - difference from one byte to
> the next. This was an eye opener. The plot looks like a nearly perfect
> inverted 'V'. In fact amazingly so.
>
> I've tried this on two different sources and I get the same result.
>
> Any comments from the grouop? I have the data and source files if
> anyone is interested.
>
> Bill Johnson
>
> remove 'nospam' to reply
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Unicity of English, was Re: New high-security 56-bit DES: Less-DES
Date: Tue, 23 Feb 1999 18:12:08 -0800
I carelessly wrote:
> > > Certainly, we can define a concept *similar* to unicity, which tells us
> > > how much unenciphered English text we need
[...]
> My reading of the quote of John Savard is that the "which tells us..."
> is meant to describe the concept hypothetical concept
^^^^^^^
I made my clarification _less_ clear than the original.
Strike the first appearance of "concept" above.
--Bryan
------------------------------
From: Anthony Naggs <[EMAIL PROTECTED]>
Subject: Re: What do you all think about the new cipher devised by a 16 year old?
Date: Wed, 24 Feb 1999 02:28:48 +0000
After much consideration fungus decided to share these wise words:
>
>It's still a secret, until the "patents go through".
Indeed.
>This sounds like twaddle to me. Once a patent is filed, you can publish
>the algorithm, whether it finally gets granted or not.
Only in the USA.
>Another mystery is that a patent is being applied for when (according
>to the press) the girl in question says she's not interested in making
>money from it. Something doesn't add up...
Firstly it was suggested to her by the science competition judges, she
doesn't seem to have given it serious consideration before that. A
patent will define the algorithm exactly, so that no variations can
carry the name. Licensing the algorithm for only a small fee could
certainly be a useful income when she goes to university.
--
BAD COMPUTER! That's my registry file you've trashed.
------------------------------
From: [EMAIL PROTECTED] (Matthias Bruestle)
Subject: Re: Block cipher in the smallest PIC
Date: Tue, 23 Feb 1999 23:38:03 GMT
Mahlzeit
Robert Scott ([EMAIL PROTECTED]) wrote:
> I have an application in remote keyless entry that,
> for economic reasons, favors the use of the smallest
> PIC processor: the 12C581. It has only 32 bytes of
> RAM and 512 words of program. Although the stakes are
You could try TEA and maybe increase the number of rounds.
It is pretty simple. But I don't know how it compares to DES.
Mahlzeit
endergone Zwiebeltuete
--
PGP: SIG:C379A331 ENC:F47FA83D I LOVE MY PDP-11/34A, M70 and MicroVAXII!
--
'If you want a picture of the future, imagine a boot stamping on a human
face - forever. And remember that it is forever' (Orwell, 1984)
------------------------------
Date: Tue, 23 Feb 1999 21:11:50 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Define Randomness
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.
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Define Randomness
Date: Wed, 24 Feb 1999 01:58:15 GMT
> >Just as an aside, there was someone in Atlantic City who won the
> >million-dollar Keno game three times in six months. It turns out the
> >PRNG in the computer generating the numbers got initialized with the
> >same value after every power failure, so when he saw the same sequence
> >of numbers coming up, he knew what games were next.
>
> >I think he even won the court case.
>
> How can someone sue him for being a smart guy? If that were allowed,
> the state could renege on any winnings it wanted just by claiming that
> the winner took advantage of something heretofore unknown.
This is keno, not a lottery, and hence the state has no say in
reneging(sp?). And the normal disclaimer is that winnings are forfeit
if the game is broken. I.e., if you come up with two cherries on the
slot machine and it dumps $100K in your lap, you don't get to keep it.
(Note: 2 cherries is like $5 or $10 or something.)
I think the court figured that since the machine was behaving exactly as
the programmers expected, it couldn't be said to be broken. Stupid, yes,
but not broken.
--
Darren New / Senior Software Architect / MessageMedia, Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"Be.... the email."
------------------------------
Date: Tue, 23 Feb 1999 20:37:52 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithms
fungus wrote:
> Patrick Juola wrote:
> >
> > Given that people have, for the past 20 years, routinely been claiming
> > that "Moore's Law cannot hold much longer due to fundamental physical
> > limitations," it's starting to look like betting that Moore's law
> > will NOT hold isn't a safe bet.
> >
>
> Simply not true.
>
> For many years people have been saying that Moore's law cannot hold
> because of technical difficultiess (eg. the wavelength of light used
> to etch the chips). So far, this hasn't come true. Process technologies
> have managed to keep up with the "law" (although things are starting
> to slow down noticably in the last few years).
>
> Only very recently have people been saying that "Moore's law cannot
> hold because of fundamental physical limitations" like the speed of
> light. There is no evidence whatsoever that Moore's law can hold
> beyond another 15-20 years or so. Electrons/photons simply don't
> move that fast...
>
> When this limit is reached, we'll have to move towards more
> parallelism in software to get things done (if we actually
> need *more* speed on the desktop...)
Either you assume that Microsoft (tm) goes out of business, or you assume
that we'll need ridiculous performance levels in the future. Since people
seem to *like* buying fast hardware to run slow software, I expect we'll be
pushing hardware for many decades.
>
>
> --
> <\___/>
> / O O \
> \_____/ FTB.
>
> PS: At 2.5GHz chips will start to emit microwaves - good for keeping
> your coffee warm...?
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Testing Algorithms
Date: Wed, 24 Feb 1999 02:52:19 GMT
In article <[EMAIL PROTECTED]>,
Darren New <[EMAIL PROTECTED]> wrote:
> > 56-bit DES was once considered unbreakable but was recently broken in
>
> Was it really? I thought the DES spec was published with a lifetime set
> to expire in the mid 1970's or something?
>
> --
> Darren New / Senior Software Architect / MessageMedia, Inc.
It was originally to have a lifetime of 'about' 20 years. It was NEVER
considered unbreakable. The prior post is yet another example of
n uninformed person posting misinformation.
And people don't seem to understand how big 2^256 is.
Simple arithmetic seems beyond them
>
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Dennis Ritchie <[EMAIL PROTECTED]>
Subject: Re: Unicity of English, was Re: New high-security 56-bit DES: Less-DES
Date: Wed, 24 Feb 1999 03:52:45 +0000
Reply-To: [EMAIL PROTECTED]
You've been given a cyphertext, which you believe is
a simple substitution with word divisions. You decrypt it to
O wail, keen Las Vegas pard, love that gaga LA birder. She flees
Silas Wang in pad vest or plaid CA slip. "It was cad Mozart or
bad-knees Yang," pled she. SOS, fated in love.
which you intepret as
A sensitive cowboy gambler, smitten by a valley-girl naturalist
who's fallen in with the infamous Mozart/Yang gang, despairs as his
beloved is pursued in dishabille by one of the gang's victims,
to whom she protests her innocence, crying out that the real culprits
are the gang's notorious leaders.
It turns out you're wrong. Instead, the message really
has interpretation more like this:
A swell buffoon fishing on a Maine dragger met a pair of
mermaids who lured him to their sea cave and
boozed him up. Now he's suing the captain for leading him
into embarrassment.
What's the message?
http://cm.bell-labs.com/cm/cs/who/doug/crypt.html
--Dennis
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Testing Algorithms [moving off-topic]
Date: Wed, 24 Feb 1999 02:57:57 GMT
In article <x$[EMAIL PROTECTED]>,
Withheld <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>, fungus
> <[EMAIL PROTECTED]> writes
> >
> [cut]
> >Only very recently have people been saying that "Moore's law cannot
> >hold because of fundamental physical limitations" like the speed of
> >light. There is no evidence whatsoever that Moore's law can hold
> >beyond another 15-20 years or so. Electrons/photons simply don't
> >move that fast...
> >
> >When this limit is reached, we'll have to move towards more
> >parallelism in software to get things done (if we actually
> >need *more* speed on the desktop...)
>
> Or if we want to run Windows NT version 43.8 beta... :-)
Jokes aside, people STILL can't do arithmetic. Chips have non-zero area
and consume power. Try computing how much space is needed, how much
power is needed, and how much cooling is needed to power (say) 10^7
processors running in parallel. And my earlier analysis posited a 10^10
increase over all computers in existence today. Note also that as clock
rate increases, so does required power and heat output....
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Define Randomness
Date: Tue, 23 Feb 1999 23:05:32 -0500
Anthony Stephen Szopa wrote:
>
> [Description of the Keno game, deleted]
>
> So, unreproducibility and equal probability of outcome are two essential
> characteristics of randomness. I am not an expert but are there other
> characteristics or do they all derive from these two?
Equal probability of outcome is not necessary for randomness. Even a
source with a very skewed distribution of outcomes can be random--it
just has less entropy.
> Now, let us define our object random process, the one we will consider
> to support my definition of randomness as it applies to computer
> software.
>
> [Discussion about the possibility of precisely simulating and predicting
> the behavior of a Keno machine, deleted]
>
> There is no reason that we could not do this given an ideal Keno
> machine, perfect information at one instant in time, and a powerful
> computer.
>
> But we do not have a perfect Keno machine, or perfect information, or a
> sufficiently powerful computer to process this data and give us our
> predictable outcome. But if we had, we could predict the outcome!
>
> So, for our discussion, randomness all comes down to knowledge and
> programming: measurement and technology. What we call randomness is
> nothing more than a measure of our own ignorance and lack of ability.
For the game of Keno as you described, it is true. One factor that you
didn't mention is the extreme sensitivity of the outcome to small
changes in the initial condition. Without this important property,
approximate knowledge of the initial system state may be used to
estimate the final system state, and the degree of apparent randomness
will be diminished or lost.
> [Discussion about how ignorance of state information can lead to apparent
> unpredictability, deleted]
>
> 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.
What you called "randomness" in your first remark is properly termed
"pseudorandomness". Your second remark is incorrect. A computer, as an
example of a deterministic device, cannot produce *true* random
numbers. Knowledge of the computer's state will cause the supposedly
random numbers to lose their random appearance.
Nicol
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Pentium III Hardware Random Numbers
Date: 24 Feb 99 03:30:02 GMT
Earlier, there was a post speculating that the Pentium III might use a
technique described in a recent Intel patent to generate random numbers,
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. 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.
John Savard
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Subject: Re: Define Randomness
Date: Tue, 23 Feb 1999 20:38:24 -0800
Reply-To: [EMAIL PROTECTED]
D wrote:
> You know, I was reading this thread and I had an interesting thought. If
> naturally occurring phenomenon are random, and they repeat periodically,
> such as in the adage about history, then shouldn't 'crypto-grade randomness'
> actually be something completely different than randomness?
Who passed this law that "naturally occurring phenomenon are random?"
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Subject: Re: Define Randomness
Date: Tue, 23 Feb 1999 20:34:37 -0800
Reply-To: [EMAIL PROTECTED]
"Tony T. Warnock" wrote:
> Actually, the future positions (and momenta) of the balls often depends in a
> chaotic way on the initial conditions. It is possible (I haven't done the
> computations.) that the initial conditions must be known so accurately that
> quantum effects obtain. That is to say, if you have to know the initial
> conditions to a greater degree of accuracy than QM allows, even large
> systems can show random behavior. A simple example would be to have a ball
> (the usual perfect weightless, frictionless, odorless, shameless, particle)
> bouncing back and forth in a 1 dimensional space 1 meter long. If the ball's
> velocity is 1 meter per second with an uncertainty of 1 part in 10000, then
> by the next day one cannot say where the ball is. The same for an
> uncertainty in position.
>
> Tony
My example is as subject to quantum effects effecting the outcome as is the
firing of the pistons in a V-8 engine. We do not need to know the parameters of
a real system (keno game) to this degree for my argument to be valid.
Accurate predictions can be made and practicably so with no effect of outcome in
such a system while ignoring quantum effects.
For example, a moving body in space with constant velocity can be measured
accurately enough such that for the next 50 million years we could predict its
position.
This is done every day with your quartz crystal watch. Over a years time it is
accurate to less than 1 second deviation. So, within a years time we know what
time it is within one second.
It would be absurd to say we can only think we are close to knowing the exact
time from a practicable view point.
And we are all trying to be practicable. Cryptography is an applied technology.
------------------------------
** 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
******************************
