Re: End to end Mixminion issues, with proposed solutions

[Roger Dingledine <arma@mit.edu>]

I have a few statements interspersed in the text below, but the bulk
of my response is here. Let me know if it's cryptic, and I'll try to
explain better.

The problem is that in some scenarios we treat these messages as Russian
dolls, but we're going to have to saw the outer dolls in half to be sure
of fitting the inner ones.

Imagine that Alice sends a plaintext message with 28k bytes of text in its
payload, to bob@nymserver. Then Bob delivers a reply block to nymserver.
The nymserver takes payload_A, and creates a new payload_B which is
"Mix Reply", two bytes of size, payload_A. So it's 28k+11 bytes.

Can we get around this by declaring that text forward messages must have
the last 11 bytes of payload be 0? This would give us more redundancy too,
to be sure it's a text message. Then the nymserver would simply drop the
last 11 bytes of the payload.

A binary message already has 2 bytes of size, and it won't change when
nymserver prepends "Mix Reply" to it. So binary forwards can't use
the last 9 characters of the payload --- and they should be random,
because we're trying to plausibly look like we could have come from a
nymserver ourselves.

Yet it's not possible to chain nymservers (by which I mean Bob has nyms
bob1 and bob2, and sends reply blocks such that Alice's mail queues at
bob1, gets transferred to bob2, and then goes to Bob). We can't do this
because the payload must grow by 11 characters (mix reply plus two more
for length, because the old payload is encrypted by K so we can't see
the old length) at each point in the chain.

Can we produce a design where length does not increase when a message
traverses a nymserver? Maybe; I'm still working on that direction. But
in the meantime, we don't need to --- if we add fragmentation to the
protocol, as Len was arguing this evening.

We must also address the problem of: Alice wants to anonymously deliver
a 40k payload to Bob. Bob should not require any special software. Thus
Alice's software needs to split it in a way that the exit module can
recgonize and recombine the messages.

If we add a new delivery type (eg, SMTPFRAG), then senders can specify
that this payload is #a of n. If we're going to allow replies to be split
as well, then we want to keep the a,n values in the payload rather than
the header.

Should we support multiple algorithms for splitting, e.g. a k-of-n
scheme as well? We would need to standardize on a k/n ratio so senders
don't leave signatures on their multi-part messages, and we'd still be
dividing the anonymity sets.

To solve this, we could specify only one possible algorithm: a n/2-of-n
system using some common tornado/erasure code/IDA.

When the nymserver delivers messages to the recipient, it needs an
algorithm of its own to "pack" messages together. So if Bob gets four
5k messages to his nym, a single reply block should be sufficient to
fetch all of them. When it's packing the messages, should it pack them
into a blob and then use the k-of-n algorithm to reliably deliver the
blob to Bob? Is that redundantly redundant or just fine?

More thought required. But I should get these ideas out first.

Thanks,
--Roger


On Fri, Sep 20, 2002 at 04:20:32AM -0400, Nick Mathewson wrote:
> And here's the design.  It's got some weaknesses, but I think it's a
> good start.  Please let me know what's wrong, and how to fix it.
> 
>  _META_
>   A) All exit types have their Routing-Info field begin with a 20-byte
>      Tag.  In all cases, the contents of a Tag field should be a 20-byte
>      random number, with MSB=0.  (I.e., 0 <= Tag < 2**(159): Tag is really

You don't mean random number here. You mean random-looking number. But
we can get away for now with not specifying "random to who?", because
I think intuitively we all get it.

Setting the MSB to 0 is a standard trick, eg onion routing does it. So
I think it's reasonable. ("Nobody ever got fired for requiring MSB 0.")

>   C) For EFWD messages, the sender generates a 128-bit temporary key K at
>      random, and RSA-OAEP encrypts it with the recipient's public key.
>      If the encrypted key EK has its MSB=1, the sender generates a new
>      key and tries again.  Otherwise, the sender uses the first 20
>      bytes of EK as the Tag.  The payload contains: The remaining bytes
>      of EK, followed by the LIONESS encryption (with K) of:
>                    2 size bytes, 
>                    the message
>                    Random padding up to 28K.
> 
>      {{This is the iffy part.  I know that RSA-encrypted data is
>      distinguishable from random numbers, since the encrypted message
>      is never greater than the public key modulus.  I _think_ that
>      discarding results with MSB=1 forces the encrypted data to 'look 
>      random', but I've really got no clue.
> 
>      Does this work at all?  How well?  If this doesn't work, what might?

I think it will do, yes.

>   SMTP DELIVERY:
>   E) If the message is to be delivered over a text medium such as
>      SMTP, the exit node checks whether the message is contains only
>      'printing' characters (hex 07..0D, 20..FF), and 
>      ends with a string of 00 characters.  If so, the exit node strips
>      the 00 characters at the end, and delivers the message as-is.
>  
>      Otherwise, the exit node sends the entire payload, base-64
>      encoded.
> 
>      In either case, the exit node includes the tag as part of the
>      SMTP body, base-64 encoded.

Putting it in the SMTP headers isn't good enough?

>      {This way, senders can send text-only FWD messages to 
>      recipients without special software.  The problem is, I think
>      this fails in the presence of UTF-8 and friends.  Is this okay?}

I know nothing about UTF-8, so I can't comment here.

>     K) If the recipient has a public key of size N, she appends the

(prepends 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.
> 
>     L) The message is either unencrypted data, or junk.
> 
> Open questions:
>  1) We should figure out compression at some point.

Did you want to do compression between mixes, or also to the endpoints?

>  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?
> 
> 
> Part II: WHAT'S AN ADDRESS?
> 
> Another end-to-end issue is: how can clients specify addresses?  
> 
> To send a forward message, or to generate a SURB, the program must know:
>     1) The final routing type.
>     2) The non-Tag portion of the routing info.
>     3) If the sender wants to send a EFWD message, the recipient's
>        public key.
>     4) If the routing type depends on a particular node (as does
>        MBOX), a valid sever descriptor for that node.
> 
> If the sender knows (3) and (4), we're okay.  But -- as George asks --
> how is a sender supposed to find them out?  If the sender just gets them
> off a keyserver, an observer (or the keyserver) can tell who wants to
> talk to whom.  
> 
> Possible solution: just use the Mix system to query the keyserver! The
> would-be recipient uses Minion to sent the keyserver a list of users and
> a SURB to receive the reply.  (Alternatively, just send a non-encrypted
> anonymous mail to the user and ask for his key.)

I think either of these will work.