Cryptography-Digest Digest #900, Volume #11 Wed, 31 May 00 04:13:01 EDT
Contents:
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May ("Anarchist Lemming")
Re: any public-key algorithm (Roger Schlafly)
Re: DVD encryption secure? -- any FAQ on it ("Dulando")
Re: email list for the contest (Arthur Dardia)
Description of algorithm for hamilton cycle problem (root)
Re: Does it even matter? (Paul Rubin)
Re: Retail distributors of DES chips? (zapzing)
Re: Description of algorithm for hamilton cycle problem (David Blackman)
Number Theory Book -- one last thing for now (tomstd)
Re: Does it even matter? (David A Molnar)
Re: email list for the contest (David A Molnar)
Re: TEA analysis (Pogo)
Re: Note on the Hill cipher (II) (Mok-Kong Shen)
Re: A Family of Algorithms, Base78Ct (Mok-Kong Shen)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (George Edwards)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (George Edwards)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (George Edwards)
Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
(George Edwards)
(fwd) Internet Security Glossary (Mok-Kong Shen)
----------------------------------------------------------------------------
From: "Anarchist Lemming" <[EMAIL PROTECTED]>
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: Wed, 31 May 2000 02:13:29 +0100
Go with it!
Lemming
www.hellnet.org.uk
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: any public-key algorithm
Date: Tue, 30 May 2000 18:37:39 -0700
Eric Verheul wrote:
> > 2. its only advantage over DL in GF(p) is shorter public keys.
> Have you read the paper? Just have a look at the website then,
> there you can find the advantages, XTR is much faster than DL in GF(p) and
> so is it's key gen.
I just skimmed it. I see one comment that it is faster than DL,
but the comparison in sect. 4.4 is only to RSA and ECC, not DL.
Seems odd, since XTR is really a variation on DL.
I also didn't understand the key size comparisons, where you
claim XTR is competitive with ECC. You compare XTR over GF(p^6)
to ECC over GF(p), where p is around 2^170. ISTM an EC public
key is 170+1=171 bits plus whatever is needed for shared
parameters. But XTR need at least 1 (and maybe 3) elements
of GF(p^2), so at least 340 bits are needed, plus shared
parameters. So I don't see how XTR is competitive unless you
always send the shared parameters.
------------------------------
From: "Dulando" <[EMAIL PROTECTED]>
Subject: Re: DVD encryption secure? -- any FAQ on it
Date: Wed, 31 May 2000 01:42:30 GMT
lament wrote in message ...
>The content of a DVD movie is encrypted with the intent to prevent piracy.
However,
>every DVD player has to be able to decode the data for playback. This being
so, how
>is it possible to have security?
>
>My guess is that the DVD decoder chip has the key "hidden" in silicon
somehow, and
>that only a "few" chip designers have that information (the key). If this
assumption
>is close to correct, then it seems a doomed scheme from the outset.
>
>I completely understand why content producers want their works protected,
but I
>cannot imagine how this could ever be possible, given the consumer nature
of the
>system and the vast numbers of systems and disks involved. I wonder how
encryption is
>actually carried out on DVD. Forgive me if this has been beaten to death
before--
>perhaps there is a faq on the subject.
>
>Is there really a way to do it?
Salutations, Lament
I'll do a terse explaination on CSS (Content Scrambling System) and how it
is used on DVD players.
Well, basicly, every DVD player has a unique key to use for descrambling
which ubiquely needs to be encrypted within the program to prevent reverse
engineering of the application to determine the key. While a different key
for each player seems like a nice precaution as to not invalidate the entire
cipher if one key is discovered. However, apparantly (and this is just what
I've read) the system (CSS itself) is not the best encryption, and the
people who made DeCSS (Masters of Reverse Engineering, or MoRE) were able to
identify around fourty or fifty acceptable keys all from one original one,
which they gathered from the Xing DVD player for Windows, which was found to
not encrypt thier CSS key. (Blame RealPlayer, they made Xing).
You could probably find a more in depth description from doing a Websearch
or asking someone with more information on the subject.
Sincerely,
Michael
------------------------------
From: Arthur Dardia <[EMAIL PROTECTED]>
Subject: Re: email list for the contest
Date: Tue, 30 May 2000 21:42:47 -0400
Mok-Kong Shen wrote:
> tomstd wrote:
>
> > Here are the revelant email addys you need to know.
>
> > [snip]
>
> Since many of us are also interested in mathematics, it may be of
> interest to know that there has recently been estabished a contest
> for solving seven well-known mathematical problems, each with
> a prize of one million dollars.
>
> It would be fine, if some benevolent rich person (Gates?) could
> donate a similar prize to solve the problem of crackability of a
> certain cipher that is destined for universal use in the new millennium.
>
> M. K. Shen
My father heard this on the way to work and informed me. He said the URL
was something along the lines of claynet.org. "Under Construction?" What's
up with that?
--
Arthur Dardia Wayne Hills High School [EMAIL PROTECTED]
PGP 6.5.1 Public Key http://www.webspan.net/~ahdiii/ahdiii.asc
------------------------------
From: root <[EMAIL PROTECTED]>
Subject: Description of algorithm for hamilton cycle problem
Date: 31 May 2000 01:48:09 GMT
Axel Lindholm <[EMAIL PROTECTED]> wrote:
AL# Even though your program doesn't solve the Hamilton Cycel problem I would
AL# like to obtain a copy of your source, if you feel like sharing it with me.
AL# Also, if it's not too much to ask for, I'd love a small description of the
AL# algorithm itself.
AL# Thanks!
AL# Axel Lindholm
I can give you a brief description.
Most of the people here seem to be quite sharp, so I will not bother with
too much detail.
Set up a Simplex minimization problem with the following characteristics:
Make each row correspond to a node. (n nodes)
Make each column correspond to an edge. (m edges)
Place a 1 in the row corresponding to the nodes that
the edge connects. i.e. if edge 15 connects nodes 2
and 10, place a 1 in row 2 and a 1 in row 10 of column
15. The rest of the column is zeros.
Make the rhs of each side 2 (the number of edges that a node
can have for a hamilton cycle)
Make the weight of each column 2 as well.
Then run the simplex algorithm. If the objective function is
greater than -4n, there is no hamilton cycle. I call the value
in the lower right corner the objective function, as there is no
true objective function in this case (or I never used one).
If the objective function equals -4n, it is possible there is a
cycle, but you have to check. This behavior also manifests
when there is a covering of subcycles. The explanation of this
is that I was able to create a basis without breaking the constraint
that each node have only two edges. The basis columns are the
edges that make up the Hamilton Cycle.
That is the basic algorithm. I came up with several variations
for recovering hamilton cycles when there were multiples.
The reason that it works so well for determining no cycle, or
unique cycle, is that the condition that each node have only
two edges is necessary, but not sufficient.
By the way, I don't think this says anything about P=NP because
the Simplex algorithm is not polynomial (or at least that is what
I have read).
Let's wait on the source until someone else gets at least as far
as confirming that this works. Besides, I have to figure out how
to send it (can I attach a tgz file to an email from elm?)
stan
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Does it even matter?
Date: 31 May 2000 02:36:25 GMT
In article <[EMAIL PROTECTED]>,
tomstd <[EMAIL PROTECTED]> wrote:
>As some of you may already know, I was offered a job with RSA
>this summer (in San Mateo) working on some software. Sounds
>great seems like people appreciate my work, obviously since I am
>not even done high school.
>
>Of course they hype me up about the job, get me all excited.
>
>And what happends (thru no fault of RSA) big old mr government
>steps in and acts like a dolt. I can't get the job because I
>don't have a "post-secondary education diploma with three years
>work experience". Super, if I had a job, why would I move 3000
>miles to work in the states?
Sigh. RSA is not exactly the US government's favorite company and
that might have something to do with it.
There is lots of good crypto work going on in Canada, at places like
Nortel/Entrust, Certicom, BNR, ZKS, and so forth. Maybe you could
approach some of them and tell them what happened with RSA, and get
some kind of summer job with them.
>Anyways, I am beginning to think my research is pointless since
>well I would rather focus on my school now and prepare for the
>exciting job as a mop-jocky.
It's obvious that you're learning a lot from the crypto stuff that
you're doing, and that's the idea of education, right? But yes, do
everything you can to get into a good university program, even if it
means backing off messing with computers for a while. You are wasting
your time in high school.
>It has been nice chatting with you guys, maybe I will come back
>some time.
Yes, do come back.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Retail distributors of DES chips?
Date: Wed, 31 May 2000 02:34:29 GMT
Well first of all I would like to say how
flattered I am that you boys are haveing a
flame war over me. Oh, what the heck, I
*will* say it. I'm flattered that you boys
are haveing a flame war over me. Now on
to the meatier issues.
In article <[EMAIL PROTECTED]>,
ritter <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>, tomstd
> <[EMAIL PROTECTED]> wrote:
> >In article <[EMAIL PROTECTED]>, ritter
> ><[EMAIL PROTECTED]> wrote:
> >>
> >>In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> >>(Mark Wooding) wrote:
> >>>Terry Ritter <[EMAIL PROTECTED]> wrote:
> >>>
> >>>> But how shall we measure this "trustworthy" property so we
> >can
> >>"make
> >>>> sure" that it exists?
> >>>>
> >>>> There is an alternative, and I have been promoting it for
> >>several
> >>>> years: Use *scalable* cipher designs, so we can perform an
> >>extensive
> >>>> or even exhaustive analysis of the tiny scaled-down version.
> >>>
> >>>Sorry to interrupt while you're on your hobby horse, Terry,
> but
> >>I was
> >>>referring to *implementations* of existing cipher designs.
> >>
> >>Oh, well, if "implementation" is the distinction,
> >>then perhaps you will tell us just how you *test* for
> >>the "trustworthy" property in *implementations*.
> >>
> >>Or maybe your idea of "trustworthy" is the real
> >>hobby-horse ride being so rudely interrupted.
> >>
> >>
> >>>The
> >>>discussion in hand is about the possibility of hardware
> >>implementations
> >>>of strong (as a matter of hypothesis) having been deliberately
> >>>compromised by the vendor. Cipher design doesn't help here.
> >>
> >>"Software" is just another name for the
> >>customization of hardware digital systems. In
> >>general, when we want a complete understanding of
> >>what is present in a digital system, we must have
> >>exhaustive tests. Such tests are impossible in real
> >>size cipher systems, either hardware or software.
> >>Only tiny systems allow exhaustive tests, only
> >>scalable ciphers allow us to build tiny systems
> >>directly related to real ones, and only exhaustive
> >>testing allows us to know that nothing else is there.
> >>
> >>Perhaps that is clearer now.
> >
> >Yup it's clear you are not answering the question.
> >
> >His question was the possibility of DES being fudge-up by some
> >naughty person. Not whether DES was strong or not, whether the
> >CHIP was.
>
> Really? Well, here it is:
>
> >>>>>Well, One of the things I have been considering is the
> >>>>>possibility of malicious software.
> >>>>>That's why I was considering using a chip.
> >>>>>That way there is absolutely no possibility
> >>>>>that anythink will be placed in any
> >>>>>subliminal channels.
>
Yup. I absolutely positively did say that. But
later on it occured to me that since "trick
questions" could eliminate the possibility of
hardware subliminal channels, and also a sort
of hardware attack where the algorithm used
reverts to one that is significantly weaker, I
chose to include that defense against malicious
hardware in my defensive arsenal, too.
> The issue I have addressed is the idea that "there
> is absolutely no possibility" of a subliminal
> channel on a chip. That is false, thus making the
> only real advantage of hardware that new subliminal
> channels are unlikely to be added -- unless of course
> there is a programmable subsection that we don't know
> about.
>
> What we really want is a cipher subsystem -- hardware
> or software -- which demonstrably produces no more
> data than we send to it. To assure this, we might
> send in a buffer of data, and then use that same
> buffer with the original length as the result. There
> must be (at this level) no subsystem-selected or
> produced random values.
>
And I'm glad you pointed that out because only
hardware can assure us that no *more* data is
being transmitted than we want. After all, a
software system could do everything we wanted
it to do, and then sneak through some other
information in the FAT table, for instance.
Such as the key, for example.
> >Not like you do bad work, but you are plugging it in the wrong
> >spot my friend.
> Really? Perhaps you have a deeper insight you
> would like to share with us.
>
The way I see it the problem with a scaleable cipher
as a defense against a malicious attacker (hardware
*or* software), is that the attacker might make it
so that the cipher performed as expected in a small
system but then reverted to a significantly weaker
algorithm when it was scaled up a certain amount.
Finally I would just like to say that this thread
has indeed brought in many issues that were not
in the original post, and these have made it
possible for me to include more defenses in my
plan than it had originally. This is, of course,
a good thing. But it can be confusing if you have
"missed a few episodes". So perhaps it is best
not to "shoot from the hip" (even if you think
you have just been shot at!).
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: Description of algorithm for hamilton cycle problem
Date: Wed, 31 May 2000 12:51:09 +1000
root wrote:
>
> By the way, I don't think this says anything about P=NP because
> the Simplex algorithm is not polynomial (or at least that is what
> I have read).
Simplex can turn exponential for some cases, but usually doesn't in
practice. However there are alternative linear programming algorithms
that are guaranteed to run in polynomial time.
The dubious bit is if you can always turn the Hamiltonian path problem
into a linear program. Those multiple cycles are probably where it will
fail. (I had similar problems trying to do the traveling salesman using
linear programming, and i think someone published a paper proving it
can't be done back in the 1980s.)
------------------------------
Subject: Number Theory Book -- one last thing for now
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 30 May 2000 20:04:51 -0700
at
http://tomstdenis.com/crypto/Elements%20of%20Linear%20and
Abstract%20Algebra.ps
Is a book on algebra that may help the younger math students. I
found it usefull (although I admit I haven't read it in abit).
Well, I am out.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Does it even matter?
Date: 31 May 2000 03:38:33 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> And what happends (thru no fault of RSA) big old mr government
> steps in and acts like a dolt. I can't get the job because I
> don't have a "post-secondary education diploma with three years
> work experience". Super, if I had a job, why would I move 3000
> miles to work in the states?
That's criminal. :-(
> Anyways, I am beginning to think my research is pointless since
> well I would rather focus on my school now and prepare for the
> exciting job as a mop-jocky.
It's not pointless. and you're not going to end up as a mop jockey.
But there is some sense in rendering unto Caesar just long enough to get
into college -- and once there picking it back up with a vengeance.
Good luck with school, and hope to see you again sometime..
Thanks,
-David
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: email list for the contest
Date: 31 May 2000 03:39:40 GMT
Arthur Dardia <[EMAIL PROTECTED]> wrote:
> My father heard this on the way to work and informed me. He said the URL
> was something along the lines of claynet.org. "Under Construction?" What's
> up with that?
www.claymath.org I think
------------------------------
From: Pogo <[EMAIL PROTECTED]>
Subject: Re: TEA analysis
Date: Wed, 31 May 2000 02:40:46 -0400
On Wed, 08 Mar 2000 14:31:02 +0800, Raphael Phan Chung Wei
<[EMAIL PROTECTED]> wrote:
>I note that there was a post by R. Fleming to sci.crypt in 1996 about an
>attack on a weakened version of TEA. Anyone has a record of that, or
>are the posts to sci.crypt archived anywhere?
You can search www.deja.com (formerly dejanews) Usenet archives.
We has met th' enemy an' he is us.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Note on the Hill cipher (II)
Date: Wed, 31 May 2000 09:44:25 +0200
Mark Wooding wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > The Hill cipher
> >
> > C = H * P mod u
> >
> > where H is an invertible matrix in Z_u, has the known disadvantage
> > that, if a pair of plaintext and ciphertext is available, then H, the
> > 'key', can be recovered.
>
> Still wrong. You must have a set of n linearly-independent plaintext/
> ciphertext pairs to recover an n x n key matrix.
Yes, I see one should be very careful in using words in natural
languages. My 'can' was not intended to be an equivalent of
'is ALWAYS able to'. I should have employed standard terminology
and said instead that the scheme falls under known-plaintext attack.
Thaks for the hint.
I like to take this opportunity to add two remarks:
1. One can of course generate a new H for each P and in addition
fill the main diagonal of P with random entries, i.e. combine the
two measures. This may be desirable if one worries about
possibilities of inference of the PRNG.
2. The variant of the Hill method I described in the first note needs
proportionately more material for launching the known-plaintext
attack.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A Family of Algorithms, Base78Ct
Date: Wed, 31 May 2000 09:44:12 +0200
wtshaw write:
> If increased length is tied with increased security, you pay the freight
> for it, which can be worth the price if reasonable. Constant length
> require more investment in algorithm than is necessry for results given
> conservative freedom to add length. I would not suggest that base
> translations are nearly as effective in getting strength this way then the
> GVA.
Through the time I saw you several times mentioning GVA but I have
never understood what that scheme really performs. Could you give
a pointer or post a sketch to the group? Thnaks.
M. K. Shen
------------------------------
From: George Edwards <[EMAIL PROTECTED]>
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: Wed, 31 May 2000 08:41:20 +0100
In article <[EMAIL PROTECTED]>, David
Boothroyd <[EMAIL PROTECTED]> writes
> You are approving of a law which will make it a criminal offence to have
>> privacy.
>
>It does not.
I think it does.
But the mistake is to think the net can be confined. Suppose I purchase
a .tv or .au? On a laptop it doesn't matter. To make it matter would
require all .tv and .au users register in sone way with the UK
authorities. Oink oink flap flap.
--
George Edwards
------------------------------
From: George Edwards <[EMAIL PROTECTED]>
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: Wed, 31 May 2000 08:41:29 +0100
In article <[EMAIL PROTECTED]>, Cynic
<none@none.?> writes
>The RIP bill *does* allow a person to be prosecuted if s/he has lost
>the key. How would anyone prove that they have lost a key, rather
>than they are deliberately withholding it?
When threatened with an injunction recently, to prevent me "finding out"
the address of my wife I pointed out to the solicitors that there was
no way they could prove I KNEW something, and had therefore broken the
injunction, unless they could show I used that knowledge, and only that
knowledge, in some way. I could in any case say in court that I
"believed it to be" .. "wrong address".
They dropped the threat
How on earth can anyone prove that you HAVEN'T forgotten your key,
unless you suvsequently use it? I see huge legal bills on this, all fees
for the solicitors.
--
George Edwards
------------------------------
From: George Edwards <[EMAIL PROTECTED]>
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,alt.politics.uk,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Wed, 31 May 2000 08:42:03 +0100
In article <[EMAIL PROTECTED]>, Peter G.
Strangman <[EMAIL PROTECTED]> writes
>Are you saying the government
>> was dishonest when it introduced it?
There needs be no relationship between the inherent dishonesty of many
politicians and any spcific subsequent action.
--
George Edwards
------------------------------
From: George Edwards <[EMAIL PROTECTED]>
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,alt.politics.uk
Subject: Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
Date: Wed, 31 May 2000 08:42:15 +0100
In article <CdRY4.419$[EMAIL PROTECTED]>, Michael
Watson <[EMAIL PROTECTED]> writes
> MI5 is almost down the road from me, in Catterick Garrison I believe!!!
> BASMIC
REALLY?
CATTERICK?
--
George Edwards
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: (fwd) Internet Security Glossary
Date: Wed, 31 May 2000 10:04:32 +0200
There is a new RFC 2828 entitled Internet Security Glossary.
URL:
ftp://ftp.isi.edu/in-notes/rfc2828.txt
------------------------------
** 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
******************************
