# Encaminamiento cebolla

El encaminamiento cebolla o enrutamiento cebolla, en inglés onion routing, fue introducido por David M. Goldshlag, Michael Reed y Paul Syverson aplicando las ideas de las redes de mezclado de David Chaum a los sistemas de encaminamiento, para conseguir redes que preserven la privacidad (tanto del mensaje en si como de los interlocutores) de forma transparente a las entidades que se comunican. De esta forma podemos tener infraestructuras para comunicaciones privadas sobre una red pública.
Con este sistema las comunicaciones pueden ser bidireccionales, casi en tiempo real y pueden ser usadas para tráfico orientado a conexión o no.
A las redes que utilizan esta forma de encaminamiento se las llama redes cebolla (en inglés onion networks). Ejemplos de este tipo de redes, algunas de las cuales nunca han sido implementadas, son Freedom Network, Onion Routing, MixMaster, Babel, Mixminion, Zach Brown's Onion, PipeNet, IronKey, MorphMix, Tarzan y Tor, la más importante red que usa esta tecnología y que actualmente está desplegada en internet.

## Objetivo

El objetivo principal para el que se diseñó el encaminamiento cebolla es separar la identificación del enrutado de los mensajes y por tanto perseguir el enrutado anónimo (en inglés anonymous routing). Para enrutar no es necesario tener en todo momento identificado tanto el origen como el destino de la comunicación. Cuando hablamos de 'identidad' nos referimos a cualquier dato que ayude identificar a un individuo. Por ejemplo la dirección IP ayuda a identificar ya que a través de ella se puede obtener información como el usuario particular u organización a la que estaba asignada esa IP en ese momento o el país desde el que se envía el mensaje.
Para tener una buena protección de la identidad de los interlocutores, es necesario que la ruta de nodos por los que pasa el mensaje para ir desde el origen al destino, sea impredecible a priori y se oculte todo lo posible. Por esta razón se persigue que cada entidad solo conozca la entidad desde la que recibe el mensaje y la entidad a la que tiene que enviar el mensaje. Esto se puede aplicar no solo a los nodos enrutado sino también a las propias entidades que se comunican. El destino no tiene que saber la identidad del que se quiere comunicar con él. El origen de la comunicación puede no saber la identidad de la entidad con la que se quiere comunicar, son los definidos como servicios ocultos (en inglés hidden services). Los servicios ocultos no son soportados por la mayoría de sistemas de encaminamiento de cebolla. Sin embargo sí hay sistemas que los soportan como Tor.
Observar que para ocultar la ruta no es necesario confiar en todos los nodos de la ruta, teóricamente (si los nodos tuvieran un comportamiento ideal) con que hubiera un solo nodo confiable no comprometido, la privacidad de los interlocutores estaría garantizada debido a que sería imposible establecer correspondencia entre los mensajes que le llegan y los que salen de él.
Para que sea efectiva la protección de la identidad es necesario que se preserve la confidencialidad de la propia información que el origen quiere enviar al destino. Si no se hiciera, un simple análisis de tráfico podría identificar cual es el recorrido que hace cada mensaje desde el origen al destino.
Observar que el enrutado anónimo no asegura el que la entidad origen sea desconocida para la entidad destino. Esto se debe a que los protocolos de nivel superior pueden transmitir información sobre la identidad. Por ejemplo un servicio web puede usar cookies o simplemente pedir que nos identifiquemos. Cuando queremos un anonimato a nivel de aplicación es bueno configurar el cliente adecuadamente y protegernos usando proxys que modifican los contenidos en este sentido. Por ejemplo para conseguir más privacidad cuando navegamos por la web es recomendable configurar el navegador adecuadamente (ej. deshabilitando cookies, no permitiendo plugins Java o deshabilitando el historial) y redirigir el tráfico hacia un proxy web intermedio (Ej. privoxy o polipo) que nos filtre contenido que puede ser aprovechado para violar nuestra privacidad (ej. cookies o cabeceras HTTP que puedan ser usadas para identificar).

## Implementación

El encaminamiento cebolla aprovecha la idea de Chaum de esconder la relación entre el origen y el destino de una información encapsulando los mensajes en capas de criptografía de clave pública. Aplicando esta idea para implementar un modo de encaminamiento, lo que hacemos es transmitir mensajes con distintas capas de cifrado (por ese ligero parecido resultante y coincidente con ese interior enrollado del bulbo con un diagrama de la explicación de su viaje, a éstas redes se les conoce como 'de cebolla') sobre un camino compuesto por nodos de mezclado (mixes) convertidos ahora en routers (enrutador de cebolla) donde cada enrutador del camino lo que hace es descifrar ('pela' una capa de la cebolla), transmitir y reordenar los mensajes antes de transmitir al siguiente enrutador.
Cuando un enrutador descifra una capa obtiene una cabecera que puede interpretar y un fragmento cifrado (siguiente capa de la cebolla). A continuación el enrutador envía el fragmento cifrado al próximo salto de acuerdo al contenido de la cabecera y el estado interno del propio enrutador.

### Idea primigenia

En el encaminamiento cebolla se persigue que cada nodo intermedio (enrutador) conozca solo lo que es estrictamente necesario: La dirección de la entidad que le envía el mensaje y la dirección a la que tiene que redirigir el mensaje. Los mensajes que se intercambian los routers no tienen que proporcionar ninguna información adicional. De esta forma ningún enrutador intermedio sabrá quien es el emisor ni el destinatario de la comunicación. Por ser el último enrutador de la ruta el que directamente se comunica con el destinatario, este será el único que sabrá quien es el destinatario y el contenido del mensaje original que tenía que entregar.
Para conseguir este objetivo la idea original era seguir el siguiente esquema:
* El emisor origen de la comunicación establece una conexión de inicialización con un proxy de aplicación (en inglés Application Proxy) que convierte los mensajes del protocolo específico de la aplicación a un formato genérico que pueda ser manejado por los routers.
* A continuación el proxy de aplicación envía los mensajes a un Onion Proxy (se le suele llamar nodo OP), el cual decide la ruta hacia el destino y construye la estructura de datos que se va a enviar al siguiente nodo y a la que se llama onion ('cebolla' en inglés) o onion forward ('cebolla hacia adelante', para indicar el sentido de la comunicación). La estructura de datos tiene una capa cifrada por cada enrutador que vaya a formar parte del circuito.
    Si $E_{PK}({\rm {\langle datos\rangle )}}$ representa el cifrado usando la clave pública PK, $D_{SK}({\rm {\langle datos\rangle )}}$ representa el descifrado usando la clave privada y el onion proxy inicial decide que se va a usar la ruta <4,3,5> de routers, entonces el paquete que se envía al siguiente enrutador puede ser representado por:
       $E_{PK_{4}}({\mbox{direcciónderouter}}_{3},E_{PK_{3}}({\mbox{direcciónderouter}}_{5},E_{PK_{5}}({\rm {\langle datos\rangle )))}}$.
* La estructura de datos es enviada por el onion proxy al entry funnel (punto de entrada al canal). El cual es un onion enrutador (nodo OR) usado como punto de entrada a la red de encaminadores de la red cebolla. Este enrutador descifra el paquete (pela su capa de la 'cebolla') y obtiene la dirección del siguiente nodo OR en el camino del mensaje.
* A continuación el entry funnel coge el resto del mensaje y lo manda al siguiente onion router.
* Así se continúa hasta llegar al onion router que actúa como nodo de salida al que llama exit funnel. Este nodo descifra y obtiene el mensaje que originalmente produjo el proxy de aplicación. Este mensaje se envía a la dirección destino especificada.
* Cuando el receptor envía una respuesta a un mensaje particular, el exit funnel lo convierte al protocolo genérico, lo cifra con su clave privada y lo envía de vuelta al onion router del que le vino el mensaje original.
* Cada onion router opera de forma similar cifrando la respuesta y lo envía de vuelta obteniendo una estructura de datos, a la que se llama reply onion o onion forward, que tiene la siguiente estructura:
       $E_{SK_{4}}(E_{SK_{3}}(E_{SK_{5}}({\rm {\langle datos\rangle )))}}$
* El mensaje llega al onion proxy el cual descifra usando las claves públicas de los onion routers que escogió como camino del mensaje original.

### Problemas

Actualmente hacer que los sistemas que usan encaminamiento cebolla sean seguros es un área de investigación en activo. Se están desarrollando muchos estudios de mejoras, pero se siguen teniendo puntos débiles que hay que subsanar. Aunque no hay propuesta definitiva se han desarrollado una serie de técnicas que han demostrado ser efectivas para mejorar las prestaciones y el grado de seguridad.

#### Confusión entre paquetes de entrada y de salida en los routers

Si analizamos el tráfico de entrada y salida de cada enrutador podemos llegar a establecer una correspondencia y establecer qué paquete de salida se corresponde con cierto paquete de entrada. Aplicando este análisis a todos los routers podemos llegar a establecer quien se está comunicando con quien. Para evitar que se pueda llegar a este tipo de conclusiones se pueden tomar distintas estrategias:
* Introducir retardos artificiales en el tiempo de proceso de los mensajes en los routers
* Introducir tráfico de relleno, esto es, paquetes que tienen información inútil y que su única función es confundir al posible atacante.
* Hacer que el tráfico se realice a través de mensajes de tamaño fijo. A estos paquetes se les suele llamar células. Si los mensajes que circulan por la red no son de tamaño fijo nos podríamos basar en este tamaño para hacer conjeturas sobre que paquete de entrada se corresponde con qué paquete de salida.
* Hacer que los paquetes, en lugar de viajar en solitario, viajen agrupados y junto a ellos viaje información de relleno e información de control (por ejemplo instrucciones para los retardos en los nodos). Todo ello se encapsula en un paquete cifrado. A esta forma de encaminamiento se la conoce como encaminamiento de ajo. Este sistema lo usan por ejemplo I2P o Perfect Dark.

#### Proxy de aplicación

En este sistema se requiere un proxy de aplicación para cada protocolo de aplicación soportado. Esto conlleva mucho trabajo y provoca que algunos proxys no sean escritos nunca y por tanto algunas aplicaciones nunca sean soportadas. Por este motivo, en posteriores diseños de redes que usan encaminamiento o enrutación cebolla (Ej. TOR), se suele usar un protocolo como interfaz genérico (Ej. SOCKS) de forma que toda aplicación con soporte en ese protocolo genérico puede usar la red cebolla para realizar comunicaciones anónimas sin necesidad de modificaciones adicionales. Ese protocolo genérico tiene que dar soporte a distintos protocolos y al final los múltiples posibles protocolos de entrada se convierten en uno solo. Por ejemplo el protocolo SOCKS permite tener por debajo cualquier tipo de tráfico TCP/IP.

#### Posible reinyección de mensajes

Los sistemas con encaminamiento de cebolla son vulnerables a ataques de replay que se basan en capturar mensajes y luego los reinyectan en la red con el objetivo de sobrecargarla y que deje de funcionar (ataque de denegación de servicio). Para evitar este tipo de ataques es habitual que los routers detecten cuando un paquete ya ha sido procesado (y por tanto descarten ese paquete) y que los propios mensajes tengan un tiempo de validez que una vez agotado permita que los routers eliminen esos mensajes.

#### Publicación de datos de configuración

Observar que los nodos necesitan saber una serie de valores de configuración (Ej. routers activos, direcciones y claves públicas). Si esos valores de configuración son fijos, podemos decidir que, como parte de la configuración del nodo, se cargue un fichero con esa lista de valores y a partir de ahí se utilizan.
Sin embargo en la realidad esto no es operativo ya que los valores de configuración cambian (por ejemplo caducan las claves asimétricas), se añaden o desaparecen nodos etc. Por eso es necesario el uso de un sistema que permita tener disponible para los distintos nodos esos valores de configuración necesarios para el correcto funcionamiento. Algunos sistemas publican esa información mediante un sitio Web. Otros, como Tor o Mixminion, usan un servicio de directorio para publicar esa información. Los servidores que proporcionan estos servicios son autoridades confiables y se encargan de mantener el servicio actualizado y de distribuir la información, normalmente de forma firmada. Esta información firmada a veces también puede ser distribuida a modo de mirror por otros routers de la red para así reducir la carga del servicio de directorio.
Observar que tener un servicio para dar valores de configuración puede ser usado para protegerse contra ataques basados en introducir en la red routers malintencionados. Ello es debido a que cada enrutador para entrar efectivamente en la red (se publiquen sus datos de configuración) tiene que ser aprobado por el proveedor del servicio.

#### Políticas de entrada y salida

Algunos sistemas (Ej. Tor) permiten establecer un conjunto de restricciones de funcionamiento del nodo en el caso de que este sea el último nodo de un circuito de datos. A esto se le suele llamar políticas de salida o en inglés exit policies. Por ejemplo puede definir una lista de posibles direcciones IP o una serie de puertos a los cuales tiene que estar dispuesto el nodo de salida para llevar el tráfico. La exit-policy puede ser variable a lo largo del tiempo.
Análogamente se pueden establecer políticas de entrada o entry policy. Por ejemplo podríamos usarlas en una organización para obligar a que se use un punto de entrada a la red de encaminamiento cebolla.
Observar que las políticas de salida son críticas en infraestructuras distribuidas de voluntarios ya que cada OR puede restringir el tipo de tráfico que puede salir de su nodo.

#### Control de congestión

En las redes del mundo real es necesario balancear la carga y realizar control del flujo. Esto provoca que sea necesarias comunicaciones de control entre los nodos y una visión del tráfico de forma global. Para ello algunos sistemas (Ej. Tor) permite a los nodos en los bordes de la red detectar congestiones y enviar allí menos datos hasta que esto se haya subsanado.

#### Integridad extremo a extremo

Muchos sistemas (Ej. Tor) proveen integridad extremo a extremo para evitar que algún nodo del circuito pueda cambiar el contenido de los mensajes de datos que pasan por ellas, para por ejemplo alterar el servidor web al que se está pidiendo conexión o cualquier otra utilidad. Esta integridad se verifica antes de que los datos salgan de la red.

#### Compartición de circuitos entre distintos flujos

Para mejorar la eficiencia y el anonimato algunos sistemas (Ej. Tor) permiten que varios flujos sean multiplexados sobre el mismo circuito de comunicación.

#### Número de saltos variable

Algunos sistemas (Ej Tor) permiten a los iniciadores cambiar parcialmente la topología del circuito. Por ejemplo se puede aprovechar para permitir la salida del circuito usando un nodo intermedio (Leaky-pipe circuit topology) y de este modo frustrar ataques que se basan e detectar y atacar el último nodo de un circuito.

#### Ineficiencia

Utilizar exclusivamente criptografía de clave pública para cifrar cada capa de la cebolla es muy costoso a nivel de computación. Esto es especialmente importante para aplicaciones de baja latencia. Por esta razón en muchos casos es necesario el uso de criptografía simétrica la cual es, en general, mucho más 'barata' computacionalmente.
Para poder usar criptografía simétrica es necesario que todas las partes que se comunican compartan una clave que mantienen en secreto. Se puede aprovecha la criptografía de clave pública para en un primer paso establecer esta clave (simétrica) compartida y que a partir de ahí se use ésta a modo de clave de sesión. Por esta razón, en estos casos, se dice que usamos la criptografía de clave pública, computacionalmente más cara, para establecer un circuito (ruta) de claves simétricas compartidas. Una vez establecido el circuito, este puede ser utilizado para ir transportando los mensajes usando criptografía simétrica. El circuito construido puede usarse de forma bidireccional. Un ejemplo de esquema usando claves simétricas podría ser el siguiente:
* Se establecen una serie de claves simétricas compartidas entre los routers.
* A continuación los datos son enviados 'envueltos' en capas creadas usando las claves simétricas. Cada enrutador quitará una capa de cifrado de los datos que le pasan, usando la clave simétrica que obtuvo cuando se estableció el circuito. De esta forma los datos original emergerán en claro al final del circuito.
* El destinatario puede responder con otro mensaje. Este mensaje en cada nodo se le añadirá una capa de cifrado simétrico y luego se mandará al siguiente. Cuando llega al destino (el iniciador de la comunicación) llegará como una estructura de datos con las distintas capas de cifrado. El iniciador de la comunicación, para obtener el mensaje de vuelta en claro, quita las distintas capas descifrando con las distintas claves simétricas utilizadas.
Entre los enfoques que se han ido proponiendo para conseguir encaminamiento de cebolla, se han propuesto distintas formas de establecimiento de circuito usando claves simétricas construidos a partir de criptografía de clave pública. Sin embargo los sistemas utilizados no son la panacea teniendo cada uno sus propios inconvenientes por lo que se considera un problema abierto habiendo actualmente nuevas propuestas de formas de establecer los circuitos, algunos usando solo criptografía asimétrica.

### Uso de la criptografía para implementar el encaminamiento cebolla

En una red que usa encaminamiento cebolla la decisión más importante es el tipo de criptografía que se usa y la forma en que esta se usa. Esto se debe a que esta decisión será crucial en la eficiencia y en la seguridad del sistema. Veamos algunos de los ejemplos más representativos y sus repercusiones en la seguridad

#### Enfoque usando criptografía asimétrica tradicional

Sería el enfoque utilizado en la idea primigenia.
Este sistema es vulnerable a ataques basados en capturar el tráfico. Efectivamente, supongamos que un atacante puede grabar todos los datos que intercambian los routers. Si finalmente el atacante consigue comprometer todos los routers (acceder a sus claves privadas) entonces este puede descifrar todo el tráfico almacenado anteriormente. Para acotar este problema podríamos cambiar periódicamente las claves (pública y privada) de los routers. Para ello estableceríamos un periodo de tiempo a la finalización del cual las claves caducarían y sería necesario establecer nuevas claves. La clave pública habría que difundirla y la antigua clave privada se destruiría para que no pudiera ser obtenida nunca, asegurando así la persistencia de la seguridad del tráfico que se realizó usando la antigua clave. Serie bueno que el cambio de claves fuera frecuente ya que esto limitaría la cantidad de tiempo que tiene A para comprometer B y C, pero a la vez requeriría que los routers del sistema contactaran frecuentemente con un sistema que les actualizara las nuevas claves lo que llevaría a problemas de escalabilidad.

#### Enfoque usando claves simétricas de sesión establecidas desde el primer enrutador

Algunos sistemas, por ejemplo Onion Routing, establecen circuito de claves simétricas, a partir de criptografía de clave pública, mediante una estructura de datos con capas que se pueden representar por el siguiente esquema (suponiendo que estamos en una camino de encaminamiento con tres saltos R$_1$, R$_2$, R$_3$):
       $E_{PK_{R_{1}}},(K_{1},R_{2},E_{PK_{R_{2}}},(K_{2},R_{3},E_{PK_{R_{3}}},(K_{3},{\mbox{Pad}}))))))$
    donde
       $PK_{R_{i}}$ es la clave pública $R_{i}$
       $R_{i}$ es la dirección del nodo $R_{i}$
       $K_{i}$ es un material que permite establecer la/s clave/s de sesión compartida (puede haber una para cada sentido de la comunicación) entre el origen de la comunicación (el iniciador) y $R_{i}$ (en inglés se le llama key seed material).
Observar que la capa final se identifica porque no contiene ni dirección destino, ni datos con significado para ser transmitidos. Este sistema es el que se usa por ejemplo en Onion Routing. En este sistema, en las capas de cebolla, aparece lo que se llama key seed material el cual consiste en 128 bits que aplicándole SHA producen las claves simétricas que luego se usan para establecer las claves simétrica. Onion Routing introduce además en su formato de mensaje un campo que permite meter como parámetro el algoritmo de cifrado simétrico que se va a usar en cada sentido de la comunicación. El sistema soportaba DES OFB y RC4. Dependiendo del algoritmo que se seleccione se calcula la clave a partir del key seed material de distinta forma. En este sistema el número de mensajes necesarios para establecer el circuito entre los routers de la red es igual al número de routers que intervienen. Por ejemplo si A se quiere comunicar con B a través de R$_1$,R$_2$ y R$_3$ y en ese orden, son necesarios los siguiente mensajes:
* A-R$_1$
* R$_1$-R$_2$
* R$_2$-R$_3$
La principal desventaja de este enfoque es que no provee de perfect forward secrecy. Supongamos que un circuito se construye desde el iniciador con la secuencia de nodos A,B,C y que A es un enrutador malicioso y por tanto el atacante puede descifrar todo lo que pasa y ha pasado por él. Si A graba todo el tráfico y en el último momento se compromete B (el cual sabe quién es el último nodo C), entonces se compromete C y A puede saber con quien se está comunicando el iniciador.
Una posible mejora para este problema es cambiar frecuentemente las claves públicas de cada nodo. Esto limita la cantidad de tiempo que tiene A para comprometer B y C, pero requiere que los routers del sistema cotacten frecuentemente con un sistema que les actualice las nuevas claves lo cual puede tener problemas de escalabilidad.

#### Enfoque telescópico

Otros sistemas (Ej Tor y Cebolla) realizan una construcción incremental e interactiva del circuito, a la que llaman enfoque telescópico (del inglés telescopic approach).
En concreto Tor se apoya en el Tor Authentication Protocol (siglas TAP), cuya seguridad fue probada en el modelo de oráculo aleatorio. Tor lo que hace es realizar una ejecución secuencial de múltiples instancias de TAP. Para establecer el circuito realiza una autenticación RSA (criptografía de clave pública) de un solo sentido (ya que el iniciador nunca se auténtica) y se aprovecha el protocolo de establecimiento de claves de Diffie-Hellman para establecer una clave simétrica entre cada enrutador de la ruta y el iniciador de la comunicación. Para ello se utiliza el circuito parcialmente construido hasta ese momento. Podemos decir que en cada tramo sucesivo del circuito se realiza una negociación interactiva de claves (protocolo de establecimiento de claves de Diffie-Hellman). Por ejemplo, cuando se establece una clave para el primer salto, el iniciador de la conexión tunela a través de esa conexión para establecer otra clave de sesión con el segundo enrutador y así sucesivamente. Cuando el circuito ya no se usa, las claves de sesión se destruyen.
En el TAP la clave pública del nodo solo se utiliza para iniciar la comunicación durante la cual se establece la clave temporal de sesión vía el protocolo de establecimiento de claves de Diffie-Hellman. Las claves se forman a partir del intercambio de mensajes en lugar de ser enviadas de forma cifrada. Por tanto, una vez que la sesión finalice (el circuito ha dejado de usarse) y se destruyan las claves de sesión, si se compromete un enrutador (se obtiene su clave privada) esto no permite al adversario recuperar las claves de sesión eliminadas y descifrar así el tráfico cifrado bajo esa clave que pudiera tener almacenado. Por tanto tenemos perfect forward secrecy.
Por otra parte ya no es necesario almacenar hashes de las estructuras de datos previamente procesadas para evitar ataques de replay. Reinyectando uno de los mensajes del handshake del protocolo de establecimiento de claves de Diffi-Hellman provoca unos resultados de clave de sesión diferentes y por tanto ya no es un ataque efectivo.
Otra ventaja de estos sistemas es que son más robustos frente a nodos que no acepten conexiones, siendo la información que tiene que aportar el sistema, por ejemplo mediante un servicio de directorio, menos importante. Por ejemplo si el tercer enrutador intermedio está caído durante el establecimiento del circuito, los dos primeros y el iniciador solo tienen que escoger un nodo alternativo para sustituirlo.
En este sistema el número de mensajes necesarios para establecer el circuito entre los routers de la red es de complejidad O(n$^2$). Por ejemplo si A se quiere comunicar con B a través de R$_1$,R$_2$ y R$_3$ y en ese orden, son necesarios los siguiente mensajes:
* A-R$_1$
* A-R$_1$ (tunelado de conexión con R$_2$)
* R$_1$-R$_2$
* A-R$_1$ (tunelado de conexión con R$_3$)
* R$_1$-R$_2$ (tunelado de conexión con R$_3$)
* R$_2$-R$_3$
    Observar que el establecimiento de la conexión tiene una complejidad O(n$^2$) para el número de mensajes transmitidos como para el número de cifrados/descifrados. Esta forma de trabajar en sistemas de baja latencia suele ser solo viable si el número de nodos intermedios se mantiene bajo. Por ejemplo cuando se usa Tor se suele restringir el número de nodos intermedios a 3.
Øverlier and Syverson mejoran la eficiencia de Tor usando un protocolo de establecimiento de clave Diffie-Hellman medio certificada. Para ello confía en parámetros de Diffie-Hellman precalculados cuyos componentes públicos son publicados y actualizados regularmente por cada enrutador en el servicio de directorio. Los clientes pueden entonces generar sus propios parámetros de Diffie-Hellman y, usando la información publicada por los routers, calcular las claves de sesión que se compartirán con los routers en los circuitos. Estas propuestas reducen el coste de computación pero mantienen la complejidad de comunicación en O(n$^2$).

#### Enfoques basados en criptografía asimétrica no basada en PKI

Se han hecho diversas propuestas que persiguen establecer los circuitos en un solo paso para reducir la sobrecarga de coste de computación y de comunicaciones que tienen los sistemas que se basan en establecer circuitos en varios pasos (Enfoque telescópico).
Sin embargo el enfoque telescópico proporciona buenas propiedades como el secreto-hacia-adelante (en inglés forward-secrecy). Informalmente, se dice que esta propiedad es la que se da cuando se garantiza que las propiedades de seguridad permanecen incluso si el adversario puede corromper todas las partes que intervienen y aprender sus claves secretas después de que éstas hayan caducado. Sobre la base de esta propiedad podemos precisar aún más y diferenciar así entre dos propiedades:
* Se dice que hay secreto-hacia-adelante inmediato (en inglés immediate forward-secrecy) si se mantiene el secreto-hacia-adelante de todas las sesiones pasadas que han finalizado incluso si un adversario compromete un enrutador. Observar que el secreto permanece aunque las claves privadas no hayan cambiado porque están en su periodo de validez. Este tipo de propiedad es satisfecha por Tor usando su Enfoque telescópico.
* Se dice que hay secreto-hacia-adelante eventual (en inglés eventual eventual forward-secrecy) si se mantiene el secreto-hacia-adelante aunque un adversario pueda corromper un enrutador después de un específico periodo de tiempo (después de que las claves privadas de los routers hayan cambiado).
Se ha demostrado que es imposible obtener secreto-hacia-adelante immediato usando establecimiento de circuito con un solo paso (de un modo no interactivo). Por tanto lo que intentamos buscar es secreto-hacia-adelante eventual.
Es evidente que es posible conseguir secreto-hacia-adelante eventual cambiando frecuentemente las claves asimétricas de los routers (criptografía asimétrica) de forma que se minimice el periodo de tiempo, y por tanto el impacto, de que se comprometiera la clave de un enrutador. Una vez que se tiene la clave privada de un enrutador entonces el atacante solo puede violar la seguridad de la comunicación en el periodo de validez de esa clave. Implementar esta idea usando una PKI tradicional (cambiando las claves privada/pública asociada a cada enrutador) es muy complicado en la práctica ya que fuerza a los enrutador a generar nuevas claves, a generar su correspondiente certificado válido, a publicar dicho certificado y a que los usuario repetidamente obtengan dicho certificado.
Para conseguir secreto-hacia-adelante eventual de una forma más eficiente se han hecho varias propuestas usando criptografía asimétrica que no usa PKI: criptografía basada en identidad, criptografía sin certificado.

##### Usando criptografía basada en identidad

Aniket Kate y otros han propuesto usar esquemas de criptografía basada en identidad para construir un protocolo con encaminamiento cebolla al que han llamado PB-OR (del inglés pairing-based onion routing). En la criptografía basada en identidad las claves públicas y las claves privadas de las partes se obtienen a través de un confiable Centro de Generación de Claves o KGC (del inglés Key Generation Center) que suministra claves con un periodo de validez determinado. PB-OR usa la idea original del encaminamiento cebolla para cifrar mensajes usando la clave pública del enrutador, con la peculiaridad de que en este caso las claves son suministradas mediante el KGC y tienen asociadas el periodo de validez. Este sistema tiene dos problemas:
* La existencia de un KGC confiable hace que este pueda descifrar cualquier mensaje de la red (key scrow problem). Esto puede ser resuelto utilizando por ejemplo un KGC distribuido. Construir este sistema no es para nada trivial y tiene sus propios problemas.
* Se requiere que los routers interactúen con el KGC para obtener las nuevas claves secretas cada vez que acaba el periodo de validez. Aunque tienen la ventaja de no tener que gestionar y verificar certificados.
Mario Catalano, Mario Di Raimondo, Dario Fiore, Rosario Gennaro y Orazio Puglisi han propuesto un sistema, al que llaman fs-ID-OR, que usa un sistema de cifrado basado en identidad seguro hacia adelante (siglas fs-IBE) para las claves públicas de los routers. El circuito se forma de forma no interactiva y en un solo paso. Este sistema logra eventual forward secrecy sin tener que usar KGC (como necesitabla PB-OR), ni tiene que comunicar ninguna clave pública ya que permanece estática (como necesitaban PB-OR o CL-OR). Al no ser interactivo, tampoco tiene una complejidad cuadrática sino lineal (como tenía el enfoque telescópico). El problema que tiene este sistema es que la KGC tiene que ser confiable ya que puede descifrar cualquier mensaje (key scrow problem). Para resolver este problema propone hacer modificaciones al esquema usando Criptografía sin certificados o PKI.

##### Usando criptografía sin certificados

Catalano y otros han sugerido usar criptografía sin certificados y han definido dos protocolos con encaminamiento cebolla (CL-OR y 2-CL-OR). Sin embargo este sistema resucita los problemas de escalabilidad que tenían los sistemas que usaban PKI con claves cambiantes. En efecto, cada enrutador tiene que generar una clave asimétrica y comunicarse con otra entidad, por ejemplo un servidor de directorio, para que publique la parte pública y que pueda ser descargada por el resto de usuarios para su uso.

### Anonimato en la localización de la entidad que responde

Las redes con encaminaminamiento cebolla tradicionalmente proporcionan anonimato en la localización del que inicia la comunicación (el iniciador). Sin embargo también es interesante perseguir el anonimato en la localización de la entidad que responde. Ha habido algunas propuestas interesantes para conseguir esto. Veamos algunas de ellas.

#### Reply onions

La red Onion Routing disponía de lo que llamaba reply onion. La red Onion Routing usa un enfoque usando criptografía simétrica establecida a través de las claves asimétricas para establecer una conexión. Esta conexión se puede aprovechar para transmitir mensajes en ambos sentidos de la comunicación.
Si A se quiere comunicar con B a través de los nodos W, X, Y y Z, el onion que construiría el nodo W y que enviaría a X tendría la siguiente estructura:
       $PK_{X}({\mbox{exptime}}_{X},Y,F_{fx},K_{fx},F_{bx},K_{bx},PK_{Y}({\mbox{exptime}}_{Y},Z,F_{fy},K_{fy},F_{by},K_{by},PK_{Z}({\mbox{exptime}}_{Z},{\mbox{NULL}},F_{fz},K_{fz},F_{bz},K_{bz},{\mbox{PADDING}})))$
donde:
* $PK_{X}({\mbox{exptime}}_{X},Y,F_{fx},K_{fx},F_{bx},K_{bx},\langle {\mbox{datos}}\rangle )$ indica cifrar con la clave pública de X un tupla formada por el tiempo de caducidad, el destinatario del siguiente salto, el par de configuración de la comunicación hacia (forward) X $(F_{fx},K_{fx})$ y el par de configuración de la comunicación desde (backward) X $(F_{b}x,K_{b}x)$.
* Una comunicación unidireccional queda configurada por un par formado por $(F,K)$ que especifican el algoritmo de cifrado a usar (F) y la clave (K).
* Si el destinatario es NULL entonces quiere decir que no hay enrutador siguiente.
Sin embargo ¿Qué pasa si el iniciador espera una respuesta que puede demorarse bastante tiempo?. Por ejemplo, esta situación se puede dar para responder a correos electrónicos anónimos enviados usando la red. Una solución obvia es mantener la conexión abierta para permitir esa respuesta. Sin embargo esto lleva a un desaprovechamiento de recursos. Otra solución es utilizar reply onions después de que la conexión original haya sido terminada.
Los reply onions construyen un circuito desde el destinatario hasta el iniciador de una petición anterior en la que ese iniciador quería mantener su localización oculta. El reply onion es creado por el iniciador en la comunicación original y se lo envía al destinatario para que pueda posteriormente usarlo. Posteriormente ese 'reply onion' es enviado por el destinatario al enrutador que le sirvió la petición para que llegue hasta el iniciador original para así establecer la conexión. Una vez establecida la conexión cada enrutador funciona de la misma forma que actúa con un 'onion' normal. La estructura de datos del 'reply onion' es similar que la de los 'onion' normales y los routers la procesan de la misma forma.
Usando la misma notación que antes, el 'onion replay' para que B responda a A usando la ruta W, Z, Y y X tendría la siguiente estructura:
       $PK_{Z}({\mbox{exptime}}_{Z},Y,F_{bz},K_{bz},F_{fz},K_{fz},PK_{Y}({\mbox{exptime}}_{Y},X,F_{by},K_{by},F_{fy},K_{fy},PK_{X}({\mbox{exptime}}_{X},W,F_{bx},K_{bx},F_{fx},K_{fx},PK_{W}({\mbox{exptime}}_{W},{\mbox{NULL}},{\mbox{NULL}},{\mbox{NULL}},{\mbox{NULL}},{\mbox{NULL}},({\mbox{IDENTITY}},F_{bx},K_{bx},F_{fx},K_{fx},F_{by},K_{by},F_{fy},K_{fy},F_{bz},K_{bz},F_{fz},K_{fz},{\mbox{PADDING}})))))$
    La diferencia fundamental entre las dos estructura es la capa más interna. Ahora no estamos ante un relleno, sino que contiene suficiente información para permitir al enrutador del iniciador alcanzar al iniciador y toda la información criptográfica necesaria para cifrar los datos que recorren el circuito virtual.
Los 'reply onion' también se pueden usar para dar acceso a servicios que quieren mantener su localización oculta. En este caso el iniciador publica un 'reply onion' el cual puede ser obtenido y usado por el destinatario. A continuación el destinatario envía el 'reply onion' al enrutador designado para establecer el circuito hasta el iniciador.
Un problema abierto en este tipo de configuraciones es que el 'reply onion' puede no ser funcional en el momento en que el destinatario decida usarlo.

#### Puntos de encuentro

La idea de los puntos de encuentro, denominados por las siglas RP (del inglés Rendezvous Points), es, en lugar de explícitamente enviar un paquete a un destino, establecer un punto de encuentro que actúe como nivel de indirección. De esta forma desacoplamos el acto de enviar del acto de recibir. Cada extremo de la comunicación envía sus mensajes a ese punto de encuentro y desde ahí son enviados a donde corresponda usando circuitos que esconden la localización del destino. Por ejemplo podríamos usar este sistema para conectarnos a un servidor de chat IRC.
Ejemplos de sistemas que soportan esta funcionalidad es la antigua Onion Routing y su evolución Tor.

#### Servicios que ocultan la localización

Los servicios que ocultan la localización (por ejemplo, la dirección IP) de quien provee el servicio (Ej. un servicio web accesible solo desde la red de encaminamiento cebolla) se les suele llamar servicios de localización oculta (en inglés location-hidden services) o simplemente servicios ocultos (en inglés hidden services).
Por ejemplo esta funcionalidad es soportada por Tor. Para ello los proveedores de servicios generan una clave pública y privada para identificar su servicio. A continuación anuncian su servicio a distintos routers, haciendo peticiones firmadas con su clave pública, para que sirvan como punto de contacto. A los routers con esta función se les llama puntos de introducción, en inglés introduction point. El proveedor de servicio asocia a su servicio una FQDN del pseudo-TLD .onion y la publica en un servidor de directorio. La FQDN tiene la forma <valorhash>.onion donde el valor hash es de 16 caracteres en Base32 y está generado usando una función hash sobre la clave pública del servicio. Cuando un cliente se quiere conectar a cierta FQDN (por ejemplo ha encontrado la dirección a través de un sitio web) consulta un servicio de búsqueda (lookup service) y este le indica un punto de introducción (introduction point) y la clave pública del servicio. Observar que para mantener el anonimato es necesario que la consulta del servicio de búsqueda se realice a través de Tor. A continuación el cliente se conecta con un punto de encuentro (esto lo podría haber hecho antes) y se establece un identificador de esa conexión (rendezvous cookie). A continuación el cliente le envía un mensaje, firmado con la clave pública del servidor, al punto de introducción indicándole el punto de encuentro donde está, el identificador que permita identificar al cliente en el punto de encuentro (la rendezvous cookie) y parte del protocolo Diffie-Hellman ((start of a DH handshake). A continuación el punto de introducción envía el mensaje al servidor del servicio el cual determina si se conecta al punto de encuentro para proveerle el servicio o no. Si determina que quiere conectarse con él entonces se conecta al punto de encuentro y le indica a este el identificador del cliente con el que quiere conectarse (la rendezvous cookie), la segunda parte del Diffie-Hellman (the second half of the DH handshake) y un hash de la clave que comparten. A continuación el punto de encuentro conecta al cliente y el servidor y se establece una comunicación normal.

## Clasificación

Los distintos sistemas que implementan este tipo de encaminamiento se distinguen por cómo se gestionan las claves, en cómo se construyen y procesan los mensajes, en cómo los nodos se conocen entre sí, en cómo se eligen los caminos o paths que recorren los mensajes, en si hay retardos intencionados y de qué tipo, en si hay tráfico de relleno, en el protocolo al que dan servicio (Ej IP, TCP, HTTP), etcétera. Veamos algunas de esas clasificaciones según distintos criterios

### Según los retardos

Podemos clasificar las redes que usan encaminamiento cebolla según los retardos que introducen los routers desde que el mensaje llega a un nodo hasta que ese mensaje sale del nodo. Podemos distinguir dos tipos:
* De alta latencia.- Este tipo de redes introducen de forma intencionada retardos comparativamente largos y variables. Son más resistentes a ataques pero introducen demasiados retardo para tráfico interactivo (Ej navegación web, chat o conexiones SSH). Ejemplos de este tipo de redes son MixMaster, Babel y Mixminion
* De baja latencia.- Este tipo de redes son adecuadas a tráfico interactivo. Debido a esta restricción no introducen retardos artificiales o los introducen pero son de muy pequeña duración. Este tipo de redes tienen dificultades en contrarrestar ataques:
** Basados en escuchar los dos extremos de la comunicación y hacer correlaciones de tiempo y volumen de tráfico
** Que introducen tráfico entrante con patrones de tiempo y buscan patrones relacionados con ellos en el tráfico de salida.
Ejemplos de este tipo de redes son Freedom Network, Onion Routing y Tor

### Según los circuitos

Podemos clasificar las redes de cebolla atendiendo a si se establecen o no circuitos desde el origen al destino, también llamados caminos o túneles, por los que circulan mensajes. De esta forma podemos distinguir:
* Redes en las que se establecen circuitos. La mayoría de redes de cebolla funcionan de esta manera. A su vez podemos dividir este tipo de redes según el número de pasos realizados para elegir el circuito
** Redes en las que el camino que tiene que recorrer un mensaje se decide en un solo paso. Ejemplos de este tipo de redes son Freedom Network y Onion Routing
** Redes en las que el camino se va decidiendo poco a poco en varios pasos. Ejemplo de este tipo de redes es TOR.
* Redes es las que no se establecen circuitos. Se trata del llamado Encaminamiento cebolla de caminos dinámicos (en inglés Dynamic Multipath Onion Routing). En estas redes cada paquete desde el origen al destino puede elegir un camino diferente. Ejemplo de este tipo de redes es MORE.

### Según la naturaleza de los routers

Marc Rennhard propone clasificar las redes con encaminamiento de cebolla en función de la naturaleza de los nodos. Basándose en esto distingue entre:
* Redes estáticas: Estos sistemas tienen unos relativamente escasos y bien conocidos routers de cebolla que son usados por un número mucho más grande de usuarios. Por eso decimos que son estáticas. Ejemplos de este tipo de sistemas son Onion Routing, Freedom Network y Tor. Este tipo de redes se pueden clasificar a su vez en función de quien proporciona los routers. Podemos distinguir:
** Redes estáticas con routers proporcionados por voluntarios. En muchas redes estáticas los onion routers son proporcionados por voluntarios individuales o entidades colaboradoras. Es difícil encontrar voluntario o entidades independientes que aporten sus recursos para proporcionar desinteresadamente onion routers a la red. En especial en este tipo de redes que proporcionan cierto grado de anonimato y que pueden ser usadas como soporte para actividades controvertidas (Ej. publicación de información comprometida) o simplemente delictivas (Ej. tráfico de drogas). Ejemplo de este tipo de redes son MixMaster o Tor.
** Redes estáticas con routers proporcionados como un servicio comercial. En estos sistemas una compañía proporciona un servicio de anonimato para el que es necesario el pago de cierta cantidad para usarlo. Para realizar el servicio la empresa realiza unas inversiones y proporciona el servicio directamente o a través subcontratas. La ventaja de este tipo de sistemas es que el servicio está controlado por una sola organización y se pueden tomar medidas centralizadas para paliar cualquier problema que pudiera haber. La gran desventaja de estos sistemas es que, debido al gran control que ejerce la organización, es necesario tener confianza en que ella misma no va a comprometer nuestra privacidad. Otra desventaja es que estos sistemas stán enfocados a ser rentables y proporcionar un alto grado de anonimato suele estar reñido con la rentabilidad (necesitaría mucho tráfico de relleno). Un problema para el éxito de este tipo de redes es que es difícil vender una servicio de anonimato no confiable al 100%. Un ejemplo de este tipo de sistemas fue la red Freedom Network cerrada en 2001.
* Redes dinámicas: Estos sistemas están compuestos por onion routers que aparecen y desaparecen una y otra vez. Por eso decimos que son dinámicas. Ejemplos de este tipo de sistemas son los sistemas peer-to-peer Tarzan y MorphMix en los que cada usuario es al mismo tiempo un onion router.

## Debilidades

El encaminamiento de cebolla no proporciona un anonimato total de los interlocutores contra todo tipo de atacantes que escuchan las comunicaciones. Sin embargo dificulta bastante esta tarea. El grado de dificultad que aporta es generalmente función del número de routers de la ruta elegida y del número de esos routers que son maliciosos o que han sido comprometidos.

### Ejemplos de ataques

* Análisis de tiempos (en inglés Timing analysis): Analizando el flujo de mensaje que pasan a través de un nodo poco cargado podemos deducir la correspondencia entre ciertos mensajes de entrada y otros de salida. Para evitar esto se propone el uso de mensajes del mismo tamaño, tráfico de relleno y la introducción tiempos de espera artificiales que lo dificulten.
* Ataques para la denegación de servicio (en inglés Denial Of Sevices attacks): En este tipo de redes es fácil desarrollar ataques de denegación de servicio por ejemplo forzando a muchos routers a realizar una fuerte cantidad de operaciones criptográficas o agotando el ancho de banda. Para evitar este tipo de ataques de forma radical se han propuesto sistemas en los que se establece alguna forma de 'moneda digital' que los clientes tienen que 'pagar' para usar los servicios del sistema. Por ejemplo se podrían usar sistemas que obligaran a los usuario a realizar un esfuerzo importante y que fueran fáciles de verificar. Es aplicar la misma idea que Hashcash.
    Hay distintas formas de implementar ataques de denegación de servicio, veamos un ejemplo:
      * Ataques de replay: Los sistemas con encaminamiento de cebolla son vulnerables a ataques de replay que se basan en capturar mensajes y luego los reinyectan en la red con el objetivo de sobrecargarla y que deje de funcionar (ataque de denegación de servicio). Para evitar este tipo de ataques es habitual que los routers detecten cuando un paquete ya ha sido procesado (y por tanto descarten ese paquete) y que los propios mensajes tengan un tiempo de validez que una vez agotado permita que los routers eliminen esos mensajes.
* Ataques de intersección (en inglés Intersection attacks): Este ataque se basa en obtener una colección de conjuntos de nodos que sabe que contienen el iniciador de la comunicación. A partir de este conjunto podemos sacar conclusiones válidas simplemente hallando la intersección de estos conjuntos. Si la intersección es solo un nodo entonces se puede estar seguro de quien es el iniciador. Para que los distintos conjuntos de nodos que vamos obteniendo sean distintos, y por tanto tenga sentido la hacer la intersección, podemos analizar los nodos que se desconectan o entran en la red mientras cierto circuito continúa funcionando sin ningún tipo de problema. El coste de este tipo de ataques es significante si el tamaño de la red es grande, pero puede ser factible en algunos escenarios.
* Ataques de predecesor (en inglés Predecessor attacks): Este tipo de ataques se basan en dos suposiciones:
   * Hay una conexión recurrente entre un iniciador y un destinatario que se intercambian mensajes.
   * En los mensajes transportados hay información que puede ser utilizada por el atacante para identificar esa conexión recurrente.
    Podemos justificar estas suposiciones basándonos en como se comportan las aplicaciones que usan ciertos protocolos. Por ejemplo cuando usamos HTTP, FTP, SSH, Telnet o IRC normalmente nos conectamos recurrentemente al mismo servidor.
    En general los routers de una red con encaminamiento de cebolla no tienen conexiones totalmente estables. Cuando un nodo se desconecta, cualquier circuito en el que participara ese nodo se ve afectado y tiene que volver a configurarse (en inglés se le llama chain reformation). A este evento le vamos a llamar reset. Al periodo de tiempo entre dos resets lo vamos a llamar una ronda.
    Los ataques de predecesor se basan en los siguiente: Si un nodo comprometido intercepta un mensaje, el nodo predecesor tendrá una probabilidad más alta de ser el nodo iniciador comparado con otros nodos. Por tanto para realizar el ataque el atacante estudia las rondas en las cuales se envían mensajes que son parte del flujo que estamos estudiando y que pasan a través de nodos comprometidos (los cuales almacenan de forma pasiva toda la información para poder hacer luego el análisis). A partir de ahí se establece el nodo predecesor con probabilidad más alta.
* Ataque basado en capturar el tráfico de los nodos de salida: Los nodos de salida (los últimos de la cadena de routers) tienen un acceso completo al contenido que se transmite desde el origen al destino. Basándose en esto ha habido ataques que han capturado información privilegida. Este tipo de ataques pueden ser resueltos empleando cifrado extremo a extremo, por ejemplo unsando SSL.
* Los sistemas que se han ido añadiendo al esquema para mejorar las presentaciones tienen sus propios puntos débiles que pueden ser objeto de ataque. Ej. de ataques sobre estos elementos:
** Ataques contra el servicio de que directorio que suele usarse para proveer de información de configuración.
** Ataques contra los puntos de encuentro.