Cryptography-Digest Digest #145, Volume #9 Fri, 26 Feb 99 05:13:04 EST
Contents:
Re: paper on all 15 AES candidates ?? ([EMAIL PROTECTED])
Re: Unicity of English, was Re: New high-security 56-bit DES: Less-DES (Bryan Olson)
Re: True Randomness - DOES NOT EXIST!!! (Alan DeKok)
Re: Define Randomness (Michael Sierchio)
Re: Testing Algorithms ("Tim Woodall")
Re: Define Randomness (Patrick Juola)
Re: Quantum Computation and Cryptography (Matthias Meixner)
Re: Testing Algorithms (Matthias Meixner)
Re: VxD Crypto - Win 95/98/NT ("R H Braddam")
Re: A New Public-Key Cryptosystem (Bryan Olson)
Re: Define Randomness (Terry Ritter)
Re: IDEA test vectors? (Wei Dai)
Re: Why Physical Randomness? (Anthony Naggs)
Re: Quantum Computation and Cryptography (R. Knauer)
Re: RC4 40 bit compared to RC4 128 bit. ("Rats")
----------------------------------------------------------------------------
Subject: Re: paper on all 15 AES candidates ??
From: [EMAIL PROTECTED]
Date: 26 Feb 99 06:05:55 GMT
Christopher Jobmann <[EMAIL PROTECTED]> writes:
>I'm looking for a paper (or any other information) giving a brief
>overview over all the 15 AES candidates, considering underlying
>structure (Feistel-Network, SP-Network and such), Numbers of Rounds, as
>well as safety (I heard a couple of the candidates are already broken -
>is that true ??).
I have comments on some of that in my paper:
L. Brown, " A Current Perspective on Encryption Algorithms", to be
presented at the UniforumNZ'99 conference in NZ, April 1999. This has
been revised from the version presented to AUUG98. You can grab it from:
http://www.adfa.edu.au/~lpb/papers/unz99.html
The references include pointers to a number of other sites with additional
comments.
As to the broken ciphers - there are major problems known for:
DEAL, FROG, LOKI97 (sigh!!!), and MAGENTA, as well as some minor
caveats on DFC and MARS.
Cheers
Lawrie.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Unicity of English, was Re: New high-security 56-bit DES: Less-DES
Date: Thu, 25 Feb 1999 18:27:30 -0800
[EMAIL PROTECTED] wrote:
> Bryan Olson <[EMAIL PROTECTED]> wrote:
> > [EMAIL PROTECTED] wrote:
> > > "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).
> >
> > Different yes, independent no. See Shannon's theorem 7.
>
> Next, with the same line of "reasoning" you would certainly tell me that time
> and distance are dependent since in the special case of uniform motion, s =
> s0 + v*t.
You had implied that if key and message equivocation had to be
zero "at the same length of received text", that would make them
dependent. I took that to mean the issue is whether they are
independent given some intercepted text. You are right that
they are /a priori/ independent, but given ciphertext they are
related, as shown in Shannon's theorem 7.
[...]
> > > I would suggest you simply write down the
> > > formula!!!
> >
> > The formula for the random cipher? H(k) is zero, and D, the
> > [snip, wrong]
>
> OF COURSE NOT! How can you have a random cipher with only one key "granted"?
> There is no randomness below two choices, Bryan.
Shannon's random cipher model works perfectly well for a key space
of one key. There is still randomness in the construction: since
there is one key, there will be one line from each E, and the model
says each line leads to a random M.
> You need to use the conditional message entropy formula, what else? Note, I
> even wrote it explicitly, above:
O.K. I get zero for that too, as I'll explain below.
I do observe you are correct that the formulas on the bottom of
page 685 are misprinted. They both need a minus sign before the
summation, and in the formula for H_E(M), the factor that reads
P_E(K) should read P_E(M).
[...]
> I must say. BTW, this points
> out that "granted" is not just a discussion stopper -- it is an attitude. And,
> one that demands integrity.
I assure you it was a sincere attempt to make progress. Let me
see if I can identify exactly where we disagree on this one
issue. First, I think we can agree that as Shannon defines unicity
(distance), he says that at the unicity point message equivocation
(entropy given the intercepted letters) must be zero, or negligibly
far from zero.
I hold that the message he is talking about is the plaintext
corresponding to the intercepted letters. You hold, correct me
if I'm wrong, that the message in question does not depend on the
number of intercepted letters; as the attacker intercepts more
letters, they form a longer prefix of (the ciphertext of) the same
message.
If (what I presented as) your interpretation is correct, then I
grant it is impossible to have a unicity (distance) of zero for
English. As you observe, we would have to know any message in
the absence of any information about the message.
Now I'll ask you to grant that if my interpretation is correct,
then the unicity distance a system with only one possible key is
in fact zero. At zero intercepted letters, the ciphertext
corresponds to the one and only zero character plaintext which has
no equivocation. Under my interpretation, H_E(M) is zero, since
P(M) is one, so log P_E(M) is zero.
If you agree, then the question to settle is which message's
equivocation must be zero by the unicity point: the message
corresponding to the intercepted letters, or a complete message, of
which the intercepted letters form a prefix (upon decryption).
If you agree that my understanding would imply what I say it does,
I'm ready to argue that I am reading the definition as Shannon
intends. I invite you to argue for your interpretation, possibly
after correcting my description of it.
Fair enough?
--Bryan
------------------------------
From: [EMAIL PROTECTED] (Alan DeKok)
Subject: Re: True Randomness - DOES NOT EXIST!!!
Date: 24 Feb 1999 21:42:33 -0500
In article <[EMAIL PROTECTED]>,
BRAD KRANE <[EMAIL PROTECTED]> wrote:
>
>No where near a joke random does not exist!!! Every thing that happens
>relies completly on something else.
Sorry, nice try, but you're wrong. Go read about Heisenberg's
uncertainty principle. (Among others)
Everything that happens depends on things which are to some extent
unknown, and unknowable. Add enough of that "unknown" up over time,
and you've got complete unpredictability. Which is to say, randomness.
Alan DeKok.
--
"Thus we can conjecture that Special Relativity may ultimately be derived from
a simpler and more fundamental principle of _Conservation of Computational
Resources_." - Complexity, Entropy, and the Physics of Information, p. 315.
------------------------------
From: Michael Sierchio <[EMAIL PROTECTED]>
Subject: Re: Define Randomness
Date: Thu, 25 Feb 1999 23:21:05 -0800
Reply-To: [EMAIL PROTECTED]
"Trevor Jackson, III" wrote:
> The real universe is already debugged....
You mean that it is defect-free? I personally feel cheated. ;-)
> ...We should just use it.
There will always be adherents of this point of "view" --
"I know what I believe -- don't confuse me with the facts."
------------------------------
From: "Tim Woodall" <No Spam [EMAIL PROTECTED]>
Subject: Re: Testing Algorithms
Date: Thu, 25 Feb 1999 17:59:11 -0000
R. Knauer wrote in message <[EMAIL PROTECTED]>...
>On 25 Feb 1999 09:07:12 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>>If FTL communication is possible,
>
>It is possible, as was shown by Alain Aspect.
I'm afraid I have never heard of this person and the only reference to him I
could find on the web was on a website (sorry I cant remember the address, I
looked him up the last time his name was mentioned) about the EPR effect
that was, to say the least, wrong. :-)
Interestingly, on the subject of random numbers, the EPR effect can be used
to transmit information faster than light if you are prepared to accept an
error rate of _EXACTLY_ 1/2 :-)
Tim.
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Define Randomness
Date: 25 Feb 1999 10:19:17 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 24 Feb 1999 14:43:53 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>>But yes, in general, a uniform generator and only a uniform generator
>>will output a normal number.
>
>I believe that the notions of "uniform" and "normal" are essentially
>the same thing. I cannot imagine a number that possesses one of those
>characteristics not possessing the other. For example, what is a
>non-uniform normal number, or a uniform non-normal number. I suppose
>one could fabricate some weasel-worded contorions to get around that,
>but then they would not be using conventional meanings for those two
>words.
Well, a standard example of a non-uniform normal number is the
Champernowne sequence 1234567891011121314151617...; a formalist might
point out that that's not a 'number' per se, but the equivalent
real number 0.1234567891011121314.... certainly is.
It's provably normal (at least in base 10), but is also not the result
of a uniform Bernoulli process; in fact, it's not the result of a
random process at all!
And, of course, Champernowne's sequence is *not* a typical example of
the "general case," but it also doesn't exhaust the set of non-uniform
normal numbers; consider the result of encrypting it with some sort of
numeric Caesar cypher, for example. I think I could produce a countably
infinite number of variations on this sequence, all distinct, all normal,
and none of them the result of a Bernoulli process.
>>Problem : Li & Vitanyi state (p. 158, p. 3) that "it is universally
>>agreed that a random infinite sequence must be normal." Well, bluntly,
>>it ain't so, guys. There's lots of random infinite sequences that
>>aren't normal. This paragraph counts as one that, most kindly, they
>>oversimplified.
>
>Hmm... I did not expect Li & Vitanyi to publish falsehoods. I am truly
>crushed.
Deal. 8-) As I said, they oversimplified; they're not interested in
the study of random sequences per se; they're interested in the study
of Kolmogorov complexity. Discussing this sentence in full would have
doubled the length (and cost) of the book -- and their sales were low
enough anyway.
>Maybe they have a different notion of randomness than you have. We all
>know that the term "random" has been heavily abused in both math and
>crypto.
Of course. That's the problem. But I'd be very surprised to see someone
suggest that the result of rolling a K-sided golf ball isn't "random"
in any sense of the word.
Kolmogorov complexity yields one very specific definition of "randomness"
that matches, with probability one (there's that phrase again), most other
useful definitions of randomness on infinite sequences. It's also a very
powerful definition and technique, which is why I like looking at it as
a primary analytic tool. But it's not THE definition....
-kitten
------------------------------
From: [EMAIL PROTECTED] (Matthias Meixner)
Subject: Re: Quantum Computation and Cryptography
Date: 26 Feb 1999 08:08:13 GMT
fungus ([EMAIL PROTECTED]) wrote:
>
>
> "R. Knauer" wrote:
> >
> > A quantum computer results in an exponential increase in computing
> > capability. That's because it contains all eigenstates simultaneously,
> > like a massively parallel classical machine. These eigenstates
> > interact in an exponentially large manner as the computer steps along.
> >
>
> Ok, so we know the result's in there somewhere...
>
> ...but how do we get it out?
>
The QC algorithm has to filter out one result (preferrably the one you
are interested in), which does not use superposition of 0 and 1. This
result can be read.
- Matthias Meixner
--
Matthias Meixner [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Matthias Meixner)
Subject: Re: Testing Algorithms
Date: 26 Feb 1999 08:19:28 GMT
Coen Visser ([EMAIL PROTECTED]) wrote:
> Yes, but the argument was not limited to classical computer circuits.
> My guess is, as long as there is enough need for faster/bigger computers,
> faster/bigger computers will be build. Not just by extrapolating current
> technology but by scientific innovation. The question is if there is a need.
> For structural biology/chemistry we need at least an order of 1 million
> in speed. Other things than can be better are storage and net bandwidth.
The question is not if it is needed, but if someone is willing and has got
enought money to pay for this computer.
--
Matthias Meixner [EMAIL PROTECTED]
------------------------------
From: "R H Braddam" <[EMAIL PROTECTED]>
Subject: Re: VxD Crypto - Win 95/98/NT
Date: Fri, 26 Feb 1999 03:07:04 -0600
Peter Gutmann wrote in message
<7b38t2$mr8$[EMAIL PROTECTED]>...
>
>
>"R H Braddam" <[EMAIL PROTECTED]> writes:
>
>>Eatpages.VxD could also serve as a starting point for
a
>>secure memory allocator for Crypto functions. A VxD
can
>>map a pointer to its page-locked memory to an
>>application's address space. A lot is needed to
convert
>>it to a memory allocator and manager, though.
>
>Both parts of this already exist, all you need is
someone to glue the two
>together. The VxD allocator is the SCNSM driver,
available from
>http://soundcode.com/content/download/products/scnsm/,
the memory manager (or
>at least the one I'd use) is Doug Lea's malloc,
>http://gee.cs.oswego.edu/dl/html/malloc.html. I
looked at combining the two a
>few months back, but other things kept getting in the
way.
>
>Peter.
>
Thanks for the help. I downloaded the code, and I'll
start studying it right away. As soon as I've figured
out how they work and get something done, I'll post my
additions or changes to this thread. I looked at the
sources for malloc and heapmalloc that came with VC++
5.0, and they don't appear to be too complicated.
Thanks again for giving me some pointers.
--
Rick [EMAIL PROTECTED]
Murphy's Law is the only sure thing in the universe.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: A New Public-Key Cryptosystem
Date: Thu, 25 Feb 1999 23:33:29 -0800
Lowball61 wrote:
> One of the key questions about such a system is: can a
> rectanglar matrix (longer than it is wide) be diagonalized?
Uh, what does that mean for a non-square matrix?
> I tried a bruce force attempt at diagonalizing a 24x12 binary matrix. The
> number of operations ran well into the trillions, and still did not put the
> "diagonalized" matrix in a form that was useful.
What form were you trying for?
> How can a rectanglar matrix be put in a diagonalized form that is useful in the
> sense that somehow an inverse-like operation can be preformed?
First, what relationship do you want between a rectangular
matrix and its "inverse"?
I don't understand the "New Public Key System" from the description
in sci.crypt.research. Can you explain:
What is the public key, and algorithm for encryption?
What is the private key, and algorithm for decryption?
What is the key-pair generation procedure?
--Bryan
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Define Randomness
Date: Fri, 26 Feb 1999 09:24:10 GMT
On Thu, 25 Feb 1999 17:59:53 -0800, in <[EMAIL PROTECTED]>,
in sci.crypt Michael Sierchio <[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>
>> ...If the OTP really was "the best"
>> cipher, everyone would be using it....
>
>You're being disingenuous. You know better. That's equivalent to
>saying if Mercedes really were the best, everyone would be driving
>one. Just as there are barriers to entry in the Mercedes market
>($$$$), there is a barrier to using OTP that has nothing to do
>with the proof of a TRNG -- key distribution.
Well, "best" is often subjective, and the "best" thing may depend upon
one's situation.
Certainly price is *not* an issue for OTP crypto, so the reason we all
don't use the OTP must be something other than price. What is that
reason?
It may be that few of us think an OTP will provide sufficiently better
security to be worth the effort and risk of key-generation, transport,
and storage. Because of increased risks, the overall security from
using a realized OTP might even be *less* than (properly!) using some
other modern cipher. If so, the OTP is hardly "best," even *if* we
assume that the cipher per se cannot be "broken."
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Wei Dai)
Subject: Re: IDEA test vectors?
Date: Thu, 25 Feb 1999 23:39:11 -0800
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> are there other vectors too? (URL?)
Here is a bunch more:
key plaintext ciphertext
00010002000300040005000600070008 0000000100020003 11FBED2B01986DE5
00010002000300040005000600070008 0102030405060708 540E5FEA18C2F8B1
00010002000300040005000600070008 0019324B647D96AF 9F0A0AB6E10CED78
00010002000300040005000600070008 F5202D5B9C671B08 CF18FD7355E2C5C5
00010002000300040005000600070008 FAE6D2BEAA96826E 85DF52005608193D
00010002000300040005000600070008 0A141E28323C4650 2F7DE750212FB734
00010002000300040005000600070008 050A0F14191E2328 7B7314925DE59C09
0005000A000F00140019001E00230028 0102030405060708 3EC04780BEFF6E20
3A984E2000195DB32EE501C8C47CEA60 0102030405060708 97BCD8200780DA86
006400C8012C019001F4025802BC0320 05320A6414C819FA 65BE87E7A2538AED
9D4075C103BC322AFB03E7BE6AB30006 0808080808080808 F5DB1AC45E5EF9F9
------------------------------
From: Anthony Naggs <[EMAIL PROTECTED]>
Subject: Re: Why Physical Randomness?
Date: Fri, 26 Feb 1999 08:14:37 +0000
After much consideration John Savard decided to share these wise words:
>
>This says - as well as anything that anyone has said here - why a
>physical source of randomness is useful to have, and what the
>advantage is that it has over an algorithmic method of generating
>random numbers, however good.
Absolutely.
I've been watching Intel's website, and in the last couple of days a
number of Pentium III manuals and such have started to trickle out.
Despite filling my hard drive with these PDF files I can't find any
description of the hardware RNG. Not even in the P-III datasheet; which
fits with Terry's suggestion that the RNG could be on one of the support
chips.
Incidentally there is now a document, "AP-909: Intel Processor Serial
Number", which explains how to read the processor serial number with the
CPUID instruction though.
http://support.intel.com/design/pentiumiii/applnots/245125.htm
Cheers.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Quantum Computation and Cryptography
Date: Thu, 25 Feb 1999 18:49:42 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 26 Feb 1999 06:16:26 +0100, fungus
<[EMAIL PROTECTED]> wrote:
>> A quantum computer results in an exponential increase in computing
>> capability. That's because it contains all eigenstates simultaneously,
>> like a massively parallel classical machine. These eigenstates
>> interact in an exponentially large manner as the computer steps along.
>Ok, so we know the result's in there somewhere...
>...but how do we get it out?
I am only up to the part in the book where the authors are discussing
the Feynmann quantum computer. In his design, there are so-called
cursor qubits (quantum bits) that keep track of how far the
computation has progressed internally. Once the cursor shows up at the
last posible position, the calculation is finished and the answer is
guaranteed to be correct.
Interestingly each time the simulation is run it takes a different
number of steps to get the answer, since the machine evolves
differently each time. IOW, the time to completion of the computation
is indeterminant.
Bob Knauer
"Did you ever notice that when a politician does get an idea
he usually gets it all wrong?"
------------------------------
From: "Rats" <[EMAIL PROTECTED]>
Subject: Re: RC4 40 bit compared to RC4 128 bit.
Date: Fri, 26 Feb 1999 08:03:02 +1300
Thank you one and all for your help!
Cheers
Rats
Rats wrote in message <7b27s5$k92$[EMAIL PROTECTED]>...
>Hi all
>
>I've been looking through the "supposed RC4 algorithm" and I believe I've
>come to grips with how it works.
>
>However what puzzles me is the referrence sometimes used to describe RC4
>i.e. RC4 40 bit and 128bit. What I don't understand is the relevance of the
>bit values since the algorithm itself doesn't seem to make any mention of
>it.
>
>Any help will be appreciated.
>
>Thanks in advance.
>
>Ratnesh Gautam
>
>P.S.
>R Knauer please don't bother replying to this posting!
>
>
------------------------------
** 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
******************************
