[freehaven-dev] Mixnet security and Freedom design choices

["Michael J. Freedman" <mfreed@MIT.EDU>]

Adam,

I hope the work up in Montreal has been going well. I'm excited to start 
my internship in about a month. Until then, I'm still actively working on 
the data haven research project here at MIT. It's been going well; 
however, I thought I might try posing a few questions, if you wouldn't 
mind. I'm sure you and the Evil Genius group have considered these 
issues in depth while developing the Freedom Network.

To refresh your memory, our working abstract is the following: 

| The Free Haven Project aims to deploy a system for distributed data 
| storage robust against attempts by powerful adversaries to find and 
| destroy stored data. Free Haven uses a secure mixnet for communication, 
| and it emphasizes distributed, reliable, and anonymous storage over 
| efficient retrieval. Some of the problems Free Haven addresses include 
| providing sufficient accountability without sacrificing anonymity, 
| building trust between servers based entirely on their observed 
| behavior, and providing user interfaces that will make the system easy 
| for end-users.

The project's web page is at  http://freehaven.net/.  Please be aware that
the 
project, papers, and web page are still very pre-alpha.  We recently became
aware of Hannes Federrath's workshop at Berkeley and submitted two 
possible topics -- Free Haven's design, our definition of various types of 
anonymity -- for consideration.

I'm primarily in charge of developing the communications module of Free 
Haven. We've currently been layering communications between different data 
("servnet") servers on a already deployed mixnet, and abstracting this 
layer as being anonymous. While the design is extensible to different types 
of anonymous channels, we're currently using the Mixmaster remailer.

We've been specifying some different concepts of anonymity within our 
system. Given that the pseudonymity of mixnet reply blocks are only 
computationally secure, and reply-blocks are generally persistant in many 
public systems (Mixmaster,), we've begun considering the development of 
our own anonymous communications network.   I guess there are a 
few central aspects desirable in such a channel:

---- Low latency 
---- Resistance to traffic analysis
     (These two goals are somewhat inherently conflicting: 
      Freedom's answer seems to be to use a heartbeat queue.)

---- Delivery robustness 
---- Perfect forward anonymity 
---- Anonymity vs. pseudonymity: the security of each

It's really across the last three issues with which I have some questions 
and would invite some input. 

For delivery robustness, we're considering what to do when a link on a 
supplied reply-block has gone down. A more centralized meeting place 
server has been considered to exchange reply-blocks (a la Napster); 
however, this creates points of failure and degrades fully distributed 
operation.  Another idea includes "garlic routing":  consider the normal
layered encryption used for Chaum mixes ("onion routing", "telescoping
encryption" in Freedom parlance.)   When the top-most layer is 
unencrypted and the contents revealed, the mix-net server finds several
"garlic bulbs" inside, instead of another onion layer.  Each bulb is a viable
path-to-destination (i.e., another "onion")  from that intermediate node, 
herefore providing several routes.  Earlier intermediate nodes would have
no knowledge of these newly exposed paths. Obviously, this complicates 
the actual encryption of the data.

Perfect forward anonymity is akin to perfect forward secrecy, with some 
concept of a "session location" which is valid for a given transaction and 
then untraceable afterwards. With current mixnets, an adversary with 
significant computing resources can eventually computationally decrypt the 
"onion" and determine the proper path (and thus source and destination). 
Admittedly, this is very hard, but we're still worried as we expect/hope lots 
of people will eventually use the system...and their use will anger some
powerful adversaries.  I notice that in your Security Issues and Analysis
white paper that this is mentioned, but other issues are deemed more
important for the vast majority of end-users.  The Free Haven system --
emphasizing the long-term storage of information -- is willing to trade 
availability for anonymity.

The last issue describes the mapping of destination IDs to exact or general 
locations. If a mapping can be derived from the supplied reply-block 
information to an exact IP address (as currently is down with mixnets), 
then we rely on computational security. The alternative is that the 
reply-block/address/ID given only maps to a general location. For 
example, some address only tells the network that the data should be sent 
to some zone A. Several/many servers exist on zone A, some type of random 
walk or broadcast function would be used to send the information to the 
proper one. (We later found that Avi Rubins at AT&T Labs implemented 
something similar to this called "Crowds".) Similarly, we could imagine 
some shared naming scheme across a network where data is sent from 
a server to neighboring nodes whose names are "closer" to the destination 
node's name (similar to an idea of Hamming distance).  Gnutella's 6-degree
of freedom model, or the "small-world" model, might be some approximation 
of this idea.

Generally, all of these ideas are motivated by the desire to increase 
anonymity across the communications nework. In general, we are willing to 
sacrifice speed for the benefit of privacy.  We are concerned that with 
sufficient computation resources (powerful organizations, large 
corporations, perhaps even governments), the security of mixnets can be 
compromised by cracking the "mixed" route and/or performing traffic 
analysis.   For reference, many of these concerns are the same as listed
in your Security Analysis white paper, sect 4.3:  Passive Attacks.

While Freedom and our system have sufficiently different uses and goals
(thus different exposure to risks), they overlap in many of these issues. 
Any input or discussion of these problems that you (or others in the Evil 
Genius group) might be willing to given, and why you've chosen to go 
the path which Freedom has, would be greatly appreciated.  

Anyway, I've been taking care of some of the work visa issues with 
Meredith, and everything appears to be progressing nicely. I look forward 
to being up there in Montreal at the end of the month.

Thanks in advance. Sorry for the length  :)
--mike



---------------------------------
  Michael J Freedman

Mail:  mfreed@mit.edu
Web:     griffen.mit.edu
Phone:    617.225.9381