source: libros/maquetacion/capitulo7/capitulo7.tex @ cd5b68a

\chapter{Anonimato}
\chapterauthors{R. Sumoza
\chapteraffil{Fundación Centro Nacional de Desarrollo e Investigación en Tecnologías Libres}
}

\section{Modelo de protocolo para un sistema anónimo basado en estrategias bio-inspiradas}


\textbf{Resumen}

En este artículo se propuso utilizar algunas herramientas provista en el área de la Computación Emergente, específicamente en Inteligencia Artificial Distribuida (IAD), y en particular se utilizaron las Colonias Artificiales de Hormigas para construir sistemas anónimos que tengan la virtud de poseer niveles de anonimato aceptables a un bajo costo. Este costo se refiere a un criterio de rendimiento comúnmente utilizado en los procesos de los sistemas de enrutamiento en telecomunicaciones, tal como lo son los tiempos de respuesta (latencia), consumo de recursos de la red, entre otros.

\subsection{Introducción}
Para preservar la privacidad de los datos de cada una de las personas que participan en una red de interacción, tal como Internet, se deben utilizar herramientas que sean capaces de proveer protección contra al menos algunos de los ataques típicos. Los ataques en este case de estudio en particular están orientados, sin autorización, a obtener información privada de los usuarios, incluyendo su propia identidad. Para contrarrestar este tipo de ataques se han propuesto varias ideas que apuntan a establecer cierto nivel de Anonimato, el cual en la mayoría de los casos tienden a socavar el rendimiento de las comunicaciones. Esto es aun un problema abierto: los sistemas anónimos aún necesitan asegurar el Anonimato a un bajo costo (bajos tiempos de respuesta, bajo consumo de recursos, mayor usabilidad, etc.), y a esto es lo que se le denomina \emph{Anonimato Eficiente}. Este trabajo presente un nuevo enfoque que aplica por primera vez la idea de utilizar la Inteligencia Artificial Distribuida en esta rama de la seguridad en las Tecnologías de Información y Comunicación (TIC), esto quiere decir que se le delega la responsabilidad de alcanzar niveles de Anonimato Eficiente a la Inteligencia Artificial Distribuida,  específicamente se propone utilizar las Colonias Artificiales de Hormigas.

\subsection{Colonias Artificiales de Hormigas en Anonimato}
\label{rlsm:ia-anonimato}

Considerando las ideas propuestas en los sistemas anónimos probabilísticos \cite{rlsm:chaum-mix}\cite{rlsm:mixminion}\cite{rlsm:diaz-mixes}\cite{rlsm:tor-design}, las características de los Colonias Artificiales de Hormigas utilizadas en las redes de telecomunicaciones \cite{rlsm:antnet}\cite{rlsm:ants-white}\cite{rlsm:ants-loadbalancing}, se propone seleccionar las rutas de los mensajes de forma probabilística, utilizando las probabilidades que configuran los agentes móviles adaptativos (las hormigas). Estas rutas, teniendo componentes probabilísticos pueden incluir, dependiendo de los parámetros de configuración, proporcionar ciertos niveles de Anonimato, en este sentido, se podría tener un "control inteligente" sobre los tiempos de respuesta generados y se podría tener un "control inteligente" sobre otros índices que pudiesen ser incorporados, tal como el consumo de recursos (balanceo de cargas).

Se propone mimetizar los mensaje reales con los agente, esto es, cada mensaje tiene la misma estructura que las hormigas, y la única diferencia entre ellos radica en el contenido del mensaje, estos mensajes mimetizados se encriptan con las claves públicas de los nodos destino. Para hacer similar sus tamaños, se propone utilizar un tamaño  único para el envío de mensajes y para cada agente, incluyendo la estructura de datos que almacena la información necesaria para actualizar las tablas de enrutamiento de cada nodo, más un relleno inválido y la clave pública del destino. Si un mensaje se fragmenta para cumplir con el requisito del tamaño único, el mismo es reensamblado en el nodo destino, utilizando un número de secuencia establecido por el nodo emisor. Los fragmentos de los mensajes también tienen la tarea de actualizar las tablas de enrutamiento de los nodos que visitan, de esta manera los atacantes no pueden ditinguir entre las hormigas y los mensajes reales. De este modo, se puede comparar los mensajes enviados con hormigas de carga que llevan el alimento a los nidos, y es por esto que se identifican dos tipos de hormigas, las de carga y las exploradoras, sin tener diferencias aparentes.

Se utiliza una estrategia de cifrado por capas, cada nodo que una hormiga visita cifra la información relacionada al nodo anterior con una técnica de cifrado simétrico, e involucra solo la clave del nodo anterior el nodo anterior, y para alcanzar cada destino, incluyendo el final, se pueden registrar sólo los nodos previos, y no la ruta completa hacia el origen. Para hacer la ruta de retorno (respuesta del  nodo destino), este nodo final envía su respuesta al nodo anterior, y éste desencripta la capa que contiene la información del nodo anterior a él, y así hasta llegar el nodo origen (el emisor).

Para optimizar el o los criterios de rendimiento usualmente utilizados en los sistemas de enrutamiento y a su vez incrementar los niveles de Anonimato, se debe configurar apropiadamente la tabla de rutas. Para hacer ésto, cada vez que una hormiga se mueve de un lugar a otro, actualiza la tabla de rutas. Para cambiar las probabilidad de las rutas, se selecciona un mecanismo basado en los criterios de rendimiento.

En los pasos siguientes muestran el proceso:

\begin {description}
  \item [A.] Se considera un sistema de $N$ nodos, formando una red P2P (tal como Gnutella u otra con características similares), junto con sus servidores bootstrap.
  \item [B.] Se configuran los valores de los parámetros a utilizar, junto con el índice de uniformidad. 
  \item [C.] Cada nodo participante solicita a uno o varios servidores una lista de los otros nodos en la red. Esta lista contiene sus claves públicas (certificados electrónicos).
  \item [D.] Se inicializan la tablas de rutas con la probabilidad $1/M$. $M$ depende del número de vecinos que cada nodos posea.
  \item [E.] El sistema se representa por un grafo el cual forma el espacio de solución por el cual viajarán las hormigas.
  \item [F.] El procedimiento siguiente se repite sobre el grafo hasta alcanzar una solución estable:
  \begin {description}
    \item [1.] Se generan $m$ hormigas exploradoras en cada nodo.
    \item [2.] Por cada $N-1$ lugares desde cada nodo se envían $m$ hormigas exploradoras que escogen el salto a nodo vecino utilizando las probabilidades de transición de la tabla de rutas.
    \item [3.] Se actualizan las tablas de rutas. 
  \end {description}
  \item [G.] Cuando un nodo envía un mensaje anónimamente, éste lo cifra con las clave pública del nodo receptor y utiliza una estructura de datos similar al de las hormigas exploradoras, es decir, se crea una hormiga de carga. Cada hormiga de carga traslada una parte del mensaje, el cual se fragmenta para que el tamaño de cada fragmento pueda cumplir con el requisito de igualar su tamaño con el de la hormiga exploradora. Cada fragmento del mensaje se le asigna un número de secuencia. 
  \item [H.] Por cada salto de la hormiga, el nodo intermedio cifra el identidad del nodo anterior con su clave privada. 
  \item [I.] Cuando una hormiga de carga alcanza el nodo final, y todas las otras hormigas de carga vinculadas a un mensajes también han llegado, es posible reensamblar el mensaje original descifrando los su clave privada, y utilizando los números de secuencia correspondientes.
  \item [J.] Para enviar un mensaje de respuesta, el nodo final utilza el camino de retorno cifrado en capas.
\end {description}

\subsection{Conclusión}
\label{rlsm:conclusion}

Se propuso implementar un sistema distribuido P2P basado en anonimato probabilístico provisto por sistemas de colonias artificiales de hormigas. Para lograr esto se configuran los nodos participantes como potenciales enrutadores de los mensajes anónimos.  Las rutas para los mensajes de envío se construyen en base a las estrategias propuestas en los sistemas de telecomunicaciones para optimizar criterios de rendimiento a través del uso de Colonias Artificiales de Hormigas. Una vez que se crean la rutas, el Anonimato se logra al seleccionar probabilísticamente las rutas de los mensajes enviados utilizando cifrado en capas establecido para la ruta de retorno o respuesta.

\subsection*{Agradecimientos}
Se agradece a José Lisandro Aguilar Castro por su revisión, consejos y recomendaciones sobre todo el contenido propuesto.


\begin{thebibliography}{1}

\bibitem{rlsm:terminology}
Pfitzmann, A., Hansen, M.: Anonymity, Unobservability, and Pseudonymity: A Consolidated Proposal for Terminology. In: http://dud.inf.tu-dresden.de/Anon\_Terminology.shtml, (2000)

\bibitem{rlsm:diaz01}
D\'{\i}az, C., Seys, S., Claessens, J., Preneel, B.: Towards measuring Anonymity. In: Designing Privacy Enhancing Technologies (PET'02). Springer LNCS 2482, pp. 54-68, (2002)

\bibitem{rlsm:serj01}
Serjantov, A., Danezis, G.: Towards an Information Theoretic Metric for Anonymity. In: Proceedings of Privacy Enhancing Technologies Workshop, (2002)

\bibitem{rlsm:chaum-mix}
Chaum, D.: Untraceable electronic mail, return addresses, and digital pseudonyms. In: Communications of the ACM, Vol. 4, No. 2, (1981)

\bibitem{rlsm:diaz-mixes}
D\'{\i}az, C., Serjantov, A.: Generalising Mixes. In: Proceedings of Privacy Enhancing Technologies workshop (PET 2003), pp. 18-31, (2003)

\bibitem{rlsm:mixminion}
Danezis, G., Dingledine, R., Mathewson, N.: Mixminion: Design of a Type III Anonymous Remailer Protocol. In: Proceedings of the 2003 IEEE Symposium on Security and Privacy, pp. 2-15, (2003)

\bibitem{rlsm:tor-design}
Dingledine, R., Mathewson, N., Syverson, P.: Tor: The Second-Generation Onion Router. In: Proceedings of the 13th USENIX Security Symposium, (2004)

\bibitem{rlsm:antnet}
Caro, G.D., Dorigo, M.: AntNet: Distributed Stigmergetic Control for Communications Networks. In: Journal of Artificial Intelligence
Research, (1998)

\bibitem{rlsm:ants-white}
White, T., Pagurek, B.: Connection Management using Adaptive Mobile Agents. In: Proceedings of the International Conference on
Parallel and Distributed Processing Techniques and Applications, pp. 802-809, (1998)

\bibitem{rlsm:ants-loadbalancing}
Schoonderwoerd, R.: Ant-Based Load Balancing in Telecommunications Networks. In: Adaptive Behavior, Vol. 5, pp. 169-207, (1997)

\end{thebibliography}




\section{Sistema de medición alternativo}


\textbf{Resumen}
This paper proposes the use of a system of measures for Anonymity based on the characteristics that define their main properties: the index of uniformity of the probability distribution and size of all anonymous. In previous proposals, the most widely used is based on the entropy, an index used in information theory, which has several drawbacks with respect to representation of the properties mentioned in the first place does not represent them explicitly and being a logarithmic index does not represent Anonymity levels or degrees that require linear behavior. To measure the uniformity index is proposed to use the Root Mean Square Error criterion or the Jensen-Shannon divergence. For anonymous set size proposes the use of a function of N.
Claves(metrics, Anonymity, Root Squared Mean Error, Jensen-Shannon Divergence).



\subsection{Introduction}

The measures used to quantify levels of Anonymity achieved by the systems, mechanisms and tools in general is still considered an open problem. Several alternatives have been proposed for this purpose, and used more widely accepted so far is based on a type of measurement based on the Information Theory: Entropy, however, does not explicitly consider the fundamental characteristics of Anonymity: anonymous set size and uniformity index of the probability distribution. In this paper, we propose two indices explicitly representing both indicators. On one hand the anonymous set size would be represented by a function of N and uniformity index would be represented using one of these indicators: the Root Mean Square Error (RMSE) or the criteria of Jensen-Shannon divergence (CDJs .)

Pfiztmann et al. \cite{terminology} established terminology to standardize the terms used in the context of Anonymity, in which it was determined that a subject is anonymous when it can not be differentiated from other subjects belonging to the same set. This set is called the Anonymous Set. In describing the Anonymity in these terms, states that its levels increase as you grow the size of that set and when the probability distribution assigned by the attacker to the members of that group tends to be uniform. The proximity of a probability distribution to any uniform probability distribution is what we call uniformity index of the probability distribution.

The latest proposals and the most widely used so far are those based on a measurement used in the context of Information Theory: Entropy, as defined Shannon \cite{shannon}. This proposal was discussed in the work Díaz et al. \cite{diaz01} and Serjantov et al. \cite{serj01}, then there have been several streams that use the same basis, such as those proposed by Deng et al. \cite{yuxin}, Edman et al. \cite{combinatorial} and Gierlichs et al. \cite{revisiting}. However, not explicitly shown in the two aforementioned Anonymity characteristics, in particular the uniformity index.

Section 2 provides a theoretical review of the entropy and specific problems are shown in relation to its use as a measure of Anonymity, in sections 3 and 4 show the basic concepts necessary for the use of the measures proposed in section 5, establishing the uniformity index measurements of the probability distribution.


\subsection{Related work}
There have been several proposals to quantify the degree or level of Anonymity provided by any anonymous system. In \cite{reiter} define the degree of Anonymity as $1 - p$, where $p$ is the probability assigned to a particular user by the attacker. In \cite{berthold} define the degree of Anonymity as $A=\log_2(N)$, where $N$ is the number of users of the system. This degree only depends on the number of users of the system, and does not take into account the information the attacker may obtain by observing the system. In \cite{diaz01} and \cite{serj01} propose to measure the information the attacker gets, taking into account the whole set of users and the probability information the attacker obtains about them, to do that they propose to use Information Theory Entropy to measure the degree of Anonymity (using Shannon's entropy definition \cite{shannon}). None of them takes explicitly in consideration the anonymous set size and its uniformity index of probability distribution function like separated indexes 
to be measures, and these are the most important Anonymity's descriptors. Besides, in \cite{diaz01} proposed to use a normalized degree, but this measures could reach its maximal level with $N=2$ (anonymous set size), contradicting the Anonymity's fundamental characteristics described in \cite{terminology}: Anonymity level increases by increasing the size of the anonymous set and by increasing the uniformity index of probability distribution function. In \cite{yuxin}, \cite{combinatorial}, \cite{revisiting} use Shannon's entropy with different focus but with the same problems. When they use Entropy, are using the logarithmic function, that mean to have no linear degrees to compare systems. For example, if we have four (4) systems, and the attackers don't have any information about them, that mean the attackers assigned the uniformity distribution function for all of them, and, if the first set has $N=100$, the second one has $N=200$, the third one has $N=400$ and the fourth one has $N=800$, the Anonymity 
degrees using Entropy are: $6.6438$, $7.6438$, $8.6438$, $9.6438$, respectively. These scenarios with the same probability distribution and different $N$ (twice between each one) must to have twice the Anonymity degree comparing each one with the next one, but it is not happening because entropy's logarithmic function is not linear.


\subsection{Proposal}

We propose to use two indexes to measure Anonymity, each one to establish the levels of Anonymity's characteristics: One to measure the anonymous set size(we can use $N$ or $1/N$, where $N$ is the number of the elements), and one to measure uniformity index of probability distribution function assigned by the attacker. To measure the uniformity index we propose to use two metrics: the MSE - Mean Square Error and/or the JSD - Jennsen-Shannon Divergence.

\subsubsection{Root Squared Mean Error - RSME}

This term is used to estimate variance's error, this error is the residual sum of squares divided by the number of degrees of freedom. In regression analysis, it's an observed quantity given a particular sample, it's sample-dependent. Besides, this term is often referred to as "out-of-sample mean squared error": the mean value of the squared deviations of the predictions from the true values, over an out-of-sample test space, generated by a model estimated over a particular sample space. This also is an observed quantity, and it varies by sample and by out-of-sample test space.

\begin{equation}
RSME=\frac{\sqrt{(\bar{X}-X)^{2}}}{n(n-1)}
\end{equation}


In our case, we can use $p_{i}=\frac{1}{N}$ (probabilities in a uniform distribution) to represent $\bar{X}$, and $p_{i}$ is the probability assigned to the attacker to represent $X$. This measure permit to establish how far is the attacker's probability distribution from the uniform distribution.

\begin{equation}
RSME_a=\frac{\sqrt{\displaystyle\sum_{i=1}^N (\frac{1}{N}-p_{i})^{2}}}{N(N-1)}
\end{equation}

If one system has a $RSME_a\approxeq1$ that mean it provides bad Anonymity protection. 
If another system has a $RSME_a\approxeq0$ that mean it provides good Anonymity 
protection. But we have to look the set size to definitively take a real 
perspective of the Anonymity degree.

\subsubsection{Jennesen-Shannon divergence}

The Jensen-Shannon divergence is a popular method of measuring the similarity between two or more probability distributions. It is based on the Kullback-Leibler divergence, with the notable (and useful) difference that it is always a finite value. The square root of the Jensen-Shannon divergence is a metric to measure one Anonymity index: uniformity index of probability distribution function.

\begin{equation}
JSD(P_{1},P_{2})=H\left(\displaystyle\sum_{i=1}^2 \pi_i P_i\right)-\displaystyle\sum_{i=1}^2 \pi_i P_i
\end{equation}

\begin{equation}
JSD_a(P_{1},P_{2})=\sqrt{JSD(P_{1},P_{2})}
\end{equation}

where $\pi_i$ are the weights for the probability distributions  $P_1,P_2$, in this case $\pi_i=1, \nabla i=\{1,2\}$, and $H(P)$ is the Shannon entropy for distribution $P$. In this case, $P_1$ is a uniform distribution and $P_2$ is attacker's probability distribution.

With this result we can use both indexes to represent anonymity level o degree.


\subsubsection{Results}
\begin{description}
  \item[Option 1:] Anonymity degree ($AD$)using MSE to measure 
  uniformity index of probability distribution function and 
  $1/N$ to measure anonymity set size.\\

  \begin{center}$AD =  1 / N \pm MSE_a$\end{center}
  \item[Option 2:] Anonymity degree using JSD to measure uniformity 
  index of probability distribution and $1/N$ to measure anonymity set size.\\

  \begin{center}$AD =  1 / N \pm JSD_a$\end{center}
\end{description}

In both cases, the uniformity index and the set size are expressed separately and don't have the linearity problem.

\subsubsection*{Acknowledgments.}
This work was supported by the Ministerio de Industria, Turismo y Comercio (MITyC, Spain) through the Project Avanza Competitividad I+D+I TSI-020100-2010-482 and the Ministerio de Ciencia e Innovaci?n (MICINN, Spain) through the Project TEC2010-18894/TCM. Rodolfo Leonardo Sumoza Matos is also supported by the Programme Al$\beta$an, the European Union Programme of High Level Scholarships for Latin America, scholarship No. E07D401826VE.


\begin{thebibliography}{}

\bibitem{terminology}
Pfitzmann, A.,  Hansen, M.: Anonymity, Unobservability, and Pseudonymity: A Consolidated Proposal for Terminology. http://dud.inf.tu-dresden.de/Anon\_Terminology.shtml, (2000)

\bibitem{diaz01}
Diaz, C., Seys, S., Claessens J., Preneel, B.: Towards measuring anonymity. In: Proceedings of Privacy Enhancing Technologies Workshop (PET'02) - Springer LNCS 2482. pp. 54-68, (2002)

\bibitem{serj01}
Serjantov, A., Danezis, G.: Towards an Information Theoretic Metric for Anonymity. In: Proceedings of Privacy Enhancing Technologies Workshop (PET'02) - Springer LNCS 2482. (2002)

\bibitem{shannon}
Shannon, C.: The mathematical theory for communicactions. In: Bell Systems Technical Journal. pp. 30:50-64, (1948)

\bibitem{yuxin}
Deng, Y., Pang, J., Wu, P.: Measuring Anonymity with Relative Entropy. In: Proceedings of the 4th International Workshop on Formal Aspects in Security and Trust (FAST'06), Lecture Notes in Computer Science 4691. pp. 65-79, Springer, (2007)

\bibitem{combinatorial}
Edman, M., Sivrikaya, F., Yener, B.: A Combinatorial Approach to Measuring Anonymity. In: In Intelligence and Security Informatics. pp. 356-363, (2007)

\bibitem{revisiting}
Gierlichs, B., Troncoso, C., Diaz, C., Preneel, B., Verbauwhede, I.: Revisiting A Combinatorial Approach Toward Measuring Anonymity. In: Workshop on Privacy in the Electronic Society (WPES 2008), V. Atluri and M. Winslett (Eds.), pp. 111-116,  ACM Press, (2008)

\bibitem{berthold}
Berthold, O., Pfitzmann, A., Standtke, R.: The Disavantages of Free Mix Routes and How to overcome them. In: Hannes Federath (Ed.), Proceedings of Privacy Enhancing Technologies Workshop (PET'01), Lecture Notes in Computer Science. pp. 30-45, Springer-Verlag, (2001)

\bibitem{reiter}
Reiter, M., Rubin, A.: Crowds: Anonymity for Web Transactions. In: ACM Transactions on Information and System Security. vol. 1, no. 1, (1998)

\bibitem{vernier}
Vernier, D., and Gastineau, J.: What are Mean Squared Error and Root Mean Squared Error?. Article \#104. http://www.vernier.com/ (2011)

\bibitem{jianhua}
Jianhua, L.: Divergences Measures Based in Shannon Entropy. IEEE Transactions on Information Theory. vol. 37, no. 1 (1991)


\end{thebibliography}