Cryptography-Digest Digest #290, Volume #10 Tue, 21 Sep 99 21:13:03 EDT
Contents:
Re: Q: Is this key-exchange OK? (David P Jablon)
Re: Second "_NSAKey" ("Trevor Jackson, III")
Re: crypto papers (Tom St Denis)
Re: Second "_NSAKey" ("Trevor Jackson, III")
Re: frequency of prime numbers? ("Trevor Jackson, III")
Re: crypto export rules changing (Greg)
Re: EAR Relaxed? Really? ("Trevor Jackson, III")
Re: Exclusive Or (XOR) Knapsacks ("rosi")
Re: frequency of prime numbers? ("Trevor Jackson, III")
Re: frequency of prime numbers? ("Trevor Jackson, III")
Re: Schrodinger's Cat and *really* good compression ("Trevor Jackson, III")
Re: crypto papers (David A Molnar)
Re: some information theory (SCOTT19U.ZIP_GUY)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David P Jablon)
Subject: Re: Q: Is this key-exchange OK?
Date: Tue, 21 Sep 1999 22:42:47 GMT
In article <dsTF3.19008$[EMAIL PROTECTED]>,
Douglas Clowes <[EMAIL PROTECTED]> wrote:
>>> ... Is this open to attack? If so, how do I secure it?
>> [Tom Wu wrote:]
>>These are all slower and less secure than established password methods
>>like SRP, SPEKE, and EKE. Read up on them at:
>>
>>http://srp.stanford.edu/srp/
>>http://www.integritysciences.com/~dpj/
>
>These all seem to be four or more messages. My goal is two.
The shortest forms of mutually authenticating protocols that
result in explicit confirmation of both parties require
three messages. Several forms of SPEKE, EKE, and related
protocols have been published with 3-message formats.
These protocols can also scale down to 2-message protocols
if you loosen-up on the requirements, like getting rid of
explicit authentication of A to B. Some 2-message forms
were described in a 1999 paper by Perlman and Kaufman
<www.IntegritySciences.com/links.html#PK99>.
======================================================
David P. Jablon
Integrity Sciences, Inc.
[EMAIL PROTECTED]
<http://www.IntegritySciences.com>
------------------------------
Date: Tue, 21 Sep 1999 19:48:44 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Second "_NSAKey"
Greg wrote:
> > Occam's razor indicates that we need not invoke any dark
> > agencies in order to explain the facts available.
>
> Uh Hmmmm.. I would disagree here. The NSA is the MOST viable
> suspect to consider since it must sign off on any export license.
> This would be far too convenient NOT to ask for a key of their own.
If you want to speculate on the motives of the NSA go ahead. But if you
want to explain the _NSAKEY variable in Microsoft(tm)'s software there
is no need to invoke the NSA, little green men, or Elvis.
lease do not misinterpret this statement. It is entirely possible that
the NSA had a hand is whatever nefarious activities are being hidden.
But we have no evidence of that. Nor do we need to assume their
participation. Microsoft(tm) is perfectly capable of concocting this
mess all by their lonesome.
>
>
> --
> Truth is first ridiculed, then violently opposed, and then it is
> accepted as self evident ("obvious").
>
> I love my president... I love my president... I love my president...
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: crypto papers
Date: Tue, 21 Sep 1999 22:53:26 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> i think it is a very good idea but it will be more convenient to
> share them through a web or a ftp site.
True but I don't have the 46 mb to host them.
BTW when I pasted the list in it had carriage returns I don't know why it
formatted like that and I barely care. If you want a copy of the list email
me at [EMAIL PROTECTED]
The only reason I offer this is because when I started in crypto I found it
really tedius to find anything worth reading... the list of papers is about 6
months of work or so...
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
Date: Tue, 21 Sep 1999 19:56:22 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Second "_NSAKey"
Greg wrote:
> > Does anyone want to explain how this purported "back door"
> > operates, even if the NSA does hold the matching private key
> > (MS claim they don't)?
>
> Let's say you are the NSA and you want to stop my encryption
> from keeping your eyes shut to my e-mail. You slip in (and who
> is to say MS has not provided this means either?) your own CPDLL
> that will broadcast to your covert site my plain text in simply
> crypto, but it also encrypts as it normally would. You have
> now a CPDLL operating off the NSA key that does more than encrypt-
> it spills the plain text to the NSA.
>
> > I believe that even if the NSA has the key, it doesn't further
> > weaken the already fatally flawed MS operating systems
>
> I agree...
>
> > (in other words, to use the NSAkey requires greater access
> > to the machine than can be gained from using the key).
>
> But you assume it is hard for them. What if MS made it easy?
>
> >I also believe that the good folks at Cryptonym know that,
> > but didn't want to let the facts get in the way of a good story.
>
> It is more than a good story. It represents conspiracy to commit
> fraud between MS and NSA. This is obvious.
>
> > Why do so many people wishing to defend intellectual freedom undermine
> > their case by using political/nonrational statements as weapons?
>
> Because it's fun? :)
>
> No, seriously, this is one time NSA has been caught with its
> pants down.
In what sense has the NSA been caught? None that I can see.
Certainly the agency might be interested in compromising the vast number of
machines now in use. But this was crude. Amateurish. I suspect the agency
simply isn't that crude.
Consider that you are assuming a vast bureaucratic conspiracy where none may
exist. But if it did/does exist, and Microsoft(tm) were doing NSA's
bidding, they could simply weaken critical aspects of the CryptoAPI and
traceless ly (note that word -- it is important) read the bulk of the data
secured under Microsoft(tm)'s OS.
The last thing they would do is attempt a hole for the insertion of a trojan
horse crypto DLL. the hole leaves traces. Inserting the the DLL leaves
footprints. And anyone who detected such a trojan (and someone, or many,
would) would have the equivalent of a smoking gun.
I suspect this is proof not of a vast bureaucractic conspiracy but of simple
stupidity. Lots of it.
> And for all we know, someone at MS allowed the
> symbols to ship in hopes it would be discovered. Perhaps they
> resent big brother?
You may have a future in comedy!
------------------------------
Date: Tue, 21 Sep 1999 19:40:12 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Boris Kolar wrote:
> Bob was right. There are true statements that can't be proved. One of such
> statements is "This axiomatic system is consistent" (for some axiomatic
> systems). Obviously it can be either true or false. But if the axiomatic
> system is rich enough, the statement can't be proved.
In what sense is the statement true then?
>
>
> Donald Welsh <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > On Fri, 06 Aug 1999 17:27:45 GMT, Bob Silverman <[EMAIL PROTECTED]> wrote:
> >
> > >No. What Goedel showed was that any sufficiently rich axiomatic
> > >system is incomplete in the sense that there are true statements
> > >which can not be proved. [as well as other stuff I won't discuss].
> > >Peano arithmetic is "sufficiently rich", BTW.
> >
> > I'd like to correct this misconception, if I may. Godel's theorem
> > does not say that "there are true statements that cannot be proved".
> > It says that there are unprovable statements. These statements are
> > neither true nor false.
> >
------------------------------
From: Greg <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: crypto export rules changing
Date: Tue, 21 Sep 1999 01:46:57 GMT
The only true liberalization that can occur with any meaningful
results is the total freedom for any American to publish, sell,
or distribute strong encryption any way, time, or amount.
ANY licensing by the government constitutes compromised software.
No one will ever be able to have confidence that the software they
are using has a trap door courtesy of NSA secret requirements if
it had to pass NSA for a government license.
--
Truth is first ridiculed, then violently opposed, and then it is
accepted as self evident ("obvious").
I love my president... I love my president... I love my president...
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
Date: Tue, 21 Sep 1999 19:27:47 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: EAR Relaxed? Really?
Douglas A. Gwyn wrote:
> Greg wrote:
> > .... What market exists today anywhere in the world
> > for use of 128 bit compromised (by definition of NSA examination)
> > encryption software?
>
> Why is that "compromised"? It is axiomatic in cryptology that
> the strength of a cryptosystem should not depend on the adversary's
> lack of knowledge of the general system, but only upon the key.
>
> The interesting question is whether the "technical review"
> will be allowed to end with the product failing to be approved
> (presumably because it is too secure, although that might not
> be the officially stated reason).
Preciely because the review is either bureaucratic nonsense or a
meaningful restriction on exports. If it is meaningful -- establishes a
ceiling on strength -- then all approved products are weaker than those
not approved. Those that are weaker are reasonably considered
compromised because an implementor will put in the strongest available
techniques. Unfortunately this may cause rejection, in reaction to
which the implementer will reduce the strength of the system, en effect
compromising it.
I believe it to be a fair usage of the term.
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Exclusive Or (XOR) Knapsacks
Date: Mon, 20 Sep 1999 21:13:14 -0400
Dear Tim,
I think you are right. GE can not answer the negative efficiently (or
even
effectively) in all cases. I do not want NP=P in any of such proper form
other than the improper one (yes, which?).
The answers people try to provide (based on their best judgement) are
very much dependent on the actual question asked. I for one went a bit
too far. I apologize. It is not a sin or any such to discuss such a subject
giving one's own view. Unless we know what this XOR is to achieve, it
is not easy to answer satisfactorily. I can not.
I repeat, if using 'the XOR' as a hash, it may not be secure. GE poses a
threat but GE, IMO, does not solve the problem. I can be wrong, but I need a
proof, and not just an example of a solution. I will NOT take it as NP=P.
I simply won't. I think I made it clear that David Wagner is right ONLY in
a particular sense (referring to his word 'solve', which you tried to
clarify).
It is now quite obvious that David was talking in that sense and he is right
in that sense, yet not necessarily in all senses. But before Gary gave more
specifics, I was not sure his application would face a threat for sure, for
I did
not know what application it would be.
I have no stomach to turn my self into a saint and make any war I engage
in a holy one. There are many things I can ramble into garbage, but this is
one I think may clarify some.
Given such a matrix, the XOR'd result (of the elements) in a 'controlled'
way, can yield a stream that can be useful. So it much depends on what
the application is. _AND_ it depends on the definition of one-way. I believe
Gary will not find people's sincere viewpoints, be they right or wrong,
rambling garbage. Once again, Gary, REMEMBER! given a bit value, for
example, knowing only that it is the XOR of n (unknow number of) bits is
ONE-WAY! That is, sticking strictly the the word "one-way", you can not
get back to the n bits that produced it. (I know, if I do not get it to the
Turing
Machinery kind of granuity, I will always be in trouble. But please do not
drag me in. :)) Every reader can go and perform the tests with GE and see
if that is or is not one-way. This request I sincerely hope will not be
taken as
abuse.
There is one type of garbage: deliberate falsehood, that is, with the
knowledge of something being false, trying every way to defend it. Luckily,
we do not have that here.
Thank you very much Tim and thank all who sincerely participated in the
discussion.
--- (My Signature)
Tim Tyler wrote in message ...
>David Wagner <[EMAIL PROTECTED]> wrote:
>: Gary <[EMAIL PROTECTED]> wrote:
>
>:> Problem:
>:> Given an n bit number X and a set {B1,B2,...,Bn} of n bit numbers;is
there a
>:> subset whose elements collectively XORed give X?
>:>
>:> Can the general problem be solved easily?
>
>: Yes. Gaussian elimination will solve it in O(n^3) time.
>
>...assuming it has any solutions in the first place, that is.
>--
>__________
> |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
>
>Drilling for oil is boring.
------------------------------
Date: Tue, 21 Sep 1999 19:41:09 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Douglas A. Gwyn wrote:
> Donald Welsh wrote:
> > I'd like to correct this misconception, if I may. Godel's theorem
> > does not say that "there are true statements that cannot be proved".
> > It says that there are unprovable statements. These statements are
> > neither true nor false.
>
> False unprovable statements are trivial. Goedel's result
> pertains to statements that are true, yet unprovable within
> the given axiomatic system.
Really. Do you have a trivial solution to the (false) statement "Turing
machine N halts?"
------------------------------
Date: Tue, 21 Sep 1999 19:42:10 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Tim Tyler wrote:
> Donald Welsh <[EMAIL PROTECTED]> wrote:
> : On Fri, 06 Aug 1999 17:27:45 GMT, Bob Silverman <[EMAIL PROTECTED]> wrote:
>
> :>No. What Goedel showed was that any sufficiently rich axiomatic
> :>system is incomplete in the sense that there are true statements
> :>which can not be proved. [...]
>
> : I'd like to correct this misconception, if I may. Godel's theorem
> : does not say that "there are true statements that cannot be proved".
> : It says that there are unprovable statements. These statements are
> : neither true nor false.
>
> Such statements are neither true nor false *from within the axiom system
> in question*.
>
> Calling it a misconception may be a bit strong: Godel demonstrated
> sentences which read like "axiom set X can never prove this statement to
> be true", which an external observer not bound by axiom set X genuinely
> *could* verify as being true statements.
But an external observer not bound by axiom set X can also show the statement
as false.
> --
> __________
> |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
>
> Thus quoth the raven: "Eat my shorts!"
------------------------------
Date: Tue, 21 Sep 1999 19:35:08 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Schrodinger's Cat and *really* good compression
Erwin Bolwidt wrote:
> "Douglas A. Gwyn" wrote:
>
> > [EMAIL PROTECTED] wrote:
> > > And here we come to Schrodinger's cat. One of the interpretations of
> > > quantum mechanics held that a superposed quantum state did not resolve
> > > itself into one state until it was exposed to the gaze of a *human
> > > observer*.
> >
> > The point of Schr�dinger's cat is that it points up the logical
> > problem with that interpretation (which seems to have fooled
> > Roger Penrose too) -- why can't the cat play the role of observer?
Just to confuse the issue, one of the first examples of superposition was that
of a cat enclosed in a box with a radioactive substance whose emission would
trigger the death of the cat. To an observer who has not opened the box the
contents are described best as a superposition of a dead cat and a live cat. To
an observer watching someone else open the box, the best description of the
someone else is a superposition of a person seeing a dead cat and a person
seeing a live cat. But these are indistinguishable, which leads to some
problems with the theory. Indistinguishable states are the same state. There's
no possible wave collapse.
Now, when you make the cat an observer you end up with the superposition of a
dead observer and a live observer. I'd like to referee the superposition of the
papers they'd write.
Anyway, the superposition of a live observer cat and a dead (nonobserver) cat
may be best represented by the Cheshire cat. Half there and half not. And it
knows the difference and you don't. That's why its smiling.
>
>
> Isn't that the problem; who observes the observer?
> If you checked on the cat and I haven't spoken with you, isn't the state of
> the cat still undefined to me? And (let's not make this personal) if the
> observer dies before having spoken to anyone, isn't the state of the cat
> completely undefined again?
>
> (At least until a technique is known to read memories out of human brain
> tissue)
>
> I guess what I'm wondering is, does nature take into account the
> peculiarities of human consciousness; if you've seen something, spoke to me,
> but didn't tell me what you saw, is that something still undefined to me, or
> is it defined to me because we exchanged photons and my quantum state has
> merged with yours?
>
> >
> > A self-consistent quantum theory of measurement has to be apply to
> > the measuring device as well as to the object being measured.
> > There *is* at least one such theory in general use today.
>
> Erwin
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: crypto papers
Date: 21 Sep 1999 23:38:19 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> The only reason I offer this is because when I started in crypto I found it
> really tedius to find anything worth reading... the list of papers is about 6
> months of work or so...
Maybe an annotated bibliography would be good, then ? You can put up the
list, plus some notes on "I liked this paper," or "Not very clear why this
was written," or whatever. It'll take 10K max. Then at the bottom note
that you are willing to e-mail papers out.
-David
------------------------------
From: SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]>
Subject: Re: some information theory
Date: Wed, 22 Sep 1999 00:04:12 GMT
In article <[EMAIL PROTECTED]>,
Anti-Spam <[EMAIL PROTECTED]> wrote:
> SCOTT19U.ZIP_GUY wrote:
> >
> > In article <[EMAIL PROTECTED]>, Anti-Spam
<[EMAIL PROTECTED]> wrote:
> > >Tim Tyler wrote:
> > >>
> > >**** WHOLE LOTTA LOTTA STUFF WE FAST FORWARD OVER *****
>
> > >
> > >
> > >The statement on resulting bit-stream pseudo-randomness still
stands as
> > >true for the use of a binary file. If the algorithm used to
compress
> > >the original file into a "compressed and *random* " output file
relies
> > >only and totally on any or all possible substring (bit patterns) in
the
> > >original uncompressed file, in any combination, accessed in any
order
> > >(front of file, back of file, middles of file, round and round
file..)
> > >no matter how complex, involuted and twisted, AND this operation
must
> > >reverse the process on the compressed output to reproduce the
original
> > >input, the result will be a new file of bits whose substrings will
> > >evidence some correlations and thus fail some or all tests for
> > >statistically valid random bit patterns.
> > >
> > >Random bits exhibit no correlation or dependence on any bits that
appear
> > >before them or that follow them in the file. Unless randomness is
> > >injected into the process of compression from some true random
exernal
> > >source, the resulting file's bits are pseudo-random.
> >
> > Actually it is very hard to define what a random file is. Once
you have
> > any file and start talking about it. It is not random but you could
make
> > up some defination that if it passes some certain tests. You could
call
> > it random. But if you keep making up more tests there are really no
random
> > files. But if you take what you call a random file by your tests.
And if you
> > run my decompression method. You will get a nonrandom file by some
> > of your tests. You may have to run it more than once if you cooked
the
> > example by compressing a random file to get another random file. But
> > the expanded file will most likely not pass all your random tests.
> > Do something your mind my think is fair using quatum measurements.
> > Take many long runs. Most but not all will pass your test for
randomness.
> > The fact is a random file really refers to how the file was
generated but
> > it can still fail your tests for randomness. And just becuase it
fails does
> > not mean it was not generated in a random way. But take one that
> > passes all your tests. Decompress it. It will more than likely fail
> > your test for randomness even though the compressed specially
> > generated file passes. I know this is hard for you to grasp but
> > think about it.
> >
>
> Not hard to grasp, the point is already understood. The tests for
> randomness provide only confidence levels as to the likelihood that
the
> observed bits are from a random source. A truly random source
produces
> an output (bits in this case) whose values at any instant are
> uncorrelated with any future or past output value. The standard
> statisitical tests to which I refer provide a probabalistic estimate
as
> to just how likely it is that the observed sequence came from such a
> source.
>
> The tests of which I speak only tell us this - if a sequence fails any
> one of the tests to the level of confidence chosen, we can chose to
> reject this sequence as originating from a random source. We could
look
> at some more of the sequences and judge again, and if it continues to
> fail one or more tests, reject it as random with some probability (as
> given by the level of confidence). There is a finite probablity for a
> truely random sequence to fail one or more of the tests. To do so
> repeatedly is less probable, but still there's a non-zero probability.
>
> If the sequence passes all of the tests to the level of confidence
> chosen, we can accept it with some probability (as given by the
> confidence levels) as coming from a random source.
>
> The confidence levels can be set so high that even a sizable number
of
> true random sequences fail them (false negatives.) The levels can be
> set so low that a sizable number of pseudo-random sequences can pass
> them (false positives.)
>
> A deterministic, fully reverseable (no matter how "gnarly") algorithm
> applied to determinstic data/files to generate an output faces in
> general a tough row to hoe when trying to pass all of those tests with
a
> high level of confidence. Look at the history of pseudo-random number
> generators. Quite a few of them can be successfully predicted by
> algorithms fed just short lengths of their outputs. Linear
Congruential
> Generators are a good example. Jim Reeds and Joan Boyar showed us that
> LCGs are entirely predictable. And Linear Feedback Shift Registers
fell
> to the Berlekamp-Massey Algorithm.
>
> I do encourage you to continue your research with your compression
> algorithm, and I suggest an analysis of it in the same vein as Jim
> Reed's, Joan Boyar's, Berlekamp and Massey's analyses on those other
> algorithms.
I think you miss the while point. While it is nice that a compressed
file fails many more random tests than whatever you feel like calling
a random file. The whole thrust of these discussion was that it is
better to use a compressor that is "one to one" since if you don't you
immedately give information to an attacker about your encryption
key since whole classes of keys may be eliminated from consideration
if they lead to cases that can't decompress. This is true even if
the user was sending random files.
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
** 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
******************************
