As per Hal's suggestions, I've come up with a simpler example. I've also hardened it against an attack that he noticed, which has considerably changed the protocol. Hal writes:

Another general point, which may be important. Chaum emphasized that his anonymous addresses should be use-once, because if two people send messages to the same anonymous address, someone who has access to the mail going into and coming out of the remailer will see identical address fields coming out for the pair of messages. I think Eric's scheme has the same property.

While thinking about this weakness, I realized that everything gets a lot easier if each (re)mailer knows the public key of the next. This is public knowledge, so there's no need to hide the key once the next destination is known. If there was a complete database of public keys of remailers that each remailer had, the key could be found from the address. Since that database might not be up to date, the public key is transmitted along with the address. Consequently, I was able to remove all of the conventional keys from the protocol. All encryptions are now done with public keys. Of course, there is still the conventional encryption done for each public key encrypted packet. The protocol is strengthened against this attack by fresh encryptions at each stage which hide the constant string. Note that the remailer itself can still identify the set of messages that were sent using the same envelope. It would be nice to fix this, but it seems unlikely at this point. Any ideas anyone? --------------------------------------------------------------------- I've got two examples here: a paired down one, and a slightly fuller one. The first has no postage, which cuts down considerably on the excess. The second example is just the first with the postage added back in (just to show that it still works). The envelope specifies hosts &Z and &R. The sender routes the message through &Y before using the envelope. So, the message goes from &S to &Y to &Z to &R where it is delivered. The complete simplified transaction is reproduced below, starting with the initial envelope: Addr: &Z, z, z(&R, r, r(junk)) To: &Y Addr: y(y(&Z, z, z(&R, r, r(junk))), pad) Message: y(M, pad) To: &Z Addr: z(z(&R, r, r(junk)), pad) Message: z(M, pad) To: &R Addr: r(r(junk), pad) Message: r(M, pad) The sender basically ignores the contents of the envelope, but wraps it in the public key y for safe delivery to &Y. The message and the address info are both then padded and encrypted with y. The reason for encrypting the address info with y twice will become clear shortly. &Y receives the message labeled To: &Y above. The outer y encryptions are removed, followed by the inner y encryption on the address field. The message M, and the original envelope are thus revealed to &Y. &Y now knows to send the message to &Z, and knows the public key z. The message M is then padded and encrypted with z. There is already a portion of the address field that is encrypted with z. That portion contains all of the info that &Z needs to know, but this info, as Hal pointed out, is a constant string; an external observer could use this to associated a group of messages with a single envelope. To obscure this, the string is encrypted a second time with z. Recall that a random conventional key is generated each time a public key encryption is done, so a constant plaintext string will encrypt to a different cyphertext string each time. The padding helps keep the string from being identified by its length. To keep the protocol consistent, the original envelope had to be encrypted with y twice. The resulting message is sent to &Z, where the same processing is done. Let's trace it in detail this time, but without the extraneous padding. &Z has received: Addr: z(z(&R, r, r(...))) Message: z(M) Which looks to the outside world like: Addr: z(...) Message: z(...) But &Z can decrypt those z(...)'s to obtain, first: Addr: z(&R, r, r(...)) Message: M And then: Addr: &R, r, r(...) Message: M With r thus exposed, &Z can encrypt both M and r(...) with it to obtain: To: &R Addr: r(r(...)) Message: r(M) Which to the outside world looks like: To: &R Addr: r(...) Message: r(...) With everything nicely hidden. This is what gets sent to &R. Knowing r, &R can recover M. We're done. -------------------------------------------------------------------- I'll present the postage example without further comment, except to note that at each step, all fields are freshly encrypted with the next hop's public key. Addr: &Z, z, z(Sz, Qz, &R, r, r(junk)) Pneed: Pz, Amt_z, Pr, Amt_r To: &Y Addr: y(y(Sy, Qy, &Z, z, z(Sz, Qz, &R, r, r(junk))), pad) Post: y(Py($y, Pz($z, Pr($r))), pad) Pdue: y(Qs(stuff_s), pad) Message: y(M, pad) To: &Z Addr: z(z(Sz, Qz, &R, r, r(junk)), pad) Post: z(Pz($z, Pr($r)), pad) Pdue: z(Qy(stuff_y, Qs(stuff_s)), pad) Message: z(M, pad) To: &R Addr: r(r(junk), pad) Post: r(Pr($r), pad) Pdue: r(Qz(stuff_z, Qy(stuff_y, Qs(stuff_s))), pad) Message: r(M, pad) -eric messick