Cypherpunks, Here's a long article on some issues surrounding the "next generation" of remailers, hopefully a closer approximation to the digital mix. I hope you folks will add ideas, comment on this article, critique it, etc. This article includes: * discussion of the need for a second generation of remailers * ten basic features needed to better approximate the ideal digital mix * material on reputations and market systems that cryptologists ignore (the blend of economics and crypto is a fertile hybrid, one that solves for practical uses many of the problems as-yet-unsolved with pure cryptography) * suggestions for a series of agreements needed on message formats, digital postage (or some variant), and other things to make a second generation ecology of remailers more useful INTRODUCTION The recent experiences with Detweiler beginning to use Cypherpunks remailers (what took him so long?) points out some weaknesses of the current overall architecture which we've known about for a long time. We always knew the first generation of remailers, operational since circa November 1992, was far from optimal. Traffic analysis would be relatively trivial for any motivated agency with access to Internet traffic to do (e.g., most messages flow into a site and then out immediately, and also have characteristic packet sizes), and the remailers are far from meeting even the basic standards laid out in David Chaum's 1981 paper on digital mixes. I suspect most users don't even do any encryption at all, let alone nested encryption, so the origin-destination information is trivially recoverable. How to change this for the better depends on a number of things: faster and easier to use PGP, scripts which can take the various remailers and generate valid paths through the labyrinth of sites, and cultural factors. Also, the existing remailers are sensitive to abuse, both in "flooding" sites and mailing lists with junk mail, and in death threats, harassment, etc. Stopgap measures, such as excluding Detweiler as an origination address (for the first chain in a remailer, or later, if he failed to use encryption), are obviously not a robust solution. Flooding is best solved with some form of "user pays" type of payment system, which we call "digital postage"; this could use a basic form of prepaid "digital postage stamps" (e.g., 20-digit numbers) which are bought in "rolls" (I'll mention some ideas later) and used _once_. (Yes, this scheme is weak, but it's more than we have now, and it may be useful anyway.) The first generation remailers were a fantastic experiment, and became operational very quickly through the Perl-hacking efforts of Eric Hughes and others. The enhancements added by Hal Finney, Eric Hollander, Matt Thomlinson, Miron Cuperman, Karl Barrus, and others (sorry if I left some names out, or miscredited these folks with having added functionality!) were impressive. But the basic architecture, the "ecology of remailers" is showing some serious faults and limitations. Detweiler's attacks and threats to attack are actually fairly mild compared to what is possible and what may be coming soon. We shouldn't be wailing about "abuse" of our remailers when the basic architecture and current features are so lacking. We may succeed in getting Detweiler blocked at Colorado State--not that I am advocating this--or in doing some basic source-screening, but this is not a robust solution. Consider this a wake-up call. Actually, I'm flabbergasted that it's taken so long....I expected the first generation system to "break" a long time ago. It is probably time to seriously think about a "second generation remailer," incorporating the various ideas discussed in the past 15 months on this list. FEATURES NEEDED IN A SECOND GENERATION REMAILER: I. DIGITAL POSTAGE, so that the user pays for his use. (This reduces "flooding" and provides a profit motive for "Mom and Pop" remailers, to make remailers more ubiquitous. More on this later. Late note: This article ended up way too long, so I'll defer the discussion of digital postage to another time.) II. JUNK MAIL SCREENING. Support for "Don't send anonymous mail to me" registries, with a database maintained (for a fee?) of sites that wish no anonymous mail. (I'm not at all sure how best to do this...) III. IDEAL DIGITAL MIX. A closer approximation to the "ideal digital mix" (a la Chaum'S 1981 paper and the various later DC-Net embellishments) is needed. This is a _huge_ discussion area, one we have touched upon several times. In particular, Hal Finney wrote up a nice summary of the issue about half a year ago, maybe longer; he may want to repost his summary if this thread generates any interest. What follows is my own far from complete summary of some key features: - variable message latency, L, set either as policy by remailer site ("this site sets latency = L = 20 messages") or by the message itself (i.e., user sets, and perhaps pays for, a latency of his own choosing, such as "wait for 60 messages before sending") (Note: I strongly favor letting the _user_ pick the latency time, when possible, not having it "hardwired" into the site itself. Several reasons for this: doesn't commit the site to a particular latency, allows more diversity, lets user pay for more latency, etc.) - quantized message lengths, to defeat traffic analysis based on watching packet sizes. We've talked about quantizing message lengths as "short" (2K = 1 screen full of text), "medium" (10K = a 5-screenful typical article), "long" (30K), and so forth. How many levels of quantization affects the overall security of the system, of course. Too few levels unnecessarily pads shorter messages out to longer lengths, too many levels makes traffic analysis easier, all other things being equal. Digression on Diffusivity of Remailers: A careful analyis of "diffusivity" in remailers--roughly, how many possible paths a message may have taken--in terms of number of remailer hops, latency at each hop, and packet size needs to be done. As a very simple example, suppose there are 30 operational remailer sites, all with roughly the same functionality (not what we have now!). A message entering the "labyrinth" (my name for the web of remailers) may go to any of these 30 remailers, wait until, say 20 messages of the same length have accumulated (a situation very from the current situation, where low volumes and demands for speedy response mean there's almost *zero* latency), and then be sent to any of the remaining remailers (or even itself, in a tricky move of simply not sending the message). After N such remailings amongst M remailers with a latency of L messages, a rough measure of the diffusivity is: D = diffusivity = number of paths the original message may have taken = L ^ N (i.e., the diffusivity rises exponentially with the number of hops) (This is a simplistic equation, which does not take into account the practical limitations of there being only so many total messages flowing in the system, a point addressed briefly below. If only 10 messages "enter the system" and 10 messages "leave the system," the attacker has an easier problem than than a D = 3125, for example, might otherwise suggest.) M = number of remailers is not critically important when M is fairly large. For example, if M = 1, the solution is trivial. If M = 5, and N > M, this means the same remailers were used multiple times (recirculating), and the diffusivity is still quite high. If M is very large, with N < M, the situation is even better and we can ignore M. In the limit, M will tend toward infinity (we hope). Example situations: 1. Current Cypherpunks remailer situation: L = 1 (most remailers are not "batching" messages, so L =1), N = a few hops, if even that. Thus, D = 1, which means the path through the labyrinth is trivial to find for anyone with access to packet traffic. (I'm also ignoring for the moment the _logging_ of remailer traffic, a real no-no in terms of Chaum's ideal mix, which originally called for hardware-based mixes which kept no records, and more recently called for DC-Nets which _could not_ determine sender. A Chaumian mix which meets his 1981 standards is beyond the "second generation remailer" I'm describing here.) 2. Better use of existing remailers: L = 5, N = 5, dozens of total messages flowing Thus, D = 5 ^ 5 = 3125, meaning that a traffic analyst sees 3125 paths to follow for every original message, crudely. (In practice, the calculation above is not accurate unless enough total messages are used. In this example, there are not likely to be thousands of messages flowing, so the numbers are reduced. These corrections to the equation need to be made....I haven't done a combinatorial analyis--perhaps its about time I did.) This level of diffusifity could be gotten _today_ be using the remailers in this way: - pad messages out to quantized sizes (as we have discussed, and some technical issues of multiple PGP rounds exist) - set minimum latency to L = 5, for any given quantized size - send messages through N = 5 hops - D = L ^ N = 5 ^ 5 = 3125 (That few folks will do this, including me, is a _cultural_ and _educational_ problem unto itself. Topic for another article.) 3. Future use of existing remailers: L = 10, N = 5 Thus, the naive estimate of D is L ^ N = 10 ^ 5 = 100,000. Of course there are not this many paths to follow, but the goal has been achieved of _effectively obscuring_ the origin-destination mapping. Note to Readers: I may be losing some readers here by doing these crude calculations and making related points, so I will return instead to the listing of features to consider. (Too bad the Net and the various computers used can't support a collapsible outline structure!) End of digression. Back to the list of features: IV. NO LOGGING. No logging of in-out traffic should be done. I realize that many operators wish to do this to debug their remailers and to be able to deal with abusive messages. But make no mistake about it: This is a serious flaw! The sooner we can move away from such logging, the better. And sites which log should tell users, sites which don't log should as well. (Sites which log but say they _don't_ is of course the real issue in the long run....I'll save this interesting topic for another article, maybe. Just be aware that this kind of "collusion" (not exactly, but this is what the literature calls related behaviors) is not easily solved with existing remailers.) V. HARDWARE-BASED REMAILERS. Remailers which are essentially "hardwired" to behave in a particular way are the next step to take. Since not many people want to dedicate a machine on the Net to this, this may take a while. Note that this might still be possible locally as a cheap machine attached to an existing machine, via a local network. (Terse scenario: Machine on net gets incoming mail, passes it to cheap 386 box which runs store-and-forward remailer functions in simple, semi-hardwired way. Perhaps using remailer code sold on ROMs (a long-range fantasy, I know) and "authenticated" by "remailer credentialling" private agencies. Mixed messages then get handed back to machine on the Net, which sends them out. VI. MARKETS. And advertising, reputations, etc. Various remailers will have varying features: - latency L (though I think users should be able to request the latencies they think they need) and any other "pseudo-latencies" added (e.g., a site may send out packets to other machines and back to _itself_, even if not requested by the packet itself, as a way to increase inter-site traffic and add latency...I dub this "pseudo-latency"). - packet quantizations supported - digital postage fee (ideally, price competition will occur) - types of encryption supported, etc. - sources that are blocked (e.g., Detweiler's site) or destinations that are blocked (e.g., president@whitehouse.gov). (Thus leading to the flaw in source-filtering I noted at the beginning: all Detweiler, for example, has to do is find a remailer site that does _not_ block him, and he's off and running.) - policies on reported abuse, logging of traffic, etc. - any other relevant information. How users can keep track of this variable information and then make a selection of which remailers to use is a central issue. Full use of a remailer system will almost certainly require scripts and automation at the user site, scripts which select a path through the labyrinth of remailers based on desired security, cost, and acceptable time delays, and perhaps other things as well. I suggest a second generation remailer use an agreed-upon standard format for summarizing this kind of information, requestable by users or credentially agents by sending a message like "::policy" to the site. This would return a summary of digital postage fees, latencies, packet sizes supported, PGP parameters, and any other special items. If done according to a reasonable standard, then scripts could be written to automate this pinging process and the automatic generation of routes. (Joe User would decide how much security he wants for what price, would ping the remailers at some reasonable intervals, and a program would select a set of remailers, do the envelope-within-envelope preparation, adding postage in each envelope as needed, and ask Joe User if the plan looks OK to him...also allowing him to manually (ugh! many dangers of goofs!) add or delete nodes. VII. STANDARD FORMATS. The item above points to the need for a standard format, to be decided upon, for all of the features mentioned here. Where in the message body (or headers, though I favor message body, for reasons of encrypted packets within encrypted packets....) is the digital postage to be included? (This could vary from remailer to remailer, but a standard would make things simpler. Anyone deviating from the standard would be free to do so, of course, but this would make scripts to generate paths tend to avoid his site...a market solution.) I won't speculate as to what form this should take. Perhaps we need to have a "working group" on the Cypherpunks list, made up of the real workers out there. Even a physical meeting that as many folks as possble can attend. VIII. RATINGS AGENCIES. Independent agents that report on which remailers are "up," which are experiencing delays and problems, what the policies are, and what the experiences have been are. This is part of an ecology or economy of mixes and could also use some form of digital money, or digital postage stamps to pay for these reports. These "reputation servers" would give us several useful functions: 1. More of a market, as in VI (MARKETS). 2. Faster feedback, as remailers see problems reported quickly. Users can see a snapshot of which remailers are up, which are not. (If a reasonable standard for the report is established, users can plug into this report for routing messages. In fact, the various ratings agencies--initially I'd only expect one or two to appear, if that--could also sell scripts/programs which work with their report formats.) 3. Another prototype use of some simple form of digital money. 4. Incentives for better performance, security, and standardization on a message format. 5. Performs both a lubrication and a glue function (how's that for mixing two opposite ideas?) of publicizing information. Increases liquidity, decreases transaction costs, making the remailers easier and more reliable to use. The work by some on "black pages" (crypto equivalent of "yellow pages") is a step in this direction. The "key servers" which have PGP keys could be paralleled by "remailer servers" which summarize remailer information, ping results, user feedback, etc. IX. DIVERSE SITES. We need more sites which are outside the U.S., more which are independently owned (i.e., not running on a university or commercial service provider), and more which are otherwise "untouchable" and not subject to pressure. (Aside: I also think we also need "virtual sites" which are themselves only accessible by remailers. For exmaple, a node called "TIM," running on my Netcom account, might actually link in a path known only to _me_, to a site elsewhere. Users would mail to "TIM," but the messages would flow transparently to some other site, perhaps still located in the U.S., perhaps not. From an abstract point of view, this is no different than the "pseudo-latencies" I mentioned earlier, and can be viewed as just a bunch of extra hops in the chain of "first class object nodes," but in my opinion it alters the flavor slightly and makes any publically visible site, like "TIM," more resistant to attack and shut-down, or at least to seizure of the actual mix itself. Other names for these sites might be "sacrificial sites" or "digital cutouts" (a cutout in spy lingo is a person who relays information, an expendable link).) X. ATTEMPTS TO BREAK REMAILERS. Just as cryptography is incomplete without cryptanalyis, so mixes are incomplete without serious attempts to crack them, to spoof them, to subvert them. This breaking does not have to be of the "public disaster" sort, that is, we don't have to "squish" a site by successfully getting a threatening message sent to Janet Reno! Rather, a "tiger team" approach where the breakages are useful to the operators. (The ratings agencies would likely play a role here, reporting on their own experiences, the experiences of their customers, and the results of, say, independent "tiger teams" sent in to try to break the systems.) There are obviously things few of us can hope to do: the NSA may have extensive Internet packet monitoring facilities (a speculation) that we cannot hope to have, or to spend time to develop. Ditto (squared) for covert monitoring of Van Eck emissions (breaking systems by monitoring local computer emissions). Brute force attacks on ciphers. And so on. So let's not kid ourselves that we can break the systems in all the ways the real world will try. CLOSING COMMENTS: Well, these are some basic ideas. A tall order to incorporate these into a second generation set of remailers. But necessary if remailers are to take off and thrive. The addition of the profit motive, by charging for remailing in some way, I view as particularly important in incentivizing progress and proliferation, as well as in in reducing "tragedy of the commons" types of remailer abuses. As this message is already so long, I won't elaborate here, as I promised earlier, on how simple digital postage could be deployed. The idea is the one we've discussed before: sell 20-digit numbers for perhaps 20 cents apiece, in "rolls" of 100 or so. The numbers would ber spendable _once_, perhaps only at the site which issued them (more like a gift certificate). There are obvious weaknesses in such a system, but it may be usable for relatively cheap transactions like remailers. I'll leave it to readers to think about the issues and will perhaps address them in another article, after I've recovered from writing this one! I think the first generation of Cypherpunks remailers has been a wonderful learning experience, but it's time to start planning the next generation. --Tim May -- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@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 | Public Key: by arrangement Note: I put time and money into writing this posting. I hope you enjoy it.