Tor es un cojunto de herramientas que pretende conseguir el anonimato online. Usa una red de máquinas o nodos a través de los cuales enruta el tráfico de red, tal y como se muestra en el esquema siguiente:

Como se ve en el dibujo una conexión a través de la red Tor usa tres nodos intermediarios entre el origen y el destino. De esta manera la máquina destino que recibe la conexión solo tendrá acceso a la IP del último nodo.

Tor ofrece una interfaz SOCKS a las aplicaciones, por lo que cualquier aplicación preparada para usar SOCKS podrá utilizar la red Tor sin problemas.
Sin embargo, no es necesario que una aplicación disponga de soporte para SOCKS, dado que Tor distribuye un script llamado "torify" que permite que cualquier aplicación use la red tor.

Este script emplea la herramienta tsocks para permitir que una aplicación use SOCKS de forma transparente.


Para que un usuario pueda conectarse a la red Tor necesita obtener un listado de nodos de la red. Este proceso, como indica el dibujo, se realiza sin cifrar.



A continuación se empieza a crear el circuito por el que viajaran los datos en la red Tor. Cada servidor conoce únicamente al servidor que le proporciona los datos y al servidor al que se los envía. por lo que ninguna máquina conoce el recorrido completo. Además, en cada tramo, los servidores afectados negocian claves diferentes, impidiendo que las conexiones sean rastreadas.



Una vez el circuito ha sido establecido se utilizará durante unos diez minutos. Posteriormente se creará un circuito nuevo.







La forma de instalar Tor depende en gran medida del sistema operativo utilizado, por lo que para instalarlo lo mejor es partir de la documentación oficial.

Una vez instalado su uso es sencillo. Por ejemplo, podríamos torificar la aplicación netcat con el comando siguiente:

$ torify nc www.google.com 80

Observemos el funcionamiento de Tor. Si no usamos el comando "torify" vemos que estamos realizando una conexión directa a google.

$ nc www.google.com 80

# En otro terminal
$  netstat  | grep ESTABLISHED
tcp        0      0 192.168.1.69:34362          nf-in-f99.google.com:http   ESTABLISHED

Sin embargo, torificando netcat los resultados son diferentes.

$ torify nc www.google.com 80

# En otro terminal
$ netstat  | grep ESTABLISHED
tcp        0      0 192.168.1.69:34352          tor.outra.net:9090          ESTABLISHED
tcp        0      0 192.168.1.69:34351          cyberphunk.eu:9001          ESTABLISHED

Queda claro que no saltamos directamente al servidor de google sino que entramos en la red Tor. Veamos ahora con que dirección IP llegamos a nuestro destino. Necesitaremos una web que nos diga la dirección IP (http://www.vermiip.es/) y otra que nos diga la localización geográfica (http://www.ip2location.com/free.asp),

Esto nos permitirá obtener la IP con el comando:

$ torify lynx --dump http://www.vermiip.com 2>/dev/null | grep "Tu ip" | cut -c 18-30
85.214.63.25

Y su localización geográfica:

$ torify lynx --dump http://www.ip2location.com/free.asp?ipaddresses=85.214.63.25 \
2>/dev/null | grep "85.214.63.25\|mapit" |  sed -e 's/\[.*\]//'
          85.214.63.25 DE GERMANY
BERLIN BERLIN STRATO RECHENZENTRUM BERLIN

De esta manera podemos construir un sencillo script que nos de el listado de nodos de salida de Tor.

$ cat  print_tor_nodes.sh
#!/bin/bash

while true; do

IP=`torify lynx --dump http://www.vermiip.com 2>/dev/null | grep "Tu ip" | cut -c 18-30`;

DATA=`torify lynx --dump http://www.ip2location.com/free.asp?ipaddresses="$IP" \
2>/dev/null | grep "$IP\|mapit" |  sed -e 's/\[.*\]//'`

echo $DATA
sleep 300

done

Del que extraemos el siguiente listado, que nos permite ver los nodos que nos dan acceso a Internet en último lugar.

208.64.29.34 US UNITED STATES NEW YORK NEW YORK R & D TECHNOLOGIES LLC
217.20.117.1 DE GERMANY BERLIN BERLIN NETDIREKT E. K
128.197.11.3 US UNITED STATES MASSACHUSETTS BOSTON BOSTON UNIVERSITY
88.191.29.92 FR FRANCE ILE-DE-FRANCE PARIS DEDIBOX SAS
88.191.25.27 FR FRANCE ILE-DE-FRANCE PARIS DEDIBOX SAS
89.149.207.1 DE GERMANY BERLIN BERLIN NETDIREKT E.K
87.234.124.1 DE GERMANY BERLIN BERLIN QSC AG DYNAMIC IP ADDRESSES
88.191.29.92 FR FRANCE ILE-DE-FRANCE PARIS DEDIBOX SAS
87.234.124.1 DE GERMANY BERLIN BERLIN QSC AG DYNAMIC IP ADDRESSES
88.191.29.92 FR FRANCE ILE-DE-FRANCE PARIS DEDIBOX SAS
128.197.11.3 US UNITED STATES MASSACHUSETTS BOSTON BOSTON UNIVERSITY
75.72.79.46 US UNITED STATES
203.26.16.68 AU AUSTRALIA NEW SOUTH WALES WEST WYALONG TPG INTERNET PTY LTD
88.191.11.18 FR FRANCE ILE-DE-FRANCE PARIS DEDIBOX SAS
88.198.50.14 DE GERMANY - - HETZNER-RZ-NBG-NET
83.243.80.77 DE GERMANY BERLIN BERLIN SERVERCREW LTD. PI
88.191.29.92 FR FRANCE ILE-DE-FRANCE PARIS DEDIBOX SAS
209.160.32.1 US UNITED STATES DISTRICT OF COLUMBIA WASHINGTON HOPONE INTERNET CORPORATION
60.167.39.24 CN CHINA BEIJING BEIJING CHINANET ANHUI PROVINCE NETWORK
83.217.66.50 BE BELGIUM OOST-VLAANDEREN DENDERMONDE NMV-CUST-DIGITALROOT
128.2.141.33 US UNITED STATES PENNSYLVANIA PITTSBURGH CARNEGIE MELLON UNIVERSITY83.171.182.9 DE GERMANY BAYERN NüRNBERG MNET TELEKOMMUNIKATION GMBH
85.214.63.25 DE GERMANY BERLIN BERLIN STRATO RECHENZENTRUM BERLIN
74.208.46.15 US UNITED STATES NEW YORK NEW YORK 1&1 INTERNET INC
122.145.8.19 JP JAPAN - - FREEBIT CO. LTD
71.226.252.2 US UNITED STATES PENNSYLVANIA WEST CHESTER COMCAST CABLE COMMUNICATIONS INC
83.233.181.9 SE SWEDEN - - PROVIDER LOCAL REGISTRY
166.70.207.2 US UNITED STATES UTAH SALT LAKE CITY XMISSION
195.71.90.10 DE GERMANY - - PROVIDER LOCAL REGISTRY
...

Respecto al script anterior, realiza un sleep de cinco minutos antes de reintentar, lo que hace el procese extremadamente lento. Si se reinicia Tor antes de cada petición el circuito se crea de nuevo y se obtiene un nodo diferente. De esta manera puede suprimirse el sleep del script.



En el momento de escribir este artículo la red Tor es relativamente pequeña, lo que disminuye notablemente el grado de anonimato. Aunque, sin duda, tiene un futuro prometedor.


Referencias:
- Tor Project: http://www.torproject.org

Continuando con la serie de artículos sobre factorización, hoy veremos el método Rho de Pollard. Un instructivo algoritmo que permite factorizar números bastante más grandes que los que podríamos factorizar mediante divisiones sucesivas de números primos o aplicando directamente el método de Fermat, tal y como vimos en "Factorización I: Introducción".

A lo largo de este artículo (y de los siguientes) se usará la operación mod. Esta operación representa el resto de una división entera. Por ejemplo 6 mod 5 =1 pues si dividimos seis entre cinco la division no es exacta, dado que tiene resto 1. Otros ejemplos pueden ser: 101 mod 99 = 2, 4^2 mod 15=1 o 33² mod 989 = 10².

Ahora supongamos que tenemos la ecuación F(x)=x² mod n. Si aplicamos esta ecuación para diferentes valores de x queda claro que el resultado siempre será menor que n. Por lo tanto, si aplicamos la ecuación para diferentes valores de x es lógico pensar en que en algun momento los resultados empezarán a repetirse, pues son finitos!

Veamos un ejemplo para n=323, empezando por ejemplo con x=2.

F(2) = 2² mod 323 = 4
F(4) = 4² mod 323 = 16
F(16) = 16² mod 323 = 256
F(256) = 256² mod 323 = 290
F(290) = 290² mod 323 = 120
F(120) = 120² mod 323 = 188
F(188) = 188² mod 323 = 137
F(137) = 137² mod 323 = 35
F(35) = 35² mod 323 = 256
F(256) = 16² mod 323 = 290
F(290) = 290² mod 323 = 120

Como se ve marcado en rojo, a partir de F(35) los resultados empiezan a repetirse, entrando en un ciclo.

Si representamos en un dibujo los resultados obtenidos vemos que su forma es similar al de la letra griega rho. Lo que da nombre al algoritmo.



El algoritmo Rho de Pollard permite encontrar ciclos cuando se trabaja con grupos donde los elementos son finitos. De manera que lo único que hemos hecho hasta ahora es encontrar un ciclo en un campo de números finitos con n=323. Pero, ¿Cómo aplicar esto para factorizar?

Si nos fijamos bien en la Rho dibujada vemos un hecho interesante producido al cerrar el ciclo. Llegamos al número 256 tanto a partir de 16² como a partir de 35². Este hecho, conocido como colisión, nos permite ver que 35²=16² mod 323. Lo que se conoce como congruencia y significa que 35² mod 323 = 16². Así pues, de forma similar a como vimos en el método de Fermat encontraremos un factor p mediante 35-16=19.

Resumiendo, el algoritmo Rho de Pollard nor permitirá encontrar colisiones, que a su vez nos permitiran encontrar un factor de n.

Para aplicar el método Rho de Pollard tal y como lo hemos visto, es necesario almacenar todos los elementos y compararlos con los elementos nuevos que se van generando. Esto es muy costoso tanto en tiempo como en espacio. Afortunadamente, existe una variación conocida como método de Floyd para encontrar ciclos, que permite encontrar una colisición sin almacenar apenas datos. Este método consiste en mantener dos valores. El primero recorrera en cada paso un elemento de la Rho, el segundo recorrerá dos. El tiempo estimado en el que ambos se encontrarán de nuevo, formando una colisión, es en el peor de los casos la raiz de n.

Algoritmo:

1. Elegir un entero aleatorio a entre 1 y n-3.
2. Elegir un entero aleatorio s entre 0 y n-1.
3. Inicializar U=V=s;
4. Calcular U=F(U), V=F(F(V)));
5. Si MCD(U-V, n) = 1, volver al punto 4.
6. Si MCD(U-V, n) = n, volver al punto 1.
7. MCD(U-V, n) es un factor de n.

NOTA: MCD=Máximo Común Divisor.



Hemos visto que el tiempo estimado para factorizar un número es de raiz de n en el peor de los casos. Pero existe una manera de mejorar considerablemente el tiempo de resolución del algoritmo cuando se dispone de cierta información sobre uno de los factores de n.

Se estima que usando F(x)=x^(2k) +a mod n, el número de iteraciones necesarias para encontrar un factor de n es de c*RAIZ(p)/RAIZ(MCD(p-1,2K)-1).
Es decir, quanto más factores comunes existan entre p-1 y 2k, menor será el número de iteraciones necesario para encontrar p.
Si no sabemos que factores puede tener p-1 puede ser útil calcular el factorial de un número B y usarlo como k: k=B!. Cuanto más grande sea B menos operaciones seran necesarias para encontrar el factor. Pero tampoco se puede abusar del tamaño de B, pues para valores demasiado grandes el tiempo por iteración será muy elevado.


Veamos un ejemplo usando el programa rho_2k.cpp que pego al final:

$ g++ -lgmpxx rho_2k.cpp -o rho_2k
$ ./rho_2k [n number] [B bound]

El primer parámetro es el número que queremos factorizar, el segundo el número B que usaremos para calcular k mediante su factorial.

Intentemos factorizar el número de 32 bits: 2930992620606930277. Primero con B=1, que equivale a k=1:

$ ./rho_2k 2930992620606930277 1
factor: 1065951967
count: 19188

Hemos necesitado 19.188 operaciones. Intentemoslo ahora con B=10:

./rho_2k 2930992620606930277 10
factor: 2749647931
count: 9516

El número de iteraciones baja. Con B=100:

./rho_2k 2930992620606930277 100
factor: 2749647931
count: 50

Como podemos observar la mejora es tangible. Finalmente con B=1000:

./rho_2k 2930992620606930277 700
factor: 2749647931
count: 1

En una sola operacion!


Hemos visto que cuantos más factores coinciden entre p-1 i k mejores son los resultados. Hasta el punto de que si todos los factores de p-1 estan en k, se resuelve la factorización en una sola operación. Sin embargo B no puede incrementarse indefinicademente, pues el factorial crece muy rápido, y no tardaremos en llegar a valores que relentizarán demasiado las operaciones.


Finalmente dejo una copia del programa usado:

#include <gmpxx.h>
#include <iostream>

// F(x) = x^2k + a mod n
mpz_class F(mpz_class &x, mpz_class &k, mpz_class &a, mpz_class &n)
{
  mpz_class res;
  mpz_class pow;

  pow = 2*k;
  mpz_powm(res.get_mpz_t(), x.get_mpz_t(), pow.get_mpz_t(), n.get_mpz_t());
  res += a;

  return res;
}

int main(int argc, char *argv[])
{
  using namespace std;

  mpz_class n;
  mpz_class U;
  mpz_class V;
  mpz_class s;
  mpz_class g;
  mpz_class k;
  mpz_class a;
  mpz_class count;

  if (argc!=3)
  {
     cout << argv[0] << " [n number]  [B bound]" << endl;
     return 0;
  }

  n = argv[1];
  int B = atoi(argv[2]);
  count = 0;
  s = 2;
  U = s;
  V = s;
  g = 1;

  mpz_fac_ui(k.get_mpz_t(), B);
  a = 3;

  while(g==1)
  {
     U = F(U, k, a, n);
     V = F(V, k, a, n);
     V = F(V, k, a, n);

     g = U-V;
     mpz_gcd(g.get_mpz_t(), g.get_mpz_t(), n.get_mpz_t());

     if(g==n)
     {
        cout << "bad seed" << endl;
        U++;
        V++;
        g=1;
     }
     count ++;
  }

  cout << endl << "factor: " << g << endl;
  cout << "count: " << count << endl;

  return 0;
}

Referencias:
- Prime Numbers, A Computational Perspective. Crandall & Pomerance. Ed Springer.

Ya hablamos de la importancia que tiene la factorización en criptografía en "Rompiendo claves RSA". En esta serie de artículos se hará un repaso a los algoritmos usados para factorizar números grandes, empezando por los algoritmos más básicos hasta llegar a los más actuales y modernos sistemas, que permiten factorizar números de más de 150 dígitos decimales.

Como veremos, existen decenas de algoritmos de factorización, pero los más destacados por su mayor velocidad (o menor complejidad) son:

- Quadratic Sive (QS): El algoritmo más rápido para factorizar números grandes de propósito general menores de 110 dígitos decimales (aproximadamente).

- Number Field Sieve (NFS): El algoritmo más rápido para factorizar números grandes de propósito general mayores de 110 dígitos decimales (aproximadamente).

- Elliptic Curve Method (ECM): El algoritmo más rápido para factorizar números grandes cuando uno de los factores es relativamente pequeño.


Estos tres algoritmos tienen un complejidad subexponencial que es lo más rápido que se ha conseguido llegar en el campo de la factorización. Si se encontrase un algoritmo de complejidad polinómica, podríamos decir que el problema de la factorización queda resuelto y dejaría de poder utilizarse en criptografía. Esto significaría, entre otras cosas, el fin de algoritmos como RSA.

Los algoritmos QS i NFS se basan en una vieja estratégia atribuída al genial matemático Pierre de Fermat. La vemos a continuación:
Supongamos que disponemos de un número n del cual queremos obtener su representación como multiplicación de dos factores, es decir n=pq. Ecuación que también podríamos representar como n=(x+y)(x-y).

Si encontramos dos números enteros positivos que cumlan la ecuación de manera que x-y sea mayor que 1, diremos que hemos encontrado un factor no trivial de n, quedando el problema resuelto. Pero para buscar a y b cambiaremos el enfoque del problema.

Sabemos que (x+y)(x-y)=x²-y² , lo que nos permite un cambio de estrategia importante, pues ya no tenemos que buscar directamente factores de n, sino parejas de cuadrados cuya diferencia sea n.
Veamos un ejemplo para n=989. Si realizamos una búsqueda de cuadrados empezando por la raiz entera de 989, es decir 31, tenemos que 32²-989=35 no es cuadrado, continuamos, 33³-989=100 y bingo! Pues vemos que 33²-10²=989. Partiendo de la fórmula anterior tenemos que el factor p corresponde a p=33-10=23 y el factor q corresponde a q=33+10=43. Quedando n factorizado como 989=23*43.

El método utilizado puede parecer muy rápido, pues hemos factorizado el 989 en solo dos operaciones. Si nos hubiesemos dedicado a probar con todos los números primos menores que 31 habríamos necesitado 9 operaciones! (2, 3, 5, 7, 11, 13, 17, 19, 23). Pero lo cierto es que cuando tratamos de factorizar números más grandes vemos que el enfoque no es el adecuado, pues resulta extremadamente lento.

Lo que debemos tener en cuenta de la idea de Fermat es que proporciona una estrategia diferente para atacar el problema, de manera que pasamos de buscar factores de n a buscar diferencias de cuadrados. Como veremos en próximos artículos, esta estratégia se usa con éxito en los algoritmos QS y NFS.