From: Hal <hfinney@shell.portal.com>
Date: Sun, 29 Jan 95 13:14:56 PST
To: cypherpunks@toad.com
Subject: Re: Secure (?) Remailer-net
Message-ID: <199501292113.NAA06033@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


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