Cryptography-Digest Digest #890, Volume #11 Mon, 29 May 00 22:13:01 EDT
Contents:
Re: Crypto patentability (Bill Unruh)
Re: encryption without zeros (Mathew Hendry)
Re: No-Key Encryption (Bryan Olson)
Re: encryption without zeros ("Scott Fluhrer")
Re: encryption without zeros (Mathew Hendry)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (Dave Howe)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (Dave Howe)
Re: Math problem (P=NP) prize and breaking encryption (Scott Contini)
new public key? ("G. Orme")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Crypto patentability
Date: 30 May 2000 00:17:11 GMT
In <[EMAIL PROTECTED]> Mok-Kong Shen <[EMAIL PROTECTED]> writes:
>> It's not the operation in itself that's patented, but the use to which it is
>> put.
>That's o.k. Nevertheless there can be discussed what should and what
>should not be awarded patents, I believe. If an operation is used in
>a specific piece of software and the software is patented, I have no
>personal objection at all. The issue is whether I am free to use that
>same (primitive) operation in a different piece of software.
Sure that is always true. Bending a piece of wire into a certain form
for holding paper was patentable and was patented. Bending wire for
other puposes was not covered by that patent and could be done with
impunity. Not just the process but the purpose of th eprocess are
important. The patentor must tread carefully, since if he makes his
patent too broad, it could be declared invalid because one of the
things it was claimed to cover could not be patented, thus invalidating
the whole thing.
However, in the case of software, I find it hard to find a justification
for patents. Since software must be readable by computer, and thus also
( with more work) by humans, it is very very hard to maintain trade
secrecy. The publication of the patented process is the primary reason
for patents. Why should society grant a monopoly when it gets little in
return it would not get anyway? (Of course some people are of the
opinion that monopolies are a good thing, especially if granted to them.
I had thought however that this was always one of the chief criticisms
of the Soviet system-- the state granting monopolies)
>M. K. Shen
------------------------------
From: Mathew Hendry <[EMAIL PROTECTED]>
Subject: Re: encryption without zeros
Date: Tue, 30 May 2000 01:22:00 +0100
On 29 May 2000 19:02:49 GMT, Postmaster@[127.0.0.1] (real address at end of
post) wrote:
>> > :> lcs Mixmaster Remailer <[EMAIL PROTECTED]> wrote:
>> > :> > block through the encryption function again, and repeat until you
>> > :> > don't get any zeros.
>
>[much snippage]
>
>Also, this method leaks timing info which can not be compensated because
>of the non-determinism.
How would such timing info help an attacker?
-- Mat.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Date: Tue, 30 May 2000 00:24:32 GMT
Steve Roberts wrote:
> Er, ROT-13 *does* have a key - it's the "13" in the name. Maybe it
> could be called "Known-Key Encryption"
I suppose that's arguable.
What I'm going to argue is that ROT-13 is not even
encryption as we use the term today. ROT-13 lacks the
defining adversarial characteristic, since it is designed to
keep plaintext from exactly those who do not want to see it.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: encryption without zeros
Date: Mon, 29 May 2000 17:16:25 -0700
Mathew Hendry <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On 29 May 2000 19:02:49 GMT, Postmaster@[127.0.0.1] (real address at end
of
> post) wrote:
>
> >> > :> lcs Mixmaster Remailer <[EMAIL PROTECTED]> wrote:
> >> > :> > block through the encryption function again, and repeat until
you
> >> > :> > don't get any zeros.
> >
> >[much snippage]
> >
> >Also, this method leaks timing info which can not be compensated because
> >of the non-determinism.
>
> How would such timing info help an attacker?
If you send an 8 block message, and the attacker can determine that it took
long enough to actually encrypt 10 blocks, then he has a good guess that two
of the blocks has a zero in them when they were encrypted, and had to be
re-encrypted (or, possibly, one of the blocks had to be encrypted three
times).
Now, this is leaking information. Not much, though, and it's by no means
obvious how the attacker could use this.
--
poncho
------------------------------
From: Mathew Hendry <[EMAIL PROTECTED]>
Subject: Re: encryption without zeros
Date: Tue, 30 May 2000 01:43:32 +0100
On Mon, 29 May 2000 17:16:25 -0700, "Scott Fluhrer" <[EMAIL PROTECTED]>
wrote:
>Mathew Hendry <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> On 29 May 2000 19:02:49 GMT, Postmaster@[127.0.0.1] (real address at end
>> of
>> post) wrote:
>>
>> >> > :> lcs Mixmaster Remailer <[EMAIL PROTECTED]> wrote:
>> >> > :> > block through the encryption function again, and repeat until
>> >> > :> > you
>> >> > :> > don't get any zeros.
>> >
>> >[much snippage]
>> >
>> >Also, this method leaks timing info which can not be compensated because
>> >of the non-determinism.
>>
>> How would such timing info help an attacker?
>
>If you send an 8 block message, and the attacker can determine that it took
>long enough to actually encrypt 10 blocks, then he has a good guess that two
>of the blocks has a zero in them when they were encrypted, and had to be
>re-encrypted (or, possibly, one of the blocks had to be encrypted three
>times).
>
>Now, this is leaking information.
Yes, I figured out that much. ;)
>Not much, though, and it's by no means
>obvious how the attacker could use this.
That's more what I was getting at.
-- Mat.
------------------------------
From: Dave Howe <DHowe@hawkswing>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Tue, 30 May 2000 02:04:35 +0100
Reply-To: DHowe@get_email_from_sig
In our last episode (<alt.security.pgp>[Mon, 29 May 2000 19:51:59
+0000]), [EMAIL PROTECTED] (David Boothroyd) said :
>In article <[EMAIL PROTECTED]>, Adrian Kennard
><[EMAIL PROTECTED]> wrote:
>> David Boothroyd wrote:
>> >...
>> > I thought you said you were too young. The Poll Tax was replaced because
>> > Conservative MPs realised it was too unpopular. The idea that the police
>> > being able to demand that encrypted data (about which they have a reasonable
>> > suspicion) be decrypted is in some way unreasonable is absurd.
>> The idea that the police may have unfounded suspicion.
>Then they will find the decrypted document does not contain anything
>wrong, and no further action will be taken.
That's not the point.
Ok, Lets take a hyperthetical case.
Five years from now, you are negotiating to buy a house from it's
previous owner. Unfortunately, that previous owner is under suspicion
for Tax Evasion (note - we are talking a tax offence here, not a "four
horseman" crime).
You exchange digitally signed, encrypted mail routinely, after one
of your business deals went sour a couple of years ago after a hacker
got access to another firm's corporate email, and managed to undercut
every bid that company had made, including the one you had an interest
in. Negotiations with the former owner (currently abroad, probably
Spain) are taking place via encrypted email.
The Inland Revenue have intercepted and seized copies of all his
email under an appropriate order, which is redirected in such a way
that encrypted mail does NOT get forwarded to you until they approve
it. They come to you demanding a key. However:
1. That key protects legally-priviledged communications between you
and your lawyer; these cover not only the contract negotiation for the
house, but several queries you have made on the legal limits of your
NDA with your current employer, should you choose to accept a job
offer from their biggest competitor; you haven't decided if the job
offer is enough yet, or even if you want to leave your current
employer at all.
2. Your recently married wife has a digital camera, and took several
snaps of herself while abroad, to stop you getting so lonely; She
emailled these (non-illegal, but embarrassing for her if they got into
the wrong hands) piccies to you, first protecting them with your key.
3. You have negotiated several good prices from a supplier that you
have used to put in a VERY good bid for a contract; your competitors
would be *very* interested in this information if they could get it -
certainly enough to pay a decent bribe if approached.
4. You had to work overtime a couple of months ago, with no notice,
and therefore had to cancel a holiday you had planned. You made your
private feelings on your current boss, his probable sexual preferences
and skill levels, and exactly what you would like to have happen to
him pretty plain in a email to some friends that DID go on that
holiday; Things are all smoothed over now, but you would almost
certainly have no chance of advancement with your current employer if
he ever saw it.
5. One of your ex-girlfriends emailled you with a rather sad warning
- she is HIV positive. She suggests that you get a test (even though
it HAS been a few years) just to be on the safe side.
If the key you are obliged to hand over unlocks ALL of that, to a Tax
investigator, who has a complete set of your email going back a year,
how much trust are you willing to place that he will discard and
forget the stuff that isnt' relevant? Will your wife suddenly find
she has been added to a website? Will your current boss, potential
employer or competitors get an interesting phone call from someone who
cleans in the IR offices? How do you feel to find that communications
that you thought were private are now potentially available to whoever
will pay, just because someone in the Tax Office assumes a person not
even in the country has evaded tax?
>I'm sure many people interviewed by the police do not wish to disclose
>things. This does not cause particular problems now.
>> The idea that the data may not be encrypted, or the suspect
>> may not have the key and cannot prove this. After all, if plod
>> knew what it was then they would not need the key - they must have
>> only suspicions.
>People cannot be put in jail because they have lost their keys, as
>Ministers have made clear during debate on the bill.
indeed - unfortunately, the BILL does'nt say this. We are told it will
be in the Code of Practice... Now, isn't that a wonderful safeguard?
Why not save time and rewrite the bill to say that the Home Secretary
or such other persons that he specifies in the Code of Practice may
override any or all laws applicable to collection of evidence, privacy
in the home or in presumed private areas (hotel rooms, changing rooms,
church confessionals) provided he stays within the Code of Practice he
gets to write and indeed can rewrite if he wants to?
I *would* suggest that they add that the executor of the warrant (who
may not be on the list the HS specified) may perform any action he
wishes within the wording of the warrant (however unreasonable, and
regardless of if this means ignoring the Code of Practice) and be
completely in the clear - but this is already the case!
>
>Without this bill criminals will get away with it. With it they will
>not. It's a simple as that.
No, without this bill, Criminals will get away with it. WITH this
bill, criminals will CONTINUE to get away with it, but innocent people
and companies will have their privacy violated. There are several
ways to work around this if you have (or can buy) the skill, provided
both ends of the transaction want it that way. Messaging systems can
be set up so that the key cannot be recovered - actual message traffic
is worthless. The simplest way of doing this involves having both
people online at the same time - not really that unreasonable given
today's cable and ADSL modems.
------------------------------
From: Dave Howe <DHowe@hawkswing>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Tue, 30 May 2000 02:04:37 +0100
Reply-To: DHowe@get_email_from_sig
In our last episode (<alt.security.pgp>[Mon, 29 May 2000 19:55:23
+0000]), [EMAIL PROTECTED] (David Boothroyd) said :
>In article <8gu8im$762$[EMAIL PROTECTED]>, "Steve Walker"
><[EMAIL PROTECTED]> wrote:
>> Of course it's unreasonable, you pillock. Because *they* define
>> 'reasonable suspicion',
>No, the court decides it.
This is the court that doesn't get to see the order unless you refuse
to hand over the key? You *do* remember that these can be issued by a
wide range of people don't you...
>> and we know that whenever *they* have had powers to invade privacy in
>> the past, these have been used against political and social targets too.
>"They" in that paragraph begins to sound paranoid. There are inevitably
>cases in which the police have gone too far. That does not amount to any
>sort of argument against police powers in general.
Yes, it does - What we have here is a law that is useless against any
crime that carries a heavier maximum sentence than the two-year
"refusal to hand over key" one (and I suspect that "refusal to assist
the police in convicting me) will have less side-effects once you get
in prison than "convicted child abuser" for example...) Once they
figure that out, then they won't even bother trying it on the Four
Horseman, but it will come in very handy when investigating (for
example) tax fraud. obviously, this may mean that they demand keys to
online shopping and online banking, but I don't imagine that worries
you, does it? after all, nothing you have bought online and nothing in
your bank records needs protection....
>
>> You are approving of a law which will make it a criminal offence to have
>> privacy.
>It does not.
You are actually right here - it just makes it a criminal offence to
hide your communications from a Home Office designated list of people
if they decide to ask you to unlock it, or tell anyone your
communications are being read. You may still keep your privacy for as
long as they let you.
However, they do indeed NEED this bill. IIRC, some recent "bugging"
cases were overturned in the ECHR, because there wasn't a law
explicitly authorising it to take place (there wasn't a law banning
it, so they were just going ahead and doing it anyhow). It seems the
ECHR doesn't care how reasonable or unreasonable the law is, just that
there is one - it is a case of "the victim must know that it is legal
for him to be compromised in this fashion, so he can regulate his own
behaviour accordingly" so that as long as the victim knows he COULD be
tapped, it is ok.
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: 30 May 2000 01:53:08 GMT
In article <[EMAIL PROTECTED]>,
root <[EMAIL PROTECTED]> wrote:
>And now I would like to make a further request of you (and a small
>confession).
>
>First the confession. About 4 years ago I developed an algorithm that
>seems to solve the Hamilton Cycle problem. I've only tested it on random
>graphs up to 100 nodes. My exhaustive search algorithm became ineffective
>at approximately 30 to 50 nodes, so I haven't been able to check the larger
>graphs. It is not perfect. If there is no cycle, it is fast and right
>every time. If there is a unique cycle, it is fast and finds it immediately.
I believe that the hamiltonian cycle problem requires you to determine
if a cycle exists ... It doesn't require you to find all such cycles.
>The problem is if there are sub cycles or multiple cycles. As the number
>of cycles grows, the solution time grows also (I suspect it grows
>combinatorically). A 100 node graph took approximately 5 minutes to solve
>on an Intel 486DX2 66(or maybe it was an AMD 486DX4 133). The exhaustive
>search would run for days, and would still be running when a killed it.
>
>Now the request. I realize after seeing all of your comments above that
>it must seem unlikely that my claim is true. How would you go about
>the process of verifying and publicizing such an algorithm if you were
>me? Do I just post my (beginners C++) code on the internet or an ftp
>site? Do I write an article (horrors)? I have to confess that once the
>problem was solved, my interest declined quickly. I got a tepid response
>on inquiries as to whether it was important (I didn't ask here).
>Rehashing and improving it or documenting it seemed tedious. I moved on
>to other things. The article in the paper spurred me to investigate
>again, possibly pursue publication.
>
It is good that you realize that it is unlikely that your claim is true,
because (sorry for sounding so negative), it certainly is not true.
There are hundreds of people to claim to have algorithms to solve
NP-complete problems, but these people can generally be classified
as crackpots. Although there is no proof, you first should accept
that P != NP and try to find the error in the analysis of your
algorithm.
On the other hand, I'll try to sound a little less negative and say
that your algorithm may be of value regardless. There is a lot of
research on determining what are the hard instances of these problems,
and which instances can be solved quickly. I suggest you look at the
research that other people have done on this problem and compare it
to your own. I also suggest that you try to characterize the type of
graphs that your algorithm fails on, or takes more than polynomial time
on.
If you really want to get a good understanding of the difficulty
of solving an NP-complete problem, and if you have a lot of free
time on your hands, I suggest you try this exercise: Write a
program that will reduce the factorization of an integer (where
the user inputs the integer) to the hamiltonian cycle problem.
Then see what integers you can factor with your hamiltonian cycle
algorithm, and which ones you can't. I think a lot of people
would be interested in seeing the code for a program that does
such a reduction!
Scott
------------------------------
From: "G. Orme" <[EMAIL PROTECTED]>
Subject: new public key?
Date: Tue, 30 May 2000 02:01:48 GMT
Hi,
Many encryption programs work on calculations that are easy to do one
way, but hard to do in reverse. For example 2 large numbers x and y
multiplied together makes a number xy often difficult to factor. Has anyone
tried finding the xth root of y and the yth root of x? These would both give
an irrational number hard to find x and y, usable then as a public key. One
might also have a convention of discarding the first say 100 digits as it
makes it that much longer to try different combinations to find x and y, as
someone must calculate the first 100 digits taking more time. This also has
the advantage that one can continue to use the same key for longer. One
might use the first n digits as a key, then the next time use the next n
digits, and so on as long as is safe.
Also this can eliminate communication between two parties. Say there are
many published keys in the form xy, and 2 parties look up x and y. A sends a
message encrypted by the xth root of y to B, who checks that the key is
either the xth root of y or the yth root of x. B then picks the one A didn't
use then encrypts with that and sends a message back to A. They then use
additional digits from this as long as is secure.
------------------------------
** 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
******************************
