[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Fixed typesetting issues, expanded related work sect...
Update of /home2/freehaven/cvsroot/doc/pynchon-gate
In directory moria:/tmp/cvs-serv25541
Modified Files:
pynchon.pdf pynchon.tex
Log Message:
Fixed typesetting issues, expanded related work section, clarified active
attack protection mechanism against distributor-based DOS.
Index: pynchon.pdf
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/pynchon-gate/pynchon.pdf,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
Binary files /tmp/cvsAb8Jr1 and /tmp/cvsNquRLY differ
Index: pynchon.tex
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/pynchon-gate/pynchon.tex,v
retrieving revision 1.69
retrieving revision 1.70
diff -u -d -r1.69 -r1.70
--- pynchon.tex 31 Aug 2005 22:06:05 -0000 1.69
+++ pynchon.tex 1 Sep 2005 23:01:25 -0000 1.70
@@ -57,7 +57,7 @@
\author{
\alignauthor Len Sassaman\\
\affaddr{Katholieke Universiteit Leuven}\\
- \email{len.sassaman@xxxxxxxxxxxxxxxx}
+ \email{lsassama@xxxxxxxxxxxxxxxx}
\alignauthor Bram Cohen\\
\affaddr{BitTorrent}\\
\email{bram@xxxxxxxxxxxxxxx}
@@ -149,7 +149,7 @@
\subsubsection{In this paper.}
We begin in Section~\ref{sec:background} with a discussion of related work,
-and an overview of known attacks against existing pseudonymity systems. (To
+and an overview of known attacks against existing pseudo-nymity systems. (To
motivate our work, Subsection~\ref{subsec:disclosure} presents new analysis
on the effectiveness of passive traffic analysis against current reply-block
based nym servers.) Section~\ref{sec:design} presents the Pynchon Gate in
@@ -176,16 +176,21 @@
communicating with whom. Currently deployed designs are based on Chaum's
mix~\cite{chaum-mix} architecture, and include the
Mixmaster~\cite{mixmaster-spec} and Mixminion~\cite{mixminion} anonymous
-remailer networks.\footnote{Other descriptions of the use of PIR in
-preserving recipient anonymity have been independently proposed but not
-deployed~\cite{berthold,cooper}. Independent work by Jim McCoy describes a
-similar architecture to the Pynchon Gate, but does not use an
-information-theoretic primative for preserving privacy~\cite{mccoy}.} It
+remailer networks. It
is trivial to use these systems to {\it send} pseudonymous messages: the
sender can make an anonymous message pseudonymous by signing it with a
public key associated with her pseudonym. Thus, these designs focus on how
to {\it receive} messages sent to a pseudonymous address.
+Other descriptions of the use of PIR in
+preserving recipient anonymity have been independently proposed but not
+deployed. Earlier work by Jim McCoy describes a
+similar architecture to the Pynchon Gate, but does not use an
+information-theoretic primative for preserving privacy~\cite{mccoy}. Independent work by
+Cooper and Birman~\cite{cooper} describes a PIR-based message service for mobile
+computing systems, and Berthold, et al. have presented work~\cite{berthold} which shows that
+simple optimizations to the PIR protocol are possible.
+
\subsubsection{Reply blocks and return addresses.}
In 1981, Chaum~\cite{chaum-mix} described a method of using \emph{return
addresses}
@@ -209,7 +214,7 @@
remailers~\cite{hal-remailer}), such as {\tt
alpha.c2.net}~\cite{alpha-faq} and {\tt
nym.alias.net}~\cite{nym-alias-net}, implement a central
-reply-block repository that allowed pseudonym holders to receive messages
+reply-block repository that allowed the pseudonym holders to receive messages
delivered to a email address. Unfortunately, Type I remailers
allow multiple uses of their reply blocks, which are vulnerable to replay and
flooding attacks as discussed in~\cite{remailer-attacks,tcmay}.
@@ -290,7 +295,7 @@
\subsubsection{Broadcast messages and dead-drops.}
-Chaum discusses a traffic-analysis prevention method wherein all reply
+Chaum discusses a traffic-analysis prevention method in which all reply
mail in the anonymous mail system is sent to all possible recipients. A
less invasive optimization has already been implemented in the form of
Usenet mail drops~\cite{aam}: an anonymous remailer can
@@ -386,7 +391,7 @@
reset by the nym holder after account 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
+secret in a given cycle $i$, then $S[i+1] = H(S[i]|\mbox{\tt "NEXT CYCLE"})$, where
$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
@@ -483,7 +488,11 @@
bucket pools for a reasonable window of time, to be sure that all clients
have time to download their messages.
-Since it is not necessary for every distributor to be operational at the given point
+The message integrity and tagging attack protection mechanism described in Section~\ref{subsec:tagging} also ensures
+that malicious distributors will be discovered if they attempt to execute denial of service attacks
+by dropping or garbling messages.
+
+Since it is not necessary for every distributor to be operational or honest at the given point
that a client wishes to retrieve mail, the system handles distributor node failure in a
graceful manner.
@@ -548,7 +557,7 @@
following categories.
\subsubsection{Legal and hacking attacks.}
-Attackers may attempt to coerce the operators of pseudonymity systems
+Attackers may attempt to coerce the operators of pseudo-nymity systems
through lawsuits or other
means~\cite{nym-alias-net,wagner,helsingius,jap-backdoor,jap-pr}, or may
attempt to surreptitiously obtain information about nym holders.
@@ -615,7 +624,9 @@
%topology of the Pynchon Gate infrastructure further eliminates areas of
%potential replay attack risk.
-\subsubsection{Tagging and known-cleartext attacks.} An attacker may alter
+\subsubsection{Tagging and known-cleartext attacks.}
+\label{subsec:tagging}
+An attacker may alter
a message, or observe the cleartext of a message, so that he may be able
to later link an input message with a given output retrieved by the
nym holder.
@@ -696,6 +707,60 @@
\subsection{Statistical disclosure against reply-block-based nym servers}
\label{subsec:disclosure}
+
+
+\begin{figure*}[t]
+\begin{center}
+\begin{minipage}{\linewidth}
+\renewcommand{\thefootnote}{\thempfootnote}
+{\tiny
+\begin{tabular}{|r|c|c|c|c|}
+\hline
+{\bf System} & {\bf Nymserver bandwidth} &
+ {\bf Infrastructure bandwidth} &
+ {\bf User bandwidth} &
+ {\bf Nymserver storage} \\
+% Infrastructure storage?
+\hline
+Type I nymservers &
+ $\sum \Vol_i + CVol_i$ &
+ $\CVol_i$ &
+ $\frac{2 \ell \sum \CVol_i}{S}$ &
+ $r N$ \\Type III nymserver
+\footnote{\tiny Underhill can be used in a full padding mode. In this case, the
+performance evaluation is the same, except that $CVol_i$ is calculated as
+the maximum compressed volume a user can recieve, rather than the
+average.} &
+ $\sum \Vol_i + (M+r) \sum \left\lceil \frac{\CVol_i}{P} \right\rceil $&
+ $\frac{2 L (M+r)}{S} \sum \left\lceil \frac{\CVol_i}{P} \right\rceil $&
+ $(P+r) \left\lceil \frac{\CVol_i}{P} \right\rceil $ &
+ $r W \sum \left\lceil \frac{\CVol_i}{P} \right\rceil $ (best
+ case) \\
+Usenet drop &
+ n/a &
+ $\frac{W}{S} \sum \CVol_i$ &
+ $\left[ \frac{N}{S} +1 \right] \sum \CVol_i $ &
+ $\sum \CVol_i$
+ n/a \\
+The Pynchon Gate &
+ $\sum \Vol_i + \mbox{Pool} $ &
+ $\frac{1}{S}\left[ \sum \mbox{ClientB}_i + \mbox{Pool} \right]$ &
+% $2 \mbox{ME} I + \mbox{Buckets}_i \left[ (K-1) SS + \frac{(m+I)}{8} + B
+% \right] $ &
+ $2 \mbox{ME} I + \mbox{ClientPIRVol}$\footnote{\tiny ClientPIRVol is the
+amount of data sent and received during PIR, or
+ $\mbox{Buckets}_i \left[ (K-1) SS + \frac{(m+I)}{8} + B \right]$} &
+ $W \mbox{Pool}$
+\\
+\hline
+\end{tabular}
+}
+\end{minipage}
+\end{center}
+\caption{Performance comparison for several pseudonymity designs.}
+\label{fig:performance}
+\end{figure*}
+
Nym servers based on reply blocks (discussed in Section
\ref{subsec:related-work} above) are currently the most popular option for
receiving messages pseudonymously. Nevertheless, they are especially
@@ -766,7 +831,7 @@
clients should make sure that each of the distributors they use agree
about the value of the hash root.
-\section{Performance, Scalability and Optimizations}
+\section{System Performance, Scalability and Optimizations}
\label{sec:performance}
In this protocol, the size of requests is linearly proportional to the
total number of messages and the size of responses is the bucket size. If
@@ -797,7 +862,7 @@
resources. This delay is prudent, since
% from a security standpoint, since
%the potential effectiveness of attacks in which a distributor sends back
-%garbled data to see if the client accepts it is unclear. Also,
+% data to see if the client accepts it is unclear. Also,
private
information retrieval primitives are an area of active research with
ongoing improvements~\cite{beimel-barrier}, so waiting to
@@ -835,65 +900,14 @@
%
%Describe the derivation of each value.
-
-\begin{figure}[t]
-\begin{center}
-\begin{minipage}{\linewidth}
-\renewcommand{\thefootnote}{\thempfootnote}
-{\tiny
-\begin{tabular}{|r|c|c|c|c|}
-\hline
-{\bf System} & {\bf Nymserver bandwidth} &
- {\bf Infrastructure bandwidth} &
- {\bf User bandwidth} &
- {\bf Nymserver storage} \\
-% Infrastructure storage?
-\hline
-Type I nymservers &
- $\sum \Vol_i + CVol_i$ &
- $\CVol_i$ &
- $\frac{2 \ell \sum \CVol_i}{S}$ &
- $r N$ \\Type III nymserver
-\footnote{\tiny Underhill can be used in a full padding mode. In this case, the
-performance evaluation is the same, except that $CVol_i$ is calculated as
-the maximum compressed volume a user can recieve, rather than the
-average.} &
- $\sum \Vol_i + (M+r) \sum \left\lceil \frac{\CVol_i}{P} \right\rceil $&
- $\frac{2 L (M+r)}{S} \sum \left\lceil \frac{\CVol_i}{P} \right\rceil $&
- $(P+r) \left\lceil \frac{\CVol_i}{P} \right\rceil $ &
- $r W \sum \left\lceil \frac{\CVol_i}{P} \right\rceil $ (best
- case) \\
-Usenet drop &
- n/a &
- $\frac{W}{S} \sum \CVol_i$ &
- $\left[ \frac{N}{S} +1 \right] \sum \CVol_i $ &
- $\sum \CVol_i$
- n/a \\
-The Pynchon Gate &
- $\sum \Vol_i + \mbox{Pool} $ &
- $\frac{1}{S}\left[ \sum \mbox{ClientB}_i + \mbox{Pool} \right]$ &
-% $2 \mbox{ME} I + \mbox{Buckets}_i \left[ (K-1) SS + \frac{(m+I)}{8} + B
-% \right] $ &
- $2 \mbox{ME} I + \mbox{ClientPIRVol}$\footnote{\tiny ClientPIRVol is the
-amount of data sent and received during PIR, or
- $\mbox{Buckets}_i \left[ (K-1) SS + \frac{(m+I)}{8} + B \right]$} &
- $W \mbox{Pool}$
-\\
-\hline
-\end{tabular}
-}
-\end{minipage}
-\end{center}
-\caption{Performance comparison for several pseudonymity designs.}
-\label{fig:performance}
-\end{figure}
+%Moved table figure to the previous section to get it on the correct page.
We have evaluated the resource requirements of various pseudonymity systems
described in Section~\ref{subsec:related-work}, and compare their
respective performance in Figure~\ref{fig:performance}. Bandwidth
requirements for the independent
-components of the pseudonym system are averages per cycle. We use the term
+components of the pseudo-nym system are averages per cycle. We use the term
``infrastructure'' to denote mix nodes in the Type I (Cypherpunk) and Type
III (Underhill~\cite{underhill-spec}) nym server systems, NNTP
servers~\cite{rfc-1036} for the Usenet news drop, and distributors in
@@ -961,7 +975,7 @@
\label{sec:conclusions}
We have presented a system for anonymous message retrieval that provides
-stronger anonymity assurance and greater robustness than other theorized
+stronger anonymity assurance and more robustness than other theorized
or deployed high-latency pseudonymous message retrieval systems. Our
system resists traffic analysis better than current deployed systems, and
offers convenient scalability options.
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxx with
unsubscribe freehaven-cvs in the body. http://freehaven.net/