Cryptography-Digest Digest #575, Volume #9 Fri, 21 May 99 14:13:03 EDT
Contents:
DSA (Digital Signature Standard) and the Schnorr Patents (Vin McLellan)
Re: Biprime Cryptography, Part II (Matthias Bruestle)
Re: Reasons for controlling encryption (Doug Stell)
Re: Biprime Cryptography, Part II (kurt wismer)
Re: Biprime Cryptography, Part II (David A Molnar)
Re: Reasons for controlling encryption ("Renegade")
Re: Crypto export limits ruled unconstitutional (AllanW)
Re: CRC16 polynomials (Russell Harper)
Re: Crypto export limits ruled unconstitutional (Mok-Kong Shen)
----------------------------------------------------------------------------
From: Vin McLellan <[EMAIL PROTECTED]>
Reply-To: The, Prtivacy, Guild
Crossposted-To: talk.politics.crypto
Subject: DSA (Digital Signature Standard) and the Schnorr Patents
Date: Fri, 21 May 1999 01:32:31 -0300
On Coderpunks, Vin McLellan <[EMAIL PROTECTED]> wrote:
>> Prof. Schnorr is an active defender of his patent claims
>> with regard to the DSA, as indicated by his several posts
>> to this List last year
James A. Donald <[EMAIL PROTECTED]> accurately noted:
>Posts that failed to impress some people on this list.
While the estimable Ben Laurie <[EMAIL PROTECTED]> growled:
/> i.e. if you believe that division is addition, 1 is 2 and black is
/> white, you'll have no problem with these claims.
I hesitate to get into this, since I'm not qualified to judge
the viability of Prof. Schnorr's case, or even to effectively present
his technical arguments, but Schnorr's claims -- to judge from their
impact on DSA adoption, US crypto policy, and specifically the NSA's
strategy for managing the US standards process to ensure universal
government access to crypto keys (GAK) -- are neither trivial nor
vacuous.
I think it is misleading to suggest that they are.
In 1992, the best patent lawyers the US government could hire
were far less certain than Ben and others here that Schnorr's US
patent did not impinge on the DSA design -- to say nothing of
Schnorr's broader European and Japanese patents on digital signature
tech.
NIST's 1993 DSA patent (filed two months after Schnorr's US
patent was issued in 1991) is one of 51 US patents on cryptography,
many of them now classics, which explicitly refer to Schnorr's digital
signature patent. Among cryptographers, Whit Diffie has noted a
"strong resemblence" between DSA and the Schnorr design, and Bruce
Schneier, who studied and wrote about the DSS patent issues in Applied
Crypto, certainly didn't glibly dismiss Schnorr's claims as some have
here.
I don't have a formal cite or even a quote, but I've always
understood Prof. Schorr's digital signature algorithm to have been
inspired by El Gamal's work at Stanford in '89, and to have in turn
inspired Brickell and McCurley. It is, I think, commonly believed
among European crypto scholars, at least, that the El Gamal and
Schnorr designs were the basis for David Kravitz's invention of the
DSA.
I do know that in 1991-'92 NIST hired two or three prominent
US
patent firms to review the applicability of the Schnorr patents to the
DSA. The only consensus they got was: "Maybe, maybe not."
And this was _after_ Kravitz, the NSA mathematician who
developed the DSA at Princeton for the NSA, was given the Schnorr
patent and asked by NIST to tweak his initial DSA design to minimize
potential conflict with Schnorr's US patent.
Those who didn't see the Coderpunks posts in which Prof.
Schnorr responded to a thoughtful challenge from Anon on this List
last year may wish to read Schnorr's own informal pitch at:
<http://privacy.nb.ca/cryptography/archives/coderpunks/new/1998-08/0006.html
> (Cut and paste the URL.) But Schnorr's submission to the IEEE PKC working group is
>probably still the best source: <http://grouper.ieee.org/groups/1363/patents.html>
Mr. Donald argued:
>If Schnorr's patent covers the DSA, then the patent office
>has erred in giving a patent to the NSA for the claims that
>the NSA made, since the claims overlap.
That may well be. Anyone who recalls how the NSA had NIST
doing
backflips to push the Key Escrow FIPS (FIPS 185) through in record
time -- with an abbreviated period for public comment which garnered
322 responses; only two pro-GAK -- would not be surprised to learn
that the US Patent Office was cowed by the NSA's expertise.
The DSS, of course, became FIPS 186 -- a federal purchasing
requirement which, with 185, effectively locked US government agencies
out of the commercial infosec market for years; probably cost hundreds
of millions in federal-only development costs; and contributed
substantially to the woeful state of computer security in federal US
agencies even now.
Patent-haters and nostalgic PGP adherents who today see DSA
only as a royalty-free alternative to RSA digitial sigs forget the
context in which the NSA initally sponsored the development of the
DSA.
The DSA was developed by the NSA explicitly to undermine the
de facto status of RSAPKC as an industry-supported standard. Yes, it
was royalty-free -- but there were other "costs" presumed to be
associated with any widespread adoption of DSA in commercial compsec.
While there certainly are apps which require only digital signatures,
in many if not most situations where a user needs a guarantee of
authentication and integrity, he will want at least the option of
confidentiality as well. The DSS was not intended to serve alone.
The DSS was a key element in a coordinated US government
strategy to block industry acceptance of any public key crypto in
software in order to force upon the market the NSA's version of
fully-GAKed PKC in silicon. This was the NSA's Capstone program --
strategic papa to CCEP, Clipper, GAKed Fortezza, key escrow/key
recovery, et cetera.
At the time, as any industry veteran will tell you, the NSA
had the US standards-development groups almost completely in its
thrall. As a reporter covering compsec and federal info security
policy at the time, I came to the conclusion that -- PGP and Phil Z.
as Jonny Appleseed notwithstanding -- it was only _because_ PKC was
patented, privately owned, and defended by Jedi Knights with a knack
for dirty street-fighting was there any future for strong crypto in
the US. (I still think historians will agree with me, although I
realize that it is an opinion shared by few on the Net's crypto forums
today.)
Ten years ago, the idea of mass market products which packaged
DES and a software version of public key crypto -- either RSA or D-H,
both then managed by the PKP partnership -- for key exchange was a
vivid NSA nightmare. The NSA's strategy for blocking this was to use
the NSA's control over the US standards orgs to block any American or
international effort to standardization around either RSA or D-H --
until the market accepted Capstone and GAKed key-exchange in silicon.
To meet the acknowledged market needs for a digital signature
utility -- and to prep the market for Capstone key management -- the
NSA came up with DSA (ignoring industry howls that DSA was 10-40
times slower than RSAPKC for verification -- then, as now, the
crucial functionality in digital signature apps.)
Watching NIST abjure its obligations under Brooks' Computer
Security Act of '87 to foster strong computer security for industry
and government and become a mere cat's paw for the NSA's
eavesdroppers in offering the DSA -- in what was clearly a strategic
ploy to undermine the acceptance and slow the adoption of public key
crypto with un-GAKed confidentiality -- was a turning point in my view
of the Clinton Administration and the prospects for privacy and
e-commerce in the US.
Democrats proved no more resistant than Republicans to the
blandishments of whispers from Fort Meade. (The lure of the Dark Side
of the Force is strong, my fellow geeks.)
Twenty year earlier I had provided Sam Ervin and the US
Senate's
Constitutional Rights Subcommittee with the internal US Army plans
which described the full extent of how Army intelligence agencies
were misused to illegally surveil US citizens during the Vietnam era.
GIs were assigned to track elected labor union officers, under some
1930s presumption that unions were radical hotbeds. (Honest!) Then I
had watched Congress heroicly struggle to force the revocation of
Reagan's NSDD 145, which had temporarily established the NSA as the US
Infosec Czar. The idea that the Pentagon and the NSA were again
presuming to claim hegemony in civil society irked me greatly.
People forget that with Clipper and Capstone, the NSA was not
only trying to GAK all commercial and personal communications, but
that the spooks of the NSA were also claiming the right to determine
which vendors would be allowed the privilege of integrating GAKed PKI
chips into their products. This was like giving the NSA a veto over
which entrepreneurs could get venture capital!
I think the historic importance of the Schnorr patents (at
least in the US) was that, in '92, when Claus Schnorr chose to align
himself with RSA rather than sell out to NIST and the NSA, he gave
RSA's Jim Bidzos a powerful weapon, at a crucial time, to counter the
DSS FIPS. Neither Prof. Schnorr nor RSA has suggested that any
challenge to DSS is pending, although the Schnorr patents are valid
until 2008, so at one level this discussion is a mere intellectual
exercise. Five years ago, when the DSS was issued, the Schnorr
patents posed the threat of an embarassing checkmate.
The existance of the Schnorr patents made the adoption of the
royalty-free DSA -- authentication and integrity, stripped of both
key-managment and confidentiality -- and the Capstone/Fortezza scheme
inextricably linked to it, much less attractive for US computer
vendors.
When RSA got control of the Schnorr patents, the NSA and NIST
pulled the plug on their campaign to foster commercial acceptance of
DSA. Balked -- NIST was forced to announce that they would assist
anyone RSA sued, if the sued firm was using DSS persuant to a
government contract, but everyone else was on their own -- the
strategists at the NSA turned instead to pushing the main event:
Capstone, Fortezza, and the Escrowed Encryption Standard (ESS).
With the threat of a patent suit -- and marvellous theater,
like when Bidzos got 20 major RSA licensees to purchase rights to the
Schnorr patents so that they could "legally" use DSA -- RSA managed to
stall widespread acceptance of the DSA just long enough for it to be
seen as what it was: part and parcel of the Fort Meade's overall
strategy to deny US citizens (as well as overseas customers of US
vendors) access to un-GAKed, interoperable, public key crypto.
The NSA's imprematur on DES gave it credibility and allowed its
widespread adoption with minimal liability within the private sector.
The DSA, just because it came from the NSA, never escaped the taint
of Capstone and Clipper, despite the fact that it was royalty-free.
Free code is a relative value. Context is all.
Suerte,
_Vin
[It is, I presume, clear that this is a personal statement and none of
my clients are responsible for these meandering recollections. I have
been a consultant to SDTI, RSA's parent firm, for many years, which
may have warped my judgement.]
========
"Cryptography is like literacy in the Dark Ages. Infinitely potent,
for good and ill... yet basically an intellectual construct, an idea,
which by its nature will resist efforts to restrict it to bureaucrats
and others who deem only themselves worthy of such Privilege."
_A Thinking Man's Creed for Crypto _vbm
* Vin McLellan + The Privacy Guild + <[EMAIL PROTECTED]> *
53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548
------------------------------
From: [EMAIL PROTECTED] (Matthias Bruestle)
Subject: Re: Biprime Cryptography, Part II
Date: Fri, 21 May 1999 09:07:20 GMT
Mahlzeit
kurt wismer ([EMAIL PROTECTED]) wrote:
> Mok-Kong Shen wrote:
> > Simple: Any permutation of the three characters.
> lets see if we can't avoid alphabetical order though... ARS Encryption
> just doesn't sound right...
Just reverse RSA and every sysadmin feels better.
Mahlzeit
endergone Zwiebeltuete
--
PGP: SIG:C379A331 ENC:F47FA83D I LOVE MY PDP-11/34A, M70 and MicroVAXII!
--
I hit myself and it was good.
-- Stuart Woolford
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: Reasons for controlling encryption
Date: Fri, 21 May 1999 14:43:00 GMT
On Thu, 20 May 1999 09:02:36 -0400, Mark E Drummond
<[EMAIL PROTECTED]> wrote:
>> Keep the good stuff out of the hands of organized crime for law
>> enforcement reasons.
>
>These are interesting because my superiors were discussing the idea of
>deploying enterprise wide user-to-user encryption using certificates and
>one argument _against_ it was that it would let the "bad guys" _inside_
>the organisation traffic inappropriate material. eg encrypting
>classified material or pictures of your neighbors daughter sans
>vetements and emailing it to your friend in <pick you enemy's country>.
If you stop to think about it, you have brought the national security
and law enforcement problem down to within your own enterprise.
Companies do have their network police. Companies do protect their
information and, if government contractors, the government's
information. Encryption hampers these efforts just as it hampers
similar efforts at the national level. Same problem, different scale.
> ... and emailing it to your friend in <pick you enemy's country>
It could be the next office, the next department or another facility
down the block. I personally know of one guy who requested encryption
for very valid business reasons. He then used it to encrypt email
between himself and a woman in the next department, with whom he was
having an affair. That relationship turned out to be very costly to
all involved, including their employer. Again, same problem, different
scale.
These sorts of things and plain old emergency data recovery are
reasons why key escrow techniques might be considered by the corporate
enterprise, as a means to have both security and authorized access.
>To me this is along the same lines as "security through obscurity" and
>it is about as dense as you can get.
If you try to put yourself in the position of other parties in the
puzzle, you can at least get an appreciation for their perspective and
concerns. Then, it becomes obvious that this has all the complexities
of gun control, plus the added complexity that these software guns can
be copied at vertually no cost and they do shoot.
I hope my partitipation in this thread has helped some people to gain
an appreciation of the perspective and concerns of other parties in
the puzzle. I've spent a lot of time with all parties involved and
have come to respect their mission, even if the means are questionably
logical. It's a very complex issue.
>--
>_________________________________________________________________
>Mark E Drummond Royal Military College of Canada
>[EMAIL PROTECTED] Computing Services
>Linux Uber Alles perl || die
>
> ...there are two types of command interfaces in the world of
> computing: good interfaces and user interfaces.
> - Dan Bernstein, Author of qmail
------------------------------
From: kurt wismer <[EMAIL PROTECTED]>
Subject: Re: Biprime Cryptography, Part II
Date: Thu, 20 May 1999 22:32:47 GMT
Nathan Kennedy wrote:
>
> David A Molnar wrote:
> >
> > John Savard <[EMAIL PROTECTED]> wrote:
> > > The alternative to it, whose patent has already expired, can be termed
> > > the MEPG algorithm (Mutual Exponent Product Generation), a special
> >
> > Please not this particular acronym. It's too close to MPEG and it's
> > hard to pronounce.
>
> In fact, don't change the name "public key cryptography" at all.
> I do not believe you could change that to anything more helpful.
i don't know... asymetric key cryptography may be a little more
descriptive...
at least to those who know what symetric and asymetric mean in general..
--
"close your eyes and bow your head
i need a little sympathy
cause fear is strong and love's for
everyone who isn't me"
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Biprime Cryptography, Part II
Date: 21 May 1999 17:04:14 GMT
wtshaw <[EMAIL PROTECTED]> wrote:
> Biprime may be a useful term, but it begs for someone to do algorithms
> that might be called Triprime or even more complicated; how do you group
> all of these sub-groups? And, you can certainly define algorithms of
> non-PK nature that use various numbers of primes in one way or another.
Note that RSA would still work if you had a modulus that was of the form
p^k * q, p and q prime. In fact, you get a possible speedup that way
by using the Chinese Remainder Theorem to compute modular exponentiations
over each of the small p s and the q independently before combining 'em
together.
Tsuyoshi Takagi had a paper along these lines, "Fast RSA_Type Cryptosystem
Modulo p^k q" in Crypto '98. Interestingly enough, there is a paper
on "Factoring N = p^r q for Large r" by Dan Boneh, Glenn Durfee, and
Nicholas Howgrave-Graham on the list of accepted papers for Crypto '99.
So maybe "medium-number-of-prime" cryptography might be a better idea.
-David Molnar
------------------------------
From: "Renegade" <[EMAIL PROTECTED]>
Subject: Re: Reasons for controlling encryption
Date: Fri, 21 May 1999 12:24:33 -0500
> I have heard various reasons why commercial encryption is being
> controlled and what real motives are behind these control maneuvers. I
> would like to learn more what you think that real motives behind many
> encryption control issues are and how, if true, this might be tied to
> some commercial and business interests.
Since epoch, USG has had unrestricted access to unencrypted communications.
Crypto systems will prevent that from happening. Since the US is leading
developer of the most used communication systems, export controls are
needede. Plus, you can't outlaw domestic crypto until you push the export
agenda.
------------------------------
From: AllanW <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Crypto export limits ruled unconstitutional
Date: Fri, 21 May 1999 16:50:39 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (wtshaw) wrote:
> In article <[EMAIL PROTECTED]>, Mok-Kong Shen
> <[EMAIL PROTECTED]> wrote:
>
> > If publication
> > in source code (valid program) is not allowed, then one can use
> > (almost) plain English to express the stuff (though maybe sometimes
> > in uneconomical ways) in such a form that a knowledgeable reader
> > can readily transform it into a program.
>
> Bear in mind that much source code is common between encryption and
> non-encryption software. With some simple instructions various lines
of
> code might berearranged, slightly modified, and/or copied to make
> something cryptographic or not. The instructions to make the changes
from
> noncrypto to crypto would definitely not be to a computer but to a
human
> who would have to act on them. It would make no sense to forbid the
export
> of programs that could be made into crypto because any program could
be so
> altered, be it laboriously in most cases.
The fact that it makes so sense is precisely what makes this decision
so important.
One of the "friend of the court" papers was from one of the
founders of the Apache Web Server project. The web server
had a hook for encryption. Note that the web server never
did have any encryption code, just a hook to make it
convenient for someone else to add an encryption routine
later. Nevertheless, government officials applied pressure
to have the hook removed. The apparent idea is that it's
dangerous to have this hook because it could be used to run
a subroutine, which in turn could be used to do encryption
if someone knew how to write an encryption subroutine.
This is no more ludicrous than having anti-smoking advocates
lobby to make flint illegal, on the grounds that anyone with
steel could use the flint to start a fire, which in turn might
be used to burn tobacco.
(If I had time to follow the stock market, I'd be rich, if
I also had $10 million.)
--
[EMAIL PROTECTED] is a "Spam Magnet" -- never read.
Please reply in newsgroups only, sorry.
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: Russell Harper <[EMAIL PROTECTED]>
Subject: Re: CRC16 polynomials
Date: Fri, 21 May 1999 17:58:33 GMT
Thanks, I did check there - lots of fluff but no real substance (like most
of the WWW) /Russell
Sundial Services wrote:
> Any search of Yahoo, e.g. on "CRC" or the like will produce a cornucopia
> of papers, source-code and so on...
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Crypto export limits ruled unconstitutional
Date: Fri, 21 May 1999 20:11:43 +0200
AllanW wrote:
>
> The demonstration is more nonsensical than you seem to realize.
> That translation program would itself be an encryption program!
> Somehow I doubt that there is any special protection for
> encryption programs which are used only to encrypt other
> encryption programs.
The main issue is export. The point is whether the English text is
exportable. There is no problem of using the translation program
even if it is regarded as an encryption program. (You are allowed
to use crypto software of any strength in US. You needn't tell
the authority that the text is from using the software.) If a
program can translate any C program to English and back then
it is a general software, just like software that translates
programs written in one programming language to another. Is a
compiler that translates C to assembler an encryption program?
M. K. Shen
------------------------------
** 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
******************************
