Cryptography-Digest Digest #750, Volume #12 Fri, 22 Sep 00 23:13:01 EDT
Contents:
Re: State-of-the-art in integer factorization ("Dann Corbit")
Re: Software patents are evil. (Darren New)
What make a cipher resistent to Differential Cryptanalysis? ("David C. Barber")
Re: Software patents are evil. ("Dann Corbit")
Re: What make a cipher resistent to Differential Cryptanalysis? (Tom St Denis)
Re: Software patents are evil. (Bill Unruh)
Re: Software patents are evil. (Bill Unruh)
Re: winace encryption algorithm (correction) (David Hopwood)
Re: t (David Hopwood)
Re: Tying Up Loose Ends - Correction (David Hopwood)
How many possible keys does a Playfair cipher have? (Alex)
----------------------------------------------------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: State-of-the-art in integer factorization
Date: Fri, 22 Sep 2000 16:20:18 -0700
"Jerry Coffin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <8qfefu$g2v$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> says...
> > In article <8qedb0$c49$[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] (Ed Pugh) wrote:
> > > Bob Silverman ([EMAIL PROTECTED]) writes:
> > > >
> > > > Nothing has been written. Improvements have been only incremental.
> > > > (i.e. slightly faster machines, a few more percent squeezed from
> > > > code, etc.). There hasn't been a new algorithm in 11 years.
> > >
> > > Well, at least none that the NSA have let on about, anyway. ;-)
> >
> > That's right because the public open academia are just stupid people.
>
> I don't think anybody's said that. Keep in mind, however, that the
> NSA has a LOT of extremely smart people. Right now, there are
> probably no more than a dozen or so mathematicians producing most of
> the world's knowledge of factoring. Most of them work more or less
> separately from each other, and most of them have LOTS of other
> duties in addition to studying factoring.
On the other hand, with the internet, worldwide communication of ideas is
practically instantaneous. I rather suspect that a brilliant idea is as
likely to spring from some new genius as it is from someone the NSA has
employed. Could be some unknown grad student. After all, Lenstra,
Ramanujan, and everybody else like that were simply grad students at one
time themselves.
For that matter, what remarkable new algorithm has the NSA invented? Are
there *any*?
Furthermore, like any government agency, the employees will have a lot more
to do than their jobs. Just like a teacher at a university must "publish or
perish" -- similarly government workers have a bazillion silly tasks on
their hands and beaurocratic hoops to jump through. To imagine that the NSA
members are a bunch of the world's most intellectual number theory experts
who do nothing but sit around and try to figure out how to factor is surely
a monstrous misnomer. If there is solid evidence to the contrary to show
that I am wrong, I would love to hear about it.
> The NSA probably has at
> least as many mathematicians of the same talent level,
If there were mathematicians of the same talent level we would know who they
were. They would have to publish remarkable findings and excell at a
university first in order for both us and the government to take notice.
Can anyone name 5 super-duper Ramanujan/Gauss/Euler/etc level mathematicians
who work for NSA?
I doubt it. But it's possible. Do you know many mathematicians who would
rather work at the NSA than at a university or in private industry?
> and can afford
> to saddle them with fewer ancillary responsibilities.
But I would be astonished if it really turned out that way. We are talking
about the *Government* here.
> Consider teamwork possibilities as well: think of a situation where
> you can get a half-dozen people each the caliber of Bob Silverman or
> Arjen Lenstra, and give them time to brainstorm on a regular basis.
Wouldn't people like that generally prefer to work in a place where they can
publish what they find? Private industry generally pays better than the
government also.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Software patents are evil.
Date: Fri, 22 Sep 2000 23:25:46 GMT
Jerry Coffin wrote:
> Keep in mind that if something is
> currently protected by a valid patent, then nobody did it more than
> 20 years ago.
Nonsense. One company I worked for had to license a patent that was applied
for three years after we'd been selling what they described as a commercial
service. I think if all the patents were valid, there would be much less
complaining.
> > But _IF_ I don't want to get such a help ?
>
> Fine, don't take it. If you don't want to use the patented
> invention, nobody says you have to.
Unless you're already using it, of course. Then you're just screwed.
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"No wonder it tastes funny.
I forgot to put the mint sauce on the tentacles."
------------------------------
From: "David C. Barber" <[EMAIL PROTECTED]>
Subject: What make a cipher resistent to Differential Cryptanalysis?
Date: Fri, 22 Sep 2000 16:33:04 -0700
DES, for example is considered resistant to Differential Cryptanalysis,
particularly in its selection of S-boxes. What about them, or any cipher,
makes it DF resistant?
*David Barber*
------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Subject: Re: Software patents are evil.
Date: Fri, 22 Sep 2000 17:02:30 -0700
"Jerry Coffin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <kQ8y5.67$bx3.1112@client>, [EMAIL PROTECTED]
> says...
>
> [ ... ]
>
> > And yet it is the huge conglomerates like IBM and AT&T that own almost
all
> > of the software patents.
>
> Likewise with hardware patents. What of it? Would it surprise you
> if GM had more patents on automotive technology than you or I do?
> Software is no different from anything else in this respect.
>
> Also keep in mind that every time IBM, AT&T, Lucent, etc., writes a
> patent (on hardware, software or whatever) they're voluntarily giving
> that technology to ALL of us as soon as the patent expires.
17 years later. By that time, a new and superior algorithm will be
patented, starting the circle over again. Oh joy.
> > Really small operators cannot afford the legal
> > battles that can ensue.
>
> Nonsense. If you've got good patents on useful technology, you'll be
> able to take your choice of firms with REALLY deep pockets to help
> you enforce them.
This is pretty funny. Name ONE time that this has EVER happened. They
might buy a patent from you, but they won't help you enforce a patent they
don't own.
> There are a fair number of quite large companies
> that do NOTHING but help their clients enforce patents. For one
> example, the Mahr-Leonard Management Company has made a huge amount
> on patent licensing. Contrary to some statements in this thread
> though, the owners of the patents really DO make money on them -- it
> doesn't all go to the attorneys or anywhere close to it.
I would be interested in seeing some figures for small-time people or
start-up companies to see how this really works out for "the little guy."
> > On the other hand, it might go unchallenged -- even
> > at that, they are sitting on top of a huge money pit if it does get
> > challenged. But (for the most part) it is the mega-mega huge players
that
> > benefit. They already have multiple millions of dollars in their legal
> > budget so that they can afford software patents.
>
> Quite the opposite: patents are the majority of what lets little
> companies compete with the huge ones. Of course, anymore many of the
> little companies don't really WANT to compete: they want to start up,
> create some new technology (patent it, of course) and get bought out
> by a big company. Without patents, that wouldn't happen though: the
> little company might start up and create some great new technology,
> but without something to give them ownership of it, the big company
> wouldn't bother buying out the small one -- they'd just take the
> technology and use it for free instead.
In my experience working as a subcontractor and as an employee, the firms I
have worked for have never bothered to try and patent anything.
I will admit that there have been compelling arguments that I had not
thought of to support patents. I still think they are evil, and here's why:
"Back in the day" (I've been a programmer a long time) people used to invent
algorithms and just publish them in the ACM. No patent, no secrecy, no
nothing. "Lookie! A new algorithm! Here is the explanation. Have fun."
Now, back in those days, algorithms exploded like a bomb blast going off.
With the heavy advent of patents (and even copyrights for that matter) that
has really simmered down.
How many interesting and new algorithms have been invented outside of
academia in the 30 years since Knuth's TAOCP?
Very, very few. Or maybe it is just as many as always, but the new
algorithms are hidden in the bushes.
To me, I see exponential drop-off of sharing algorithms. With the advent of
instantaneous world-wide communication via the internet and all the recent
advances, it should be just the opposite.
Are you really sure that patents and trade secrets are not to blame?
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: What make a cipher resistent to Differential Cryptanalysis?
Date: Sat, 23 Sep 2000 01:13:40 GMT
In article <8qgqab$e85$[EMAIL PROTECTED]>,
"David C. Barber" <[EMAIL PROTECTED]> wrote:
> DES, for example is considered resistant to Differential
Cryptanalysis,
> particularly in its selection of S-boxes. What about them, or any
cipher,
> makes it DF resistant?
Having a low probable differentials, having no impossible
differentials, having no high probable nonzero to zero differences, um
and being a markov cipher.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Software patents are evil.
Date: 23 Sep 2000 01:50:49 GMT
In <[EMAIL PROTECTED]> Jerry Coffin <[EMAIL PROTECTED]>
writes:
>>
>> AFAIK PGP has simply violated the RSA patent. And GnuPG
>> became possible because ElGamal expired.
>PGP _licensed_ the RSA patent. Expired patents being put into the
Actually , no it did not. PGP used RSA and got RSADSI very annoyed with
Zimmermann, and was one of the things which forced development out of
the US. MIT, the owner of the patent finally talked to RSADSI, their
exclusive licensor, and pointed out that version 1 of RSAREF had been
released with a sufficiently unrestrictive license that RSADSI could not
mount a convincing challenge.
The commercial version (VIACRYPT first and then NAI) did license RSA fo
rthe commercial versions.
Ie, pgp did start out by violating the patent. It then continued by the
patent owner encouraging the use of the product (although the licensor
was very unhappy).
>public domain aren't exceptions: they're part of the rule. IOW,
>that's _exactly_ what we (the public) receive in return for giving
>the inventor a monopoly for a limited period of time. To summarize,
Yes, the question is whether we could get the same thing for less cost
(ie a smaller patent lifetime). Or whether trade secrecy is really such
a threat in software. (Ie reverse engineering in software being easier
perhaps than in an industrial process/product).
>you're giving fine examples of how well the patent system really
>works.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Software patents are evil.
Date: 23 Sep 2000 01:54:34 GMT
In <[EMAIL PROTECTED]> Darren New <[EMAIL PROTECTED]> writes:
>Jerry Coffin wrote:
>> Keep in mind that if something is
>> currently protected by a valid patent, then nobody did it more than
>> 20 years ago.
>Nonsense. One company I worked for had to license a patent that was applied
>for three years after we'd been selling what they described as a commercial
>service. I think if all the patents were valid, there would be much less
>complaining.
The problem is that the patent does not get sent back to the patent
office for initial determination as to whether the original patent was
valid, it goes to the courts. This is very expensive. IF the cost of
fighting the patent were commensurate with the cost of applying for a
patent, at least in so far as determining the intial presumption the
courts would operate under, the situation would be far more equal. As it
is the cost of disputing a patent is far far higher, and it is
financially disasterous usually to fight rather than license.
------------------------------
Date: Sat, 23 Sep 2000 01:40:18 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: winace encryption algorithm (correction)
=====BEGIN PGP SIGNED MESSAGE=====
An Metet wrote:
> Again (*sigh*), this is the secret Ace (and WinAce) encryption
> algorithm. I hope it will be posted correctly this time! It is a
> combination of a Blowfish derivation and a SHA-1 derivation and it
> uses Cipher Block Chaining. I called it AceFish therefore...
>
> About one month ago, there was a hint in sci.crypt, that it could be
> a combination of BlowFish and SHA-1. This code was created by
> disassembling, examining and debugging ace32.exe (version 1.2b) and
> comparing the results to the original Blowfish and SHA-1 algorithms.
> The differences are commented in the source code. I hope I didn't
> forget to comment on one of them.
It's based on SHA-0, not SHA-1 (the difference is the 1-bit rotation).
The key scheduling is equivalent to using the output of SHA-0 as a
160-bit Blowfish key (this depends on SHA-0 and Blowfish both being
big-endian). I.e. excluding the possible errors described below, the
algorithm is Blowfish in CBC mode with the 160-bit key
SHA-0(byteswap(password))), where 'byteswap' swaps the byte order of
each 32-bit word (treating the last word slightly differently).
However, if the reverse engineering is correct then there is a bug in
the SHA-0 implementation: the array holding the SHA-0 input is not
fully initialised to zero; only the first word is initialised
("u32 w[80] = { 0 };" in the code). This bug would cause incorrect
(nondeterministic) operation, unless that area of memory happened
to be initialised to zero. The initial Blowfish S-boxes also have
some errors (although that wouldn't affect security).
My advice would be not to use Ace/WinAce: there is no salt, and no
attempt to slow down the hash, so dictionary attacks are much more
feasible than they should be.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOcvarDkCAxeYt5gVAQGBpwgAiuaeOyjkrXz0lVnYgburOSOrre4dTodl
YA8gmMIaRmEdQAvsQ29mswiOhWrcxc2cS8N80CqUW9c3ioE3yVqwFmr5vhyeqAsV
XDNWioPaKnJ2kBw4I+fbQrQ3CMWmSfiwOdHuXRPS0QBsf8v8a0Cc2HveL7i7Gsxl
rG79Vj3SiJjpb1M52S8aqV1Av4KkI9ocI+OsEV08QlScf9fZr+48jb6thcVkcCfT
mh8tTcUgTyZIrcPe5URHH8KcJ9Ae5rRFPmlIY2Z3eyYQqHJe7puRATjKaZRR4HGP
4DiPwHvlf/jqHSvSzMs+JMUUeMOlbB7bmLrUU7v5mk/7GyWgCjRdmQ==
=7EFt
=====END PGP SIGNATURE=====
------------------------------
Date: Sat, 23 Sep 2000 01:40:50 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: t
=====BEGIN PGP SIGNED MESSAGE=====
zapzing wrote:
> In article <8qcise$l6i$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Thomas Pornin) wrote:
> > There is also the classical "Stranded on Venus" problem: some
> > scientists have a technical problem on the ground of planet Venus.
> > To get back to the orbital station, a button must be pushed on the
> > control panel of the station, but there is nobody left to push that
> > button... except some bypassing (and altogether cooperative) aliens.
> >
> > The scientists manage to establish a radio communication with the
> > aliens, and build up some sort of language (they are *good*
> > scientists).
> > But the main problem is that there are two buttons on the panel. The
> > left one is the one to be pushed. The other one is the self-destruct
> > command.
> >
> > How will the scientists and aliens agree on the notion of left and
> > right ?
>
> OK, Helpful Aliens. Just take a look at the third planet
> from this here star. It's got a Nitrogen, Oxygen atmosphere
> with a bunch of other neat stuff. The "northern" hemisphere
> is the one with most of the land masses on it. If you are
> standing with your back to the sun, and looking at Earth
> (the third planet) with your head pointing north, and your
> feet pointing south (opposite of north) then a point on the
> planet on the sunny side will be moving left to right (or
> is it right to left?).
Head? Back? Feet? The aliens don't have those.
A simpler approach is to draw a 2D schematic picture of the control
panel and buttons from the point of view of someone looking at it,
digitise that picture (neglecting rotations, there are two ways of
serialising a 2D pixellated image, and if the control panel has no
bilateral or rotational symmetry, the aliens can determine which one
has been used), and transmit the digitised picture over the radio.
That would probably even work even if you hadn't first established a
language.
If the control panel is bilaterally symmetrical, send a picture of
something else that isn't symmetrical as a reference, e.g. the
Earth, or an experiment demonstrating the left-hand rule in
electromagnetism. (If the panel and the spaceship are rotationally
symmetrical, it's not just the aliens who will have problems :-)
[Interestingly, and even more off-topic, even human languages vary
in how body parts are used to derive prepositions:
# For example, the concept /front/ has its basic characterisation in
# the body and then is extended metaphorically to other objects.
# In English, it is extended to objects like bushes as follows:
# If you are looking at a bush, the "front" of a bush is the side
# facing you. In Hausa, the reverse is true: the "front" [*] of the
# bush would be the side facing /away/ from you, that is, in the same
# direction as you are facing. Both choices are equally reasonable--
# equally consonant with our experience. In such situations, the
# same conceptualizing capacity and experiences can give rise to
# different systems.
-- George Lakoff,
"Women, Fire, and Dangerous Things - What Categories Reveal
about the Mind,"
The University of Chicago Press, ISBN 0-226-46803-8.
Chapter 18 page 180.
[*] i.e. the word that is also used for the front of the body.]
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOcv6/zkCAxeYt5gVAQFaqggApZRVFfQJPjg8xS6LPifEp4vtoACh2WJ2
CVXWqhF9nmoPU6OyUY1fTQwMaxDeqjYSW8gzyZSMREmRZe8eHKjXjI9t2RB4iS4x
MwSxVu7HaQxJPYdf63aYqi7WQVEv3fZPEWkedEelvF/yxPzF4ycpVjbJt98KSa1L
AUNnfSVf/dUfVyRW0I/bCb+5UYvk/FKnuBRhvWTOWdzwW5WirgKelxkZpo9HZuC8
iorIri3wXsVzkisroduZC0WVrbNlaMucTmR9W+tL+rum0r6eMhgPeFBvRpbnayv9
zfem/rxNHnBJKfaa31RK264dXFaCJ3ik+5FZ1lPbWkesHFEyOa7+oQ==
=H8Dz
=====END PGP SIGNATURE=====
------------------------------
Date: Sat, 23 Sep 2000 01:41:42 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Tying Up Loose Ends - Correction
=====BEGIN PGP SIGNED MESSAGE=====
Tim Tyler wrote:
> SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
> : [EMAIL PROTECTED] (Benjamin Goldberg) wrote:
> :>SCOTT19U.ZIP_GUY wrote:
> :>> I thought we are talking about compressing then ecnrypting.
> :>> If you always add 5 zeros or any other fixed amount of bits
> :>> after a compressed string or any file for that matter which is
> :>> then encrypted. The attacker know what the last few bits are
> :>> and throws out keys that don't match. So if the last five bits
> :>> of a file are known then it means you reduce your key space by
> :>> 5 bits.
> :>
> :>Reducing the message space by x bits does *not* reduce the
> :>keyspace by x bits...
[snip]
> ... David is discussing the effect of adding an additional section
> of known plaintext to the end of the file. This normally has the
> effect of decreasing the keyspace by almost exactly five bits -
> provided the effective keyspace doesn't go negative, of course.
With all due respect, this is complete nonsense.
When we talk about "reducing the keyspace", that means reducing the
size of the set of keys that need to be considered at all; it does
not mean finding a test that will eliminate keys by testing them one
by one.
For example, if you have a cipher with a keyspace of m bits, and
there is some cryptanalytic attack that can be split into two
independent parts - the first extracting partial information about
the key, and the second using that information to search 2^n
possibilities, then the first part of the attack has reduced the
keyspace by (m - n) bits:
k1 = first_part();
for (k2 <- 2^n possibilities) {
if test(k1, k2) then f(k1, k2) is the correct key
}
The time complexity of the attack is the complexity of 'first_part',
plus 2^n * the complexity of 'test' (assuming f is trivial).
If, OTOH, an attack is something like this:
for (k <- 2^m possibilities) {
if test1(k) and /* eliminates all but 2^n keys */
test2(k) /* eliminates remaining false keys */
k is the correct key
}
then the keyspace has *not* been reduced (the time complexity is at
least 2^m * the complexity of 'test1', i.e. every key still needs
to be considered). What David Scott is trying to claim is that the
existence of 'test1' reduces the keyspace by (m - n) bits, which is
at best an abuse of terminology, and is basically just plain wrong.
> [This may not necessarily reduce the difficulty of searching the
> keyspace, but does allow certain automated rejection of many keys.]
You can in practice always reject keys, if you loop over each possible
key, because plaintext messages are almost always automatically
recognisable. In particular, whether they are recognisable is not
changed by compression, including "1-to-1 compression".
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOcvxxDkCAxeYt5gVAQGZMAgAkFfcVobrEDEx+djjex0eLv4QQ+tY6mdM
FRPr02B7dUr67dSqNqmh7ef7wCtTAYiYniecRbf7WeSEwzdLH7/emu/rmRtlom1y
t2nMG0uMmS+V3AzVCf9VhSxv/YxZVUvaoZmtSMvhtD99++i1p0WBam25ueK9L8Ew
iY7ffdlflEd4XvLO8iP01VSwJM27prBPyD0nft+7mcFY0AR/OgZbGShFGfWi52kE
cS4BKrnQMZDe4pxb81au7CItC8sJUY7oFyYNh4lxFH7eTNuqMaqxSlm3PYqj1VGP
RBAyyHLH4jX83AmautmM2ZUq7Lcj8qSatUR1NU4NeSNWNv7wbPinPw==
=iT3q
=====END PGP SIGNATURE=====
------------------------------
Subject: How many possible keys does a Playfair cipher have?
From: [EMAIL PROTECTED] (Alex)
Date: Sat, 23 Sep 2000 02:57:31 GMT
How many possible keys does a Playfair cipher have?
Thanks
------------------------------
** 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
******************************
