\documentclass[handout]{beamer}
\usetheme{i4}
\usepackage[utf8]{inputenc}
\usepackage{tikz}
\usepackage{multicol}
\usepackage{listings}
\lstloadlanguages{lisp}

\usetikzlibrary{svg.path,positioning,intersections}
\usepgflibrary{shapes.geometric}
\usepgflibrary{shapes.misc}
\usepgflibrary{shapes.symbols}

\usepgflibrary{shapes}
\usetikzlibrary{shapes,decorations,shadows}
\usetikzlibrary{decorations.pathmorphing}
\usetikzlibrary{decorations.shapes}
\usetikzlibrary{fadings}
\usetikzlibrary{patterns}
\usetikzlibrary{calc}
\tikzstyle{netdb}=[anchor=center,color=black,rectangle,draw,minimum
 size=1em,minimum height=.5em]
\tikzstyle{client}=[fill=i4gray,rectangle,draw]
\tikzstyle{chain}=[rectangle,draw,minimum size=1em,minimum height=.5em]
\tikzstyle{arrow}=[->,thick,draw,shorten <=2pt,shorten >=2pt,]
\tikzstyle{tunnel}=[fill=gray,shape=ellipse,minimum size=4em,minimum height=1.1em]

\newcommand{\iip}[1]{\textcolor{i4red}{#1}}

\author[Christoph Egger]{{\bf Christoph Egger}, Johannes Schlumberger, Christopher
  Kruegel, Giovanni Vigna}
\title{Practical Attacks Against The I2P Network}
\institute{Friedrich-Alexander University Erlangen-Nuremberg\\
University of California, Santa Barbara}
\date{October 25, 2013}
\begin{document}

\begin{frame}[plain]
  \vspace{1.5em}
  \titlepage
  \begin{center}
  \includegraphics[width=0.2\paperwidth]{ucsbseal}
  \hspace{1.5em}
  \includegraphics[width=0.25\paperwidth]{streifenlogo}
  \end{center}
\end{frame}

\begin{frame}
  \frametitle{Outline}
  \begin{multicols}{2}
    \begin{block}{What is I2P?}
      \begin{itemize}
      \item Tunnels
      \item Network Database
      \item \textcolor{gray}{Floodfill Participation}
      \item Thread model
      \end{itemize}
    \end{block}
    \begin{block}{Attacks}
      \begin{itemize}
      \item \textcolor{gray}{Floodfill Takeover Attack}
      \item Sybil Attack
      \item \textcolor{gray}{Eclipse Attack}
      \item Deanonymization Attack
      \end{itemize}
    \end{block}
    \begin{block}{Evaluation}
      \begin{itemize}
      \item \textcolor{gray}{Floodfill Takeover Attack}
      \item Sybil Attack
      \item \textcolor{gray}{Eclipse Attack}
      \item Deanonymization Attack
      \end{itemize}
    \end{block}
    \begin{block}{Conclusions}
      \begin{itemize}
      \item Limitations
      \item I2P Improvements
      \item \textcolor{gray}{Related Work}
      \end{itemize}
    \end{block}
  \end{multicols}
\end{frame}

\begin{frame}
  \frametitle{Introduction I2P}
  \begin{itemize}\addtolength{\itemsep}{1\baselineskip}
  \item Solution for anonymous Communication
  \item Separated from the ``Internet'' -- \emph{Darknet} 
  \item Fully distributed Design
  \item Based on Onion Routing
  \item Between 18,000 and 28,000 active users
  \end{itemize}
\end{frame}
\section{I2P}
\begin{frame}
  \frametitle{I2P}
  \begin{multicols}{2}
    \begin{block}{Router}
      \begin{itemize}
      \item Handle Connections
      \item Provide Name Services
      \end{itemize}
    \end{block}
    \pause
    \begin{block}{Applications}
      \begin{itemize}
      \item Server, Client or P2P Software
      \item Sockets interface with TCP-like or UDP-like Semantics
      \end{itemize}
    \end{block}
    \pause
    \begin{figure}
      \centering
      \begin{tikzpicture}[scale=1.2]
        \tikzstyle{every node}=[font=\tiny]
        \node[minimum width=7em,minimum height=6em,draw=gray](clientpc) at (25mm,9mm) {};
        \node[above=0mm of clientpc.south] {User's Computer};
        \node[cloud,drop shadow,fill=white,draw,minimum
        width=4.5em,minimum height=2.5em](ip) at (22mm,27mm) {I2P};
        \node[client](client) at (22mm, 18mm) {I2P Router};
        \node[rectangle,draw,below=0mm of client.south east](app1) {Application};
        \node[rectangle,draw,below=0mm of app1.south](app2) {Application};
        \node[rectangle,draw,below=0mm of app2.south](app3) {Application};

        \path[arrow] (app1.west) -| ([xshift=3.5mm]client.south west);
        \path[arrow] (app2.west) -| ([xshift=2.5mm]client.south west);
        \path[arrow] (app3.west) -| ([xshift=1.5mm]client.south west);
        \path[arrow] ([xshift=.5mm]client.north) -- ([xshift=.5mm]ip.south);
        \path[arrow] ([xshift=-.5mm]ip.south) -- ([xshift=-.5mm]client.north);
      \end{tikzpicture}
    \end{figure}

  \end{multicols}
\end{frame}

\begin{frame}
  \frametitle{Tunnels}
  \begin{itemize}
  \item using onion-routing for anonymity
  \item unidirectional
  \item paired for bi-directional communication
  \end{itemize}\pause
  \begin{block}{Client Tunnels}
    \begin{itemize}
    \item Used for Data Interactions
    \item Several pro Application
    \end{itemize}
  \end{block}
  \pause
  \begin{block}{Exploratory Tunnels}
    \begin{itemize}
    \item Used for Database interaction
    \item 2 to 3 per Node
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Network Database}
  \begin{itemize}
  \item<1-> Kademlia-like DHT based on \texttt{XOR}-distance run on
    320 super-nodes
  \item<2-> \iip{databaseRecord}\\
    Information named using a hash over their cryptographic Keys
  \item<3-> \iip{storageLocation}\\
    Hash over name and today's date
  \item<4-> \iip{routerInfo}\\
    Peer information: IP address, Port, Protocol, Keys
  \item<5-> \iip{leaseSet}\\
    Service Information: Entry tunnels, Keys
  \end{itemize}
  % \begin{multicols}{2}
  %   \begin{block}{\iip{routerInfo}}
  %     \begin{itemize}
  %     \item Peer information: IP address, Port, Protocol, Keys
  %     \end{itemize}
  %   \end{block}
  %   \begin{block}{\iip{leaseSet}}
  %     \begin{itemize}
  %     \item Service Information: Entry tunnels, Keys
  %     \end{itemize}
  %   \end{block}
  %   % \begin{figure}
  %   %   \centering
  %   %   \begin{tikzpicture}
  %   %     \node[draw,rectangle split, rectangle split parts=2] (lease) at (-3em,0) {\iip{leaseSet}\nodepart{second}\tiny{Keys}};
  %   %     \node[draw,rectangle split, rectangle split parts=2] (router) at (3em,0) {\iip{routerInfo}\nodepart{second}\tiny{Keys}};
  %   %     \node[draw,ellipse] (hashfn1) at (0,-3em) {\tiny{SHA256}};
  %   %     \node[draw,rectangle] (hash1) at (0,-5.5em) {\iip{resourceIdentifier}};
  %   %     \node[draw,rectangle,right=-0.1mm of hash1.east] (day) {Date};

  %   %     \node[draw,ellipse] (hashfn1) at (0,-8em) {\tiny{SHA256}};
  %   %     \node[draw,rectangle] (resID) at (0,-10.5em) {\iip{storageLocation}};
  %   %   \end{tikzpicture}
  %   % \end{figure}
  % \end{multicols}
\end{frame}

\begin{frame}
  \frametitle{Sample Interaction}
  \begin{figure}
    \centering
    \begin{tikzpicture}[scale=1.2]
      \tikzstyle{every node}=[font=\tiny]
% netDB
      \foreach \sector in {%
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9}%
      {
        \node[netdb](node\sector) at ({36 * (-\sector + .5)} : 10mm) {\sector};
      }
      \node at (0, 0) {netDB};
% client
      \node[client](client) at (28mm, 12mm) {Server Router};
      \node[rectangle,draw,below=0mm of client.south west] {Application};
      \node[minimum width=7em,minimum height=4em,draw=gray](clientpc) at (25mm,9mm) {};
      \node[above=0mm of clientpc.south] {Server's System};
% server
      \node[client](server) at (-42mm, 12mm) {Client Router};
      \node[rectangle,draw,below=0mm of server.south east] {Application};
      \node[minimum width=7em,minimum height=4em,draw=gray](clientpc) at (-38mm,9mm) {};
      \node[above=0mm of clientpc.south] {Client's System};
% client client tunnel
      \node[chain,minimum size=6.5em,minimum height=2em,draw=gray](tunnel) at (16mm,20.5mm) {};
      \node[above=0mm of tunnel.north] {Server's data tunnel pair};
%  \node[tunnel,minimum width=9.5em] at (16mm, 19mm) {};
%  \node[tunnel,minimum width=9.5em] at (16mm, 22mm) {};
%
      \node[chain] (cco1) at (23mm, 19mm) {};
      \path[arrow] ([xshift=4mm]client.north) |- (cco1.east);
      \node[chain] (cco2) at (16mm, 19mm) {};
      \path[arrow] (cco1.west) -- (cco2.east);
      \node[chain] (cco3) at (9mm, 19mm) {};
      \path[arrow] (cco2.west) -- (cco3.east);
      \node[chain] (cci1) at (23mm, 22mm) {};
      \path[arrow] (cci1.east) -| ([xshift=5mm]client.north);
      \node[chain] (cci2) at (16mm, 22mm) {};
      \path[arrow] (cci2.east) -- (cci1.west);
      \node[chain] (cci3) at (9mm, 22mm) {};
      \path[arrow] (cci3.east) -- (cci2.west);
% server client tunnel
      \node[chain,minimum size=6.5em,minimum height=2em,draw=gray](tunnel) at (-30mm,20.5mm) {};
      \node[above=0mm of tunnel.north] {Client's data tunnel pair};
%  \node[tunnel,minimum width=9.5em] at (-34mm, 19mm) {};
%  \node[tunnel,minimum width=9.5em] at (-34mm, 22mm) {};
%
      \node[chain] (csi1) at (-37mm, 19mm) {};
      \path[arrow,<-] ([xshift=-4mm]server.north) |- (csi1.west);
      \node[chain] (csi2) at (-30mm, 19mm) {};
      \path[arrow,<-] (csi1.east) -- (csi2.west);
      \node[chain] (csi3) at (-23mm, 19mm) {};
      \path[arrow,<-] (csi2.east) -- (csi3.west);
      \node[chain] (cso1) at (-37mm, 22mm) {};
      \path[arrow,<-] (cso1.west) -| ([xshift=-5mm]server.north);
      \node[chain] (cso2) at (-30mm, 22mm) {};
      \path[arrow,<-] (cso2.west) -- (cso1.east);
      \node[chain] (cso3) at (-23mm, 22mm) {};
      \path[arrow,<-] (cso3.west) -- (cso2.east);
% client exploratory tunnel
      \node[chain,minimum size=4.5em,minimum height=2em,draw=gray](tunnel) at (-32.5mm,-3.5mm) {};
      \node[below=0mm of tunnel.south,align=center] {Client's exploratory\\tunnel pair};
%  \node[tunnel,minimum width=7.5em] at (-36.5mm, 0mm) {};
%  \node[tunnel,minimum width=7.5em] at (-36.5mm, -3mm) {};
%
      \node[chain] (eo1) at (-36mm, -2mm) {};
      \path[arrow] ([xshift=-4mm]server.south) |- (eo1.west);
      \node[chain] (ei1) at (-36mm, -5mm) {};
      \path[arrow,<-] ([xshift=-5mm]server.south) |- (ei1.west);
      \node[chain] (eo2) at (-29mm, -2mm) {};
      \path[arrow] (eo1.east) -- (eo2.west);
      \node[chain] (ei2) at (-29mm, -5mm) {};
      \path[arrow,<-] (ei1.east) -- (ei2.west);
% service lookup
      \draw[arrow,bend right=20,dashdotted] (eo2.east) to node[above=.8em,align=center] {service\\lookup} (node4.west);
      \draw[arrow,bend right=10,<-,dashdotted] (ei2.east) to node {} ([yshift=-1mm]node4.west);
% data link
      \draw[arrow,bend left=15,dashdotted] (cco3.west) to node {} (csi3.east);
      \draw[arrow,bend right=15,dashdotted] (cci3.west) to node {} (cso3.east);
      \node at (-9mm,20.5mm) {Data connection};
    \end{tikzpicture}
  \end{figure}
\end{frame}

\begin{frame}
  \frametitle{Thread Model}
  \begin{itemize}\addtolength{\itemsep}{1\baselineskip}
  \item Implicitly specified in terms of attacks considered
  \item Only allows local adversaries: No global view about traffic
    passing through the network
  \item Only allows limited number of malicious nodes -- around 20\,\%
    of \iip{netDB} super-nodes and 20\,\% of total nodes
  \item Secure cryptographic primitives
  \end{itemize}
\end{frame}

\section{Attacks}
\begin{frame}
  \frametitle{Sybil Attack}
  \begin{block}{Definition}
    In a Sybil Attack, the adversary utilizes multiple identities to
    break assumptions about the system
  \end{block}\pause
  \begin{block}{Goal}
    Gaining control over parts of the keyspace in the \iip{netDB} with
    limited resources
  \end{block}\pause
  \begin{block}{Challenge}
    Active identities require considerable resources to be useful
  \end{block}\pause
  \begin{block}{Solution}
    Compute a large pool of identities and only activate the relevant ones
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Deanonymizing Users}
  \begin{block}{Goal}
    Given an user Alice and a resource R, we want to confirm or refute
    Alice using R with high probability.
  \end{block}\pause
  \begin{block}{Vulnerability}
    \begin{itemize}
    \item<2-> Nodes store their \iip{routerInfo} directly in the \iip{netDB}
    \item<3-> Nodes verify the storage 20 seconds later using one of their
      \iip{exploratory Tunnels}
    \item<4-> Nodes use the same \iip{exploratory Tunnel} again for
      resource lookups
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Deanonymizing Users}
  \begin{figure}
  \centering
\begin{tikzpicture}[scale=1.4,font=\tiny]
% netDB
  \foreach \sector in {%
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9}%
  {
    \node[netdb](node\sector) at ({36 * (-\sector + .5)} : 12mm) {\sector};
  }
  \node at (0, 0) {netDB};
% client
  \node[client](client) at (-45mm, 12mm) {Client};
% store
  \draw[arrow,bend left=5,dashdotted] (client.north east) to node[above] {store} (node7.north west);
  \draw[arrow,<-,bend left=5,dashdotted] (client.east) to node {} (node7.west);
% flood
  \draw[arrow,draw,bend right=15] (node7.south east) to node {} (node8.south west);
  \draw[arrow,draw,bend right=15] (node7.south east) to node[below] {replication} (node9.west);
  \draw[arrow,draw,bend left=15]  (node7.south east) to node {} (node6.north east);
% tunnels
  \node[chain,minimum size=6em,minimum height=3.5em,draw=gray](tunnel) at (-35mm,-2.5mm) {};
  \node[below=2mm of tunnel.south] {exploratory tunnel pair};
%  \node[tunnel] at (-35mm, 0mm) {};
  \node[chain] (ol) at (-40mm, 0mm) {};
  \node[chain] (oe) at (-30mm, 0mm) {};
%  \node[tunnel] at (-35mm, -5mm) {};
  \node[chain] (il) at (-40mm, -5mm) {};
  \node[chain] (ie) at (-30mm, -5mm) {};
  \path[arrow] ([xshift=-1mm]client.south) |- (ol.west);
  \path[arrow,<-] ([xshift=-2mm]client.south) |- (il.west);
  \path[arrow] (ol.east) -- (oe.west);
  \path[arrow,<-] (il.east) -- (ie.west);
% verify
  \draw[arrow,bend left=5,dashdotted] (oe.north east) to node[above] {verify} ([yshift=1mm]node6.west);
  \draw[arrow,bend left=15,<-,dashdotted] (ie.north east) to node {} (node6.west);
%lookup
  \draw[arrow,bend right=15,dashdotted] (oe.south east) to node[above] {lookup} (node4.west);
  \draw[arrow,bend right=5,<-,dashdotted] (ie.south east) to node {} ([yshift=-1mm]node4.west);
\end{tikzpicture}
\end{figure}
\end{frame}

\section{Evaluation}
\begin{frame}
  \frametitle{Sybil Attack}
  \begin{block}{Generating identities}
    \begin{itemize}
    \item Building a Database of 50,000 identities takes around 30
      minutes on 12-core Xeon server
    \item 156 nodes on average between two adjacent database nodes
    \item All identities available to all malicious nodes
    \end{itemize}
  \end{block}\pause
  \begin{block}{Using identities}
    \begin{itemize}
    \item Malicious nodes can calculate the correct identities and
      change identity at any time
    \item Nodes coordinate to avoid duplicate identities
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Deanonyizing Attack}
  \begin{block}{Setup}
    \begin{itemize}
    \item 20 attacking nodes in Santa Barbara
      \begin{itemize}
      \item 10 nodes capturing resource lookups
      \item 10 nodes performing timing attack on \iip{routerInfo} storage
      \end{itemize}
    \item 6 monitoring nodes: 3 in Erlangen, 3 in Santa Barbara
    \end{itemize}
  \end{block}\pause
  \begin{block}{Results}
    \begin{itemize}
    \item 60\,\% of potentially observable links detected
    \item 52\,\% of attributed hits correct
    \item Working equally well for geographically remote Hosts
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Deanonymizing Users}
  \begin{figure}
  \centering
\begin{tikzpicture}[scale=1.4,font=\tiny]
% netDB
  \foreach \sector in {%
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9}%
  {
    \node[netdb](node\sector) at ({36 * (-\sector + .5)} : 12mm) {\sector};
  }
  \node at (0, 0) {netDB};
% client
  \node[client](client) at (-45mm, 12mm) {Client};
% store
  \draw[arrow,bend left=5,dashdotted] (client.north east) to node[above] {store} (node7.north west);
  \draw[arrow,<-,bend left=5,dashdotted] (client.east) to node {} (node7.west);
% flood
  \draw[arrow,draw,bend right=15] (node7.south east) to node {} (node8.south west);
  \draw[arrow,draw,bend right=15] (node7.south east) to node[below] {replication} (node9.west);
  \draw[arrow,draw,bend left=15]  (node7.south east) to node {} (node6.north east);
% tunnels
  \node[chain,minimum size=6em,minimum height=3.5em,draw=gray](tunnel) at (-35mm,-2.5mm) {};
  \node[below=2mm of tunnel.south] {exploratory tunnel pair};
%  \node[tunnel] at (-35mm, 0mm) {};
  \node[chain] (ol) at (-40mm, 0mm) {};
  \node[chain] (oe) at (-30mm, 0mm) {};
%  \node[tunnel] at (-35mm, -5mm) {};
  \node[chain] (il) at (-40mm, -5mm) {};
  \node[chain] (ie) at (-30mm, -5mm) {};
  \path[arrow] ([xshift=-1mm]client.south) |- (ol.west);
  \path[arrow,<-] ([xshift=-2mm]client.south) |- (il.west);
  \path[arrow] (ol.east) -- (oe.west);
  \path[arrow,<-] (il.east) -- (ie.west);
% verify
  \draw[arrow,bend left=5,dashdotted] (oe.north east) to node[above] {verify} ([yshift=1mm]node6.west);
  \draw[arrow,bend left=15,<-,dashdotted] (ie.north east) to node {} (node6.west);
%lookup
  \draw[arrow,bend right=15,dashdotted] (oe.south east) to node[above] {lookup} (node4.west);
  \draw[arrow,bend right=5,<-,dashdotted] (ie.south east) to node {} ([yshift=-1mm]node4.west);
\end{tikzpicture}
\end{figure}
\end{frame}

\begin{frame}
  \frametitle{Results for multiple Hits}
  \small{
  $N=144$, Number of time slices\\
  $q=0.001$, 7\,\% of total nodes accessing the resource once a day\\
  $x=0.52\cdot p + 0.48\cdot q$ \\
  $P(k~hits) = {N \choose k} x^k \cdot (1-x)^{N-k}$}
  \begin{figure}
    \centering
    \includegraphics[width=.7\textwidth]{graph}    
  \end{figure}
\end{frame}

\section{Conclusions}

\begin{frame}
  \frametitle{Limitations}
  \begin{itemize}\addtolength{\itemsep}{1\baselineskip}
  \item Only works reliable for longer/repeated resource access
  \item Less reliable for popular resources
  \item Needs extra resources per tracked user and per resource
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{I2P Improvements}
  \begin{itemize}\addtolength{\itemsep}{1\baselineskip}
  \item Limiting \iip{netDB} nodes per IPv4 network
  \item Ignoring new \iip{netDB} nodes
  \item Removing storage verification
  \item Randomizing the time delta
  \item Expiring tunnels after storage verification
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Bibliography}
  \nocite{Mittal:2012}
  \nocite{Timpanaro:2011}
  \nocite{Herrmann:2011}
  \nocite{Douceur:2002}
  \nocite{Dingledine:2004}
  \nocite{Evans:2011}
  \bibliographystyle{plain}
  \tiny{\bibliography{../i2p}}
\end{frame}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% TeX-PDF-mode: t
%%% End: