From: Nathan Zook <nzook@bga.com>
Date: Sun, 29 Jan 95 06:46:52 PST
To: cypherpunks@toad.com
Subject: Re: Secure (?) Remailer-net
Message-ID: <Pine.3.89.9501290816.A10826-0100000@edwin.bga.com>
MIME-Version: 1.0
Content-Type: text/plain


First, in case you all haven't noticed, I am seriously async here.  Sorry
that I sometimes seem to alternately really miss or firmly grasp the
obvious.


From: Hal <hfinney@shell.portal.com>
>From: Nathan Zook <nzook@bga.com>
>>     The traffic analysis that we've seen so far mainly just documents
>> tcmay's "everybody a remailer" concept.  If you look, you will notice that
>> these analyses all assume that Alice and Bob are _not_ remailers
>> themselves, and for a good reason.  If Alice and Bob _are_ remailers,
>> analysis of the type used here is worthless, especially if Alice and Bob
>> have a policy of not sending any mail unless they first receive garbage,
>> and of sending out garbage whenever they get a letter.
>
>Realistically, though, everybody is not a remailer, and there are no
>prospects of everybody becoming a remailer anytime soon, so the analyses
>of Wei and others are certainly relevant.
>


Yes, but... 
Presumably those who feel that they need remailer and are willing to put
out the effort to use one might also feel that they need a higher level of
security.  I suppose that my remark might be more accurately:
"mainly just documents the superiority of the 'everybody a remailer'
concept for TA purposes."  Of course, if the remailer-in-a-box isn't much
harder to use than PGP was two years ago, then maybe "everybody" will...


>>     HOWEVER, the analysis makes another assumption--that messages are
>> indistinguishable.  This assumption does not correlate, as I understand it,
>> with the current remailer net.
>
>Mixmaster is supposed to do splitting and, I think, padding.  I hope to
>have time to look at it soon.  It sounds very good.
>
>>     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...


>>     Suppose a signed message to be forwarded is smaller than the standard
>> packet size.  The sending remailer adds a Cutmarks:  header.  At the end of
>> the message, the cutmark is added, followed by sufficient garbage to fill
>> out the standard packet size.  The message is then pgp'ed to the recipent
>> _with COMPRESS = OFF_.
>
>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.


>>     Upon receipt, the message is decrypted, and its origination can then be
>> triply verified (at least).  From: line, packet size, and PGP signature.
>> Since the message claims to be from a packeting remailer, the packet size
>> should be the standard one.  The recipient now has the message that was
>> sent to it.  This message is probably itself encrypted, so it can be
>> handled (almost) as if this message were just received.  This includes
>> stripping the garbage and (probably) decrypting the message to get the
>> forwarding information.
>
>Why does the remailer care where the message came from?  What difference
>does that make?  I can see the final recipient caring about the original
>sender, so a PGP sig makes sense at that level, but why at each hop?
>

See below.  Basically, we don't want to be spoofed ourselves.  Bad
security for our systems.  Admittedly, this is probably not a real problem
today.  See my sig.


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


>>     To make life even more fun, there is no good reason that non-remailers
>> cannot be in on the action!  Alice, sending to Bob through Chaum, pretends
>> to be a remailer.  That is, she prepares her message to Bob, (encrypted),
>> and adds the Request-Remailing-To:  Bob@nowhere.org, and signs it.  She
>> then observes that the message is too small, so she adds the Cutmarks:
>> header, etc.  When Chaum receives the packet, he opens it, removes the
>> cutmarks, and sees a signature he does not know.  Chaum then sends a
>> request to pgp-key-server@omniscient.gov for the key, and holds the message
>> until he gets it.  He then compares the address and name on the key
>> recieved to the message.  The signature is good, so he is ready to send the
>> packet to Bob.
>
>Again, why does the remailer go to all this trouble to verify a
>signature from Alice?  That sig is for Bob!  She may not even want to
>post her public key for everyone; Bob may be the only one who has it.  I
>don't understand why the remailer, which exists to hide identities, is
>going to such trouble to verify them on its own.
>

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.


>> But Bob can be in on the game as well, since there is no
>> reason that he cannot handle the Cutmarks:, the signature, and the nested
>> encryption.  In fact, Alice could include a copy of Bob's key in the
>> message for Chaum to use, after a Recipient-Key:  header.
>
>Alice is the one who should encrypt the message for Bob, not the
>remailer!  Are you suggesting that she should let the remailer see the
>message contents?
>

NoNoNoNoNoNoNo! ;) The key she includes is Bob's public key.  The same one
that is on the key servers.  This is so the message can be standard sized
for the final trip to Bob.  As we have noted, messages are quite vulnerable
at this stage.  If every message that Bob gets from Chaum "looks the same",
who is to say which is which?


>> Bob can also
>> verify that the message was actually routed through Chaum.
>
>Why on earth does he care?  I really don't see what problem you are
>solving here with all this checking.
>

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?


>> If Chaum is
>> concerned that, at some future time, Eve might supeona his key ring in
>> order to demonstrate that Alice and Bob are using Chaum, Chaum can
>> alternately request keys that he does not need from the servers, and delete
>> (older) keys in the ring.
>
>Eve would be more likely to subpoena Chaum's secret key ring.  A public
>key ring proves nothing.
>

Ever hear of "guilt by association"?  See my sig.


>>     In other words, if all the remailers can handle nested pgp packets and
>> cutmarks, we are close to moving all small messages to a standard size.
>
>This mostly makes sense (although as I said I prefer simply enhancing the
>crypto program to take a parameter for output pad size) but I don't see
>where all the rest of it came from.
>

If the message length is world readable, it is world readable.  The super-
wrapping makes sure that it is not.  It also makes clear messages
indistinguishable from opaque ones inside the net.  See below.


>>     What if the file is too big?
>>  
>>     If the file is too big, break it in pieces.  We need a header,
>> Multipart Message:  n of m.  Note that since this is assumed to be _inside_
>> a pgp wrapper, it is secure.  The recipient could hold and merge the files
>> as needed.  If the message to be forwarded is too big, split and continue.
>> Since the messages are ascii armored, the split/combine protocal is to
>> concatenate.  Message parts could be made equal size to minimize the chance
>> of a message barely bumping over the limit as it moves.  Of course, Alice
>> could break her message to Bob directly, but we cannot assume that all
>> would do this for us.
>
>I believe Mixmaster provides a client mode to do this.  I prefer putting
>more functionality in the hands of the users and not relying on kindly
>old Uncle Remailer to do it for you.
>

Yes, but...  Breaking an overly large file makes it indistinguishable from
standard sized ones.  See below.


>>     This also means that if Alice sends a message to Bob in the clear
>> through Chaum, and David, that the message will be encrypted from Chaum to
>> David.  Thus, if Eve wants to know which message from Chaum to David is the
>> one from Alice to Bob, (perhaps to know that it is _not_ the message from
>> Frank she is interested in) she knows only that it was one of the messages
>> from Chaum to David after Chaum got the message from Alice, and before
>> David sent it to Bob.  While Chaum and David can both read the message, it
>> still provides mixing capabilites inside the remailer net itself, and thus,
>> some protection to Frank.  (Who apparently needs the help.)
>
>This is a commonly made suggestion, but philosophically I am opposed.  We
>got into this fix (lack of privacy) by letting people rely on others to
>do things for them.  It's time for people to take responsibility on their
>own.  The kind of thing you are suggesting provides the illusion of
>privacy.  Never trust remailer operators!
>

below:  (Couldn't resist ;-)

The point of "Uncling" insecure messages has nothing to do with improving
the security of the insecure messages.  I agree, as a good member of the
Libertarian-Christian wing of the Republican party (NYET!) that these folks
deserve snakeoil.  But we're _not_ doing it for them.  We're doing it for
Frank, who does everything right.  If Eve doesn't know anything we don't
have to tell her about Alice's messages, then she gains no free negative
information about Frank's.  Judging by the remailer stats, there are a lot
of messages traveling "in the clear." These messages currently do nothing
for those of us that do things right.  It's time that they do.

So I'm not encouraging Alice to trust Chaum.  I'm encouraging Chaum to give
Frank all the help he can.  Frank, who just blew the whistle on the
"Justice" Department.  Frank, who does everything right, and might even
stand out because he does.  Frank, the guy we are all really doing this
for.

To put it another way, if we really don't want centralized solutions, if no
one should trust any of us, if the users should provide all of their own
cover, then why are you running a remailer?  Let them telnet to port 25.
Let them do whatever.

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.  

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.

So if I am trusting a remailer net, wouldn't it be nice to know that no one
but the ends can even think about compromising the message?  (Until one of
them does.)  Wouldn't it be nice to know if the ends were being shadowed?

--

As for signing intra-net traffic, suppose, at some time in the future, we
agree that we do, in fact, need them.  Will it be easier or harder to
implement then?


>>     A word on remailer keys:  Since pgp uses square-and-multiply for
>> exponentiation, we see that the amount of work needed to sign a message is
>> d(m) * (d(e) + o(e)) where d(m) is the digits of the modulous, d(e) digits
>> of the exponent, and o(e) is the number of ones in e.  (I don't remember
>> the technical term.) Since the public key is small, each of the parts of
>> the private key will be large, BUT, there is no reason to assume that we
>> cannot get lucky, and find an m such that d(e) + o(e) is much smaller than
>> expected, (d(m) * 3/2, roughly) thus greatly reducing the system demand of
>> the remailer.  In fact, it might be possible to move to 768-bit keys for
>> those that have kept their sizes down in the past.  If pgp handles each
>> prime separately, we look for a double-lucky modulous.  (And a source of
>> random numbers that does not involve striking keys!)
>
>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% ;)


>I'm sorry to have been so negative, 

Not at all.  We're not talking about anything as important as unix vs
windows.  You must be a better person than I.  I usually love shooting down
lame-brain ideas.  ;-)


>                                   but this message is part of a long
>tradition advocating putting more responsibility into the remailer net.
>I strongly feel that better solutions put power into the users' hands.
>I oppose centralized solutions.
>
>Hal

See below.  I mean above.  I mean below:.  This is not, IMHO, a centralized
solution, as I see it.  As I see it, this is a _minimal_ solution to the
problem that today, our net is laughably easy to crack.  I assume that
anyone that wants to spoof will have a reason to do so.  I assume that if
the NSA/FBI/CIA/DEA/DIA/ATF wants to trace a message, they will bring the
full power of their systems to bear, including reading this list.

Anyone else?  Tim's usually pretty good at panning me. :-P  :-)


Nathan

---
Cypherpunk's precausions today look hopelessly paranoid.  Until you
consider that their precausions from yesterday are now considered
hopelessly quaint.
---

"PGP?"                        "ITAR!"                          "Oh, RKBA!"


                   |--------------------------------------------------+
  ----------------- 14712B4D 1994/12/26 Nathan H. Zook <nzook@bga.com> )
 |44B3D866 3D551E2E ---------------------------------------------------
 |F89222A6 338CDE24/ |
  -----------------