Notes from PET2003 Mixminion BOF

[nickm@alum.mit.edu]

Notes from Mixminion BOF on 26 March 2003.

Once again, because it was me taking the notes, this summary is pretty
fragmentary.  Most ideas appear uncredited; please let me know if you
should go into the acks for something.  What ideas I do attribute may
be misquoted -- let me know.

==== 1) RFCs

We discussed whether we wanted to eventually turn our spec into and
RFC, informational or otherwise.  We concluded that we shouldn't --
that it would hamper more than help.  (Quote: "It's called a Request
For Comments, but it's really for when you're past that stage.")

Perhaps someday; not for a long time.  George said that he introduced
the goal of being an RFC in order to remind people of the importance
of real specification, and that we seem to be taking that goal
seriously enough for now.

==== 2) Implementation directions

I asked people about requirements for the next version or two.

- For on-server statistics: George wanted average batch size.  Claudia
  Diaz believes she may be able to derive an anonymity measure.  I
  still need to ask Len for the list of stats he wants to gather.

- We had a discussion about whether insecure operating modes should
  be eventually removed.  (Insecure operating modes include: Batch
  inteval=1 minute, Batching algorithm=timed, log severity: trace.)

  The conclusion was: yes, mostly.  Everything not essential to
  debugging should go away before 1.0.  Everything that we need to
  keep in should cause an "insecure" flag to get set in the server
  descriptor.

- Peter reminded me that self->self delivery should be treated as a
  special case.

- Somebody (Peter?) reminded me that clients should lock their queue
  when flushing it.  Others pointed out that we call a client queue a
  pool, which is confusing to some.  (Nobody claimed that the client
  queue should do real dynamic pooling.)  It was suggested that the
  client pool have a "trickle" option, to send only a maximum number
  of pending messages.

==== 3) Spec issues

We then moved on to issues that effect the current specification.

- We need to pick a pooling identity.  The paper by Claudia and
  Andrei suggests that Cottrell is good, but that we can do a little
  better.  I'm supposed to mail them for more information.

- Generating dummy messages.  Against some adversaries, dummy
  messages do good, so we're adding them in.  As a first cut, we're
  going to have nodes add dummies to the outgoing batch every mix
  interval, with a geometric distribution, with 5 hops, with the
  sender as the last hop.

  Some people are enthusiastic about adding to the pool instead.  I
  can't fully explain the relative advantages/disadvantages here.

  George pointed out later that self->self dummies enable nodes to
  detect whether their messages are getting through, and thus detect
  flushing attacks and so on.  He's going to do more research and
  maybe write a paper.

- Path selection.  At the time of the discussion, George said that
  under some assumptions (few nodes compromised), we should choose
  nodes with replacement, or by a random walk.  (Currently, we choose
  without replacement.)

- There isn't a need to drop man-in-the-middle protection; the spec
  was incorrect.  (Ignore this if you hadn't heard about the issue
  the first time.)

- Denial-of-service multipliers.  At the cost of a single SSL
  connection, sending 32*N kilobytes, I can force a node to do N RSA
  decrypts.  This creates a denial-of-service multiplier: at little
  cost, a little client can DOS a big server.

  The protocol people have apparently thought about this field a lot.
  We should go to them for more info.

  (The goal here is not to make DOS impossible, but to make a would-be
  DOS-er spend resources of a similar order of magnitude as the system
  they want to DOS.)

- We're going to change our 1024-bit packet RSA keys into 2048-bit
  keys.  In order to do this, we'll do a packing approach I suggested:

  Currently, to add a new chunk of information Inf to a partial header
  H, you RSA-encrypt Inf, and prepend it to the AES-encrypted header.
  In the new system, you RSA-encrypt [Inf-plus-as-much-of-the-header-
  as-fits], then AES-encrypt the rest of the header.  This lets us fit
  more hops per header even when increasing the key size.

- George suspects that we can change all of our 20-byte hashes into
  10-byte hashes (since we don't need collision resistance); and that
  we can drop OAEP padding (since there's a hash of the rest of the
  header in the RSA-encrypted section).  If this is so, it would cut
  the number of header bytes needed per hop from ~100 to ~40.  This
  would let us make SURBs shorter, and fit more per packet.

  I suspect George is right.  But we don't get much from shortening
  SURBs: any anonymity I lose by sending 4 packets worth of SURBs
  rather than 2 is probably outweighed by what we lose by receiving
  56 reply packets.

  Even if the reasoning is correct, some people were worried about
  "looking bad": People intuitively fear unpadded RSA, and maybe we
  want to look conservative.

- For our spec, all pseudocode sections should be mirrored in English.

- We're fine with having our spec consist of many files.

- We're dropping SSL sessions from the spec, and here's why:

    1) They're hard to implement.  They account for a huge amount of
       code in George's student's C implementation; I've avoided them
       in my code out of raw terror.
    2) There is not much benefit.  Sessions are only a win for
       server->server connections, but server->server connections are
       a small fraction (1/path-length) of the total number of
       connections.  Therefore, we can't save much with them.

- We should force renegotiation every fifteen minutes, as a first
  approximation.  (We care about session key lifetime, not about
  total bytes encrypted.)

- We should have only one server->server connection between two
  servers at a time.

- MMTP should have a "REJECT" reply that isn't distinguishable by an
  eavesdropper. 

- MMTP should become asynchronous: the sender shouldn't need to wait
  for an ack before sending more data.  There should, however, be a
  maximum number of outstanding acks.  (The INN news software has
  good load throttling; we should examine their docs.)

==== 5) Nymservers

- I think we should store messages, not SURBs, but this is
  contraversial.

- George thinks there should be introduction servers; he can email
  the list with more info: I can't do the idea justice.

- Nymservers probably require FEC; I should re-send the old freehaven
  mail outlining patent problems to the list.

==== 6) Rotation

- We talked about the variables involved in key rotation, but didn't
  come up with a real solution.

  The variables are:
       Rotation interval
       Key lifetime after rotation ("slop")
       How long clients expect their messages to stay in the network.

  We decided to start with reasonable guesses, and hope for more research.

- We talked about the storage problem: If a server's 10mbit connection
  is saturated, it gets 2.7 million packets per day.  If we store
  20-byte hashes, that's 56MB per day.  If we store 10-byte hashes
  (because we don't care about collision resistance), that's 28MB per
  day.

  George mentioned Bloom (_not_ Blum!) filters:  If you accept a
  one-in-N probability of false collision, there's a nice packed
  representation that uses log2(N) bits per hash.  That could get us
  down to ~7MB per day if we're willing to erroneously reject one
  message in a million.  (For one-in-a-billion, it's 17MB per day.)

  Lucky thinks that Valicert has a solution; he's looking into it.

==== 7) Other notes:

- There should be a field in the server descriptor for the
  administrator's GPG fingerprint.

- What should path-selection do if the network is non-freeroute?
  George thinks it's fine to do a random walk; first ignoring any node
  that can't route to >N% of the other nodes. (50% is conservative.)
  This means that clients won't use cascades by default, which is
  fine by me.