Cryptography-Digest Digest #723, Volume #12 Wed, 20 Sep 00 06:13:00 EDT
Contents:
Re: Software patents are evil. (Jerry Coffin)
Re: CDMA tracking (was Re: GSM tracking) (Jerry Coffin)
Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption (John Savard)
Re: Algebra, or are all block ciphers in trouble? (Mack)
Re: Algebra, or are all block ciphers in trouble? ("Douglas A. Gwyn")
Re: Intel's 1.13 MHZ chip ("Douglas A. Gwyn")
Re: Hamming weight ("kihdip")
Re: Software patents ("kihdip")
Re: Double Encryption Illegal? (Arturo)
Re: Optimization for speed question. (Jonathan Headland)
Re: Optimization for speed question. (John Winters)
Re: On secret Huffman compression (Tim Tyler)
Re: Optimization for speed question. (Christian Bau)
----------------------------------------------------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Software patents are evil.
Date: Wed, 20 Sep 2000 00:38:13 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> Well consider the patent on rotation. A japanese company recently
> claimed that most of the AES finalist violate their patent. So
> what is their patent ? Using rotation in encryption !!!!!!!
You're making the same mistake as most people who condemn software
patents: you start by picking a patent that perhaps shouldn't have
been granted in the first place because it may have been more or less
marginal WRT things like originality.
You don't leave it at the fact that being run by humans, the PTO
makes mistakes now and then though -- you got a step further, and
grossly mis-characterize the patent entirely.
In this case, the patent is NOT simply on using rotations in
cryptography at all. It's on using a specific number of input-
dependent rotations combined in a fairly specific fashion.
> Not to note that using rotation is the oldest concept of
> encryption, even the first of all ciphers, the caesar one, was
> a rotation in 26 alphabetic characters, this patent was also given
> long after, for example, DES has been published (DES rotates the
> key bits), and this is a practical example how people patent maths.
No, it is not. It is a practical example of how people stretch the
truth to justify their positions.
> If you can get a patent on "using rotation in encryption", you
> can also get a patent on any piece of math you wish, don't you ?
As stated, this is a true statement (ignoring minor grammatical
problems). The problem with it is that you CAN'T (as far as anybody
knows) simply get a patent on using rotation in encryption. Given a
false premise, the statement as a whole is vacuously true, but
essentially meaningless. IOW, no, you can't get a patent on any
piece of math you wish.
> Why don't you patent "using addition in mercantile computations
> to get the sum of something" ? Hey, its patentable !
Says who? So far, you've said so, but the PTO hasn't agreed. Even
if they did, it wouldn't necessarily mean a lot: you'd have to sue
somebody for infringement and get your patent upheld in court before
it meant much of anything. Even assuming you threw enough
circumlocution into your application to convince the examiner you had
something, so you were granted a piece of paper, it's unlikely you'd
get a court to enforce a bunch of nonsense.
> Software patents will, for example, destroy free software if we
> can't hinder it. I can't see how you want to get such losses
> back.
People have been saying this for decades now. In fact the examples
they first used (e.g. on RSA encryption) are now expired. Look
around, and try to tell me that there's less free software today than
there was 20 or 30 years ago.
In reality, software patents are going to contribute heavily to free
software: when somebody writes a patent, they must reveal all the
secrets and details of how to implement the invention, and when the
patent expires, the invention is automatically placed in the public
domain. There's no room for question about whether you can use it or
not, etc. -- it's known for certain to be public domain.
Furthermore, the inventor has provided assistance so any person of
ordinary skill in the art can implement the invention as it was
intended to work. Further still more, there's a requirement that the
inventor reveal the best mode of embodiment. This basically means
the inventor has to tell you the intended area for the invention's
use. For example, if he invents some method of building legs to put
under buildings to prevent damage from both flooding and earthquakes,
his patent can be completely invalidated if he tries to mislead you
into believing that this is really about how to build table legs
instead.
To summarize: most of your points are based on a premise that's known
to be false. If you want the details of the steps required in the
patent on rotation in encryption, I posted an explanation a while
back here in sci.crypt that you should be able to find on deja news.
The dire predictions you're making have been made for decades now,
and exactly the opposite of the bad effects have come about so far.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: CDMA tracking (was Re: GSM tracking)
Date: Wed, 20 Sep 2000 00:38:17 -0600
In article <[EMAIL PROTECTED]>, eric-no-spam-for-
[EMAIL PROTECTED] says...
[ ... ]
> Does a cold start, e.g., if batteries were left out for long enough,
> then fresh batteries installed and power turned on, take a long time?
That depends on what you call a long time. If it immediately finds a
good signal from a non-roaming base station, you're usually talking
about a couple of seconds. If you're on the move as you turn it on,
and (for example) you're right at the edge of transmission range, it
can sometimes end up switching between base stations in mid-search
and such, and take close to a minute or so. I believe it could
theoretically take even longer than that, but I've never seen much
more myself.
> I haven't tried that with a CDMA phone, but with TDMA it's fast enough
> that there's no need for any power-off synchronization.
CDMA base stations have considerably greater range (as a rule) so a
CDMA phone will often have to look at the signals from more base
stations before it can decide which is giving the best signal.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption
Date: Wed, 20 Sep 2000 05:48:21 GMT
On Wed, 20 Sep 2000 02:59:38 GMT, [EMAIL PROTECTED]
(John Savard) wrote, in part:
>Very specifically, what I did and what Mr. Bajalcaliev anticipated me
>in doing, is this:
>in a block cipher particularly, but the concept also applies to stream
>ciphers,
I should note that in a stream cipher, being an autokey isn't
required: for the operation to be depending on the keystream rather
than on the fixed key would be the proper distinction.
>based on information dependent on the input plaintext or ciphertext
>block,
>select a different _operation_ (addition, XOR, multiplication) to
>perform at some stage in the block cipher.
I noted that switching between different S-boxes creates the same
difference as switching between multiplication (of the kind used in
IDEA) and addition, so DES could be considered polymorphic because of
the expansion permutation in that sense.
But I have found an earlier example of a block cipher where an
algorithmic operation depends on the data.
In this block cipher, a step follows this rule:
The block to be enciphered is divided into two halves, L and R.
Furthermore, each half is divided into two quarters, L into LL and LR,
and R into RL and RR.
If LL = RL, then the step is: LR = LR + 1, and RR = RR + 1.
If LR = RR, then the step is: LL = LL + 1, and RL = RL + 1.
But if neither of those conditions is met, then LR and RR are swapped.
If I tell you that the additions above are performed modulo 5, will
you recognize the cipher? (Essentially, the cipher consists of only
one round, but there is an initial 25-element S-box on entry, and an
inverse initial S-box on exit.)
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Algebra, or are all block ciphers in trouble?
Date: 20 Sep 2000 06:46:26 GMT
>[EMAIL PROTECTED] wrote:
>> how to build the simple AND function
>> by using only XOR and NOT ?
>
>Oops, that generates a proper subalgebra, not the full Boolean
>algebra.
>
>My point was, there are many sets of operators that generate
>the full algebra; it doesn't have to involve AND. But now that
>we're looking at subalgebras, it should be clear that using a
>suboptimal set of operators (e.g. XOR only, or XOR and NOT) one
>cannot represent all possible functions. I guess that the
>subalgebra spanned by (XOR,NOT) is what was meant by "linear"
>in an earlier posting in this thread, but that is contrary to
>the normal use of the term. (Or maybe it meant with no terms
>higher than first order in the variables, but that wouldn't
>represent any cipher worth using.) For GF(2) there are two
>binary operators (XOR,AND), which is one of the sets that is
>sufficient to represent any Boolean function. Indeed, there
>are several "canonical" forms for such functions, explained in
>logic-circuit-design textbooks.
the (XOR,NOT) algebra is indeed what is normally refered to
as 'affine'. 'linear' doesn't strictly include NOT but most use the
terms interchangeably. It is easy to see why non-linearity
is a requirement in a cipher.
>
>The simple fact is that there is no easy way to solve a
>general multivariate Boolean system. That's why it was a
>valid research topic when I was working on it a couple of
>years ago. There are all sorts of approaches one can try,
>and I still have hopes that a substantial reduction of
>resources (from a simple b.f. search of the full keyspace
>using the full system) is possible, but as an unfunded project
>it has been relegated to a back burner.
>
There is a simple way the problem is there isn't an effiecient
way. Brute force is exceedingly simple but once the number of
variables exceeds about 50 it is fairly slow.
If the number of terms is small then the equations can be solved
for larger numbers of variables. ie. low order approximation
attack among others.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Algebra, or are all block ciphers in trouble?
Date: Wed, 20 Sep 2000 02:48:02 -0400
Mack wrote:
> Normal boolean algebra uses AND; OR and NOT
No, that's just one convention. Much like "elementary particles"
of physics, various sets of operators can be taken as fundamental
and the others expressed in terms of them. The favorite sets
used by the Poles were {AND,NOT} -- {K,N} in their notation -- or
{IMPL,NOT} -- {C,N} in their notation --, usually the latter.
Sheffer seems to have been given historical credit for being the
first to observe that a single binary operator {NAND} would suffice,
although as I recall he wasn't really the first. Note that with
these systems one can create T,F constants from available variables,
e.g. T is just Caa. Kab is just shorthand for NCaNb. Etc.
> while XOR/AND/1 does form the set called ANF
> you simply can't produce my function o
That's right; there is a symmetry that can't be dispelled.
I slipped up when I included {XOR,NOT} in the list of full-algebra
generating operator sets. In a nearby posting I explored that
further.
> >An interesting case is when just
> > EQV
> >is used; one gets a "subalgebra".
> EQV = NOT(XOR(a,b))
Yes, the {EQV}-generated subalgebra is a proper subalgebra of the
{XOR,NOT}-generated algebra, which is a proper subalgebra of the
full Boolean algebra. An {XOR(only)}-generated subalgebra would
be very similar.
> without using AND with XOR or XNOR(EQV) your can't
> form all possible strings of outputs as the result of inputs.
One doesn't have to use AND; several other operators would also
work. The main reason one thinks of AND is by analogy with the
elementary arithmetic operators:
0 <=> F (FALSE)
1 <=> T (TRUE)
- <=> N (NOT)
+ <=> X (XOR)
x <=> K (AND)
which is the translation between GF(2) operations and Boolean
logic. Thus, GF(2) is able to represent any Boolean function.
However, it is worth noting that other formulations also work.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Intel's 1.13 MHZ chip
Date: Wed, 20 Sep 2000 03:01:06 -0400
Jerry Coffin wrote:
> I notice you carefully did NOT quote what you said, to try to keep us
> from noticing that in reality it's _exactly_ what you said.
No, and you know better.
To recapitulate, you accused DIRNSA (which one would be easy
to pin down from the dates involved) of irrationally forcing
procurement of suboptimal and very expensive equipment, which
if true would be malfeasance of a high order. I pointed out
that that was a very serious accusation to make, one that
would be justified only if you had evidence to back it up,
and otherwise verging on libel. Instead of producing a shred
of supporting evidence, you then engaged in sophistry and
sophomoric literalism. A morally honest person would produce
support for their accusation or else retract it, not argue
beside the point.
------------------------------
From: "kihdip" <[EMAIL PROTECTED]>
Subject: Re: Hamming weight
Date: Wed, 20 Sep 2000 09:09:45 +0200
Mack, I'm a bit puzzled:
>A good definition for base two. But Hamming weight is also
>applicable to other bases. "The Theory of Error-Correcting Codes"
>by MacWilliams and Sloane defines the Hamming Weight as
>the number of non-zero entries in the numeric string and
>the Hamming Distance as the number of places where they
>differ or alternately the hamming weight of subtracting one string
>from the other without carry.
>
Francois Grieu answered that the Hamming weight was only depending on the
binary representation.
The Hamming weight of 19 is thus 3 (2^4, 2^1 and 2^0).
If it's applicable to other bases shouldn't 19 have a weight of 2 (1*10^1
and 9*10^0) ??
Kim
------------------------------
From: "kihdip" <[EMAIL PROTECTED]>
Subject: Re: Software patents
Date: Wed, 20 Sep 2000 09:20:06 +0200
You forgot
http://petition.eurolinux.org/index_html?LANG=dk
;-)
------------------------------
From: [EMAIL PROTECTED]=NOSPAM (Arturo)
Subject: Re: Double Encryption Illegal?
Date: Wed, 20 Sep 2000 07:24:21 GMT
On 20 Sep 2000 02:13:48 GMT, [EMAIL PROTECTED] (Guy Macon) wrote:
>Trevor L. Jackson, III wrote:
>>
>>
>>Guy Macon wrote:
>>
>>> You mean I shouldn't be applying ROT-13 twice? Several experts have
>>> told me that applying ROT-13 twice is *so* secure that an attacker
>>> with infinite resourses can't even tell what algorithm I used...
>>
>>They also can't tell which of the four combinations DD, DE, ED,
>>or EE were used.
>
>Who could possibly ask for more security than that???
Hope nobody is taking you guys seriously ;-)
------------------------------
Crossposted-To: comp.lang.c
Subject: Re: Optimization for speed question.
From: Jonathan Headland <[EMAIL PROTECTED]>
Date: 20 Sep 2000 10:08:25 +0200
[EMAIL PROTECTED] (Christian Bau) writes:
> In article <G7vx5.3241$[EMAIL PROTECTED]>, "Tor Rustad"
> <[EMAIL PROTECTED]> wrote:
>
> > The error probability of Miller-Rabin is easy to control, to me proving
> > something on a computer beond a 2^{-80} error probability does not make the
> > proof better.
> >
> > For sake of argument, let us increase the security margin to 2^{-160}.
> Then if a
> > provable prime algorithm gives a different result than Miller-Rabin did, which
> > method is right?
> >
> > My bet would be the algorithm which used the less CPU time...
>
> So why did anybody bother proving Fourier's Last Theorem, when it was
> known for some time that a^n + b^n = c^n has no solutions in positive
> integers a, b and c for 2 < n < 125000, so the chances of finding a
> counter example were about 1 in 10^(-300000) ?
Fermat's Last Conjecture (colloquially, "Theorem") was important because
it had been shown that proving it would prove the more "useful"
Taniyama-Shimura Conjecture, linking elliptical curves with modular forms,
and this connexion was an important part of the Langlands programme.
Your calculation of "the chances of finding a counter example" is,
incidently, meaningless. There are an infinity of values of n above
any particular n that we choose. Therefore, until proven, the chance
of finding a counter example may be 1 (if the conjecture is not true),
or may be 0 (if the conjecture is false).
In any case, _finding_ a counter-example is unncessary: it is sufficient
to demonstrate that one exists in order to show that a conjecture is false.
> Why does anybody try to prove the Goldbach hypothesis, which is known to
> be true with a margin of error < 10^(-1000000) ?
Similar comments apply to this calculation too.
--
Jonathan Headland
Wind River
Jakob-Haringer-Str. 8
A-5020 Salzburg, Austria "function returning void" is oxymoronic
------------------------------
From: [EMAIL PROTECTED] (John Winters)
Crossposted-To: comp.lang.c
Subject: Re: Optimization for speed question.
Date: 20 Sep 2000 09:30:09 +0100
In article <[EMAIL PROTECTED]>,
Jonathan Headland <[EMAIL PROTECTED]> wrote:
[snip]
>Therefore, until proven, the chance
>of finding a counter example may be 1 (if the conjecture is not true),
>or may be 0 (if the conjecture is false).
Clearly maths has got even more head-straining since I took my degree. :-)
John
--
John Winters. Wallingford, Oxon, England.
The Linux Emporium - the source for Linux CDs in the UK
See http://www.linuxemporium.co.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: On secret Huffman compression
Reply-To: [EMAIL PROTECTED]
Date: Wed, 20 Sep 2000 09:46:40 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
[Huffman compression as encryption?]
: Use a secret key as seed of a PRNG. At each non-terminal
: node of the given Huffman tree, use a psudo-random number
: to determine whether the two branches are to be flipped,
: i.e. whether their markings of 0/1 are to be exchanged.
: Use the modified tree to do compression.
IIRC, I've mentioned before the possibility of an attacker using
known-plaintext at the start of the message to extract much of the
Huffman tree. *If* you can get the whole tree, it seems likely that it
will be possible to recover the PRNG stream - which can be used to send
forged messages (in the absence of a signature scheme).
While the above description doesn't offer a detailed algorithm, ISTM
that it's likely to suffer from this type of known-plaintext attack.
My memory is hazy - but I believe multiple passes in opposite
directions was one of the methods proposed to deal with this issue
the last time around.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: [EMAIL PROTECTED] (Christian Bau)
Crossposted-To: comp.lang.c
Subject: Re: Optimization for speed question.
Date: Wed, 20 Sep 2000 11:07:41 +0100
In article <[EMAIL PROTECTED]>, Jonathan Headland
<[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] (Christian Bau) writes:
>
> > In article <G7vx5.3241$[EMAIL PROTECTED]>, "Tor Rustad"
> > <[EMAIL PROTECTED]> wrote:
> >
> > > The error probability of Miller-Rabin is easy to control, to me proving
> > > something on a computer beond a 2^{-80} error probability does not
make the
> > > proof better.
> > >
> > > For sake of argument, let us increase the security margin to 2^{-160}.
> > Then if a
> > > provable prime algorithm gives a different result than Miller-Rabin
did, which
> > > method is right?
> > >
> > > My bet would be the algorithm which used the less CPU time...
> >
> > So why did anybody bother proving Fourier's Last Theorem, when it was
> > known for some time that a^n + b^n = c^n has no solutions in positive
> > integers a, b and c for 2 < n < 125000, so the chances of finding a
> > counter example were about 1 in 10^(-300000) ?
>
> Fermat's Last Conjecture (colloquially, "Theorem") was important because
> it had been shown that proving it would prove the more "useful"
> Taniyama-Shimura Conjecture, linking elliptical curves with modular forms,
> and this connexion was an important part of the Langlands programme.
Which is of course completely wrong. It had been shown that proving the
T-S Conjecture would prove Fermat's Last Theorem, but not the other way
round.
> Your calculation of "the chances of finding a counter example" is,
> incidently, meaningless. There are an infinity of values of n above
> any particular n that we choose. Therefore, until proven, the chance
> of finding a counter example may be 1 (if the conjecture is not true),
> or may be 0 (if the conjecture is false).
Which is exactly the point why using a probabilistic prime number proving
algorithm is pointless.
> In any case, _finding_ a counter-example is unncessary: it is sufficient
> to demonstrate that one exists in order to show that a conjecture is false.
>
> > Why does anybody try to prove the Goldbach hypothesis, which is known to
> > be true with a margin of error < 10^(-1000000) ?
>
> Similar comments apply to this calculation too.
Did anyone ever explain to you what a "rhethoric question" is?
And PLEASE don't answer to that one.
------------------------------
** 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
******************************
