Re: End to end Mixminion issues, with proposed solutions

[Nick Mathewson <nickm@alum.mit.edu>]

Hi, George!

On Tue, 2002-09-24 at 13:41, George Danezis wrote:
 [...]
> On 20 Sep 2002, Nick Mathewson wrote:
 [...]
> >  SENDER:
> >   B) For FWD messages, the sender generates a 159-bit random number for
> >      the Tag.  For a text message, the sender pads the payload with 00
> >      bytes.  For a binary message, the sender sends 2 size bytes,
> >      the payload, and random padding up to 28K.
> 
> There is a problem here: I do not see how the TAG can be encrypted if the
> key of the final recipient is not known. Do we assume that the last hop to
> process the message sends only the TAG and the BODY, to the final
> recipient? I can see how this can be done using the SMTP delivery type but
> we have not specified a way of delivering such messages using the
> TLS/TCP/IP transport to clients that listen to for messages.

Ah, I see.  I think we have a misunderstanding.

A recipient Alice can operate in one of two configurations: She may be
running her own Mixminion server, or not.

CASE I. Alice is _not_ running her own server.  She may have a public
key to receive messages.

In this case, if Bob wants to send an encrypted forward message to
Alice, he sends it through some mixes M1..M5.  He tells M5 to use the
SMTP routing type, which delivers a tag and message to Alice as
described in the EFWD mode below.

CASE II: Alice _is_ running her own server.  In this case, Bob picks
some mixes M1..M5, and send the message M1->M2->M3->M4->M5->Alice.  He
tells M5 to use the 'FWD/IPV4' routing type to deliver an entire packet
to Alice's server, just as if it were a regular Mix node.  He tells
Alice's server to deliver locally using the 'MBOX' routing type.  

In this case, there is no need to use the 'EFWD' mode: The entire packet
is encrypted when it goes over the wire to Alice, and Alice's server
decrypts it like a regular Mix node.
====
In other words, 'EFWD' is only useful when Bob wants message
confidentiality, and Alice has a public key that Bob knows, but Alice is
_not_ running her own server.  If Alice _is_ running her own server, she
gets confidentiality on all incoming messages.  If Alice is not running
her own server, and Bob does not have a public key for her, he has no
choice but to use the 'FWD' mode and send in the clear.

Please let me know if this is still unclear.


 [...]
> >     K) If the recipient has a public key of size N, she appends the
> >        tag to the first N-20 bytes of the payload, and tries to
> >        decrypt the result.  (If the OAEP padding doesn't check, the
> >        message is junk, or was not encrypted: go to step L.)  The
> >        result is a key; the recipient uses it to decrypt the rest of
> >        the message.
> > 
> 
> I do not really understand that step. Surely is the final recipient has 
> a public key address that the sender knows, it can follow exactly the same 
> procedure as a mix would in order to decrypt the message. Or do you assume 
> that the complete headers have been stripped before the message reaches the 
> final recipient?

This is for the EFWD case, where Alice is not running her own node, and
she has received an encrypted message via SMTP.

=====
I considered and rejected a few other options.  Here's why:

1) Perhaps we could introduce a FWD/SMTP routing type that, instead of
sending Alice the Tag and Body, would send her the entire packet (as if
she were a Mix node), but via SMTP.  I rejected this option because it
would make encrypted messages to non-server-runners ('EFWD' messages) 
distinguishable from all other message types.

2) Perhaps instead of having in-protocol support for encrypted messages
with SMTP delivery, Bob should instead just GPG/PGP-encrypt his message
and send it as a regular message body.  This would allow Alice to
decrypt her messages with GPG, rather than needing software from us.  I
rejected this for two reasons: first, it would make EFWD messages
distinguishable from all other types again.  Second (and more
importantly), different versions of PGP/GPG encrypt files slightly
differently: an adversary could use this fact to partition all EFWD
messages by GPG/PGP version.

3) Perhaps we could simply forbid users who cannot run their own servers
from receiving encrypted messages.  This seems unacceptable: 

 [...]
> > Open questions:
> >  1) We should figure out compression at some point.
> >  2) Likewise for fragments.
> >  3) Likewise for k-of-n and friends.
> >  4) Did I really get indistinguishability for everything but FWD?
> >  5) Will my scary hack really make RSA-encrypted data hard to distinguish
> >     from random numbers?  If not, do we have any other choices?
> > 
> 
> I will go along with Roger's comment on (5). I will have a hard look at 
> (4) in the next week. I think that Issues (1-3) do not concern the basic 
> "transport layer" that mixminion provides and will need to be addressed 
> above the "interface" that mixminion provides. Does anyone think that 
> they are so intrinsically linked to minion transport that they need to be 
> addressed now?
> 
> BTW: I do take Len's comment abou the fact that fragment recomposition 
> would need to happen on the network rather than the edges, but I rather 
> think of it as a network service rather than a basic thing that everyone 
> should do (depending on implementing a particular exit policy). Am I 
> wrong?

I remain agnostic about whether these things are needed, or where they
should go.  I think all of (1-3) should be addressed by version 1.0,
however.  My reason for wanting to tackle them now is this: I want to be
sure that our design can accommodate them without losing other desirable
properties, and the only way I'll be able to gain this confidence is to
actually design them.

(Another reason: Roger has mentioned in conversations that once we
design 1-3, they should not be optional: to prevent an adversary from
partitioning message sets, _all_ messages should use compression, and
_all_ long messages should be broken into fragments similarly.)

I'm going to see if I can come up with a design of my own in the next
couple of days.  If anybody else beats me to it, that would be neat.
This part may be more hand-waving than the part I've written here: I
just want to design enough to assure myself that it's doable.

> > Part II: WHAT'S AN ADDRESS?
 [...]
> Well relying on the anonymity system for a basic operation of the 
> anonymity system seems slightly fragile to me. I would rather have a way 
> of being able to send messages to users without (3) (as described above) 
> to bootstrap the conversation.

Ah!  You want a way to send messages to a user who is running her own
node, but whose node's key you don't know.

Suggestion: anonymous SMTP.

Wait, I think I see your point.  You can't even generate a packet for
Alice's node without knowing Alice's node's key.  We _could_ add the
notion of "unencrypted packet for unknown node, still to be transmitted
via MMTP".  It would allow the penultimate node to read the message, but
an eavesdropper would still be unable to read it.

This may have some value, but I'm not sure how much: we're assuming that
Bob knows the address of Alice's server, but doesn't know the key. 
Where did he get the address in the first place?  Why didn't he get the
key that way as well.

Thus, I still favor Bob requesting address information anonymously from
some kind of address server.  Sure, it has a bootstrapping problem: how
does Bob find the address server's address and key?  I'd suggest that
address servers should be few enough that they can advertise themselves
in the same directory as servers.

-- 
Nick