[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Rewrite the first half of the design section.
Update of /home/freehaven/cvsroot/doc/pynchon-gate
In directory moria.mit.edu:/tmp/cvs-serv7782
Modified Files:
pynchon.bib pynchon.tex
Log Message:
Rewrite the first half of the design section.
Index: pynchon.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/pynchon-gate/pynchon.bib,v
retrieving revision 1.17
retrieving revision 1.18
diff -u -d -r1.17 -r1.18
--- pynchon.bib 17 Sep 2004 21:14:55 -0000 1.17
+++ pynchon.bib 17 Sep 2004 22:11:31 -0000 1.18
@@ -557,3 +557,4 @@
www_section = traffic,
www_pdf_url = "http://freehaven.net/doc/e2e-traffic/e2e-traffic.pdf";,
}
+
Index: pynchon.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/pynchon-gate/pynchon.tex,v
retrieving revision 1.38
retrieving revision 1.39
diff -u -d -r1.38 -r1.39
--- pynchon.tex 17 Sep 2004 20:37:53 -0000 1.38
+++ pynchon.tex 17 Sep 2004 22:11:31 -0000 1.39
@@ -138,7 +138,7 @@
based nym servers.) Section~\ref{sec:design} presents the Pynchon Gate in
more detail, describing its organization, design rationales, and network
formats. We describe our simple distributed trust PIR protocol in
-subsection~\ref{subsec:client-design}. In section~\label{sec:security} we
+subsection~\ref{subsec:client-design}. In section~\ref{sec:security} we
analyze security, and in section~\ref{sec:performance} we discuss
optimizations and compare our performance to that of other pseudonymous
message systems.) We close with an evaluation of our success in
@@ -323,6 +323,8 @@
An attacker may send messages intended for nym Alice to nym Bob instead,
to confirm that Alice and Bob are the same nym holder~\cite{gd-thesis}.
+% Also: social engineering; traffic analysis; leave/join attacks...
+
\subsubsection{Usage pattern and intersection attacks.}
An attacker may analyze network usage and anonymity set members over time
@@ -404,37 +406,40 @@
% XXXX write stuff here
\subsection{Overview and Rationale}
-The Pynchon Gate is a network of servers that provide anonymous message
-retrieval capabilities. The servers receive messages for many different
+The Pynchon Gate is a group of servers that provide anonymous message
+retrieval capabilities. A nym server receives messages for different
pseudonym accounts via email\footnote{The servers could also receive
messages through any suitable medium for message transfer, such as
-``instant message'' systems~\cite{rfc-2779}. Note that there must exist a
-suitable forward anonymity protocol to allow the nym holder to communicate
+``instant message'' systems~\cite{rfc-2779}. We require a
+forward anonymity protocol to allow the nym holder to communicate
with the nym server, so at a minimum the nym server must be able to
receive email in addition to any optional support for other protocols.
Future developments in forward anonymity protocols may alleviate this
reliance on email. In our system, the nym server may communicate directly
-with Mixminion nodes via the direct communication mechanism in Mixminion.}
-and pass these messages to each independently-operated distributor node in
-the network. Through the use of a client which can communicate with the
-distributor nodes, the owner of a given pseudonym is able to make a series
-of requests from several distributor nodes, enabling her to receive her
-message without the individual nodes determining the identity of the
+with Mixminion nodes via the direct communication mechanism in Mixminion.}.
+Once every ``cycle'' (say, 24 hours), the nym server passes these messages to
+a collator, which
+batches them into an indexed ``bucket pool,'' and
+and passes these pools to each independently operated distributor node in
+the network. Pseudonym owners then make a series
+of requests to $k$ chosen distributor nodes, enabling her to receive her
+messages without the individual distributors determining the identity of the
pseudonym being requested. The protocol used is resistant to collusion:
-even if there are $(k-1)$ nodes operated by the adversary the adversary
-cannot learn the requested pseudonym.
+even if the adversary controls $(k-1)$ of the chosen distributors,
+the adversary
+cannot link the user to her pseudonyms.
-By using a PIR-based message retrieval system we retain the convenience,
+This distributed-trust PIR-based message retrieval system lets us keep the
+convenience,
reliability, and security of the ``send everything everywhere'' method,
while bringing the system back into the realm of feasibility for users
-with limited resources. The information theory-based PIR primitive allows
-us to avoid the use of cryptography wherever possible. A basic analysis of
-the security properties of PIR is trivial in comparison to many
-cryptographic primitives.
+with limited resources.
+%The information theory-based PIR primitive allows
+%us to avoid the use of cryptography wherever possible. A basic analysis of
+%the security properties of PIR is trivial in comparison to many
+%cryptographic primitives.
-The Pynchon Gate consists of a number of logical components, some of which
-may or may not coexist on the same network device or as part of the same
-application.
+We discuss the components of the Pynchon Gate architecture below.
\begin{figure}
\begin{center}
@@ -445,10 +450,9 @@
\end{center}
\end{figure}
-
\subsection{The Nym Server}
-The public-facing side of The Pynchon Gate consists a nym server which
+The public-facing side of The Pynchon Gate consists of a nym server that
sends and receives pseudonymous email. The nym server itself provides no
sender anonymity; rather, it relies on existing mix
networks~\cite{mixminion,mixmaster-spec} for forward message anonymity.
@@ -456,74 +460,111 @@
messages for the nym owners at their specified email addresses.
Nym servers manage email accounts for pseudonyms (\emph{nym accounts}).
-For each nym holder (recipient), the nym server stores a \emph{long-term
-public key,} shared between the nym server and the nym owner for use in
-encrypting and authenticating control messages related to the nym email
-address. Similarly, nym server stores a \emph{short-term shared secret}
-associated with each account, used to encrypt messages to the nym owner.
-These keys are created at account creation time. The shared secret can be
+For each pseudonym, the nym server stores a \emph{long-term
+public key,} used by the nym holder to
+encrypt and authenticate outgoing email and administrative messages.
+Similarly, nym server stores a \emph{short-term shared secret}
+associated with each account, used to encrypt messages to the nym holder.
+These keys are created at account creation time; the shared secret can be
reset by the nym holder after creation.
The shared secret is updated every cycle, such that, if $S[i]$ is the shared
secret in cycle $i$, then $S[i+1] = H(S[i]|\mbox{\tt "NEXT CYCLE"})$, where
-$|$ denotes concatenation.
-
-From each $S[i]$, the nymserver derives a set of sub-secrets for individual
-messages received that cycle. The $j$'th sub-secret on day i is
+$H(\cdot)$ is a cryptographic hash and
+$|$ denotes concatenation. From each $S[i]$, the nymserver derives a set of
+sub-secrets for individual messages received that cycle. The $j$'th
+sub-secret on day i is
$\SUBKEY(j+1,i) = H(\SUBKEY(j,i) | \mbox{\tt "NEXT SECRET"})$,
with
- $\SUBKEY(0,i) = H(S[i] | \mbox{\tt "NEXT SECRET"})$
+ $\SUBKEY(0,i) = H(S[i] | \mbox{\tt "NEXT SECRET"})$.
-We use a separate chain of keys for each cycle so that it is easier for a
-user to resynchronize after missing a few cycles.
+Once it no longer needs a shared secret or a given subkey, the nym server
+drops it immediately, to limit the impact of key compromise (at the nym
+server or at the client) and help achieve forward security. We use a
+separate chain of keys for each cycle so that it is easier for a user to
+resynchronize after missing a few cycles.
-Messages sent from the nym owner to the nym server include a simple MAC to
-authenticate them; they are encrypted at the anonymous mail forwarding
-system layer. Messages sent from the nym server to the nym owner are
-addressed at the collator to an opaque id which remains unchanged for the
-nym. The actual messages include the iteration number of the dynamic key
-in the clear, and the messages for the nym user are encrypted and MAC'd
-using that iteration of the dynamic key:
-$\UserID{}[i] = H(S[i] | \mbox{\tt "USER ID"})$
+These subkeys are used to encrypt and identify the messages received on day
+$i$. When the $j$'th message for the nym is received, the nym server
+compresses it, encrypts it with the symmetric key
+$H(\SUBKEY(j,i) | \mbox{\tt "KEY"})$, and prefixes it with the opaque identifier
+$H(\SUBKEY(j,i) | \mbox{\tt "ID"})$. By deriving the message keys and
+identifiers in this way, we allow users to store keys and identifiers for
+pending messages without risking exposure of messages encrypted in the same
+cycle.
-Dynamic key rotation allows us to achieve forward secrecy. Without dynamic
-key rotation it would be trivial for an attacker to archive all data sent
-to distributors, and the at some later time obtain the nym's collator
-address and key from the nym server though an active attack on those
-components. The attacker would then be able to read all messages that nym
-has ever received.
+Finally, the nymserver also generates an different independent identifier for
+each user, every cycle: $\UserID{}[i] = H(S[i] | \mbox{\tt "USER ID"})$.
-In the interest of retaining little information for an attacker,
-implementations should discard old secrets \emph{as soon as they are no
-longer needed.} Thus, at the start of each cycle i, a nymserver should
-derive $S[i+1]$, $\UserID{}[i]$, and $\SUBKEY(0,i)$, and immediately discard
-$S[i]$.
-After using each $\SUBKEY(j,i)$, the nymserver should calculate $\SUBKEY(j+1,i)$
-and discard $\SUBKEY(j,i)$. After each cycle, the nymserver should discard
-the last $\SUBKEY(j,i)$, and $\UserID{}[i]$.
+%Messages sent from the nym server to the nym owner are
+%addressed at the collator to an opaque id which remains unchanged for the
+%nym. The actual messages include the iteration number of the dynamic key
+%in the clear, and the messages for the nym user are encrypted and MAC'd
+%using that iteration of the dynamic key:
+%$\UserID{}[i] = H(S[i] | \mbox{\tt "USER ID"})$
+
+%Dynamic key rotation allows us to achieve forward secrecy. Without dynamic
+%key rotation it would be trivial for an attacker to archive all data sent
+%to distributors, and the at some later time obtain the nym's collator
+%address and key from the nym server though an active attack on those
+%components. The attacker would then be able to read all messages that nym
+%has ever received.
+
+%In the interest of retaining little information for an attacker,
+%implementations should discard old secrets \emph{as soon as they are no
+%longer needed.} Thus, at the start of each cycle i, a nymserver should
+%derive $S[i+1]$, $\UserID{}[i]$, and $\SUBKEY(0,i)$, and immediately discard
+%$S[i]$.
+%After using each $\SUBKEY(j,i)$, the nymserver should calculate $\SUBKEY(j+1,i)$
+%and discard $\SUBKEY(j,i)$. After each cycle, the nymserver should discard
+%the last $\SUBKEY(j,i)$, and $\UserID{}[i]$.
\subsection{The Collator}
-Messages for nym owners are passed to the collator component.\footnote{The
-collator component typically resides on the same physical server as the
-nym server component.} The collator component organizes all previously
-unretrieved messages into a three-level tree structure, with messages
-sorted by publicly viewable identifiers derived from the dynamic shared
-secrets. Nodes in the tree are organized into fixed-size \emph{buckets}.
-The collator then publishes metadata (in the form of a signed meta-index)
-about the tree as a whole in a widely available manner.
+At the end of each cycle, the nym server passes messages to the {\it
+collator}, which typically resides on the same physical server. The
+collator organizes all previously unretrieved messages into a three-level
+structure, consisting of a {\it meta-index}, a set of fixed-size {\it index
+buckets}, and a set of fixed-size {\it message buckets}.
-% XXXX Overflow? Pending messages? ACK and ERR messages? Do we discuss
-% this here, or later, after explaining the system?
+Each user's messages are stored in a different set of message buckets,
+ordered by $\UserID$. The index buckets contain, for each $\UserID$ (in
+order), the first message bucket containing that user's messages, and a
+digest of that bucket. Finally, the meta-index lists, for each index bucket,
+the first and last $\UserID$ in that bucket, and a digest of that bucket.
+(See figure XXXX
+%XXXXX figure 2!!
+.)
+The index buckets and the message buckets together comprise the cycle's
+"bucket pool." To ensure integrity, each bucket contains a hash of the
+next bucket in the pool.
-\subsection{The Distributor Nodes}
+The metaindex is signed with the collator's private key, along with the index
+of the cycle to which it applies.
-The entire set of buckets is retrieved from the collator by multiple
-independently-operated \emph{distributor nodes}.\footnote{This should be
-accomplished by using a bandwidth-sparing protocol such as
-BitTorrent~\cite{bittorrent}.} Distributors append to each bucket the path
-from that bucket to the hash tree root. These distributors communicate to
-the client application using the \emph{Pynchon Gate PIR Protocol}.
+To prevent an attacker from flooding a nym and observing which user receives
+a large volume of traffic, each nym has a maximum number of message buckets
+that may be filled in a given cycle. If there are more pending messages than
+will fit in the nym's buckets, the collator defers some messages for a later
+cycle\footnote{As an extension to save bandwidth and prevent denial of
+ service attacks, the
+ nym server can build a special ``summary message'' containing the headers of
+ pending emails, and their opaque identifiers, and include this message in
+ the user's message bucket. The user can then send a signed control message
+ to the nym server requesting that unwanted emails be deleted and desired
+ ones given priority.}. Because the encrypted messages are prefixed with
+$H(\SUBKEY(j,i) | \mbox{\tt "ID"})$, the user can tell which key to use for
+messages that are delivered out of order, or in different cycles.
+
+\subsection{The Distributor Nodes}
+Once the collator is done, it relays the signed meta-index, and the entire
+bucket pool, to a set of
+independently operated \emph{distributor nodes}. (This data should be
+transmitted using a bandwidth-sparing protocol such as
+BitTorrent~\cite{bittorrent}, so that the collator doesn't need to transmit
+the entire set of buckets to each distributor individually.)
+Client applications retrieve these buckets using the \emph{Pynchon Gate PIR
+ Protocol}.
\subsection{The Pynchon Gate PIR Protocol}
\label{subsec:client-design}
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/