- cypherpunks-legacy@lists.ogf.org

dc-nets implementation (protocol spec)
by yanek＠novavax.nova.edu 13 Dec '92

13 Dec '92

I am writing a dc-net implementation. What follows is some design discussion, a protocol specification that defines the interaction, message format, and file formats, followed by notes, and plans for future enhancements. A basic familiarity with the concept of dc-nets is assumed, for people new to this, see Chaums's article on the topic, posted here recently. I am assuming interaction through e-mail because this is, right now, the most accessible medium. A more efficient approach would be to use a true broadcast media, such as coax cable, or satellite. But coax only works for local areas, and not everyone has satellite uplink capability. In the future, I envision all or most local area networks running their own small dc-nets that use ethernet broadcast, these being linked hierarchically to medium-level dc-nets that use any internet type of communication medium (udp datagrams, tcp connections, smtp, usenet news, shared ftp space, etc) or other regional communication such as radio (amateur packet radio, spread-spectrum, or even CB) , and these finally being linked into global dc-nets that use satellite broadcast. This type of system would achieve the truly anonymous global communication system, similar to what Vinge describes in True Names: He dumped the last twenty-four hours of the world bulletin board into his home memory space and began checking through it. The bulletin board was ideal for untraceable reception of messages: anyone on Earth could leave a message [...] If a user copied the entire board, and /then/ searched it, there was no outside record of exactly what information he was interested in. There were also simple ways to make nearly untraceable entries on the board. DC-nets will remove the "nearly" from the last sentence. The system I am writing is for research purposes only, I would like to have about 6 to 8 people running it, and then observe it in action. I am not aware of any existing, operational dc-net. If you know of one, please let me know. I would not like to develop a new, incompatible protocol if it is not fundamentally better than something existing. The dc-net system is independent of how the keys are distributed/created. This system assumes that there is already a key stream existing between any two users, that it can use. There are several methods by which keys can be distributed. The most secure would probably be to use a hardware RNG to generate a one-time pad, which is then trasfered by some secure means (exchanged on floppies in person, or put on a 4GB DAT tape (4mm, $20 or less) and sent by some courier service, etc). Another possibility is to use Diffie-Hellman protocol to agree on a set of keys. The simplest method, and one I chose to use in this project, is to generate a random key stream, encrypt it with the other person's public key, sign it with yours, and send it through e-mail. See the next message for details on message formats used for this. Again, the core dc-net system described in this message is in no way dependent on this form of key exchange. Any other key distribution method can be "dropped in" without changing anything. The design document follows: -------------------------------------------------------------------------- ALGORITHM (pseudocode): This algorithm is executed independently by each participant. The list of participants, RBSIZE, and MSGSIZE must be agreed on beforehand. There must be an existing keystream, or a way to receive one. Begin Round (increment round number) Stage 1 (reservation): Take RBSIZE bits off everyone's pad, xor all together. For every message you need to send, reverse a random bit. Sign with your public key, and transmit to all. When received everyone's block, xor all together. If result is all zeros, round ends. Go on to the next round. Stage 2 (transmission): For every '1' bit in reservation block: Begin Message (increment message number) Take MSGSIZE bits off everyone's pad, xor all together. If the bit was reserved by you, xor with your message. Sign with your public key, transmit to all. When received everyone's block, xor all together, getting message. If message was yours, verify it, mark it as sent. If not, it is a message from someone else. Process as an incoming message. End Message (go to next set bit of reservation block if any) End Round (go to next round, optionally delay to save bandwidth) ---------------------------------------------------------------------------- MESSAGE FORMAT: (messages are sent as signed, armored, non-encrypted PGP messages) Subject: dc-net transmission DCNET <network>; ROUND <round>; PARTICIPANT <userid>; STAGE <stage> [MSG <n>] <binary data stream follows> ---------------------------------------------------------------------------- FILE FORMATS: dcnet/<netname>/myname your own participant name for that network dcnet/<netname>/participants list of participants and addresses in the following format: <userid>:<address> dcnet/<netname>/pad/<participant> one-time pad for the user, straight 8-bit binary data optionally pgp-encrypted with your public key, signed to prevent disclosure and tampering; these options not implemented yet dcnet/<netname>/spool/<stage>/<participant> spool where you store responses received, until you receive all of them. Your own responses are stored there too dcnet/<netname>/outgoing/* messages you need to send, one message per file. should be stored encrypted too. dcnet/<netname>/incoming program that will process any messages received from this network. In the simplest case this would be a shell script that puts the message to the user's mailbox. But it could also drop it into another net's outgoing directory if it matches some criteria, or it could be posted to a newsgroup, or anything else you want to do. dcnet/<netname>/log this file contains log of transmissions received times and sizes. it should only contain public information, so it can be posted for analysis of net efficiency, bandwidth used, etc. ------------------------------------------------------------------------ NOTES: I must thank the ILF (Information Liberation Front) for their timely post of Chaum's article. I had started with the two-person example provided in the cypherpunks glossary, and independently extended it to apply to any number of participants, and had progressed up to the idea of hierarchial dc-nets, and was struggling with the question of collision detection, when the article was posted. Chaum's reservation blocks are an elegant and efficient solution. His formal proof of security is also reassuring. RBSIZE is the number of bits in the reservation block. This should be much larger than number of participants, to minimize the chance of two participants randomly reserving the same bit (in which case the transmission has to be retried in the next round). A convenient number to use is 1024 bites (128bytes), if the number of users is small. When operating in idle mode (no messages to be sent), RBSIZE bits are sent to each participant each round. So the total bandwidth used is, assuming 1kbit RBSIZE, 25 participants, and two rounds an hour, about 150 kilobytes per day sent and received by each participant, or about 14 bits per second. This is quite insignificant, considering today's communication equipment. MSGSIZE is the size of a message. This should be about the size of an average message, not the largest one. Making this too large will waste bandwidth. I will use message size of 5kilobytes. This is quite small, but enough for research purposes. This will make the messages several screenfuls long. Longer messages can be split into parts, and reassembled. For example, this message would be split into two parts. For each message that is sent, the number of bytes that every every participant must send and receive is MSGSIZE times the number of participants (using the above assumptions, 125 kilobytes). Using a true broadcast media would dramatically reduce these bandwidth requirements, making large-scale systems with many participants feasible. This implementation uses a <netname> to distinguish between separate dc-nets a user may be participating in. A netname can be any string, subject to filename limitations. Keeping them alphanumeric and under 14 chars should work on most machines.. They might also be case insensitive. Netnames do not have to be globally unique, one person just can not be on two nets of the same name. Persons are referenced to by <participant>, which would normally be the username but can be an arbitrary string subject to the same limitations. Two perople with the same participand name can not be on one dc-net. Are any of you amateur radio (HAM) operators? I would be interested if this system could be run over packet radio. Are there any regulations against encrypted traffic? ---------------------------------------------------------------------- FUTURE ENHANCEMENTS: In addition to mail-based interaction, usenet newsgroups, ethernet broadcasts, shared ftp access, and tcp connections should be supported. A protocol for dynamically adding participants to the net, removing oneself from the net, or changing the address should exist. A way to deal with malfunctions, such as not receiving a message from a participant. Currently the net will wait forever, for that one message to arrive. A time-out should probably established, after which everyone will re-send their contribution without including the missing person. This is potentially dangerous, since it is equivalent to disclosing that participant's key streams. Since one-time pad is used, this will not compromise earlier communication, but the person must be notified if they ever come back on-line to not use that portion of key again. Support for encrypted and signed storage of keystreams and outgoing messages. A protocol for routing messages between hierarchical dc-nets. Automatic splitting of messages longer than MSGSIZE. A way to indicate the message size in the allocation block, so communications would not be wasted on small messages, and large messages would not have to be split into pieces. ----------------------------------------------------------------------- PLEASE send any comments, criticism, or ideas to: -- Yanek Martinson mthvax.cs.miami.edu!safe0!yanek uunet!medexam!yanek this address preferred -->> yanek(a)novavax.nova.edu <<-- this address preferred Phone (305) 765-6300 daytime FAX: (305) 765-6708 1321 N 65 Way/Hollywood (305) 963-1931 evenings (305) 981-9812 Florida, 33024-5819

1 0

Remailer problem at rebma fixed
by Bill O'Hanlon 12 Dec '92

12 Dec '92

My apologies to those who have used PGP with the remailer at rebma over the past week. I upgraded to pgp2.1, and I failed to notice that the PGPPASS environment variable has given way to the -z password option. Users of Hal's remailer scripts take notice. I ran the mail through that had failed, so there might be duplicates of messages sent out, since some people might have resent the message if they didn't see it go by (that is, if they sent it to something where they'd see the result, such as the cypherpunks list.) Sorry for the inconvenience. -Bill -- Bill O'Hanlon wmo(a)rebma.mn.org

1 0

no subject (file transmission)
by nobody＠soda.berkeley.edu 12 Dec '92

12 Dec '92

Cypherpunks! Like several people (I guess), I am working on an implementation of digital cash. Because of the possible legal repurcussions, I'd prefer to remain anonymous at this time. Thanks to the efforts of the people on this list, this is now possible. My implementation is pretty far along. It uses PGP modules for the arithmetic, so the speed is good. It works on Unix and I should be able to get it working on MSDOS in a day or two. Sorry, I don't have the ability to work on a Mac version. Here are some of the features. The basic cash algorithm is the Chaum system which was posted here. Multiple denominations are supported, using different exponents for each denomination. The program is presented in the context of a package to be used for an email based game like Monopoly where the program would be used to allow cash transfers. One player is the "banker", and he uses a different execution module than the other players. The banker program keeps a database of used note numbers which is used to detect money reuse. The database is maintained using a freeware version of the "dbm" package, so it should be fast even for large note number databases. The mapping between exponents and values is as follows: exponent value 17 1 19 2 23 5 29 10 31 20 37 50 41 100 43 200 47 500 53 1000 59 2000 61 5000 67 10000 and so on, up to a value of 2e9. The exponents are ascending primes starting with 17. This was chosen because you want them to be smallish for fast note checking, but it was too slow to find primes p and q for the bank key such that (p-1)(q-1) was not divisible by any small primes. The program chooses random p and then tests p-1 to make sure it passes the divisibility test, and rejects it if not. Too many were being rejected when I started with an exponent of 3. Starting with 17 rejects about 1/2 the exponents, compared to something like 80% when I started with 3. The "value" fields are presumed to be cents, but could be whatever you like. The code I've written does not do anything other than the basic electronic cash algorithms. It does not do bank account maintenance. It doesn't do PGP encryption. It doesn't send mail. (It does have some functions to scan and check the files created by the program.) Cash generation is a 3 step process. First, the user creates what I call a "withdrawal request" packet. This is a set of triplets of the form (e, s, refx), where e is the exponent from the table above, s is a 16-byte "unique identifier" used solely to link these withdrawal requests with the returned messages from the bank, and refx is r^e * f(x). f(x) is MD5 of x, padded to the size of the bank's modulus n using the PGP routine which pads MD5 signatures. This padding helps make sure the arithmetic is more "mixing". x is the random input to MD5, which I've chosen as 64 bytes since that is the block size MD5 works on. (The output of MD5 is 16 bytes.) r is the blinding factor. This is now 128 bits long; longer r's take too long to calculate r^-1 in the third step, below. (It takes longer for PGP to calculate r^-1 than to do an RSA decryption, for r = n = 1024 bits!) Second, the bank program converts the withdrawal request packet into what I call a "withdrawal" packet, by just RSA-decrypting the third entry using the inverse exponent "d" for the value exponent "e". (These "d" values are calculated at keygen time and stored with the bank's key information in a private file.) I call the return triplet (e, s, rfxd), where e is the value exponent again, s is the same unique identifier, and rfxd is r * f(x)^d. (As I said above, the code I've written does not try to maintain account balances or do any other banking functions. It just does the cash algorithms. There is a routine to scan a withdrawal request and return the total value being requested for withdrawal. The idea was that this could be used as input to a banking program to decide whether to allow the withdrawal.) Third, the "player" (e.g. user) program transforms the withdrawal packet into a "money" packet, by un-blinding it. To do this, it has to recover the x and r which correspond with each triplet. This is done by the use of a dbm database of "pending withdrawal requests" which is written during step 1, above. The database entries are keyed by (e, s) and return the corresponding (x, r) which were generated during step 1. Using x and r, the user transforms (e, s, rfxd) into (e, x, fxd), the digital cash. e is the value exponent, x is the random 64-byte number, and fxd is f(x)^d, the signed version of the MD5'd and padded x. There are also player functions to scan and check a money file (comparing a calculated f(x) to fxd^e), merge money files, and extract some items from a money file into another money file (this last is what is to be used for payment). There are banker functions to check incoming money and compare against the used-note database, and to add incoming money to that database. (The database consists of the 16-byte f(x) values for each note.) I am pretty happy with the basic routines, but the user interface needs work. There are three kinds of files floating around (withdrawal requests, withdrawals, and money files) and I'm worried that this will be confusing to the user. If he accidentally deletes one at the wrong time he could lose money permanently. Or if he accidentally reuses one he could be accused of fraud. I'm not sure what the best model is for the user. The specific issues of creating withdrawal messages and extracting "bills" from a money file are areas where the user interface should be made nice. We want to make it easy for the user to specify exactly what denominations he wants to work with. One possibility is to simply have him input the amount (e.g. $10.55) and the program calculates that that's a 1000, a 50, and a 5, but this isn't really flexible enough. A nice system would be to give him a list of options and let him fill out a form on-screen, but that's hard to do portably. Another idea I've had is that there should be a special money file called the user's "wallet" which is the default place where incoming money from the bank should go. This might help organize things. He still needs to be able to create other money files for paying other people, and remembering to delete them after he sends them. Any suggestions or thoughts on these interface issues, or comments about how this program could or should be integrated into a larger system, would be appreciated. -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.0 mQCNAisiUPkAAAED/i1Pf1DaubveDsgjh360rNJ7kWkhssobaVmmWa70l4lOTwy/ sGwhJaA+JdScO9g3B66DIAaU0GiNrTS4YEl/b5ohNDZFdqKlxZ7NW9A5JYjUlhGE a53cRwqUXs42kbPbMh/uKxXBgbUnKrKZnWAh29irDWb+G8OEPQrkCJ6S8691AAUR tAl4UGhhZWRydXM= =HVRq -----END PGP PUBLIC KEY BLOCK-----

1 0

no subject (file transmission)
by nobody＠rebma.rebma.mn.org 12 Dec '92

12 Dec '92

-----BEGIN PGP SIGNED MESSAGE----- Update on the digital cash project I am having some problems with the port to MSDOS, mostly due to implicitly assuming 32-bit integers in a few places. Probably I won't get it working until next weekend. To recap, the program provides Chaum-style digital cash via two executables, one for the "players" and one for the "banker". The banker creates a public key which has a single modulus n and multiple exponents, the prime numbers starting with 17. He sends n to the players and all is ready. Players withdraw money by running their programs and specifying the denominations they want to withdraw. For example, you could withdraw a 1, two 5's, a 10 and a 20. This would create a file with 5 entries to be sent to the bank. PGP should be used to encrypt and ascii-encode this file (for privacy) and it should be mailed to the banker. The banker receives this file and runs his program to RSA-sign the values in each of the withdrawal-request entries. This is the "blinded cash" that Chaum describes. Again, PGP should be used for mailing this back to the user. The player then has to "unblind" the file to make it "real" digital cash. This also changes it so that the bank won't recognize it when it is deposited. He uses his version of the program to do this, producing an actual digital money file with the five "digital bills" in it. To pay another user, he runs another function to extract the desired bills from this file. Suppose he wants to extract a 1 and a 5. This leaves a 5, a 10 and a 20 in the original file, and creates a new digital cash file with a 1 and a 5. He would then use PGP again to encrypt this for safety and mail it to the person he wants to pay. That person can run a "check" function on the incoming digital money to make sure it has a proper bank signature on it and is not a forgery. He would then mail it directly to the bank so that it could get credited to his account. The banker runs his program which checks the signatures on the incoming money, looks in a database file to make sure these bills haven't been used before, and adds these bills to the database. (The database stores 16 bytes per bill.) He should then record the deposit and perhaps send a confirmation to the depositor (my program doesn't get involved with that). I hope this gives a clearer picture of how the electronic money program works. It is a simple implementation but I think many systems would work similarly. I appreciated the suggestion to use cash as part of the list management itself. Rather than paying people who post, I wonder if it would be better to make people pay to post. Many people have complained about the volume. :) Unfortunately, I suspect that this would involve too much overhead for the mailing list maintainer. Maybe the thing to do is to just get the software out there and let people decide what they want to do with it (if anything). I'm probably going to take a couple more weeks to clean up the user interface and get these bugs out, then I'll try sending it someone to be put on the cypherpunks ftp archive. It's nice to be able to finally sign these messages! - -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.1 mQCNAisiUPkAAAED/i1Pf1DaubveDsgjh360rNJ7kWkhssobaVmmWa70l4lOTwy/ sGwhJaA+JdScO9g3B66DIAaU0GiNrTS4YEl/b5ohNDZFdqKlxZ7NW9A5JYjUlhGE a53cRwqUXs42kbPbMh/uKxXBgbUnKrKZnWAh29irDWb+G8OEPQrkCJ6S8691AAUR tAl4UGhhZWRydXM= =HVRq - -----END PGP PUBLIC KEY BLOCK----- -----BEGIN PGP SIGNATURE----- Version: 2.1 iQCVAgUBKyZADQrkCJ6S8691AQHneQP8DRdkOFfG9TwjGDJAX4IxymvzAITqYIJC aMhytyzqFwP6Dku955ZHEPL1SDpNCU8DwK7eKDOgvHRS3m+kihs1l6VR3Gf0AgGw 7jjRJlt7hcqfT16fLHVXtn27A16rUhl2hKrD702wjGzX+MN7mS/8MW2kchVfvQYX M/McOuwuIjs= =/HGX -----END PGP SIGNATURE-----

1 0

(fwd) EFFector Online 4.00
by tcmay＠netcom.com 12 Dec '92

12 Dec '92

Organization: Netcom - Online Communication Services (408 241-9760 guest) Cypherpunks, Here's the latest EFFector Online, which happens to have stuff about two of us, John Gilmore and me, and which mentions Tom Jennings! No mention of our little group, yet, but I expect we can't hide for long. --Tim May From: rita(a)eff.org (Rita Marie Rouvalis) Subject: EFFector Online 4.00 Followup-To: comp.org.eff.talk Originator: rita(a)eff.org Keywords: crypto, nsa, pioneer wards Organization: Electronic Frontier Foundation Date: Fri, 11 Dec 1992 20:00:04 GMT ########## ########## ########## | ########## ########## ########## | GILMORE VS. THE NSA #### #### #### | ######## ######## ######## | ######## ######## ######## | THE CRYPTO ANARCHIST MANIFESTO #### #### #### | ########## #### #### | 2nd PIONEER AWARDS DEADLINE LOOMS ########## #### #### | ===================================================================== EFFector Online December 11, 1992 Issue 4.00 A Publication of the Electronic Frontier Foundation ISSN 1062-9424 ===================================================================== ACCESSING THE NSA JOHN GILMORE FILES SUIT WITH THE NATIONAL SECURITY AGENCY At the beginning of July 1992, John Gilmore filed a FOIA request with NSA asking for access to parts of cryptologic treatises written by NSA personnel: Military Cryptanalysis, Parts III and IV, by William Friedman (WF-3/4); and Military Cryptanalytics, Parts III-VI, by William Friedman and Lambros Callimahos (LC3-6). Parts I and II of each of these treatises had already been declassified and published. At the time of the request, it was not definitely known whether the parts requested by Gilmore had been re-classified. Under the FOIA, agencies are required to communicate responses to requesters within statutorily prescribed time periods. Failure to comply with the time limits for response constitutes a denial of the request, giving the requester the right to appeal. When NSA violated the first applicable time period, Gilmore filed an administrative appeal with the NSA's FOIA appeals authority. There is also a time limit for response to such appeals. After this time limit passed without a response from the NSA's appeals authority, Gilmore filed a complaint in federal court in the Northern District of California on Sept. 4, 1992, as permitted by the FOIA. Gilmore's complaint alleged three claims: First, that the NSA improperly withheld these documents from him, and had no legal basis for withholding; second, that the NSA's failure to comply with the FOIA time limits constituted a form of improper withholding; and third, that the NSA in general engages in an illegal pattern or practice of routinely violating the FOIA time limits, which should be declared illegal and enjoined. In the period between the initial FOIA request to NSA, and the filing of the complaint in federal court, Gilmore obtained copies of two of the withheld documents: Military Cryptanalysis Parts III and IV, by Friedman. These copies were discovered in libraries accessible to the general public and were provided by these libraries without any kind of restriction. Gilmore intended to get expert opinion on the national security risk posed by disclosure of these documents. He also reasoned that their very availability in such libraries demonstrated that there could be no legal basis for withholding them from a FOIA requester. At the time the documents were obtained, Gilmore had not received any indication from NSA that the documents were classified. It was therefore possible that the documents were not, in fact, classified. In addition, FOIA requests for documents generally trigger agency declassification review. Thus, even if the documents were in fact classified at the time of the request, it was possible that NSA would decide that they should no longer be classified, and release them to Gilmore. After the complaint was filed, Gilmore not only served the complaint upon NSA, he also served a number of discovery requests upon NSA, seeking to discover information about both the history of these documents and about NSA's FOIA processing procedures. In early October, after NSA had received the complaint and the discovery requests, NSA finally sent its responses to the FOIA request. NSA informed Gilmore that the documents were not going to be released to him. NSA said that it had located WF-3/4 and LC-3, but that LC-4/5/6 had never been completed because of the death of Lambros Callimahos. First, NSA asserted that the three documents which did exist were classified. WF-3/4 were classified CONFIDENTIAL, the lowest level of classification under Executive Order 12,356 governing classified information. LC-3 was classified SECRET, the middle level of classification. Under the FOIA, an agency may withhold documents if they are properly classified for reasons of national security. Second, NSA asserted that the documents could also be withheld under a different exemption in the FOIA. Under the (b)(3) exemption, documents may be withheld if there exists a statute which authorizes an agency to withhold them. NSA pointed to several statutes which arguably covered this material. One of these statutes, 18 U.S.C. Section 798, makes it a federal crime knowingly to disclose classified cryptologic or communications intelligence information to unauthorized persons. At this point, it became clear to Gilmore that there was a problem. He now knew for a fact that the documents he had were classified (WF-3/4) and that it would be a crime for him to disseminate them. He could no longer continue with his plan of showing them to other persons for fear of criminal prosecution. He also feared that should NSA ever discover that he possessed them, he would be subjected to search and seizure and the copies confiscated. (Note that although the First Amendment Privacy Protection Act generally protects the press against search and seizure for materials intended for publication where the crime involves mere possession or dissemination of information, it does not apply to any materials covered by the espionage statutes, of which 18 U.S.C. Section 798 is one.) NSA did not, however, know that he had them. Gilmore decided that the best course of action was to submit copies of WF-3/4 to the federal district court under seal. By so doing, he would ensure that at least these copies would be kept out of the NSA's hands, since it was unlikely that a federal judge would relinquish possession of documents material to pending litigation. Thus, on November 12, Gilmore made an ex parte application to file these documents under seal with Judge Thelton Henderson, the federal judge hearing his case. Gilmore also concurrently filed a motion for leave to amend his original complaint in order to address the constitutional and other issues arising from his possession of the documents and the criminality of disseminating documents found in libraries open to the general public. It is important to realize that the criminal statute at issue here does not recognize improper classification as a defense. Under existing law, the government need only show that the documents were classified by the government, and that they are cryptologic- or communications-intelligence-related. It remains unclear precisely what the specific requirement under the statute is, i.e., whether "knowingly" means actual knowledge of classification, or merely some reason to know. (That same day, NSA filed two motions of its own: a motion for a protective order blocking Gilmore's discovery requests, and a motion for summary judgment asking the court to dispose of the case on the ground that NSA was entitled to judgment as a matter of law. In support of its summary judgment motion, NSA filed a sworn declaration by Michael Smith, Chief of Policy, explaining why the documents should be withheld, and why NSA's FOIA processing procedures were not illegal.) NSA was served with papers indicating that WF-3/4 had been received by the district court. This was the first time that NSA knew that Gilmore possessed the documents. They reacted strongly. John Martin, the Justice Department lawyer representing NSA, asked that Gilmore surrender his copies to NSA, saying that NSA was very upset and might send its own agents or FBI agents to get the copies from Gilmore. He also wanted to know where Gilmore got them. Martin also suggested that Gilmore might be criminally liable under the espionage statutes relating to possession of national defense information. NSA regained its composure the next day, realizing that it did not know exactly what Gilmore had. Although NSA had been served with papers indicating what Gilmore had done, Gilmore had not sent them copies of the documents. Thus they could not know for sure whether the documents he had were the ones they considered classified. Gilmore agreed to send copies of his copies to NSA for their review, after which NSA would decide what to do. During this period, tension was high. Gilmore considered filing an ex parte motion for a temporary restraining order against NSA and the U.S. Attorney General to prevent them from both moving against him personally and against any copies of the documents presently on library shelves. This motion was drafted but never filed. On the day before Thanksgiving, NSA announced that WF-3/4 would be declassified, and effectively renounced any claim that it could withhold them from the public. NSA gave no official reason for its action. NSA is currently reviewing the third document, LC-3, to see how much of it can be released now that WF-3/4 have been declassified. (NSA had asserted in its summary judgment papers that LC-3 was based on WF-3/4.) NSA's review is to be completed by January 15, 1993, at which time it will release an edited version of LC-3 to Gilmore. It is anticipated that this edited version of LC-3 will be analyzed by Gilmore and his experts, and that Gilmore and NSA will engage in settlement negotiations to determine whether NSA has satisfied Gilmore's request. The settlement discussions will also include Gilmore's claims regarding NSA's FOIA processing procedures. The parties have stipulated that if no settlement is reached the litigation will proceed. A status conference has been set for February 9. NSA will, if necessary, file an amended motion for summary judgment by February 12. Following opposition and reply briefs, the hearing on all motions will take place on March 22. [John Gilmore is a member of the EFF Board of Directors. He can reached as gnu(a)cygnus.com. Gilmore's lawyer, Lee Tien, can be reached as tien(a)toad.com.] -==--==--==-<>-==--==--==- THE CRYPTO ANARCHIST MANIFESTO by Timothy C. May (tcmay(a)netcom.com) A specter is haunting the modern world, the specter of crypto anarchy. Computer technology is on the verge of providing the ability for individuals and groups to communicate and interact with each other in a totally anonymous manner. Two persons may exchange messages, conduct business, and negotiate electronic contracts without ever knowing the True Name, or legal identity, of the other. Interactions over networks will be untraceable, via extensive re- routing of encrypted packets and tamper-proof boxes which implement cryptographic protocols with nearly perfect assurance against any tampering. Reputations will be of central importance, far more important in dealings than even the credit ratings of today. These developments will alter completely the nature of government regulation, the ability to tax and control economic interactions, the ability to keep information secret, and will even alter the nature of trust and reputation. The technology for this revolution--and it surely will be both a social and economic revolution--has existed in theory for the past decade. The methods are based upon public-key encryption, zero-knowledge interactive proof systems, and various software protocols for interaction, authentication, and verification. The focus has until now been on academic conferences in Europe and the U.S., conferences monitored closely by the National Security Agency. But only recently have computer networks and personal computers attained sufficient speed to make the ideas practically realizable. And the next ten years will bring enough additional speed to make the ideas economically feasible and essentially unstoppable. High-speed networks, ISDN, tamper-proof boxes, smart cards, satellites, Ku-band transmitters, multi-MIPS personal computers, and encryption chips now under development will be some of the enabling technologies. The State will of course try to slow or halt the spread of this technology, citing national security concerns, use of the technology by drug dealers and tax evaders, and fears of societal disintegration. Many of these concerns will be valid; crypto anarchy will allow national secrets to be traded freely and will allow illicit and stolen materials to be traded. An anonymous computerized market will even make possible abhorrent markets for assassinations and extortion. Various criminal and foreign elements will be active users of CryptoNet. But this will not halt the spread of crypto anarchy. Just as the technology of printing altered and reduced the power of medieval guilds and the social power structure, so too will cryptologic methods fundamentally alter the nature of corporations and of government interference in economic transactions. Combined with emerging information markets, crypto anarchy will create a liquid market for any and all material which can be put into words and pictures. And just as a seemingly minor invention like barbed wire made possible the fencing-off of vast ranches and farms, thus altering forever the concepts of land and property rights in the frontier West, so too will the seemingly minor discovery out of an arcane branch of mathematics come to be the wire clippers which dismantle the barbed wire around intellectual property. Arise, you have nothing to lose but your barbed wire fences! -==--==--==-<>-==--==--==- Date: Wed, 02 Dec 92 21:31:47 -0800 From: haynes(a)cats.UCSC.EDU (Jim Haynes) Newsgroups: comp.dcom.telecom Subject: Historical Note on Telecom Privacy Apropos of all the talk on FBI wiretapping, cellular eavesdropping, etc., I found this passage in "Old Wires and New Waves"; Alvin F. Harlow; 1936. He's writing about unscrupulous telegraph operators in the early days. They would use information in telegrams for personal gain, or delay messages or news for personal gain, or sell news reports to non-subscribers of the press association. "Pennsylvania passed a law in 1851, making telegrams secret, to prevent betrayal of private affairs by operators. When, therefore, an operator was called into court in Philadelphia a little later, and ordered to produce certain telegrams which would prove an act of fraud, he refused to do so, saying that the state law forbade it. The circuit court, shocked at this development, proceeded to override the law, saying: It must be apparent that, if we adopt this construction of the law, the telegraph may be used with the most absolute security for purposes destructive to the well-being of society - a state of things rendering its absolute usefulness at least questionable. The correspondence of the traitor, the murderer, the robber and the swindler, by means of which their crimes and frauds could be the more readily accomplished and their detection and punishment avoided, would become things so sacred that they never could be accessible to the public justice, however deep might be the public interest involved in their production. The judge therefore ordered the operator to produce the telegrams." -==--==--==-<>-==--==--==- THE SECOND ANNUAL INTERNATIONAL EFF PIONEER AWARDS: CALL FOR NOMINATIONS Deadline: December 31,1992 In every field of human endeavor,there are those dedicated to expanding knowledge,freedom,efficiency and utility. Along the electronic frontier, this is especially true. To recognize this,the Electronic Frontier Foundation has established the Pioneer Awards for deserving individuals and organizations. The Pioneer Awards are international and nominations are open to all. In March of 1992, the first EFF Pioneer Awards were given in Washington D.C. The winners were: Douglas C. Engelbart of Fremont, California; Robert Kahn of Reston, Virginia; Jim Warren of Woodside, California; Tom Jennings of San Francisco, California; and Andrzej Smereczynski of Warsaw, Poland. The Second Annual Pioneer Awards will be given in San Francisco, California at the 3rd Conference on Computers, Freedom, and Privacy in March of 1993. All valid nominations will be reviewed by a panel of impartial judges chosen for their knowledge of computer-based communications and the technical, legal, and social issues involved in networking. There are no specific categories for the Pioneer Awards, but the following guidelines apply: 1) The nominees must have made a substantial contribution to the health, growth, accessibility, or freedom of computer-based communications. 2) The contribution may be technical, social, economic or cultural. 3) Nominations may be of individuals, systems, or organizations in the private or public sectors. 4) Nominations are open to all, and you may nominate more than one recipient. You may nominate yourself or your organization. 5) All nominations, to be valid, must contain your reasons, however brief, on why you are nominating the individual or organization, along with a means of contacting the nominee, and your own contact number. No anonymous nominations will be allowed. 6) Every person or organization, with the single exception of EFF staff members, are eligible for Pioneer Awards. 7) Persons or representatives of organizations receiving a Pioneer Award will be invited to attend the ceremony at the Foundation's expense. You may nominate as many as you wish, but please use one form per nomination. You may return the forms to us via email to pioneer(a)eff.org You may mail them to us at: Pioneer Awards, EFF, 155 Second Street Cambridge MA 02141. You may FAX them to us at: +1 617 864 0866 Just tell us the name of the nominee, the phone number or email address at which the nominee can be reached, and, most important, why you feel the nominee deserves the award. You may attach supporting documentation. Please include your own name, address, and phone number. We're looking for the Pioneers of the Electronic Frontier that have made and are making a difference. Thanks for helping us find them, The Electronic Frontier Foundation -------EFF Pioneer Awards Nomination Form------ Please return to the Electronic Frontier Foundation via email to: pioneer(a)eff.org via surface mail to EFF 155 Second Street, Cambridge, MA 02141 USA; via FAX to +1 617 864 0866 Nominee: Title: Company/Organization: Contact number or email address: Reason for nomination: Your name and contact information: Extra documentation attached: DEADLINE: ALL NOMINATIONS MUST BE RECEIVE BY THE ELECTRONIC FRONTIER FOUNDATION BY MIDNIGHT, EASTERN STANDARD TIME U.S., DECEMBER 31,1992. -==--==--==-<>-==--==--==- MEMBERSHIP IN THE ELECTRONIC FRONTIER FOUNDATION If you support our goals and our work, you can show that support by becoming a member now. Members receive our bi-weekly electronic newsletter, EFFector Online, the @eff.org newsletter and special releases and other notices on our activities. But because we believe that support should be freely given, you can receive these things even if you do not elect to become a member. Our memberships are $20.00 per year for students, $40.00 per year for regular members. You may, of course, donate more if you wish. Our privacy policy: The Electronic Frontier Foundation will never, under any circumstances, sell any part of its membership list. We will, from time to time, share this list with other non-profit organizations whose work we determine to be in line with our goals. If you do not grant explicit permission, we assume that you do not wish your membership disclosed to any group for any reason. ---------------- EFF MEMBERSHIP FORM --------------- Mail to: The Electronic Frontier Foundation, Inc. 155 Second St. #40 Cambridge, MA 02141 I wish to become a member of the EFF I enclose:$__________ $20.00 (student or low income membership) $40.00 (regular membership) $100.00(Corporate or company membership. This allows any organization to become a member of EFF. It allows such an organization, if it wishes to designate up to five individuals within the organization as members.) I enclose an additional donation of $ Name: Organization: Address: City or Town: State: Zip: Phone:( ) (optional) FAX:( ) (optional) Email address: I enclose a check [ ] . Please charge my membership in the amount of $ to my Mastercard [ ] Visa [ ] American Express [ ] Number: Expiration date: Signature: Date: I hereby grant permission to the EFF to share my name with other non-profit groups from time to time as it deems appropriate [ ] . Initials: Your membership/donation is fully tax deductible. ===================================================================== EFFector Online is published by The Electronic Frontier Foundation 155 Second Street, Cambridge MA 02141 Phone: +1 617 864 0665 FAX: +1 617 864 0866 Internet Address: eff(a)eff.org Reproduction of this publication in electronic media is encouraged. Signed articles do not necessarily represent the view of the EFF. To reproduce signed articles individually, please contact the authors for their express permission. ===================================================================== This newsletter is printed on 100% recycled electrons. -- Rita Rouvalis Electronic Frontier Foundation rita(a)eff.org eff(a)eff.org CIS:70007,5621 (617)864-0665 -- .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay(a)netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^756839 | PGP Public Key: by arrangement.

1 0

keys for me and remailer@rebma.mn.org
by Bill O'Hanlon 12 Dec '92

12 Dec '92

I don't know how much use this is, since no one has signed my key, but here it is, plus the key for the remailer here at rebma, signed by me. If anyone is going to be in the Minneapolis area, lemme know. Here's mine: -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.1 mQCNAirR6jkAAAEEAOMZFXG8bGGSpctmszxLug8IoLi55pUy+gR81K6ZBfLOmrTh XCeuSBZ+yi6IZXuabOTsKo9r6wHVAvumZlfMvcp9Jbasp6Lc756aacsatHYsiQR4 7feUmp/coOyZ4ZfAXCmapc3dozYB9vWoWMhQy8QmWhotR8zTLRlm7A4meZALAAUR tCBXYXJyaW9yIDx3bW9AcmVibWEubW4ub3JnPiBrZXkgMg== =3/XA -----END PGP PUBLIC KEY BLOCK----- And here's the remailers: -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.1 mQCNAisUI2QAAAEEAKgm07Hsje5KpmXYd5azk0R6AES+qK7LcofnVGojUs7GBghD WbwrmW8oOEOhRorlShRALKeYspV4xYIw4WDkJcJxuf1B254scz1urF/Eem3zPW9b yPAx7W/cGwvs6SouZvFcSDq4v1zApvGE9hP4szPzHeGmVr0NVNeaDK0guoCpAAUR tCBSZW1haWxlciAocmVtYWlsZXJAcmVibWEubW4ub3JnKYkAlQIFECsUJGEYkFR3 jlSfhwEB1zgD/1LG9DttNEVPFddxkULPw+AkkbmSolrqJUmVx/3y3QS1AtW+vVqF 0yhgWgvg770b7+xMnwzO/I1nh0FK2shd1Jkx4FVCA5ctyqUzVFjk1NE6VaaRc5Bv BD1nUxtUheR0WXDc50f+ANHgRNkx22MGRvphseMyXq/Ok88opSn7DIrO =nBQt -----END PGP PUBLIC KEY BLOCK----- -- Bill O'Hanlon wmo(a)rebma.mn.org

1 0

YA remailer
by Eli Brandt 11 Dec '92

11 Dec '92

I have a Hal-standard remailer running at this address, ebrandt(a)jarthur.claremont.edu -- haven't compiled PGP on this silly Sequent box yet, so no ARA's. PGP 2 key by finger or e-mail (and finger works now) Eli ebrandt(a)jarthur.claremont.edu

1 0

Chaum's "The Dining Cryptographers Problem" (VERY LONG)
by nobody＠pmantis.berkeley.edu 11 Dec '92

11 Dec '92

The following article is brought to you by the Information Liberation Front (ILF), a group dedicated to the timely distribution of important information. The ILF encourages you to use this article for educational purposes only and to seek out the original article. Minor spelling errors and slight alterations of formulas may have gotten past the OCR process. We apologize for the length, but feel this is one of the key articles in this area. J. Cryptology (1988) 1:65-75 The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability David Chaum Centre for Mathematics and Computer Science, Kruislan 413, 1098 SJ Amsterdam, The Netherlands Abstract. Keeping confidential who sends which messages, in a world where any physical transmission can be traced to its origin, seems impossible. The solution presented here is unconditionally or cryptographically secure, depending on whether it is based on one-time-use keys or on public keys, respectively. It can be adapted to address efficiently a wide variety of practical considerations. Key words. Untraceability, Unconditional Security, Pseudonymity. Introduction Three cryptographers are sitting down to dinner at their favorite three-star restaurant. Their waiter informs them that arrangements have been made with the maitre d'hotel for the bill to be paid anonymously. One of the cryptographers might be paying for the dinner, or it might have been NSA (U.S. National Security Agency). The three cryptographers respect each other's right to make an anonymous payment, but they wonder if NSA is paying. They resolve their uncertainty fairly by carrying out the following protocol: Each cryptographer flips an unbiased coin behind his menu, between him and the cryptographer on his right, so that only the two of them can see the outcome. Each cryptographer then states aloud whether the two coins he can see--the one he flipped and the one his left-hand neighbor flipped--fell on the same side or on different sides. If one of the cryptographers is the payer, he states the opposite of what he sees. An odd number of differences uttered at the table indicates that a cryptographer is paying; an even number indicates that NSA is paying (assuming that the dinner was paid for only once). Yet if a cryptographer is paying, neither of the other two learns anything from the utterances about which cryptographer it is. To see why the protocol is unconditionally secure if carried out faithfully, consider the dilemma of a cryptographer who is not the payer and wishes to find out which cryptographer is. (If NSA pays, there is no anonymity problem.) There are two cases. In case (1) the two coins he sees are the same, one of the other cryptographers said "different," and the other one said "same." If the hidden outcome was the same as the two outcomes he sees, the cryptographer who said "different" is the payer; if the outcome was different, the one who said "same" is the payer. But since the hidden coin is fair, both possibilities are equally likely. In case (2) the coins he sees are different; if both other cryptographers said "different," then the payer is closest to the coin that is the same as the hidden coin; if both said "same," then the payer is closest to the coin that differs from the hidden coin. Thus, in each subcase, a nonpaying cryptographer learns nothing about which of the other two is paying. The cryptographers become intrigued with the ability to make messages public untraceably. They devise a way to do this at the table for a statement of arbitrary length: the basic protocol is repeated over and over; when one cryptographer wishes to make a message public, he merely begins inverting his statements in those rounds corresponding to 1 's in a binary coded version of his message. If he notices that his message would collide with some other message, he may for example wait a number of rounds chosen at random from a suitable distribution before trying to transmit again. 1. Generalizing the Approach During dinner, the cryptographers also consider how any number of participants greater than one can carry out a version of the protocol. (With two participants, only nonparticipant listeners are unable to distinguish between the two potential senders.) Each participant has a secret key bit in common with, say, every other participant. Each participant outputs the sum, modulo two, of all the key bits he shares, and if he wishes to transmit, he inverts his output. If no participant transmits, the modulo two sum of the outputs must be zero, since every key bit enters exactly twice; if one participant transmits, the sum must be one. (In fact, any even number of transmitting participants yields zero, and any odd number yields one.) For j rounds, each participant could have a j-bit key in common with every other participant, and the ith bit of each such key would be used only in the ith round. Detected collision of messages leads to attempted retransmission as described above; undetected collision results only from an odd number of synchronized identical message segments. (Generalization to fields other than GF(2) is possible, but seems to offer little practical advantage.) Other generalizations are also considered during dinner. The underlying assumptions are first made explicit, including modeling key-sharing arrangements as graphs. Next, the model is illustrated with some simple examples. The potential for cooperations of participants to violate the security of others is then looked at. Finally, a proof of security based on systems of linear equations is given. 1.1. Model Each participant is assumed to have two kinds of secret: (a) the keys shared with other participants for each round; and (b) the inversion used in each round (i.e., a 1 if the participant inverts in that round and a 0 if not). Some or all of a participant's secrets may be given to other participants in various forms of collusion, discussion of which is postponed until Section 1.3. (For simplicity in exposition, the possibility of secrets being stolen is ignored throughout.) The remaining information about the system may be described as: (a) who shares keys with whom; and (b) what each participant outputs during each round (the modulo two sum of that participant's keys and inversion). This information need not be secret to ensure untraceability. If it is publicly known and agreed, it allows various extensions discussed in Sections 2.5 and 2.6. The sum of all the outputs will, of course, usually become known to all participants. In the terminology of graphs, each participant corresponds to a vertex and each key corresponds to an edge. An edge is incident on the vertices corresponding to the pair of participants that shares the corresponding key. From here on, the graph and dinner-table terminologies will be used interchangeably. Also, without loss of generality, it will be assumed that the graph is connected (i.e., that a path exists between every pair of vertices), since each connected component (i.e., each maximal connected subgraph) could be considered a separate untraceable-sender system. An anonymity set seen by a set of keys is the set of vertices in a connected component of the graph formed from the original graph by removing the edges concerned. Thus a set of keys sees one anonymity set for each connected partition induced by removing the keys. The main theorem of Section 1.4 is essentially that those having only the public information and a set of keys seeing some anonymity set can learn nothing about the members of that anonymity set except the overall parity of their inversions. Thus, for example, any two participants connected by at least one chain of keys unknown to an observer are both in the same anonymity set seen by the observer's keys, and the observer gains nothing that would help distinguish between their messages. 1.2. Some Examples A few simple consequences of the above model may be illustrative. The anonymity set seen by the empty set (i.e., by a nonparticipant observer) is the set of all vertices, since the graph is assumed connected and remains so after zero edges are removed. Also, the anonymity sets seen by the full set of edges are all singleton sets, since each vertex's inversion is just the sum of its output and the corresponding key bits. If all other participants cooperate fully against one, of course no protocol can keep that singleton's messages untraceable, since untraceability exists only among a set of possible actors, and if the set has only one member, its messages are traceable. For similar reasons, if a participant believes that some subset of other participants will fully cooperate against him, there is no need for him to have keys in common with them. A biconnected graph (i.e., a graph with at least two vertex-disjoint paths between every pair of vertices) has no cut-vertices (i.e., a single vertex whose removal partitions the graph into disjoint subgraphs). In such a graph, the set of edges incident on a vertex v sees (apart from v) one anonymity set containing all other vertices, since there is a path not containing v between every pair of vertices, and thus they form a connected subgraph excluding v; each participant acting alone learns nothing about the contribution of other participants. 1.3. Collusion of Participants Some participants may cooperate by pooling their keys in efforts to trace the messages of others; such cooperation will be called collusion. For simplicity, the possibilities for multiple collusions or for pooling of information other than full edges will be ignored. Colluders who lie to each other are only touched on briefly, in Section 2.6. Consider collusion in a complete graph. A vertex is only seen as a singleton anonymity set by the collection of all edges incident on it; all other participants must supply the key they share with a participant in order to determine that participant's inversions. But since a collusion of all but one participant can always trace that participant merely by pooling its members' inversions as already mentioned, it gains nothing more by pooling its keys. The nonsingleton anonymity set seen by all edges incident on a colluding set of vertices in a complete graph is the set of all other vertices; again, a collusion yields nothing more from pooling all its keys than from pooling all its inversions. Now consider noncomplete graphs. A full collusion is a subset of participants pooling all of their keys. The pooled keys see each colluder as a singleton anonymity set; the colluders completely sacrifice the untraceability of their own messages. If a full collusion includes a cut- set of vertices (i.e., one whose removal partitions the graph), the collusion becomes nontrivial because it can learn something about the origin of messages originating outside the collusion; the noncolluding vertices are partitioned into disjoint subgraphs, which are the anonymity sets seen by the pooled keys. Members of a partial collusion pool some but not all of their keys. Unlike the members of a full collusion, each member of a partial collusion in general has a different set of keys. For it to be nontrivial, a partial collusion's pooled keys must include the bridges or separating edges of a segregation or splitting of the graph (i.e., those edges whose removal would partition the graph). Settings are easily constructed in which the pooled keys see anonymity sets that partition the graph and yet leave each colluder in a nonsingleton partition seen by any other participant. Thus, colluders can join a collusion without having to make themselves completely traceable to the collusion's other members. 1.4. Proof of Security Consider, without loss of generality, a single round in which say some full collusion knows some set of keys. Remove the edges known to the collusion from the key-sharing graph and consider any particular connected component C of the remaining graph. The vertices of C thus form an anonymity set seen by the pooled keys. Informally, what remains to be shown is that the only thing the collusion learns about the members of C is the parity sum of their inversions. This is intuitively apparent, since the inversions of the members of C are each in effect hidden from the collusion by one or more unknown key bits, and only the parity of the sum of these key bits is known (to be zero). Thus the inversions are hidden by a one-time pad, and only their parity is revealed, because only the parity of the pad is known. The setting is formalized as follows: the connected component C is comprised of rn vertices and n edges. The incidence matrix M of C is defined as usual, with the vertices labeling the rows and the edges labeling the columns. Let K, I, and A be stochastic variables defined on GF(2)^n, GF(2)^m, and GF(2)^m, respectively, such that K is uniformly distributed over GF(2)^n, K and I are mutually independent, and A = (MK) cross I. In terms of the protocol, K comprises the keys corresponding to the edges, I consists of the inversions corresponding to the vertices, and A is formed by the outputs of the vertices. Notice that the parity of A (i.e., the modulo two sum of its components) is always equal to the parity of I, since the columns of M each have zero parity. The desired result is essentially that A reveals no more information about I than the parity of 1. More formally: Theorem. Let a be in GF(2)^n. For each i in GF(2)^n, which is assumed by I with nonzero probability and which has the same parity as a, the conditional probability that A = a given that I = i is 2^(1 - m). Hence, the conditional probability that I = i given that A = a is the a priori probability that I = i. Proof. Let i be an element of GF(2)^n have the same parity as a. Consider the system of linear equations (MK) cross i = a, in k an element of GF(2)^n. Since the columns of M each have even parity, as mentioned above, its rows are linearly dependent over GF(2)^m. But as a consequence of the connectedness of the graph, every proper subset of rows of M is linearly independent. Thus, the rank of M is m - 1, and so each vector with zero parity can be written as a linear combination of the columns of M. This implies that the system is solvable because i cross a has even parity. Since the set of n column vectors of M has rank m - 1, the system has exactly 2^(n - m + 1) solutions. Together with the fact that K and I are mutually independent and that K is uniformly distributed, the theorem follows easily. 2. Some Practical Considerations After dinner, while discussing how they can continue to make untraceable statements from this respective homes, the cryptographers take up a variety of other topics. In particular, they consider different ways to establish the needed keys; debate adapting the approach to various kinds of communication networks; examine the traditional problems of secrecy and authentication in the context of a system that can provide essentially optimal untraceability; address denial of service caused by malicious and devious participants; and propose means to discourage socially undesirable messages from being sent. 2.1. Establishing Keys One way to provide the keys needed for longer messages is for one member of each pair to toss many coins in advance. Two identical copies of the resulting bits are made, say each on a separate optical disk. Supplying one such disk (which today can hold on the order of 10^10 bits) to a partner provides enough key bits to allow people to type messages at full speed for years. If participants are not transmitting all the time, the keys can be made to last even longer by using a substantially slower rate when no message is being sent; the full rate would be invoked automatically only when a 1 bit indicated the beginning of a message. (This can also reduce the bandwidth requirements discussed in Section 2.2.) Another possibility is for a pair to establish a short key and use a cryptographic pseudorandom-sequence generator to expand it as needed. Of course this system might be broken if the generator were broken. Cryptanalysis may be made more difficult, however, by lack of access to the output of individual generators. Even when the cryptographers do not exchange keys at dinner, they can safely do so later using a public- key distribution system (first proposed by [4] and [3]). 2.2 Underlying Communication Techniques A variety of underlying communication networks can be used, and their topology need not be related to that of the key-sharing graph. Communication systems based on simple cycles, called rings, are common in local area networks. In a typical ring, each node receives each bit and passes it round-robin to the next node. This technology is readily adapted to the present protocols. Consider a single-bit message like the "I paid" message originally sent at the dinner table. Each participant exclusive-or's the bit he receives with his own output before forwarding it to the next participant. When the bit has traveled full circle, it is the exclusive-or sum of all the participants' outputs, which is the desired result of the protocol. To provide these messages to all participants, each bit is sent around a second time by the participant at the end of the loop. Such an adapted ring requires, on average, a fourfold increase in bandwidth over the obvious traceable protocols in which messages travel only halfway around on average before being taken off the ring by their recipients. Rings differ from the dinner table in that several bit- transmission delays may be required before all the outputs of a particular round are known to all participants; collisions are detected only after such delays. Efficient use of many other practical communication techniques requires participants to group output bits into blocks. For example, in high-capacity broadcast systems, such as those based on coaxial cable, surface radio, or satellites, more efficient use of channel capacity is obtained by grouping a participant's contribution into a block about the size of a single message (see, e.g., [5]). Use of such communication techniques could require an increase in bandwidth on the order of the number of participants. In a network with one message per block, the well-known contention protocols can be used: time is divided evenly into frames; a participant transmits a block during one frame; if the block was garbled by collision (presumably with another transmitted block), the participant waits a number of frames chosen at random from some distribution before attempting to retransmit; the participants' waiting intervals may be adjusted on the basis of the collision rate and possibly of other heuristics [5]. In a network with many messages per block, a first block may be used by various anonymous senders to request a "slot reservation" in a second block. A simple scheme would be for each anonymous sender to invert one randomly selected bit in the first block for each slot they wish to reserve in the second block. After the result of the first block becomes known, the participant who caused the ith 1 bit in the first block sends in the ith slot of the second block. 2.3. Example Key-Sharing Graphs In large systems it may be desirable to use fewer than the m(m - 1)/2 keys required by a complete graph. If the graph is merely a cycle, then individuals acting alone learn nothing, but any two colluders can partition the graph, perhaps fully compromising a participant immediately between them. Such a topology might nevertheless be adequate in an application in which nearby participants are not likely to collude against one another. A different topology assumes the existence of a subset of participants who each participant believes are sufficiently unlikely to collude, such as participants with conflicting interests. This subset constitutes a fully connected subgraph, and the other participants each share a key with every member of it. Every participant is then untraceable among all the others, unless all members of the completely connected subset cooperate. (Such a situation is mentioned again in Section 3.) If many people wish to participate in an untraceable communication system, hierarchical arrangements may offer further economy of keys. Consider an example in which a representative from each local fully connected subgraph is also a member of the fully connected central subgraph. The nonrepresentative members of a local subgraph provide the sum of their outputs to their representative. Representatives would then add their own contributions before providing the sum to the central subgraph. Only a local subgraph's representative, or a collusion of representatives from all other local subgraphs, can recognize messages as coming from the local subgraph. A collusion comprising the representative and all but one nonrepresentative member of a local subgraph is needed for messages to be recognized as coming from the remaining member. 2.4. Secrecy and Authentication What about the usual cryptologic problems of secrecy and authentication? A cryptographer can ensure the secrecy of an anonymous message by encrypting the message with the intended recipient's public key. (The message should include a hundred or so random bits to foil attempts to confirm a guess at its content [1].) The sender can even keep the identity of the intended recipient secret by leaving it to each recipient to try to decrypt every message. Alternatively, a prearranged prefix could be attached to each message so that the recipient need only decrypt messages with recognized prefixes. To keep even the multiplicity of a prefix's use from being revealed, a different prefix might be used each time. New prefixes could be agreed in advance, generated cryptographically as needed, or supplied in earlier messages. Authentication is also quite useful in systems without identification. Even though the messages are untraceable, they might still bear digital signatures corresponding to public-key "digital pseudonyms" [1]; only the untraceable owner of such a pseudonym would be able to sign subsequent messages with it. Secure payment protocols have elsewhere been proposed in which the payer and/or the payee might be untraceable [2]. Other protocols have been proposed that allow individuals known only by pseudonyms to transfer securely information about themselves between organizations [2]. All these systems require solutions to the sender untraceability problem, such as the solution presented here, if they are to protect the unlinkability of pseudonyms used to conduct transactions from home. 2.5. Disruption Another question is how to stop participants who, accidentally or even intentionally, disrupt the system by preventing others from sending messages. In a sense, this problem has no solution, since any participant can send messages continuously, thereby clogging the channel. But nondisupters can ultimately stop disruption in a system meeting the following requirements: (1) the key-sharing graph is publicly agreed on; (2) each participant's outputs are publicly agreed on in such a way that participants cannot change their output for a round on the basis of other participants' outputs for that round; and (3) some rounds contain inversions that would not compromise the untraceability of any nondisrupter. The first requirement has already been mentioned in Section 1.1, where it was said that this information need not be secret; now it is required that this information actually be made known to all participants and that the participants agree on it. The second requirement is in part that disrupters be unable (at least with some significant probability) to change their output after hearing other participants' outputs. Some actual channels would automatically ensure this, such as broadcast systems in which all broadcasts are made simultaneously on different frequencies. The remainder of the second requirement, that the outputs be publicly agreed on, might also be met by broadcasting. Having only channels that do not provide it automatically, an effective way to meet the full second requirement would be for participants to "commit" to their outputs before making them. One way to do this is for participants to make public and agree on some (possibly compressing and hierarchical, see Section 2.6) one-way function of their outputs, before the outputs are made public. The third requirement is that at least some rounds can be contested (i.e., that all inversions can be made public) without compromising the untraceability of non-disrupting senders. The feasibility of this will be demonstrated here by a simple example protocol based on the slot reservation technique already described in Section 2.2. Suppose that each participant is always to make a single reservation in each reserving block, whether or not he actually intends to send a message. (Notice that, because of the "birthday paradox," the number of bits per reserving block must be quadratic in the number of participants.) A disrupted reserving block would then with very high probability have Hamming weight unequal to the number of participants. All bits of such a disrupted reserving block could be contested without loss of untraceability for nondisrupters. The reserved blocks can also be made to have such safely contestable bits if participants send trap messages. To lay a trap, a participant first chooses the index of a bit in some reserving block, a random message, and a secret key. Then the trapper makes public an encryption, using the secret key, of both the bit index and the random message. Later, the trapper reserves by inverting in the round corresponding to the bit index, and sends the random message in the resulting reserved slot. If a disrupter is unlucky enough to have damaged a trap message, then release of the secret key by the trapper would cause at least one bit of the reserved slot to be contested. With the three requirements satisfied, it remains to be shown how if enough disrupted rounds are contested, the disrupters will be excluded from the network. Consider first the case of a single participant's mail computer disrupting the network. If it tells the truth about contested key bits it shares (or lies about an even number of bits), the disrupter implicates itself, because its contribution to the sum is unequal to the sum of these bits (apart from any allowed inversion). If, on the other hand, the single disrupter lies about some odd number of shared bits, the values it claims will differ from those claimed for the same shared bits by the other participants sharing them. The disrupter thereby casts suspicion on all participants, including itself, that share the disputed bits. (It may be difficult for a disrupter to cast substantial suspicion on a large set of participants, since all the disputed bits will be in common with the disrupter.) Notice, however, that participants who have been falsely accused will know that they have been--and by whom--and should at least refuse to share bits with the disrupter in the future. Even with colluding multiple disrupters, at least one inversion must be revealed as illegitimate or at least one key bit disputed, since the parity of the outputs does not correspond to the number of legitimate inversions. The result of such a contested round will be the removal of at least one edge or at least one vertex from the agreed graph. Thus, if every disruptive action has a nonzero probability of being contested, only a bounded amount of disruption is possible before the disrupters share no keys with anyone in the network, or before they are revealed, and are in either case excluded from the network. The extension presented next can demonstrate the true value of disputed bits, and hence allows direct incrimination of disrupters. 2.6. Tracing by Consent Antisocial use of a network can be deterred if the cooperation of most participants makes it possible, albeit expensive, to trace any message. If, for example, a threatening message is sent, a court might order all participants to reveal their shared key bits for a round of the message. The sender of the offending message might try to spread the blame, however, by lying about some odd number of shared bits. Digital signatures can be used to stop such blame-spreading altogether. In principle, each party sharing a key could insist on a signature, made by the other party sharing, for the value. of each shared bit. Such signatures would allow for contested rounds to be fully resolved, for accused senders to exonerate themselves, and even for colluders to convince each other that they are pooling true keys. Unfortunately, cooperating participants able to trace a message to its sender could convince others of the message's origin by revealing the sender's own signatures. A variation can prevent a participant's signatures from being used against him in this way: instead of each member of a pair of participants signing the same shared key bit, each signs a separate bit, such that the sum of the signed bits is the actual shared key bit. Signatures on such "split" key bits would still be useful in resolving contested rounds, since if one contester of a bit shows a signature made by the second contester, then the second would have to reveal the corresponding signature made by the first or be thought to be a disrupter. In many applications it may be impractical to obtain a separate signature on every key bit or split key bit. The overhead involved could be greatly reduced, however, by digitally signing cryptographic compressions of large numbers of key bits. This might of course require that a whole block of key bits be exposed in showing a signature, but such blocks could be padded with cryptographically generated pseudorandom (or truly random) bits, to allow the exposure of fewer bits per signature. The number of bits and amount of time required to verify a signature for a single bit can be reduced further by using a rooted tree in which each node is the one-way compression function of all its direct descendants; only a digital signature of each participant's root need be agreed on before use of the keys comprising the leaves. 3. Relation to Previous Work There is another multiparty-secure sender-untraceability protocol in the literature [1]. To facilitate comparison, it will be called a mix-net here, while the protocol of the present work is called a dc-net. The mix-net approach relies on the security of a true public-key system (and possibly also of a conventional cryptosystem), and is thus at best computationally secure; the dc-net approach can use unconditional secrecy channels to provide an unconditionally secure untraceable- sender system, or can use public-key distribution to provide a computationally secure system (as described in Section 2.1). Under some trust assumptions and channel limitations, however, mix-nets can operate where dc-nets cannot. Suppose that a subset of participants is trusted by every other participant not to collude and that the bandwidth of at least some participants' channels to the trusted subset is incapable of handling the total message traffic. Then mix-nets may operate quite satisfactorily, but dc-nets will be unable to protect fully each participant's untraceability. Mix-nets can also provide recipient untraceability in this communication environment, even though there is insufficient bandwidth for use of the broadcast approach (mentioned in Section 2.4). If optimal protection against collusion is to be provided and the crypto-security of mix-nets is acceptable, a choice between mix-nets and dc-nets may depend on the nature of the traffic. With a mail-like system that requires only periodic deliveries, and where the average number of messages per interval is relatively large, mix-nets may be suitable. When messages must be delivered continually and there is no time for batching large numbers of them, dc-nets appear preferable. 4. Conclusion This solution to the dining cryptographers problem demonstrates that unconditional secrecy channels can be used to construct an unconditional sender-untraceability channel. It also shows that a public-key distribution system can be used to construct a computationally secure sender-untraceability channel. The approach appears able to satisfy a wide range of practical concerns. Acknowledgments I am pleased to thank Jurjen Bos, Gilles Brassard, Jan-Hendrik Evertse, and the untraceable referees for all their help in revising this article. It is also a pleasure to thank, as in the original version that was distributed at Crypto 84, Whitfield Diffie, Ron Rivest, and Gus Simmons for some stimulating dinner-table conversations. References [1] Chaum, D., Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms, Communications of the ACM, vol. 24, no. 2, February 1981, pp. 84-88. [2] Chaum, D., Security Without Identification: Transaction Systems to Make Big Brother Obsolete, Communications of the ACM, vol. 28, no. 10, October 1985, pp. 1030-1044. [3] Diffie, W., and Hellman, M.E., New Directions in Cryptography, IEEE Transactions on Information Theory, vol. 22, no. 6, November 1976, pp. 644-654. [4] Merkle, R.C., Secure Communication over Insecure Channels, Communications of the ACM, vol. 21, no. 4, 1978, pp. 294-299. [5] Tanenbaum, A.S., Computer Networks, Prentice Hall, Englewood Cliffs, New Jersey, 1981. [End of Transmission] --

1 0

Re: Questions about US/Canadian Laws about public encryption
by George A. Gleason 11 Dec '92

11 Dec '92

Any attempt at "secret law" in the US would be pretty straightforward to defeat on the basis that it denies due process and a whole lot else besides. Secret court orders! Retch! Next person to get one should run not walk to the offices of the nearest big newspaper or radio/TV station and do a live on-air interview. Then the govt has to take on the press as well, and by that time it's kinda too late.

2 1

remailers
by nobody＠cicada.berkeley.edu 11 Dec '92

11 Dec '92

This is another call for info from remailer operators. I only heard from a few of you. Please send me info about how to use your remailer, including the public key. I will be setting up a special mailing list for remailer operators so we can discuss the technical issues of remailing, so if you mail me, you get on the list (if you want to). Remember, the more remailers there are and the more they are used, the safer it is for each individual remailer operator. And people won't use them unless they know how. And they won't know how unless there's a directory of them. e hh(a)soda.berkeley.edu

1 0