December 2003 - cypherpunks-legacy

Re: Why RSA?
by derek＠cs.wisc.edu 17 Dec '03

17 Dec '03

First, my sincere gratitude for the replies to my queries regarding public key cryptography patents. To pay back such generosity, I will summarize. Also, I have done a little more digging and will present my findings, even though those findings include more questions! My original question was why cypherpunks don't just pick some non-RSA public key algorithm to achieve widespread distribution of cryptographic tools. My contention is that for such widespread distribution to occur, the price must be small in comparison to the average user's electronic communication outlay, and the tools must be beyond reproach legally so that it can be distributed by commercial email tool providers in a form that is elegantly integrated into the user's environment. My mother will not fetch, install, and configure PGP, though she might pay $10 - $20 more for an email product with "privacy enhancements". My reading of the comp.patents FAQ leads me to understand that any use of PGP by an individual in the U.S. is in violation of U.S. law (though the chances of being prosecuted are vanishingly small). Cypherpunks probably don't care too much about that, but the masses waiting for conversion probably do. The reasons for the desirability of widespread public key tools are obvious, even without considering the collapse of governments. For example, digital signatures can be used to authenticate electronically-distributed software upgrades, and so on (but this is all old hat to the folks on this list!). Unfortunately, as Perry Metzger pointed out: > All are patented in so far as one of the patents covers ALL public key > schemes. Some, like Rabin's scheme, have possible technical advantages > over RSA. First, a note: "Rabin's scheme" is (as Perry said) the one provably linked to factoring (a major advance!) and I assume it's the one implemented in RPEM. According to the RIPEM FAQ, PKP squashed that development by claiming that their patents were broad enough to cover Rabin's scheme, and the effort was abandoned "for pragmatic reasons" (another example of how superior technology can be suppressed by monopolies). Now, I've looked a little further into the patent issue, and I remain kind of confused. I went to the library and read the four patents in question (but only made a hardcopy of the first chronologically). I found the documents difficult to understand (for legal rather than crypto-tech reasons). All four applications were made in 1977-1978, and the patents were granted variously from 1980-1984. The earliest one has Hellman, Diffie, and Merkle as inventors; the second just Hellman and Merkle. Both are assigned to Stanford University. It seems to me that one of these is the one that covers, broadly, public key cryptography -- presumably the earliest one (4,200,770), since it has all three major players as inventors and the language of the eight claims seems to be rather broad (though only the second patent, 4,218,582, has the phrase "public key" in its title). Patent 4,405,829, granted in 1983, is for the RSA algorithm [footnote: the RSA patent apparently celebrated its tenth birthday two days ago; was there a party?]. There is no overlap between this patent's inventors and assignees and the earlier more general patent. Here's a question for somebody in the know: if the earlier patents cover all public key cryptography and RSA is a public key system, isn't it in violation of the earlier broader patent? Does PKP pay license fees to Stanford, or were they granted exclusive rights by Stanford as well as MIT? Similarly, apparently a public-key scheme called Warlock has been granted patent protection. How is this possible if somebody else holds patents covering all of public key encryption? If I understand patents correctly (hah!) they last for 17 years from the time they are granted. This means that the earliest public key patent will expire in about 3.5 years. After that presumably there will be no restrictions on new public key systems. The RSA patent would expire in 2000. If somebody could clarify which patent is the "broad" public key patent, I'd appreciate it (even with them right in front of me, I can't tell)! My guess is that it would have to be either 4,200,770 or 4,218,582 -- if it's the latter, how did Merkle get squeezed out of inventorship? Respondents to my initial questions pointed out that the patents may be over-broad and could be challenged on those grounds; given the history of how public key crypto was invented, it seems to me that it would be difficult to contend that the idea is obvious (Simmons says that the idea "stunned" the crypto community) -- but I'm no lawyer, and I'll leave that issue to those with more skill, brains, and money than me! For now, then, my conclusion is that for four more years at least, licensing RSA from PKP is probably the only viable commercial option for companies who wish to give their users public key crypto capabilities. It seems that the designers of Internet Privacy Enhanced Mail (PEM) agreed with this assessment, as they took the unusual step of including proprietary RSA in their standard. For their part, in RFC 1170, PKP states: "We assure the interested parties that Public Key Partners will comply with all of the policies of ANSI and the IEEE concerning the availability of licenses to practice this art. Specifically, in support of any RSA signature standard which may be adopted, Public Key Partners hereby gives its assurance that licenses to practice RSA signatures will be available under reasonable terms and conditions on a non-discriminatory basis." That sounds good -- but is troublingly vague. I have stated earlier what *I* think is are "reasonable terms" for the inclusion of a minor feature like PEM-compliance in an email processing system, but I don't get to decide that. If anybody knows more specifically how the standards bodies interpreted "reasonable", please let me know. As I am contemplating developing a PEM-compliant product, I will be writing to PKP to discuss licensing arrangements, but information from others (best: expressed publicly) would be helpful. If RSA is the only game in town, let's at least be clear about the price of admission. There seems to be a chance that manufacturing PGP-aware products (but not distributing PGP itself) could slide by, but it could also be interpreted as "inducement to infringe" which would apparently be actionable. The second point in my earlier message, largely obsoleted by the answer to the first, involved the development of new public key systems. Given that selling or otherwise using or distributing a new system now would invite litigation, the question is rather moot, but I'd like to thank L. Detweiler and P. Metzger for their comments on the all-important issue of trusting new algorithms. Finally, I suppose that it's always possible to come up with some radically new encryption technique that could be used to support authentication and yet have nothing to do with public key crypto... but I'm not holding my breath. Regarding the recent proposals for the construction of a toolkit, I'm all in favor and would personally welcome the opportunity to contribute to such an effort as a hands-on supplement to my crypto education. I have extensive experience with C and C++, and am VERY familiar with TCL (pronounced 'tickle', for those not in the know). A good start would be a clear statement of purpose. If this "Why RSA" thread has been too basic and has caused frustration for that reason, please forgive me. I have learned a great deal, and I hope that somebody somewhere else has profited as well. derek

5 6

Re: NY Times Article...
by freeman＠MasPar.COM 17 Dec '03

17 Dec '03

> Now, the real question is, will those who still call themselves "post- > human" in a million years have learned much worthwhile since the > extinction of homo sapiens? :) Fellow post-Australopithecines, how goes it? 8:) -- Jay Freeman

1 0

Re: the public key minefield
by baumbach＠atmel.com 17 Dec '03

17 Dec '03

> derek(a)cs.wisc.edu (Derek Zahn) > >* in broad terms, what would I have to do to develop an > > algorithm that works from a user's perspective like > > p.k.c. (ie public/private keys, the central functional > > point of all the wonderful schemes based on pkc) but > > doesn't violate patents? L. Detweiler writes: > others have well addressed how patent issues are involved in this. but > this appears to be a simple technical question on one level. What does > it take to come up with a good public key system? How about a poor public key system? What is the simplest public key system you can invent, if you didn't care that it is trivial to break? If the NSA can crack RSA, does that change the fact that it is a pkc? message=99 public_key= 1/3 private_key= 3 encrypted_message= message * public_key message= encrypted_message * private_key Would PKP reading of their patent claims cover this pkc? Seems overbroad! Peter Baumbach baumbach(a)atmel.com

1 0

Public-Key Crypto Toolkit
by Mike Ingle 17 Dec '03

17 Dec '03

What we need is a toolkit which makes it easy to write public-key applications. This would be an easy interface to the routines in PGP. I was thinking of doing this in Clisp under Linux, since Lisp makes it easy to put together and take apart complex objects, and makes it easy to kick around objects of arbitrary size. Unfortunately Clisp does not seem to support calling C functions! Perhaps it could be hacked right into the Clisp source code, giving it a fast modmult, idea, md5, etc. Any ideas as to what language/method would be best for implementing a PK toolbox? This could really get the "Cypherpunks write code" ideal moving. Anyone want to help? It should not contain any cryptography in itself - you should link it with the crypto from pgp, optionally applying diffs to the source files first, so that there is no fear of distributing crypto or violating patents. --- MikeIngle(a)delphi.com Brought to you by AT&T ClipperPhones - reach out and tap someone!

4 4

No Subject
by Eric.K.Kuecherer＠Dartmouth.EDU 17 Dec '03

17 Dec '03

Please remove me from the list. -kuech-

1 0

Re: a horrible conspiracy revealed!
by gtoal＠an-teallach.com 17 Dec '03

17 Dec '03

> I wonder what the significance of L. Detweiler's name is? Obviously > its a Germanic name. Perhaps he's a Nazi... in fact, he might be the Graham> I sincerely *hope* this article was a forgery, Graham> otherwise Perry you're digging yourself a big Graham> credibility hole. Drop it, please. I guess you didn't get it huh? I'm really sick of the flame wars on here, but this one had me laughing on the floor. No, I did get the joke, I just didn't think it was funny. I *do* remember the thread some time ago of Perry being accused of being a Nazi because a well- known Illinois Nazi has the same surname. I meant he was losing credibility for indulging in childish games, not for meaning whatever he said literally. I'd rather the pair of them just let it drop, instead of trying to outsmart each other. G

3 2

META: Re: a horrible conspiracy revealed!
by jrk＠sys.uea.ac.uk 17 Dec '03

17 Dec '03

I was about to do an ::exclude on this thread, when I realised that it was the cypherpunks list and not the extropians. Any chance of cypherpunks running the extropian list software? Or maybe it does already? -- ____ Richard Kennaway __\_ / School of Information Systems Internet: jrk(a)sys.uea.ac.uk \ X/ University of East Anglia uucp: ...mcsun!ukc!uea-sys!jrk \/ Norwich NR4 7TJ, U.K

3 2

Re: Clipper specifics (more)
by koontzd＠lrcs.loral.com 17 Dec '03

17 Dec '03

>From MIKEINGLE(a)delphi.com Wed Sep 29 20:44:02 1993 >Where do you get the MYK spec? From: Mykotronx, Inc. 357 Van Ness Way, Suite 200 Torrance, CA 90501 (310) 533-8100 FAX (310) 533-0527 The cover title is "VLSI Encryption/Decryption Device Data" The title block on the first page is "MYK-78 Encryption/Decryption Device" There is no copyright notice, I'm a bit vague on whether such notice is required at present. Each page bears the trademark of Mykotronx. >Do Type 1 chips use 80-bit keys like Clipper? One of the characteristics of data sheets for type I chips incommon with the MYK-78, is that no where are byte counts mentioned. The specs instead refer to reading or writing requisite bytes to satisfy testable flags. Even examining key storage device specs (Crypto Ignition Key, etc.) no byte counts are mentioned, rather a count value is specified in the header structure. One could assume that the key size of a type I device is classified. Some with exposure to Type I implementations believe that independent round keys are loaded, requiring a lot more storage. Having seen references to the cryptographic check word in Type I specs, I don't. Type I chip Cryptographic Algorithms (CA) are not specified in theire unclassified spec sheets and are presumeably classified. It is my personal belief that the cryptographic algorithm (SKIPJACK) may be the same as used in Type I devices. Major differences other than ambiguity with respect to the cryptographic algorithm, between Clipper and Type I devices includes: 1) No Red/Black Separation the MYK-78 has a single data port 2) The MYK-78 allows you to "fish" for the Cryptographic Check Word (CCW), a value used to verify the key has been loaded correctly. Type I devices require the CCW be correct, otherwise requiring passing through reset. This implies a central key management authority. 3) Strict certification requirements for Type I implementations, similar to that done for devices/firmware/software used for controling and releasing nuclear weapons. One presumes the level of testing for Escrow Encryption Standard compliant devices will be done to the black box level if conducted by NIST. 4) Some Type I chips include two sets of Cryptographic Algorithm hardware for FULL DUPLEX operatiion in a communications environment. There are otherwise higher levels of integration as well. 5) Type I chips generally contain provision for remote rekeying and remote zeroizing. Presumeably these same facilities are instead dedicated to the Law Enforcement Exploitation Field in the MYK-78. 6) At least one Type I chip is a hybrid, also cotaining an Intel 8051 type microprocessor. It is possible that the same silicon is used for clipper and Type I devices, were two different I/O pads (red and black ports) located adjacent but interleaved, with the same package pin bonded to both pads. Enabling CCW fishing could be a bonding option. While one could argue that red/black area partitioning might be employed on the silicon it is worth remembering that during encryption, only the final product is black, and for decryption the final product is red. The flexibility in control programming mentioned for the MYK-78 could reflect the requisite ability to control red and black ports as well as using remote rekeying/remote zeroizing facilities for LEEF. >How far ahead of such cyphers as IDEA and 3DES are the Type 1 cyphers? >Much more secure, or are we pretty close to *them*? Judging from the clipper chip, not much. The number of clocks for executing the CA in a Type I chip is the same as the clipper chip (64 clocks). The MYK-78 has been publicly stated to perform 32 rounds (one could image 64 rounds in 64 clocks). #From: wcs(a)anchor.ho.att.com (Bill Stewart +1-908-949-0705) ... #There's a little more information than that, though not much. #The Mykotronix blurb says that the algorithm uses S-boxes, and takes #64 clocks to do the encryption; I think someone said it's 32 rounds of >S-boxes, which would correspond well with this. ... #My personal speculation is that it's probably about 24-key-bits #stronger than DES, but I don't have a good guess on the weak keys issue. In Dorthy Dennings preliminary report on Skipjack there were several points of interest brought up in the overview on the cryptographic algorithm: 1) Differential Cryptanalysis ...We concluded it was not + possible to perform an attack based on differential cryptanalysis in + less time than with exhaustive search. -- Increasing the number of rounds descreases the S/N ratio. Changing The XOR for mixing key and data iin the cryptographic function f(R,K) to an adder would likewise make exhaustive search faster than differential cryptanalysis for DES (Chapter 4 of E. Biham and A. Shamir "Differential Cryptanalysis of the DES Encryption Algorithm", 1993 Springer-Verlag.) 2) Weak Keys + ... We saw no pattern of symmetry in the + SKIPJACK algorithm which could lead to weak keys. -- A key is weak when the encryption function and decryption function are identical (the same key works for either) 3) Symmetry Under Complementation + ...We tested SKIPJACK for this property and found + that it did not hold. -- In DES K XOR E(R) == !K XOR E(!R). All three of these can be defeated by exchanging the XOR between key and data in f(R,K) with adders. The carry is a good place to introduce more key bits per round (8 bits when modulo 64). Subtraction is used for decryption and addition for encryption (or vice versa). The key schedule is relatively easy to extend to 80 bits from 56. It might not be this easy, but then again it could. DES also has a property of the S boxes that collectively map a 32 bit input value (R) to a 32 bit output value (SboxP) according to a 48 bit subkey (Kn) that for a large portion of the keys, there are not 2^32 distinct output values. Where the holes occur in the output domain are dependent on the key, and key and not key have the same holes. Exploring this property has led investigators to discover differential cryptanalysis and linear cryptanalysis. If it were possible to "see" the output of the P permutation directly you could discover the round key (Kn) over a large amount of chiphertext by simply checking for 32 bit symbols that don't show up. Correlating missing symbols to keys is a momentous task, potentially requiring years. It is possible that a 4th category of cryptanalysis attack (Brute force is the other method) is predicated on this property (D.W. Davies cryptically :) mentions a method of discovering 16 key bits in his book published in the U.S. in 1983, I believe). Skipjack may have provision for defeating this hypothetical attack.

1 0

PGP in FIDO
by anonymous＠extropia.wimsey.com 17 Dec '03

17 Dec '03

* Reply to msg originally in CYPHERPUNKS > My question is this: how does he know that the mail is encrypted if he's > not examining the mail that passes through his system? If he *is* > examining the mail that passes through his system, it seems likely that he > is violating the Electronic Communications Privacy Act. In that FIDOnet mail points (or individual BBSs) are not required to pass or accept encrypted FIDO traffic under FIDOnet rules, some run a specific program that scans for the "PGP MESSAGE" string and bumps it to a SECURENET mail hub (or, in some cases, _kills_ it). It is not done by individual, personal inspection - at least not at mail hub level. Anyway, the ECPA is basically irrelevant in the BBS world, as 1] almost every BBS states at log-on that there is no such thing as truly "private" e-mail on the system as the sysop can, will and does see messages in all areas, and 2] he is personally _liable_ for any illegal activity on his BBS, so he can reasonably be expected to keep an eye on e-mail for anything that will put his ass in a sling. There has been a very heated war in FIDOland over PGP and other encryption. Considering the risk that sysops take on by permitting secure (?) communication on their BBSs, I must say I admire their courage when they allow it and participate on SECURENET. Personally, _I_ would never stick my neck out like that, though I convinced many FIDOnet BBSs to do so for my own political and purely selfish reasons. BTW, this message comes via FIDOnet and was originally PGP encrypted for the remailer, and the cypherpunks(a)toad.com mailing is converted to a conference on a FIDO BBS where I read the message to which I am responding.

10 25

POISON PILL
by Matthew J Miszewski 17 Dec '03

17 Dec '03

Sandy, There are a number of ways in which you can set up *your* machine to self-destruct. The best way to accomplish this is through Perry's suggestion of a regular security check to which you must reply or the PILL is activated. If all you are concerned about is private mail or the like, a simple batch wipe file would work (hide the wipe program). Putting any prompt at boot and turning off obvious ways of defeating *your* security will help. Not to start everyone flaming, but there is nothing wrong with destroying your own computer thru infamous combinations of interrupt hooks and the like (was that cryptic enough to avoid a virii flame?) --Matt ______________________________________________________________________________ "This new technology (the printing press) threatened the Crown, which shuddered at the thought of widespread dissemination of works advocating religious heresy and political upheaval. The Crown's solution to the problem was a system of regulation designed to control this "dangerous" art." -From my Copyright Law Text (refrencing the Statute of Anne - the first Copyright Statute) (c)1993 ______________________/___________________________________mjmiski(a)macc.wisc.edu

1 0