-----BEGIN PGP SIGNED MESSAGE----- From: Nathan Zook <nzook@bga.com> [ Re: remailers checking signatures on incoming messages ]

What benefit does Alice gain? 1) Plausible deniability. Remember, "reasonable doubt." Remember Abscam? The gov't is in a good position to fake source info. This squishes that. (It squishes even better if Chaum _requires_ signatures.)

She doesn't get that. A signature lets her prove that she sent a message. It doesn't let her prove she didn't send a message.

2) If Chaum sends Alice a copy of the message that failed the signature check, Alice knows that someone is trying to spoof her. This information may be critical in determining how serious her opponents are.

I don't really understand this threat that Alice may be "spoofed". Why, of all places, would her opponents try to spoof her through an anonymous remailer? Isn't this kind of like sending mail with no return address, and pretending it comes from someone else? This seems terribly subtle.

What might Chaum gain from checking or requiring signatures? Various net abuses often involve faking names. Requiring validated signatures would pressure these abuses away from the remailers. Reducing the net abuses going through the remailers is a PR goal.

This would be a good thing, agreed. And requiring signatures probably would weed out a lot of the flakes, largely by raising the threshold of cluefulness needed to use the network.

It seems to me that hacking PGP requires considerably more cooperation between remailers, and more work than just allowing recursive opening of PGP packets, automatic padding (or concatenating) of data, and automatic encryption of out-goin mail. Subways and MixMaster both appear to have far more working required to implement, far more cooperation between remailers, and far more room for failure than my idea. (Emphasis: appear. I've not seen Lance's paper, yet. He's getting it to me.)

This is not clear to me. My hope would be to persuade the PGP developers (many of whom read this list) to incorporate a pad feature in future versions so that messages can be easily rounded up to a standard size. Alternatively the mixmaster client may include this capability.

OTOH, you seem to be agreeing with me here. Who hacks PGP? Who is PGPing their outgoing stuff? Don't we have to have standard packet _inside_ the net? And you achieve this by using PGP? ?????

I can see the problem with standard packets in a chaining context, that they would shrink slightly in size as each successive remailer stripped off its envelope. Re-encrypting would solve this by providing more padding. OTOH you can actually stick padding into a PGP packet if you know what you're doing. I have a perl script around somewhere which will do this.

...

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?

The most obvious one: Eve checks messages (in vs out) for matching tails. If the tails match, the messages match. The only way around this is for the entire message to be wrapped. Thus, the extropian requirement.

It is true that encrypting messages intra-remailer would prevent this attack as far as that one remailer in the chain is concerned. But it seems to me that the message still suffers from this attack against the remailer network as a whole. This points up the fundamental problem with this form of encrypted reply block. They are really not secure unless the body itself gets transformed at each step as in Chaum's model.

When I say that the Mark I remailers are laughably easy to crack, I mean laughably easy.

None of this is news. We have been discussing these attacks for years. Even with intra-remailer encryption I think these attacks work against the remailer net.

Is the message a clear set of ::Request-Remail-To:? Pull & log. This will work when the message is heading to the net in the clear, even if it is encrypted between nodes.

Is the message clear, with encrypted headers? Match, pull, and log. You can still match the message entering and leaving the net, even if it is encrypted within.

Is the message encrypted separately from the headers? Match, pull, log. As above.

Is the whole message encrypted? Take the ones that are left, match the largest. Match the next largest. Match the next largest. Pull & log. Encryption with padding between nodes would protect against size matching, I agree. But it is the padding which is important, not the encryption.

Get stuck? Need a hint? Resend a message. Watch for the repeat on the out. That's why Chaum identified one of the main features of a remailer being that it would reject duplicates. Mixmaster does some version of this, although that needs improvement to really meet this attack.

Alice has been hauled into court. The Feds claim that she is the one that actually sent messages M1,...Mx to Bob through Chaum, even though these messages have varied From: (and From) lines. As root, she cannot claim that this is not possible. OTOH, if Chaum requires a match, the Feds would have to claim that she compromised the secret keys of all of all the cooresponding From: addresses. Much tougher.

OTOH, if Alice actually has signed those messages, her jig is up pretty good, wouldn't you say? Do we really want to force people to use the nets in a mode in which they can be incriminated like this by a hostile government?

Seriously, if a sight is being shadowed, then it is insecure. It is to our advantage to know this. You are right that we "don't care" where a message comes from only if we assume that the message _didn't_ come from an LEA. (Or a big corporation. Some of them probably have the power to do this, too.)

Hell, Detweiler has the power to do this! He's spoofed messages plenty of times. How do we know? Because of remailer logging. That's the real threat, IMO (the logging).

If it did, then the remailer net is under attack, and we most definitely _do_ care about that.

Even if a message comes from a fake address that is hardly evidence of an attack by a powerful opponent. It could just be an extra-paranoid legitimate remailer user who doesn't want to extend any more trust than necessary.

...

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.

I'm lost here. I thought that sending an identical message (producing identical output) every tick would be the equivalent to an attack.

I meant to refer to encrypted messages identical in size and otherwise opaque, so that your apparent rate of output is constant.

But what exactly constitutes "successful countermeasures"? How do you prevent an attacker from taking over a sight, thus compromising it, w/o the knowlege of the operator? How do you prevent long/short matching of the remailer net _as a whole_? How do you prevent tail matching? How do you prevent middle matching, for that matter? How do you prevent the repeated message attack?

I was referring specifically to the correlation attack described by Wei. The other attacks you describe need to be met by the kinds of countermeasures we have been discussing: standard-sized messages, remailer chains, not using encrypted reply blocks which leave message bodies alone, rejecting matching messages. All of these were discussed in Chaum's 1981 paper.

...

Do you see your suggestion as protecting against Wei's in/out correlation attack?

Yes! Well, not by itself. My suggestions about "rational use of garbage" do that. If Bob recieves x messages each tick, 0 to x of which are real, Eve is hosed--if all messages are standard sized & encrypted!. Eve is even more hosed if the x messages are concatenated & superencrypted. If Alice sends y messages each tick, Eve is hosed. Even more so if the messages are concatenated & superencrypted.

How can Bob arrange to receive a constant number of messages each tick? Do all his messages come from one remailer? Or do all of the remailers which might send to him check among themselves before sending to him so they can mutually know how many fake messages to send? IMO the real solution to the correlation attack is to have a constant message generation rate. That is sufficient. Solutions to the other attacks mentioned in Chaum are described in Chaum. (This attack was not described in Chaum's paper.)

...

Of course it was Chaum himself in his 1981 paper (which I think is available from the CP FTP site) who described the duplicate-message attack. I don't see that inter-remailing encryption helps much, because the attacker can still notice that whenever they inject message A, _something_ goes to Bob. The real solution, as Chaum pointed out, is that the remailer must reject duplicate messages, even when separated by days. Doing this without keeping a database of all messages ever sent is left as an exercise.

I disagree. If identical input to Chaum does not produce identical output to Bob, how does Eve coorelate them? Repeating, she can match the top of the body of messages, so random tails reveal the actual encrypted message, for whatever that is worth.

I'm not sure what you mean by "matching the top of the body of messages". Are you referring to an encrypted reply block, which might be the same for two different messages to the same user? Or are you suggesting that messages would have some headers or some other structures at their top which would be preserved through a remailer?

And if Bob receivs x packets per tick, or a BIG packet every tick, how does Eve trace it?

If the input to Bob really can be made constant across the whole remailer net then this does seem to largely protect against duplicate-message insertion, in conjunction with the intra-remailer encryption. However it would apparently also be necessary for every remailer to send a constant number of packets to every other remailer. Otherwise a bolus of duplicates into one remailer would all leave to go to the next remailer at once and would show up. This means that the net as a whole has to carry a constant traffic load on all inter-node links, which could mean a large cost in bandwidth load. I still think that rejecting matching messages is a better solution.

...

Another aspect worth mentioning is that message splitting can make the kinds of statistical correlations that Wei Dai was looking at more of a danger.

More than being the ONLY file in the net of your (approximate) size?

No, of course message size standardization is a necessary step. This has been recognized for 15 years.

...

It's one thing if I send a message along with thousands of other people, and Bob gets a message along with everyone else. But if I send 10 messages and Bob gets 10 from that batch, that fact alone can help to link us up. So splitting my big message into 10 standard ones isn't that great if they're all sent at once. Ideally you'd want to dribble them out at some standard rate, a rate at which you always send a message whether you have something to send or not. But this may introduce unacceptable latency.

"Dribble them out at some standard rate". Yes. y packets per tick. Set y equal to your average number of real packets per tick, plus 3 standard deviations. Since you are chaining, the latency of you input will be less than the latency of the remailernet.

OK, but chances are your average number of real packets per tick is < 1, e.g. if a tick is a few hours and you only send one or two messages a day. So when you do need to send that 500KB GIF it's going to take a lot of ticks. I would sum up by agreeing with several points: the need for standard message sizes, and for a standard rate of message output. I am neutral on whether a remailer may want to super-encrypt a message to the next link in the chain (whether a remailer or an end user) if it happens to have a key handy. I don't see any harm in this and the remailer software will already handle this transparently on the receiving end. I disagree with the idea of remailers checking signatures. I don't agree that inter-node remailer encryption provides significantly more protection than padding. I think that encrypted reply blocks are unsafe even with inter-node remailer encryption. See Chaum's paper for ways that encrypted reply blocks can be used safely. We have also had some suggestions here for modifications to Chaum's method. And I don't see how you can arrange to receive a constant load from the net without a highly centralized system, which would have its own dangers. Hal -----BEGIN PGP SIGNATURE----- Version: 2.6 iQBVAwUBLzCGHRnMLJtOy9MBAQEzlwH/XUYi0mhSUl0Dd4hMp/dE9KFEDQd3jNQs Zby7ZIDl3qQn1EK1f81pLSHUYdQgGflMrMaDS9QTrRXSR/mYqx3HeQ== =ZyWU -----END PGP SIGNATURE-----