[freehaven-dev] freehaven broadcast channels

[dmolnar <dmolnar@hcs.harvard.edu>]

This message outlines 
	1) what freehaven requires from a broadcast channel
	2) what resources a servnet node has available
	3) what adversaries might exist
		3a) their powers (possible motivations)
		3b) classifications 

I'm writing this to be shot full of holes. So please do so. The reason 
I am doing this is that I want to be sure that I can match these very
pretty graph algorithms seen in papers with the rather unpretty real world
freehaven. 


1) BROADCAST CHANNEL USES AND REQUIREMENTS

A servnet node in freehaven uses a broadcast channel to send 
	a) file reconstruction requests
	b) trust update messages (?)
	c) key refresh notices
	d) key revocation notices
	e) anything else I forgot

This gives us the following requirements (partial list - bang on this!) :
(if there are more standard names for these that you know, yell) 

	* Coverage. 
		Every message sent via the broadcast channel should reach
		every single servnet node known to the sender, with 
		high probability. (how do we handle nodes which died 
		forever after we sent the message but before receiving?)


	* Authenticity. 
		If a message sent via the broadcast channel is altered
		in transit, this alteration can be detected by the
		recipient (and possibly everyone else as well).

	* Every node receives the same message.
		Do we need that 
		Every node knows that every other node has the same
		message		
		????

	* Termination Awareness
		Two kinds :
		1) The node sending the broadcast is aware when every
		node on the network receives the message (either by
		return receipts or some other means). 
		
		2) Every node on the network is aware when a broadcast
		has reached everyone. 

		We want termination awareness so we can tell if a 
		broadcast has timed out or not. Note that these two
		seem to be different concepts. I'm sure we need 1),
		I am not sure we need 2) ??
		
	* Low computational complexity.

		Preparing a message to be sent should require as little
		computing power as possible. Each node passing along
		a message should require little or no computing power
		to process the message. 

		This requirement may have the "just in time" property
		as a sub-requirement. Speaking of which, we could
		get a "just in time" encryption system by establishing
		symmetric keys with everyone at one point, and then
		refreshing infrequently.
		Symmetric crypto tends to be lots lots faster than
		the public-key stuff, so this could be a win.
		Separate message on that later. 

	* Low communication complexity.
			
		A broadcast should require as few total messages as
		possible. We also want as few messages going through
		each node as possible; "bottlenecks" which handle 
		a disproportionate share of the traffic are avoided.
		
		or do we want to tailor it to the bandwidth each node has?


2) SERVNET NODE RESOURCES

A servnet node in freehaven is assumed to have for the purposes of this
discussion
	a) the ID and public key of every other servnet node
	b) a reply block or other means of reaching that node via 
	a mix-net. This mix-net may or may not be timely, may or 
	may not be reliable. 
	c) enough storage space and computing power to execute some
	kind of routing algorithm. 
	d) enough smarts to choose to execute or not execute routing
	instructions on a message passing through the servnet node.

NOTE : This means in some sense, we can think of the servnet as a graph
in which every node is connected to every other node. The connections are
provided by the reply blocks.
 It'd be easier to draw this, but if we let X be a node, and say every *
is a node, then we can think of the servnet as a "network" which looks
like this :

           ----------
         /           \
	X ---- * ---- *
 	|\    |      / |
	|   \ | /      |
	* ---- * -----*
         \           /
          ----------- 

with the ---- representing a means of contact or "link." 
This picture actually is not quite true, since some of those edges
may be the same, depending on whether two nodes have the same reply 
block for the third node. 

The problem is that not all of those links are reliable. Another
problem is that not all of the node *s may be reliable. Some portion
of either or both may be actively malicious. 

So suppose you are node X and you want to do a broadcast. Cool. 
You could send the message directly to every other * in the servnet,
and then ask them to send you a reply. Unfortunately, this forces you
and only you to send many many messages. 

It also gives the nodes no assurance that they all have the same message
(but I don't think we need that for file reconstruction, and it's not
quite clear to me that we need it for trust updates either??)

It would be better if you could pick some subset of nodes and edges and
ask some of the other nodes to pretty please do your work for you. 
That is, ask them to forward the message on to other people. 
The trick seems to be constructing such subsets which are resistant
to evil nodes. or adversaries which can actively corrupt nodes. or 
edges winking out of existence. things like that. 

Speaking of which, 

3) ADVERSARIES

A) TYPES OF ADVERSARIES
	
	EDGE ADVERSARIES :
				These adversaries attack the communication
				links between nodes. That is, they attack
				mix-nets or just cut off nodes from the
				outside world. 

	NODE ADVERSARIES :
				These adversaries try to take control of
				the node itself. Communication to and
				from other nodes gets through, but is 
				no longer following protocol. 

	COMBINED ADVERSARY :	does all of the above. 

Note that the difference between a passive edge adversary and a passive
node adversary is that the node adversary has access to the decrypted
contents of messages. The edge adversary just sees lots of stuff going by. 
An active adversary could be an "active edge adversary" who 
does things like change messages and reorder packets, or an "active node
adversary" which takes outside messages and then fails to follow protocol. 

We also need to make precise the distinction between 

	a) edge adversaries which can only deny service or reorder
	messages passing through an edge (say they are between the node
	and the mix-net)
	
	b) edge adversaries which can break the anonymity on the edge
	and actually figure out who's who! 


ADVERSARY MOTIVATIONS/OBJECTIVES

(I need help here) 

	* Destroy trust in the freehaven system 
	* Steal somebody else's trust for your own
	* Falsely accuse somebody else and get away with it
	* Track a particular piece of data to its source
	* Track a particular broadcast to its source
	* Determine the True Name of some node it does not control
	* Find a node's private key
	* Take down a node (denial of service)
	* Slow down a node, such that it loses trust but not enough
	to be quite suspicious (selective denial of service)

what else? 


Thanks, 
-David