The MIRV idea for messages is not bad, but by itself it does not provide enough cover. If you have a 33K byte message come in and a while later a 21K and a 12K byte message go out, there might not be many other possible messages that could add up to 33K. A more complete solution is to pad all messages to a standard size. If every message which goes into the remailer is the same size, and every message which comes out of the remailer is the same size, and each has no carried-over header or message-body information, then there should be no way of matching up incoming to outgoing message. This was the simple solution in Chaum's original February 1981 CACM paper, which I would strongly suggest that people read. CACM is probably the most widely available of the computer science journals and should be at every university library. Chaum's paper has some interesting aspects that are not often mentioned. He actually proposes two different solutions that differ somewhat. (People should also be aware of his alternative solution to the traffic analysis problem, the "Dining Cryptographers" network. I think Tim may have scanned that in at some point, so it might be on the net. DC nets tend to be high bandwidth and are more suitable for LANs or WANs than email, IMO.) The first solution in Chaum's paper is the "Cascade". In this there is a sequence of "Mixes", what we would call remailers, which are used in a FIXED order by everyone. It's as though everyone first sent their messages to soda, then to portal, then to catalyst, and so on through some specific sequence. Furthermore, these are all sent in a set of batches which stay together as they move through the network. A batch of messages starts at soda, then at a later time that same batch pops out the other end, having been decrypted and shuffled at each step.

From our perspective, this seems like a wasteful way of using the network. By keeping the messages together like this, the whole cascade does no more shuffling than would a single mix. Using the cascade provides no more confusion of messages.

But the advantage it does provide comes from the fact that there is no guarantee that the remailers are honest. This is something which is often overlooked by people who make suggestions that remailers should cooperate, should automatically choose the message paths, etc. Chaum uses the cascade so that if even one mailer on the chain is honest and uncorrupted, the whole chain is strong. If you _knew_ you were using a good remailer you wouldn't need a cascade. But by using a cascade you get that much more assurance that you have security. The other reason for using a fixed cascade, I think, has to do with the details of message padding. The problem is that, generally, when you decrypt a message it is not exactly the same size as it was when you started. Particularly with remailer messages, where there may be some encrypted address information along with the message, the output will tend to be smaller than the input. By using a cascade, the messages will all shrink in step as they move along. All of the messages coming in to any mix in the cascade will be the same size, and all the messages going out will be the same size, but the outgoing messages may not be the same size as the incoming ones. It is this size differential which would make it hard to safely combine messages which have gone through different numbers of mixes. Chaum does go on to suggest a solution to this as the second main part of his paper. That part is considerably harder to follow, but the main idea seems to be that the mixes themselves will add padding to the end of the messages so that they stay the same size. Chaum describes this in terms of messages composed of fixed-size blocks, but it would seem that the idea could be generalized to a remailer which added random padding to bring the output message up to the standard size. I can't see any security leaks in this generalization. One interesting idea Chaum suggests is that after the remailer decrypts the messages in its batch, it does not simply send each one to the next address, but rather broadcasts them (perhaps to all of the other remailers). Those remailers try decrypting all of the incoming messages and only those messages for which the decryption succeeds will be sent on. Again, I'd suggest people interested in reamailers read this paper. I believe there were some follow-ups in the Crypto 89 proceedings, but my library is missing that volume so I haven't seen them. Hal