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

\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, rlsm:mixminion, rlsm:diaz-mixes, rlsm:tor-design}, las características de los Colonias Artificiales de Hormigas utilizadas en las redes de telecomunicaciones \cite{rlsm:antnet, rlsm:ants-white, rlsm:ants-loadbalancing}, se propone seleccionar las rutas de los mensajes de forma pro\-ba\-bi\-lís\-ti\-ca, 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}

Este trabajo propone el uso de un sistema de medición para Anonimato basado en las características de sus propiedades principales: el índice de uniformidad de la distribución de probabilidad y el tamaño del conjunto anónimo. En las propuestas previas, la medida más ampliamente utilizada es la entropía, un índice utilizado y propuesto en la Teoría de la Información, el cual tiene algunos inconvenientes con respecto a la medición del Anonimato según la propiedades mencionadas, en primer lugar dichas propiedades no se representan directa y explícitamente con este índice, y al ser un índice logarítmico, no representa de forma adecuada comportamientos lineales en el Anonimato. Para medir el índice de uniformidad se propone utilizar el criterio del error cuadrático mínimo y como segunda propuesta se plantea utilizar el criterio de divergencia de Jensen-Shannon. Para medir el tamaño del conjunto anónimo se propone utilizar una función de N (número de entes del conjunto anónimo).

\subsection{Introducción}
Los sistemas de medición utilizados para cuantificar los niveles de Anonimato de los sistemas, mecanismos y herramientas aun se consideran un problema abierto. Se han propuesto algunas alternativas para este propósito, y la que más ampliamente se ha utilizado es la que se basa en una medida utilizada en la Teoría de la Información: la entropía, sin embargo ésta no representa explícitamente las características fundamentales del Anonimato: el tamaño del conjunto anónimo y el índice de uniformidad de la distribución de probabilidad vinculada al conjunto anónimo. En este trabajo, se propone utilizar como alternativa dos índices para la medición del Anonimato, y que explícitamente representen sus principales características. Por un lado el tamaño del conjunto anónimo puede ser representado a través de una función de N (el número de entes que componen al conjunto) y el índice de uniformidad puede ser representado utilizando un de los siguientes indicadores: el Error Cuadrático Medio (RMSE por sus siglas en inglés) o el criterio de divergencia de Jensen-Shannon (CDJs por sus siglas en inglés).


En Pfiztmann et al. \cite{terminology} establecieron una terminología ampliamente utilizada para estandarizar los términos utilizados en el contexto del Anonimato, en la cual ésta establece que un sujeto es anónimo cuando no puede ser diferenciado de los otros sujetos pertenecientes al mismo conjunto, denominado el conjunto anónimo. Describiendo el Anonimato en esto términos, se establece que sus niveles se incrementan si el tamaño del conjunto anónimo crece y cuando la distribución de probabilidad que establece un atacante sobre los miembros de ese conjunto anónimo tiende a ser uniforme. La proximidad de una distribución de probabilidad cualquiera a una distribución uniforme es a lo que se le denomina el índice de uniformidad de la distribución de probabilidad.

En la mayoría de la documentación hasta ahora difundida se utiliza como medida de referencia una obtenida de la Teoría de la Información: la entropía, y puede verse su representación tal como la definió Shannon en \cite{shannon}. Esta propuesta fue discutida en los trabajos de Díaz et al. \cite{diaz01} y Serjantov et al. \cite{serj01}, y desde entonces ha sido utilizada como base de medición en varios otros trabajos como el de Deng et al. \cite{yuxin}, Edman et al. \cite{combinatorial} y Gierlichs et al. \cite{revisiting}. Sin embargo, esta medida no representa explícitamente las caracaterísitcas que describen al Anonimato y que fueron explicadas previamente, particularmente el índice de uniformidad. 

\subsection{Trabajos Relacionado}
Se han hecho varias propuestas para cuantificas el grado o nivel de Anonimato provisto por los sistemas anónimos. En \cite{reiter} definen el grado de Anonimato como $1 - p$, donde $p$ es la probabilidad asignada por el atacante a un sujeto particular. En \cite{berthold} definen el grado de Anonimato como $A=\log_2(N)$, donde $N$ es el número de sujetos (usuarios) del sistemas. Este grado solo depende del número de usuarios del sistema, y no toma en cuenta la información que el atacante puede obtener a través de la observación del sistema o por otros medios. En \cite{diaz01} y \cite{serj01} proponen medir la información que obtiene el atacante, considerando el conjunto completo de usuarios la probabilidad que le asigna, y para ello como medida proponen la entropía utilizada en la Teoría de Información (usan la entropía definida por Shannon en \cite{shannon}). Ninguna de las propuestas anteriores representa explícitamente el tamaño del conjunto anónimo y el índice de uniformidad. Además en \cite{diaz01} proponen utilizar un grado de anonimato normalizado, pero esta medida puede alcanzar su máximo nivel de anonimato con un $N=2$ (tamaño del conjunto anónimo), contradiciendo una de las características fundamentales del Anonimato definida en \cite{terminology}: Los niveles de Anonimato se incrementan si se incrementa el tamaño del conjunto anónimo y el índice de uniformidad de la distibución de probabilidad. En \cite{yuxin}, \cite{combinatorial}, \cite{revisiting} utilizan la entropía de  Shannon con un enfoque diferente pero adoleciendo de los mismo problemas. Cuando utilizan la entropía, están utilizando una función logarítmica, lo que significa que no se tienen grados de medición lineales para comparar los sistemas. Por ejemplo, si se tienen 4 sistemas, y los atacantes no tienen ninguna información de sus usuarios, esto quiere decir, que le asignan una distribución de probabilidad uniforme a cada conjunto anónimo, esto es si el primer sistema tiene $N=100$ sujetos, el segundo tiene $N=200$ sujetos, el tercero tiene $N=400$ sujetos y el cuarto tiene $N=800$ sujetos, los grados de Anonimato utilizando la entropía son: $6.6438$, $7.6438$, $8.6438$, $9.6438$, respectivamente. Estos escenarios, con la misma distribución de probabilidad y con diferente $N$ (el doble del conjunto anterior) debería tener el doble del grado de Anonimato comparando cada uno con el siguiente, pero esto no sucede debido a que la entropía utiliza un función logarítmica y no lineal.


\subsection{Propuesta}

Se propone utilizar dos índices para medir el Anonimato, cada uno para establecer los niveles de cada característica fundamental del Anonimato: Uno para medir el tamaño del conjunto anónimo: $N$ o $1/N$, donde $N$ es el número de sujetos o elementos, y uno para medir el índice de uniformidad de la función de distribución de probabilidad asignada por el atacante. Para medir el índice de uniformidad se proponen utilizar una de las siguientes dos métricas: La raíz del error cuadrático medio (RSME) o el criterio de divergencia de Jennsen-Shannon (DJS).

\subsubsection{Raíz del Error Cuadrático Medio - RSME}

Este término se utiliza para estimar el error de la varianza, este es el error residual de las suma de los cuadrados divididos por el grado de libertad. En análisis de regresión, es una cantidad observada dada un muestra en particular, y depende de dicha muestra. Además, este término es referido al error fuera de la muestra: el valor medio de las desviaciones cuadráticas de las predicciones de los valores de verdad, sobre un espacio fuera de la muestra, generado por un modelo estimado sobre un espacio muestral particular. Esta también es una cantidad observada, y varía según la muestra y según el espacio fuera de la muestra probado.

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

En este caso, se propone utilizar $p_{i}=\frac{1}{N}$ (probabilidades en una distribución uniforme) para representar $\bar{X}$, y $p_{i}$, la probabilidad asignada por el atacante, se representa con $X$. Esta medida permite establecer la "distancia" de la distribución de probabilidad del atacante a la distribución uniforme. 

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

Si un sistema tiene un $RSME_a\approxeq1$, esto quiere decir que provee un muy bajo nivel de anonimato.
Si otro sistema tiene un $RSME_a\approxeq0$, quiere decir que provee un buen nivel de anonimato. Pero también se debe observar el tamaño del conjunto anónimo para tomar un visión real del sistema.

\subsubsection{Divergencia de Jennesen-Shannon}

La divergencias de Jensen-Shannon es método popular para medir la similitud entre dos o más distribuciones de probabilidad. Se basa el la divergencia de Kullback-Leibler, con la notable y útil diferencia que siempre da como resultado un valor finito. La raíz cuadrada de la divergencia de Jensen-Shannon es el índice que se propone para representar el índice de uniformidad en Anonimato.

\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}

donde $\pi_i$ son lo pesos para la distribuciones de probabilidad $P_1,P_2$, en este caso $\pi_i=1, \nabla i=\{1,2\}$, y $H(P)$ es la entropía de Shannon para la distribución $P$. Es este caso, $P_1$ es una distribución uniforme y $P_2$ es la distribución de probabilidad del atacante.

Con este resultado se obtienen dos índices para representar el grado o nivel de Anonimato:


\subsubsection{Resultados}
\begin{description}
  \item[Opción 1:] Grado de Anonimato ($AD$) utilizando RMSE para medir el índice de uniformidad de la distribución de probabilidad y $1/N$ para medir el tamaño del conjunto anónimo.\\
  \begin{center}$AD =  1 / N \pm MSE_a$\end{center}
  \item[Opción 2:] Grado de Anonimato ($AD$) utilizando JSD para medir el índice de uniformidad de la distribución de probabilidad y $1/N$ para medir el tamaño del conjunto anónimo.\\
  \begin{center}$AD =  1 / N \pm JSD_a$\end{center}
\end{description}

En ambos casos, el índice de uniformidad y el tamaño son expresados por separado pero no tiene el problema de linealidad de las otras métricas. 

\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}