July 1993 - cypherpunks-legacy

Crypto Patent Abstracts #1
by J. J. Larrea 20 Jul '93

20 Jul '93

Cypherpunks, I finally got to the library to do some patent searches. Attached to this mail is summary information on 6 significant crypto patents. Note that some of the patent numbers which have appeared in prior postings on cypherpunks were incorrect, but I managed to track down the references via other means; someone should make sure they're correct in any relavent FAQs etc. Of the 6, I have full-text for 4 of them: Schnorr: 4,995,082 Gaffney: 4,562,305 Hellman-Pohlig: 4,424,414 Rivest-Shamir: 4,405,829 and partial text for one more: Hellman-Merkle: 4,218,582 I hope to be able to get a full version of Hellman-Merkle, as well as: Hellman-Diffie: 4,200,770 within a week. So, is there an FTP site I should place these on? Have fun, J.J. Larrea O / \/ /\ ~~~~~~~~~~~~~~~~~~~~~~~~~~~ CUT HERE ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ O \ US PAT NO: 4,995,082 [IMAGE AVAILABLE] L19: 1 of 5 DATE ISSUED: Feb. 19, 1991 TITLE: Method for identifying subscribers and for generating and verifying electronic signatures in a data exchange system INVENTOR: Claus P. Schnorr, Frankfurterstr. 81, 6350 Bad Nauheim, Federal Republic of Germany APPL-NO: 07/484,127 DATE FILED: Feb. 23, 1990 ART-UNIT: 222 PRIM-EXMR: Thomas H. Tarcza ASST-EXMR: David Cain LEGAL-REP: Hill, Van Santen, Steadman & Simpson ABSTRACT: In a data exchange system working with processor chip cards, a chip card transmits coded identification data I, v and, proceeding from a random, discrete logarithm r, an exponential value x=2.sup.r (mod p) to the subscriber who, in turn, generates and transmits a random bit sequence e to the chip card. By multiplication of a stored, private key s with the bit sequence e and by addition of the random number r, the chip card calculates a y value and transmits the y value to the subscriber who, in turn, calculates an x value from the information y, v.sub.j and e and checks whether the calculated x value coincides with the transmitted x value. For an electronic signature, a hash value e is first calculated from an x value and from the message m to be signed and a y value is subsequently calculated from the information r, s.sub.j and e. The numbers x and y then yield the electronic signature of the message m. US PAT NO: 4,405,829 [IMAGE AVAILABLE] L19: 3 of 5 DATE ISSUED: Sep. 20, 1983 TITLE: Cryptographic communications system and method INVENTOR: Ronald L. Rivest, Belmont, MA Adi Shamir, Cambridge, MA Leonard M. Adleman, Arlington, MA ASSIGNEE: Massachusetts Institute of Technology, Cambridge, MA (U.S. corp.) APPL-NO: 05/860,586 DATE FILED: Dec. 14, 1977 ART-UNIT: 222 PRIM-EXMR: Sal Cangialosi LEGAL-REP: Arthur A. Smith, Jr., Robert J. Horn, Jr. ABSTRACT: A cryptographic communications system and method. The system includes a communications channel coupled to at least one terminal having an encoding device and to at least one terminal having a decoding device. A message-to-be-transferred is enciphered to ciphertext at the encoding terminal by first encoding the message as a number M in a predetermined set, and then raising that number to a first predetermined power (associated with the intended receiver) and finally computing the remainder, or residue, C, when the exponentiated number is divided by the product of two predetermined prime numbers (associated with the intended receiver). The residue C is the ciphertext. The ciphertext is deciphered to the original message at the decoding terminal in a similar manner by raising the ciphertext to a second predetermined power (associated with the intended receiver), and then computing the residue, M', when the exponentiated ciphertext is divided by the product of the two predetermined prime numbers associated with the intended receiver. The residue M' corresponds to the original encoded message M. US PAT NO: 4,200,770 [IMAGE AVAILABLE] L19: 5 of 5 DATE ISSUED: Apr. 29, 1980 TITLE: Cryptographic apparatus and method INVENTOR: Martin E. Hellman, Stanford, CA Bailey W. Diffie, Berkeley, CA Ralph C. Merkle, Palo Alto, CA ASSIGNEE: Stanford University, Palo Alto, CA (U.S. corp.) DATE ISSUED: Apr. 29, 1980 TITLE: Cryptographic apparatus and method APPL-NO: 05/830,754 DATE FILED: Sep. 6, 1977 ART-UNIT: 222 PRIM-EXMR: Howard A. Birmiel LEGAL-REP: Flehr, Hohbach, Test ABSTRACT: A cryptographic system transmits a computationally secure cryptogram over an insecure communication channel without prearrangement of a cipher key. A secure cipher key is generated by the conversers from transformations of exchanged transformed signals. The conversers each possess a secret signal and exchange an initial transformation of the secret signal with the other converser. The received transformation of the other converser's secret signal is again transformed with the receiving converser's secret signal to generate a secure cipher key. The transformations use non-secret operations that are easily performed but extremely difficult to invert. It is infeasible for an eavesdropper to invert the initial transformation to obtain either conversers' secret signal, or duplicate the latter transformation to obtain the secure cipher key. US PAT NO: 4,562,305 [IMAGE AVAILABLE] L22: 1 of 3 DATE ISSUED: Dec. 31, 1985 TITLE: Software cryptographic apparatus and method INVENTOR: John E. Gaffney, Jr., Bethesda, MD ASSIGNEE: International Business Machines Corporation, Armonk, NY (U.S. corp.) APPL-NO: 06/452,248 DATE FILED: Dec. 22, 1982 ART-UNIT: 222 DATE ISSUED: Dec. 31, 1985 TITLE: Software cryptographic apparatus and method PRIM-EXMR: Salvatore Cangialosi ASST-EXMR: Aaron J. Lewis LEGAL-REP: John E. Hoel ABSTRACT: An improved software cryptographic apparatus and method are disclosed. The apparatus and method enables the encryption of the object code of a program so as to enable relocatable code operations. The apparatus and method will adapt program execution for a mixture of encrypted and nonencrypted code. A particular advantage of the apparatus and method is its accommodation of interrupts and branches while carrying out the cryptographic function. US PAT NO: 4,424,414 [IMAGE AVAILABLE] L22: 2 of 3 DATE ISSUED: Jan. 3, 1984 TITLE: Exponentiation cryptographic apparatus and method INVENTOR: Martin E. Hellman, Stanford, CA Stephen C. Pohlig, Acton, MA ASSIGNEE: Board of Trustees of the Leland Stanford Junior University, Stanford, CA (U.S. corp.) APPL-NO: 05/901,770 DATE FILED: May 1, 1978 ART-UNIT: 222 PRIM-EXMR: Sal Cangialosi LEGAL-REP: Flehr, Hohbach, Test, Albritton & Herbert ABSTRACT: A cryptographic system transmits a computationally secure cryptogram that is generated from a secret transformation of the message sent by the authorized transmitter; the cryptogram is again transformed by the authorized receiver using a secret reciprocal transformation to reproduce the message sent. The secret transformations use secret cipher keys that are known only by the authorized transmitter and receiver. The transformations are performed with nonsecret operations, exponentiation, that are easily performed but extremely difficult to invert. It is computationally infeasible for an eavesdropper either to solve known plaintext-ciphertext pairs for the secret cipher keys, or to invert the nonsecret operations that are used to generate the cryptogram. US PAT NO: 4,218,582 [IMAGE AVAILABLE] L22: 3 of 3 DATE ISSUED: Aug. 19, 1980 TITLE: Public key cryptographic apparatus and method INVENTOR: Martin E. Hellman, Stanford, CA Ralph C. Merkle, Palo Alto, CA DATE ISSUED: Aug. 19, 1980 TITLE: Public key cryptographic apparatus and method ASSIGNEE: The Board of Trustees of the Leland Stanford Junior University , Stanford, CA (U.S. corp.) APPL-NO: 05/839,939 DATE FILED: Oct. 6, 1977 ART-UNIT: 222 PRIM-EXMR: Howard A. Birmiel ABSTRACT: A cryptographic system transmits a computationally secure cryptogram that is generated from a publicly known transformation of the message sent by the transmitter; the cryptogram is again transformed by the authorized receiver using a secret reciprocal transformation to reproduce the message sent. The authorized receiver's transformation is known only by the authorized receiver and is used to generate the transmitter's transformation that is made publicly known. The publicly known transformation uses operations that are easily performed but extremely difficult to invert. It is infeasible for an unauthorized receiver to invert the publicly known transformation or duplicate the authorized receiver's secret transformation to obtain the message sent. *** END ***

2 1

Re: ANON: AP story
by smb＠research.att.com 20 Jul '93

20 Jul '93

The federal wiretap law was expanded in 1986 to prohibit employers, including the government, from accessing employee work computer records. Under the law, the government is allowed to conduct clandestine searches if the employee is suspected of espionage or theft. Pederson was under no such suspicion. [I guess this is the ECPA?] I'd like someone to provide some statute citations or some case law to back this up. As I read the ECPA, nothing in it prevents an employer from looking at employee files. (Admittedly, the government may be different.) The following quote is from @article{hernandez, title = {{ECPA} and Online Computer Privacy}, author = {Ruel Torres Hernandez}, journal = {Federal Communications Law Journal}, volume = 41, number = 1, month = {November}, year = 1988, pages = {17--41} } ECPA protection in the employer-employee situation may indeed be non-existent. [Footnote: This legislative intent to exclude corporate monitoring of employees from ECPA was confirmed by those who followed the drafting of the legislation. According to Jerry Berman, counsel for the Americal Civil Liberties Union, a participant in the drafting of th elegislation, ``ECPA `goes right up to the water's edge [of employee privacy protection] but stops short' and to have included some employee privacy protection against employers in the corporate context `would have killed the bill.' '' Electronic message from Brock Meeks (Mar. 31, 1988)] While the corporate exception acknolwedges an employer's property rights in all parts of his business, it leaves the employee's privacy interests completely unprotected. I should note that the ECPA also explicitly permits monitoring ``as may be necessarily incident to ... the protection of the rights or property of the provider of that service''. Again, if anyone has hard citations to the contrary, I'd really like to know. In the case that has drawn the most attention, the Epson email case, the claim was based on a state law that protects employee telephone calls. From what I've read, the judge rule against the plaintiff on the grounds that only voice calls were protected. That ruling was apparently not appealed, probably because there was little chance that that holding would be overturned. --Steve Bellovin

1 0

Re: It could happen to anyone (fwd Washington Post commentary)
by allan＠elvis.tamu.edu 20 Jul '93

20 Jul '93

Is it just me? Or does CNN just not cover things like the Randy Weaver trial when the gov't loses? -- Allan Bailey, UNIX programmer, CSC | "Freedom is not free." Infinite Diversity in Infinite Combinations | or: allan.bailey(a)tamu.edu 616c6c616e206261696c6579 | or: nefud-the-delirious(a)tamu.edu

2 1

steganograpy and cryptography
by Mike Johnson 20 Jul '93

20 Jul '93

Kragen writes: > I was thinking of steganography as being in two stages: first, you encrypt, > (possibly with the identity transformation) then, you embed your encrypted > message in your medium of transmission. My previous message was describing > requirements for a strong encryption algorithm, quite apart from the actual > embedding. I stand by my statements: the purpose of steganography is to make > it difficult or impossible for an interloper to determine that enciphered data > are being transferred. Thus, embedding a magic number in the file defeats the > purpose completely. > (As opposed to "slightly reducing security.") True. I was refering to cryptographic security instead of steganographic security when I said "slightly reducing security." Sorry about the miscommunication. For steganographic purposes, there should be no _constant_ magic numbers or CRCs taken _after_ the encryption (and visible in the ciphertext). All magic numbers and CRCs should be embedded _before_ encryption and checked _after_ decryption when you want the ciphertext to look purely random. This way you can have _both_ cryptographic convenience and random looking ciphertext ready for steganographic hiding. > I think that designing a program to embed this apparently random bitstream in > an innocent-looking file is a different and much harder problem. Definitely. Such a program is also very likely to drastically inflate the message, depending on the definition of "innocent-looking" and the characteristics of the channel or storage medium used. For example, a message could be concealed in the number of blank characters after each line of text from an recipe book, but someone might even get suspicious about a sudden interest in cooking among cypherpunks. :) By the way, I heard a rumor from a telephone company employee who I met (face to face) who is in a position to know that a U. S. company was using DES to communicate proprietary information between one of its facilities in Japan and an office in the USA. They got a letter from the Japanese parliament asking them why they were sending encrypted data. Perhaps there is more to the question of steganography than purely academic interest... ----------------------------------------------------------------------------- Mike Johnson | Opinions expressed herein are mine, and come with no mikej(a)exabyte.com | warranty, expressed or implied. PGP key on request. -----------------------------------------------------------------------------

1 0

Diffie-Hellman Weakness Weakness
by norm＠netcom.com 20 Jul '93

20 Jul '93

It has been mentioned several places that the Diffie-Hellman key exchange algorithm is subject to the man-in-the-meddle attack. There is a weakness in the attack that I understand. I suppose that the attack goes as follows where I am the man in the middle: I am able to install an active wire tap that allows me to substitute the data traveling in either direction. I have a fast computer to help me. I want to conceal my activity but learn what transpires. Upon receiving signals to begin DH protocol I respond to each side separatly "lets go". I establish a secret session key with each side. I am unable to cause the two keys to be equal except by passing the b^x going one way and b^y going the other. In this case I know neither x or y and can't read the traffic. I must choose my own random numbers zx and zy and replace b^x with b^zx and b^y with b^zy. X and Y now enter secure mode with the secret keys b^(x*zy) between me and X and b^(zx*y) between me and Y. I can read the traffic. If the connection is digitized voice and if X should happen to mention the low ten bits of b^zy to Y then Y would notice the discrepency since Y knows that he sent b^y. The jig is up. I don't know how to do voice recognition so as to intercept the vocal quotation of b^zy and change it to a quotation of b^y in a way that Y would not notice. I would have to simulate X's voice. Curiously there seems to be no analog of this precaution for digital DH communicators. If there is a secret protocol for comparing b^y over the nominally secured channel then there may as well have been a secret key in the first place. If there is a public protocol for comparing b^y then I can follow that protocol my self.

3 2

ANON: AP story
by Karl Barrus 19 Jul '93

19 Jul '93

In today's Houston Chronicle appeared a story ("Federal employee's computer searched after whistleblowing") which ties together cypherpunk concerns: whistleblowing, privacy, etc. I'll just type in a few paragraphs. Washington - The Resolution Trust Corp.'s top lawyer authorized a secret search of an employee's computer that turned up files detailing whistleblowing activities, a document shows. An internal agency memo shows RTC officials conducted the search after failing to persuade the agency's inspector general to do it, and says that the IG assured the RTC officials they wouldn't be investigated if questions were later raised. The IG's office disputes the claim. Officials at the savings and loan cleanup agency say RTC acting general counsel Richard T. Aboussie gave the go-ahead for the search because he suspected Bruce Pederson, a mid-level agency attorney in Denver, was doing personal business on government equipment. [1 paragraph deleted] Pederson has never disputed that the agency found personal matters in his files, arguing instead that the search was an invasion of privacy. Pederson said he believes agency officials were trying to punish him for being a whisleblower. "These evens are outrageous," he said. The search of Pederson's computer, first reported in May, occurred less that six months after he had criticized agency management practives in testimony before a Seante panel. He gained assurances at the time that he would not be retaliated against for airing his views. [2 paragraphs deleted] The federal wiretap law was expanded in 1986 to prohibit employers, including the government, from accessing employee work computer records. Under the law, the government is allowed to conduct clandestine searches if the employee is suspected of espionage or theft. Pederson was under no such suspicion. [I guess this is the ECPA?] [4 paragraphs deleted] According to electronic time stamps on each document, many of the letters and memos were generated on Pederson's government computer after normal working hours, the memo revealed. [Probably not cryptographic timestamps :-)] [3 paragraphs deleted to end of article] He should've used PGP!

1 0

recomendations for intro books
by nate＠VIS.ColoState.EDU 19 Jul '93

19 Jul '93

CPs, can any of you give me some recomendations on introductory books on cryptography? thanks, -nate sammons +-------------------------------------------------------------------- | Nate Sammons email: nate(a)VIS.ColoState.Edu | Colorado State University Computer Visualization Laboratory | Finger nate(a)monet.VIS.ColoState.Edu for my PGP key | #include <std.disclaimer> | "I have but one single desire - to tear down the sky" -A. Toomba | Quis Custodiet Ipsos Custodes? +----------------------+

2 1

AIS BBS
by XXCLARK＠indst.indstate.edu 19 Jul '93

19 Jul '93

Paul Ferguson wrote: >I'd like to get some of your collective thoughts an a matter >which has stirred quite a debate in the free-information/computer- >virus-exchange arena. Okay... The stated charge against Kim Clancy is that she posted [or allowed to be posted], among other contraband, virus disassemblies [poor, by your reckoning]. But, as the complaint emerged on VIRUS-L, I suspect the actual offense, far worse in the eyes of builders of empires and reputations was that she openly and knowingly consorted with known "hackers" and other underground types. I suggest that what so belatedly brought the wrath of the self-righteous down on Kim Clancy is that she broke the rules of the inner circle of the VIRUS-L self-appointed elect. While Kim Clancy is not the only security type to knowingly and openly communicate with the unwashed, she is one of the few to demonstrate an excess of intelligence over ego. She would seem to know that no one person or group is the font of perfect knowledge. If the US military didn't learn from the VC, was it the VC's fault? There is, of course, little so conducive to the enhancement of undeserved reputation as that based upon knowledge alleged to be so dangerous and so sacrosanct that no one outside the inner circle can be trusted with possession. Sounds like a disease all too common inside and about the beltway, among TLA's and bureaucracies, both corporate and governmental. VIRUS-L Digest I find amusing, a suitable substitute for MAD Magazine. I've never seen it undigested, but if the signal-to-noise ratio is as poor as in the Digest, it must be gargantuan. Budding shrinks and social studies types looking for new ground to work just might find material for several dissertations there. VIRUS-L Digest seems the perfect place to look if one is bent on studying the cult of the self-appointed, self-important keepers of the myth of the mainframe priesthood. There is information there, but, as Eliot wrote in one of the Sweeney poems, "the trouble is, I gotta use words when I talk to you." Therefore, in VIRUS-L Digest, most of the information is between the lines. And some residing within the select inner circle don't have quite the depth of knowledge they think. For the record, Paul, I do not have knowledge of any virus exchange boards. I am sure they exist, I just don't know of any. And for yourself and Peterson, I've never inquired of anyone for any such information. I believe I can meet Peterson's criteria for admission to his tutelage, but have neither need nor desire... which may have been the point to his recent... challenge. I am curious how your foreign colleague discovered this threat to western civilization. As I understand it, the AIS BBS is a dial-up board. Was he running a demon dialer across the net? Was he working for MI-5? Your "exposure" of an open secret seems to me not unlike what happens on the playground during recess. Much ado about nothing. While the danger of viruses is real, I do believe those who would be our protectors have learned something from that branch of the Department of Corporate/High-Tech Welfare [aka Department of Defense], which, not content with probably unconstitutional military involvement in law enforcement, is now attempting to drum up new contracts to protect us from the comet/asteroid menace. Crikey. I dunno about secret cabals of "underground hackers" out to get you... I think the danger there is about as great as that to Bozo Reagan from "secret Lybian hit squads." Save me from legends in their own minds. No more fucking secrets... You asked... --------------------------------------------------------------------- internet : xxclark(a)indst.indstate.edu RelayNet (488) Vanilla BITNET: XXCLARK@INDST FidoNet (1:2230/114) Phone: 911 TechNet 11:800/0 One need not be a weatherman to know which way the wind is blowing. ---------------------------------------------------------------------

1 0

Re: It could happen to anyone (fwd Washington Post commentary)
by peter honeyman 19 Jul '93

19 Jul '93

> We need to be as prepared as Randy Weaver was! tell that to his dead kin. we need to be prepared, but not as randy weaver was. peter

1 0

Re: Diffie-Hellman Weakness Weakness
by smb＠research.att.com 19 Jul '93

19 Jul '93

If you compare the digital interceptor, to the voice interceptor, fairly, you will see they are in equally strong positions. When I am phoneing a person I know, I am automatically checking the `signature' of their voice. The other party on the line might be able to convince me they have a cold, but I hope I will have enough wisdom to postpone discussing the March 15th assassination plot untill the cold clears up. So we should compare a voice interceptor on a channel where the two people don't know each other's voice to the unsigned digital interceptor. In this case, the interceptor can claim to one party to be the other party, and remain undetected. This is the Diffe-Helman weakness. Alternatively we should compare the voice interceptor on a channel where the two people do know each other's voice to the signed digital interceptor. In this case, the interceptor will either be detected should some minimal authentication and verification be tried, or the interceptor will be unable to even listen in. The weakness remains here, but it has been patched over with authentication, and signed verification of the channel key. This is the Diffe-Helman weakness weakness. The (potential) interceptor is the reason why we must be so very carefull when validating other people's public keys. I know there is no interceptor between me and the people who's keys I sign. If I can be sure of no interceptors between one of them, and the person I wish to speak to, then I will be able to establish a secure channel. The AT&T Telephone Security Device (you know, the beast with the Clipper chip...) has a display that shows a few digits of a hash of the key. Each party reads off some of it to the other; the idea is that an intruder won't be able to spoof a voice in real-time. For data connections, have a look at @article{interlock, author = {Ronald L. Rivest and Adi Shamir}, journal = {Communications of the ACM}, number = {4}, pages = {393--395}, title = {How to Expose an Eavesdropper}, volume = {27}, year = {1984} } The idea is to send half of an encrypted block. You then await a half-block from the far side, at which point you send your other half, and listen for the far side's other half. The idea is that since one can't decrypt a half-block, the intruder in the middle can't send a fraudulent one. Depending on how this scheme (known as the ``Interlock Protocol'') is used, it may be vulnerable to attack. Davies and Price, in their (excellent) book ``Security for Computer Networks'', suggest sending passwords that way. But Mike Merritt and I showed how to attack that scheme under certain circumstances. (Details to appear in IEEE Transactions on Information Theory.) --Steve Bellovin

1 0