Re: strengthening remailer protocols
At 9:25 PM 9/2/96, John Anonymous MacDonald wrote:
I don't really see the use of this complicated scheme. The main problem seems to be that if M floods remailer R with messages to B, and A sends a message to C through R, then it will be clear to M that A's message was destined for C.
Rather than divert messages, then, I propose that for each input message there is a 10% chance that a piece of cover traffic is generated. Thus, if M sends 50 messages through R and sees 6 outgoing messages going to remailers C, D, and D, he will now know which messages correspond to the message that A send through.
This type of attack is why "reply-block" schemes are fundamentally flawed. Any such scheme gives an attacker (a traffic analyst) a wedge with which to deduce mappings. It is a kind of "chosen plaintext" attack (loosely speaking). Or a "forcing attack." Maybe a "flooding attack" is as good a name as any. One floods the reply block and simply watches where the water goes. (If there were more academics in the crypto community looking at digital mix issues, there would likely be clever names for the various attacks.) Several folks on this list, including (from memory), Scott Collins, Wei Dai, Hal Finney, myself, and others, have noted this weakness over the years. Note that merely fiddling around with probabilities of transmission, such as described above, will not be enough. This just adds a layer of noise, which will disappear under a correlation analysis. (For newcomers, there are interesting parallels between statistical analysis of ciphers and similar analysis of remailer networks. And lots of statistical tools can be used to deduce likely mappings based on source/sink correlations, digram analysis, etc. Making a remailer network robust against such analyses will take a whole more basic thinking. Merely increasing message volume is not enough. Nor is increasing latency enough. Generally speaking, of course.) Instead of reply blocks, I think use of message pools (a la BlackNet) is a more robust reply method, as it uses "widely-distributed messages" (a la Usenet newsgroups) to get around the source/sink correlation issue. --Tim May We got computers, we're tapping phone lines, I know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Licensed Ontologist | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."
Mixmaster prevents replay, so flooding multiple copies of a single message will not work. This is the reason Mixmaster has no reply block feature. I can see two ways in which replies can work safely. One time reply blocks. Each block is used once and only once. Each routes separately, and the creator never deploys enought to allow a good trace (no more than 5 in existence at any one time). They would probably need to be managed by some kind of nym-server. They have the disadvantage of allowing denial of service by simply using up all the available reply blocks. The block also point back to the sender (as all reply blocks must). This allows an attack to rubber hose each operator in succession at the attacker's leasure. Normal chains contain no information about where they have been, so interception and cooperation must happen in real time (much more difficult). The other solution is message pools. I think this will turn out to be the only really secure and reliable system. Some sort of automated use of pools by remailers (so the user need not do so directly) might be possible. I designed such a system several months back, with little response. At 4:50 PM -0700 9/2/96, Timothy C. May wrote:
This type of attack is why "reply-block" schemes are fundamentally flawed. Any such scheme gives an attacker (a traffic analyst) a wedge with which to deduce mappings. It is a kind of "chosen plaintext" attack (loosely speaking). Or a "forcing attack." Maybe a "flooding attack" is as good a name as any. One floods the reply block and simply watches where the water goes.
(If there were more academics in the crypto community looking at digital mix issues, there would likely be clever names for the various attacks.)
Several folks on this list, including (from memory), Scott Collins, Wei Dai, Hal Finney, myself, and others, have noted this weakness over the years.
Note that merely fiddling around with probabilities of transmission, such as described above, will not be enough. This just adds a layer of noise, which will disappear under a correlation analysis.
(For newcomers, there are interesting parallels between statistical analysis of ciphers and similar analysis of remailer networks. And lots of statistical tools can be used to deduce likely mappings based on source/sink correlations, digram analysis, etc. Making a remailer network robust against such analyses will take a whole more basic thinking. Merely increasing message volume is not enough. Nor is increasing latency enough. Generally speaking, of course.)
Instead of reply blocks, I think use of message pools (a la BlackNet) is a more robust reply method, as it uses "widely-distributed messages" (a la Usenet newsgroups) to get around the source/sink correlation issue.
--Tim May
We got computers, we're tapping phone lines, I know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Licensed Ontologist | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."
---------------------------------------------------------- Lance Cottrell loki@obscura.com PGP 2.6 key available by finger or server. Mixmaster, the next generation remailer, is now available! http://www.obscura.com/~loki/Welcome.html or FTP to obscura.com "Love is a snowmobile racing across the tundra. Suddenly it flips over, pinning you underneath. At night the ice weasels come." --Nietzsche ----------------------------------------------------------
On Sun, 8 Sep 1996, Lance Cottrell wrote:
Mixmaster prevents replay, so flooding multiple copies of a single message will not work. This is the reason Mixmaster has no reply block feature. I can see two ways in which replies can work safely.
How about a combination of the two? Suppose Alice wants to anonymously post a message and get replies. She generates a new RSA key, signs her post with it, and asks readers to send encrypted replies to a server. Then periodicly she sends a one-time reply block to the server to retrieve the accumulated replies. This would let Alice receive an unbounded number of replies and also give some protection against the denial-of-service and rubber-hose attacks Lance described. Wei Dai
Wei Dai writes:
How about a combination of the two? Suppose Alice wants to anonymously post a message and get replies. She generates a new RSA key, signs her post with it, and asks readers to send encrypted replies to a server. Then periodicly she sends a one-time reply block to the server to retrieve the accumulated replies.
I'd like to chime in and say that this is a really good idea. Basically a nymserver that holds onto incoming mail until an e-mail arrives from the nym to retrieve it. How would mixmaster be able to support one-time reply blocks? If the nym's mailbox is larger than the mixmaster message size (pretty likely) and needs to be split up, then more than one reply-block is going to be required. Should the nym generate a big stack of reply-blocks/routing headers and send them in with the retrieval request? I suppose the server could fillup as many mixmaster message parts as it had blocks, then append something like "15 more messages waiting (32,082 bytes - Two More Reply Blocks Required)" and ship it off. Reliability is a problem with remailers... what happens now if a remailer in your reply block goes out and you receive mail at your nym account? Does it just disappear? With this system you could have a simple ACK protocol to ensure reliable delivery of the mail. A magic cookie would be appended to your retrieved mail, which the server would then hold onto (it would still count against your quota...). The mail would be deleted once you sent back an ACK with the magic cookie. Here is yet another good application for DigiCash. The operator could offer free accounts with very small mailbox quotas, or charge for bigger accounts. Message retrieval could also be charged, of course. Another idea is that the sender could affix postage if they wanted their message to be appended to a full mailbox... A service like this is no different from something like pobox.com, except that this service lets you pickup your mail through e-mail instead of POP. So I don't think the operator would/should incurr any more liability for what runs through the system than pobox. andrew p.s. It would also be a cool thing, IMHO, for nym servers to bounce back an advertisement to everyone who sends mail to a nym.... A way to spread the word.
On Tue, 10 Sep 96, Andrew Loewenstern <andrew_loewenstern@il.us.swissbank.com> wrote:
Wei Dai writes:
How about a combination of the two? Suppose Alice wants to anonymously post a message and get replies. She generates a new RSA key, signs her post with it, and asks readers to send encrypted replies to a server. Then periodicly she sends a one-time reply block to the server to retrieve the accumulated replies.
I'd like to chime in and say that this is a really good idea. Basically a nymserver that holds onto incoming mail until an e-mail arrives from the nym to retrieve it.
Instead of that, how about this? 1. Create a pool of N remailers, each with its own set of public/private key pairs. The public key(s) for each remailer are widely disseminated. Each remailer also publishes a list of other remailers that it will poll for messages. (More about this later.) 2. Each remailer user MUST have at least 1 public/private key pair per nym. The public key should be widely available. 3. Each message is encrypted with the intended recipient's (nym's) public key, and then with each remailer's public key succesively, but in reverse order. (The message is encrypted last with the public key of the first remailer in the chain.) The chain is determined by selecting some subset of N at random, with the set growing as the need for security increases. Encryption is done a la PGP, with a header prepended to the message containing the fingerprint of the public key used to encrypt the session key used to encrypt the actual message. Each layer of encryption encrypts the header of the previous layer of encryption as well as the message, so only the last encryption is "visible", and it is not feasible to detect the number of encryptions by examining the message. 4. The multiply-encrypted message is sent to the first remailer in the chain. The remailer decrypts the message with its private key, and at this point one of two things can happen. If the decrypted message specifies an email address, the remailer sends the message to the specified address. Otherwise, it posts it in a publicly available database with 3 fields. 2 are public; one contains the key fingerprint of the outermost public encryption key, and the other contains the message itself. The third, private field contains the date/time the record was added to the database. Any appropriate techniques for reducing input/output correlation can be used, such as delaying the decryption for random time intervals, dummy messages between remailers, etc. Remailer-to remailer traffic (or to any nym that gets a lot of traffic) should should be bundled together (take a few hours worth of traffic going to a specific nym, ZIP it into one large message, and re-encrypt using that nym's public key) to prevent a sender from being able to recognize any of his messages in transit. 5. Anyone can do lookups in the public fields of the message database by key fingerprint. Remailer users do this to download their messages, and remailers download messages from other remailers in this manner as well. Anyone can download any message in the database; only the intended recipient will be able to decrypt it. Messages are not deleted when they are downloaded; instead they are kept for a fixed period of time (determined by the remailer operator) and then deleted. If users are required to download other people's messages, tracing a message to one specific person will be much more difficult. 6. Steps 4 and 5 are repeated until the final recipient receives his message and decrypts it, at which time crypto-anarchic utopia can resume. Randumb Thotz: Given an encryption program with a database of which remailers poll other remailers, remailer chaining can be automated, and be done randomly. If 2 nyms can agree to poll a mutually known set of remailers, (such as via anonymous Usenet/Blacknet postings) 2-way anonymous correspondence can occur without either nym having to know the other nym's email address. The remailer operators wouldn't know either, but they may be able to make reasonably informed guesses at recipient-nym relationships via analysis of database browsing patterns. This is the the weakest part of the proposal, and suggestions for preventing this would be appreciated. Remailers should use SSL or other encrypted communication protocols to ensure that third parties cannot observe who is browsing what in the public message databases. Jonathan Wienke
participants (5)
-
Andrew Loewenstern -
JonWienk＠ix.netcom.com -
Lance Cottrell -
tcmay＠got.net -
Wei Dai