Cryptography-Digest Digest #276, Volume #10 Mon, 20 Sep 99 01:13:03 EDT
Contents:
Re: Exclusive Or (XOR) Knapsacks ("rosi")
Re: Exclusive Or (XOR) Knapsacks ("rosi")
Re: unix clippers that implement strong crypto. (SCOTT19U.ZIP_GUY)
Re: Schrodinger's Cat and *really* good compression ("Douglas A. Gwyn")
Re: Second "_NSAKey" ("Douglas A. Gwyn")
Linear and differential analysis (Mathew P.)
Re: Clinton Administration Continues to BS on Encryption Export Regs ("ALF")
Re: Okay "experts," how do you do it? (Sundial Services)
Re: Okay "experts," how do you do it? ("Douglas A. Gwyn")
Re: unix clippers that implement strong crypto. (Terry Ritter)
Re: Linear and differential analysis (Sundial Services)
----------------------------------------------------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Exclusive Or (XOR) Knapsacks
Date: Sun, 19 Sep 1999 20:32:11 -0400
First, to make sure that I was properly understood (if not, no one's fault).
I am
making it explicit: I was talking about more-elements-than-bits. That way
the density can be high and provide other 'nice' properties.
GL works in special cases, with a certain probability. One, I believe, can
have misses, especially when subset sum solutions (plural) abound. This is
I think a fundamental of the whole issue around subset sum as a basis
for crytography. And it is on that ground I said: a joke.
Back on track. I am sorry that I was not thinking in terms of that
particular
application and may not know enough details to say something more
definite. One thing one has to be aware is that using that as a hash type
of thing may NOT be secure. If one depends on image resistence for the
application, one has to be very careful here. I admit that I have not been a
careful thinker in that direction as I have not had particular applications
to establish the context in which to exercise my mental capacity. Just my
question. Is this application trying to solve the problem where protection
is needed for the validation code (i.e. the XOR result) to not reveal the
binary code (behind) to an interceptor? I can not come up with a more
sophisticated scenario to fit this in. Anyway, I am sorry again that I moved
too far away from the original post.
BTW, as I said, it does not matter. In certain cases, it matters whether
the contributing elements are more than the one-bits (if one picks up and
zero does not). Even a one bit can pick up more than one element to
contribute to the subset sum, in that application where image resistence
is sought, it still makes little difference. In fact, finding a collission
is even
easier. I remember a short while ago, somebody wanted to know why his
algorithm can solve subset sum problems easily. It is the same thing, the
same why. I believe David said the same thing (GL works) in this sense.
I, as always, can be wrong.
Thanks
--- (My Signature)
David Wagner wrote in message
<7rv77k$a70$[EMAIL PROTECTED]>...
>In article <[EMAIL PROTECTED]>,
>Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>> Gary wrote:
>> > What if the matrix wasn't square?
>>
>> That's a different problem. Use SVD, which should work for GF(2)
>> so far as I can see at a first glance.
>
>I think you (and another poster) misread his question.
>You're thinking of the case where the number of elements in the set
>is _less_ than the length of the bitvectors, but I believe he asked
>for the case where you have _more_ elements.
>
>Extra elements don't hurt you; Gaussian elimination still works.
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Exclusive Or (XOR) Knapsacks
Date: Sun, 19 Sep 1999 20:48:25 -0400
Dear Gary,
You may take a look at my other in response to David Wagner.
I might have missed something here. If you do not want it to be (or does
not care it to be) a trapdoor one-way, "The licensor doesn't publicise his
disguise/trapdoor technique" is a bit puzzling.
Thanks for your good questions and posts.
--- (My Signature)
Gary wrote in message ...
>Thanks for the comments guys.
>I'm very interested by the differences between summation and XOR.
>Could an XOR system be a candidate for an authentication system rather than
>a public cryptography system.
>
>Example:
>A software licensor gives a licensee a binary code which when using public
>XOR Knapsacks creates a string of a valid format allowing shareware
software
>to become registered and full featured.
>The licensor doesn't publicise his disguise/trapdoor technique.
>
>
>
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: comp.security.unix
Subject: Re: unix clippers that implement strong crypto.
Date: Mon, 20 Sep 1999 04:13:00 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Terry Ritter) wrote:
>
>On Sun, 19 Sep 1999 04:23:19 GMT, in <7s1kvo$pfu$[EMAIL PROTECTED]>, in
>sci.crypt [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
>
>>In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Terry Ritter)
> wrote:
>
>>>[...] Damages are at the
>>>heart of patent infringement litigation.
>>>
>>>Specific damages include lost royalty income and profits made from
>>>infringement. In "cases of flagrant and willful infringement," one
>>>could recover attorney fees with *triple* damages. Deliberately
>>>breaking a cipher well-known to be patented is clearly willful and
>>>might be flagrant.
>>>
>>
>> Terry this seems to conflict with what you just anwsered in my
>>message you just wrote:
>>
>>Maybe you have the wrong idea about patents: The whole point of a
>>patent is to *reveal* information, not protect it. It is trade
>>secrecy which hides information. A patent protects the particular
>>*use* of particular information, not learning about it.
>
>I stand by it, with the provision that I am not a patent lawyer and am
>not even trying to speak in precise legal terms. This is also an area
>rich with "terms of art," where ordinary words have been re-defined by
>laws and decisions over centuries.
>
>
>But let's try to break this up:
>
>>The above is what you just wrote on another thread. If the whole
>>point of a patent is to "reveal" information to advance the art
>>of cryptograohy
>
>To get people to reveal their private information, an issued patent
>grants to the holder the sole right to make, sell and use what is
>described in the patent. This is a motivation and compensation for
>publishing what is inherently private information. Typically these
>rights are licensed to manufacturers for a fee.
>
>>who could breaking a cipher that is well-known to
>>be patented be clearly some sort of flagrant violation when you just
>>stated you want to advance cryptography.
>
>The issue is damages. In practice, a patent is an economic right to
>recover damages from people who have infringed the patent (and to
>prevent further use, or course). Now, if the sole "use" of the patent
>was simply as an academic exercise to provide a basis for a break, it
>is my understanding that that would be difficult to see as "damage."
>But if the break were then used to exploit the information in a broken
>cipher, that *would* be use and damage, and the damage should be
>recoverable if the patented thing was being "used" without license for
>economic gain.
Ok more to the point. Do you attempt to go after the guy who
made nothing from it and showed it weak. Or do you vainly try to searh for the
guy who may have secrectly used this break to great economic advantage. Or
the guy who made money from the break not knowing it was even patented.
>
>>I think I am missing something
>>in what you mean. Since the above seem like opposites to me.
>
>Since I am unable to see the conflict, you may want to be more
>explicit about what you see.
>
>---
>Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
>Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
>
David A. Scott
--
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
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Schrodinger's Cat and *really* good compression
Date: Mon, 20 Sep 1999 03:33:08 GMT
[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?
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.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Second "_NSAKey"
Date: Mon, 20 Sep 1999 03:12:04 GMT
"Trevor Jackson, III" wrote:
> OK, assume that two keys are used for efficiency reasons. Like the
> developers get one so they can diddle around with modules and not
> threaten the master corporate key. In this and all like scenarios
> Microsoft(tm) would simply say so. They haven't. They issued a
> stupendously silly exuse.
Since what they *have* said is "stupendously silly", it is presumably
not right, or at least no more than a distortion of the truth. My
guess is that only the top execs PR staff are being allowed to make
statements on this, and the worker bees who know for sure what was
going on with this backup key have not been allowed to speak, or
maybe their explanations have been filtered through the PR distortion
machine.
> > No, we know what the capabilities of the backup key are, by an
> > examination of the object code where that key is used. It acts
> > the same as the primary key (in authenticating a module), after
> > the primary key has failed to authenticate.
> This is not convincing. By examining some of the object code you
> can show the use of the backup key in that code. But showing that
> the key is not used elsewhere requires an examination of all of the
> rest of the code. It's a negative proposition in a finite space.
> Mandates an exhaustive approach.
> Problem is that searching debug symbol tables only works if
> everything ships with debug symbols, which is not usually the case.
To the contrary, it *is* the case, for registered MSDN developers.
> Point is that it is hard to show that the key has no hidden
> functions.
But there is no reason to think it has any hidden functions; it
acts just like the primary CryptoAPI validation key in the only
places where there is any evidence of the backup key. You could
make a similar "scare tactic" claim about *anything* in the system!
I'm not sufficiently worried to grep all the symbol tables, but feel
free to do so yourself.
------------------------------
From: [EMAIL PROTECTED] (Mathew P.)
Subject: Linear and differential analysis
Date: Sun, 19 Sep 1999 02:54:18 GMT
Reply-To: [EMAIL PROTECTED]
I have two questions.
What is linear cryptoanalysis?
What is differential cryptoanalysis?
Thanks for your help,
Mathew
[EMAIL PROTECTED]
------------------------------
From: "ALF" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.privacy
Subject: Re: Clinton Administration Continues to BS on Encryption Export Regs
Date: Sun, 19 Sep 1999 19:56:59 -0700
How very true, Anthony!!! - and well stated. Governments are always
trying to control us. Its their nature. Clinton's admin is no different.
Have you tried this great Canadian progam? So far no Canadian
government intereference.
PC Encrypt - Is public-key encryption that lets you communicate securely
with people you've never met, with no secure channels needed for prior
exchange of keys. Much easier to use, and just as strong as PGP.
You can download it here: http://www.a-lock.com/_site/pce/index.mhtml
ALF
--
ALF'S PRIVACY MAIL DROP - http://stop.at/apmd
"Confidential and non-traceable way to send and receive
postal mail worldwide."
Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Clinton Administration Continues to BS on Encryption Export Regs
>
> Go to http://www.eff.org to read US Press Secretary's Press Release
>
> You cannot flip a coin and have it land BOTH heads and tails. The
> Administration's stalling tactics continue.
>
> I am not going to be satisfied until this Administration and this
> Government Unconditionally Surrenders all of its objections to
> unrestricted encryption.
>
> The Catholic Church has backed down over the centuries on the Earth
> being the center of the universe, the Heavens revolving around the
> Earth, the "tenet" of there being no such thing as action at a distance
> (radio waves), "Man" being gods special unique creation in the Universe
> (life existing only on Earth), birth control, evolution, etc.
>
> This Administration and this government must not be allowed to continue
> to restrict encryption in any manner whatsoever.
>
> This Administration must be persuaded to accept advances in technology
> and the discovery of new information just like the Church. We do not
> need violent repression from this government any more than we need
> violent repression from the church.
>
> The US government is threatening every American with arrest, jail,
> forfeiture of money and property, and even death if any American
> defies their misguided restrictions on encryption.
>
> WE have a democracy with the right to privacy, peaceful assembly, free
> speech, and justice.
>
> Restricting encryption is a clear attempt to destroy democracy with the
> right to privacy, peaceful assembly, free speech, and justice.
>
> You either have it or you don't.
------------------------------
Date: Sun, 19 Sep 1999 20:50:28 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Okay "experts," how do you do it?
Douglas A. Gwyn wrote:
> Right away, the human cryptanalyst
> thinks of trying QWERTYUIOP, because he has a "feel" for how humans
> behave. It would be inordinately hard to duplicate that in a machine.
I hear what you're saying, Mr. Gwyn, but I still think that most of the
applicability of "intuition" has gone or should have gone by the wayside
in the computer age.
Cryptosystems are computer algorithms. Nothing more or less. And we
should be able to describe the characteristics of what they must do to
the plaintext, how they must depend upon the key and upon variance in
the key. There OUGHT to be an objective test-bed that we can plug these
algorithms into, to test them.
The "first blush" approach to analyzing an algorithm might be to try to
replicate what the human does, to "duplicate human behavior in a
machine," but I'm not sure that's possible or appropriate. Quite likely
we have surpassed what humans can do, and gone into what only the
computer has any hope of doing.
It may well be that a very complex, multi-step, lots-of-twists-and-turns
algorithm turns out to be "extremely hard to step through and
'understand'," and yet "totally worthless." We could be so fascinated,
and so led off-track, by trying to 'understand' the algorithm, that we
overlook or even cannot discover the cipher's weakness.
Suppose then that somehow we tread the cipher algorithm as a black-box
function: c = f(p, k). Nothing more is known. Suddenly it's an
"unknown cipher problem" except in this case it is a "we don't care what
the cipher is" function. All we want to do is to feed it inputs and
measure characteristics of its output, and thereby ascertain the quality
and desirability of "f(p,k)" as a cipher function.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Okay "experts," how do you do it?
Date: Mon, 20 Sep 1999 03:23:50 GMT
Sundial Services wrote:
> I think it would be a fascinating research-topic to see to what extent
> we could possibly replace the human cryptologist. And in what way.
Since cryptology is a body of knowledge, it is particularly human.
I think you meant the more narrow "cryptanalyst". I'm one of several
who have worked on automated cryptanalysis over the past few decades.
The biggest problem is that cryptanalysis is not like analytical
chemistry, where there is a decision tree that if followed exactly
will tell one what the target consists of. There is certainly an
*approximate* decision tree, but unfortunately most tests are not
*decisive*, merely *indicative*. Due to the large number of possible
contexts, it is impractical to program in advance the best way to
make *guesses* based on these indications; certainly, if one always
picks "the most likely" choice, the cryptanalysis will nearly always
fail. Experienced "hunches", aka "intuition" or "insight", have
played a large role historically in practical cryptanalysis, and
we really don't know how to duplicate this phenomenon in automata.
Another factor is that humans design and use cryptosystems, so other
humans can sometimes intuit the choices that were made. For example,
suppose an operator at a keyboard has to type in a key consisting of
"10 letters chosen at random". Right away, the human cryptanalyst
thinks of trying QWERTYUIOP, because he has a "feel" for how humans
behave. It would be inordinately hard to duplicate that in a machine.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Crossposted-To: comp.security.unix
Subject: Re: unix clippers that implement strong crypto.
Date: Mon, 20 Sep 1999 03:52:18 GMT
On Mon, 20 Sep 1999 04:13:00 GMT, in <7s48od$23ns$[EMAIL PROTECTED]>, in
sci.crypt [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
>[...]
> Ok more to the point. Do you attempt to go after the guy who
>made nothing from it and showed it weak.
Not I, nor any reasonable patent holder, since there is unlikely to be
sufficient recovery to make the action worthwhile. I suspect that
such a position would be unlikely to prevail in any case.
>Or do you vainly try to searh for the
>guy who may have secrectly used this break to great economic advantage.
If there *is* great economic advantage as a consequence, that may be
hard to hide. New employees are hired, old ones do leave, and some
are disgruntled "whistle blowers." So the search may not be as vain
as one might think. And if big bucks are involved, a very substantial
search could be mounted for possible recovery.
>Or
>the guy who made money from the break not knowing it was even patented.
Somebody who is running around exploiting data hidden by a broken
cipher does so at his own risk even in the best possible case. But if
he uses the decipher system for a patented cipher, I suspect it would
be hard for him to convince a jury that he did not know about the
patent, or that the data were intended by the owner to be secret.
If such a guy causes sufficient damage to warrant legal action, he is
likely to get legal action. The patent part of this would be a civil
action, of course, not criminal. But *theft* is criminal, presumably
even data theft, as is, generally, the misuse of trade secrets.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
Date: Sun, 19 Sep 1999 20:53:12 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Linear and differential analysis
Mathew P. wrote:
>
> I have two questions.
>
> What is linear cryptoanalysis?
>
> What is differential cryptoanalysis?
There are a LOT of good cryptology pages out there on the web which
detail topics like these. Try Dr. Savard's page at:
http://fn2.freenet.edmonton.ab.ca/~jsavard/jscrypt.htm
Now to briefly nutshell your question: both of these are attacks which
try to feed a cipher known plaintexts with specific characteristics and
to learn more about (to attack) the cipher by measuring the changes in
the output produced.
Equally fascinating reading, also in abundance on the web, is how
various ciphers can be made resistant against these attacks.
------------------------------
** 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
******************************
