From: Hal <hfinney@shell.portal.com>
Date: Wed, 1 Feb 95 23:14:37 PST
To: cypherpunks@toad.com
Subject: Re:  Why encrypt intra-remailernet.
Message-ID: <199502020714.XAA15798@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


-----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-----