From: Nathan Zook <nzook@bga.com>

...

...

First, the message is signed with the sender's key. (More on that later.)

I did not see why this should be done.

No? Isn't the InterNet currently under a serious packet-spoofing attack? Don't we expect Eve to be AKA NSA? If I run a remailer, I want to know that I'm not being lied to in the process. That insistance might just save the legal butt of the guy being spoofed, by demonstrating that the packet did not in fact originate from the remailer. Just because remailers are legal doesn't mean that the govt won't still try to shut them down...

I can see the advantage from the sender's point of view. If I sign all messages I send, then I have some defense against the charge that I sent a particular message, if it doesn't bear my signature. (OTOH the prosecutors can argue that I simply skipped signing that one.) This does of course expose me to the risk that if I _did_ send a particular message, my signature will be incriminating. In any case I am still puzzled by your statement that you as a remailer operator would want to be able to verify the source of all incoming messages. Would you do things differently with messages from different sources? I hear you saying that you care if you get a message claiming to be from Alice but not bearing a good signature from her. Why? Again, what would you do differently?

...

A better approach IMO is to embed the message length in the encrypted information (as PGP does) and pad with cryptographic random garbage (which PGP could be patched to do).

In this instance garbage is defined as cryptographic random. If the message has a length indicator in the clear, then Eve can read it. (Remember, Eve runs snakoil@nsa.gov.) Therefore, such a marker has to be _inside_ the wrapper. Given this, (that everything is PGP wrapped) there is always the chance that PGP will compress a message, even one with cryptographically strong bits in the end. While compression can improve protection, it is not likely to do so if the original message was already PGPed. Only "clear" messages, therefore, risk losing protection. As you note, such messages don't deserve as much help as opaque ones.

PGP already includes a cryptographically protected length field in the message. It will ignore any data past that, according to my experiments. All that is needed is a simple patch to add junk data to the end.

...

...

Note that this system would allow the extropian remailer to be compatible with Matt Ghio's alias system. (Right now, the remailer doesn't like separate pgp packets, or packets it can't read, or something.) Under the current system, the precausion is entirely warranted.

I don't think so. The problem with Miron's extropy remailer is that it only passes through the contents of a PGP block. For anonymous addresses to work, the (chained,encrypted) address must be in a PGP block which precedes the message body. I don't see how any cutmarks idea would affect this.

Sure it does. If the whole thing is inside a PGP wrapper, then it is secure. "Only passing through the contents of a PGP block" is currently a security measure that makes good sense. But if you have two separate blocks _inside_ an outer wrapper, you already have full security. Strip off the outside, find two more wrappers. Strip the first, get remailing instructions. Attempt to strip the second. Fail. Attach second wrapper to forwarded message. Full security.

I still don't quite follow this. Exactly what attack would be possible against Miron's remailer if it allowed encrypted reply blocks (as all others do) which would fail if the messages were wrapped as you suggest?

Alice signs her messages to the remailer because she doesn't want anyone spoofing her use of the remailer. If a message goes in at 00:00:00.01, 1 Jan, 2001 that is "From:" her, it is FROM her. More of the same reasoning. This key doesn't have to have anything to do with the key she uses with Bob. It is the one that she wants the general public to use for HER.

Alice may not have a key whe wants the general public to use - she may just be using one for her private correspondents. Actually it seems to me given the nature of remailing that it would be superior if it were easy for people to "spoof" my use of the remailer. That would give me more credence to claim innocence. The more useless return addresses are, the less we even need remailers.

Suppose you were using the remailer net. Would you care to know that someone was spoofing a node? I would. It would indicate that someone is either hacking the system (probably no big deal), or that someone might be shadowing a remailer. That is, the remailer is no longer secure. Spoofing is a big deal on the net generally, and if we start being used a lot, we will have to deal with it as well. Why not now?

It's not my job to fix the damn Internet. So what if I get mail claiming to be from abc when it's actually from def? I of all people care the least, specifically because I throw away this data. Virtually everyone else on the net cares where their mail comes from, but I don't. My whole purpose is to discard the information about where it comes from. That is why I am so confused about your emphasis on checking signatures.

Maybe that was too harsh. I don't advocate holding people's hands. What I _do_ want to do is to provide the best service that we can. Note that from earlier and current work (thanks, guys!), we see that even if the remailer net itself is completely secure, the sender and reciever can still be traced with near-exponential speed.

Although I agree with Wei Dai's mathematics, to my mind it points up the importance of successful countermeasures rather than implying that the remailer network is inherently insecure. For example, if you send one identical message every batch, Wei's math shows clearly that you can't be traced. Let's not get rumors started about how the remailers don't work.

So our systems provide a delay in tracking of a couple of months. Big deal. The TLAs routinely take years to build a serious case. If we are going to be any help to folks that _really_ need it, we have to extend the black box all the way to people outside the net. As you said, not everyone will be remailers anytime soon.

Do you see your suggestion as protecting against Wei's in/out correlation attack? I don't see it. If fixed-sized packets are used, with chained encryption, I think you have as good a system as you do with all of your inter-node encryption and signing. Suppose one good encrypted message enters the net with 10 unencrypted ones. Won't the full path of each of the 10 be visible to an outsider? Even if the remailer helps out those 10 doltish users by encrypting them from there on out, the outsider already saw their whole paths! They will know how many unencrypted messages are going out to each destination, and from that determine where the encrypted message is going.

...

Since the secret key d is effectively a random number from 0 to m, you would have to create, say, 1000 key pairs to have a good chance of finding a d that was as much as 10 bits shorter than m. Then o(d) might be 5 bits shorter. So you'd be done from 768+384 to 758+379 or about a 1% reduction in time. And it will take a while to generate 1000 keys. To get a 2% reduction you would have to generate 1000000 keys. I hope you have a lot of time on your hands.

Actually, I did make this error when I first considered this, also. We do not hope for a short key. In fact, we know that the key will be long, when viewed in parts, as I now believe that it is. We hope that the key will be 0 rich. The chance of this just comes off of the binomial distribution, which is not nearly so bad. Sorry. And a, say, 10% improvement above expected allows a cooresponding length increase--which does something _more_ than improve security by 10% ;)

Yes, I see that you are right about this. It would be easy to generate e,d pairs and get a d which is significantly short on 1's by 10% or more. I did not quite follow your algorithm to do this (was n the modulus or was it phi, the sum of the modulus' divisors?). The one caveat is that if "high-zero" decryption exponents are widely used, it could conceivably reduce the search space somehow, although I don't see offhand how to exploit this. Hal