miércoles, 21 de noviembre de 2007

Factorización III: P-1 de Pollard

Continuamos la serie de artículos sobre factorización con un algoritmo muy sencillo conocido como P-1 de Pollard.

El algoritmo de factorización P-1 de Pollard parte de la idea de smoothness o suavidad. Un número se considera B-smooth cuando todos sus factores son más pequeños que B. Esta idea, puede ser usada con éxito como herramienta de factorización, usando como base el Teorema Pequeño de Fermat:

b^p = b mod p
b^(p-1) = 1 mod p

A partir de la formula anterior deducimos que b^(p-1) - 1 es múltiplo de p. De manera que si disponemos de un número n=pq el cual deseamos factorizar , podremos hacerlo si somos capaces de calcular b^(p-1).
Inicialmente, esto puede parecer complicado, dado que no conocemos p. Pero supongamos que p-1 es B-smooth, para un valor de B bastante pequeño. Esto significaría que podemos calcular un valor M que contenga todos los factores de p-1, por ejemplo, calculando B!. Y si p-1 es un divisor de M, podemos aplicar el Teorema Pequeño de Fermat de la siguiente manera:

b^M = 1 mod p

Lo que nos llevarà a obtener un factor de n calculando el Máximo Común Divisor entre b^M-1 y n.

MCD(b^M-1, n)


Para finalizar, adjunto un programa en C y un ejemplo de su uso.

$ gcc pollard_pm1.c -lgmp -o pollard_pm1
$ ./a.out 97231944203 10
Factor = 888799
Factor = 109397




/* Pollard P-1 */
#include <stdio.h>
#include <gmp.h>


int main(int argc, char *argv[])
{
mpz_t n, a, GCD, tmp, k;
unsigned long int b;
gmp_randstate_t state;

if(argc!=3)
{
printf("Usage: %s [n] [B]\n", argv[0]);
return 0;
}

mpz_init(n);
mpz_init(tmp);
mpz_init(a);
mpz_init(GCD);
mpz_init(k);

mpz_set_str(n, argv[1], 10);
b = atof(argv[2]);

if(mpz_perfect_power_p(n) != 0)
{
mpz_sqrt(tmp, n);
gmp_printf("factor: %Zd\n", tmp);
return 0;
}
mpz_sub_ui(tmp, n, 1);
mpz_fac_ui(k, b);

gmp_randinit_default(state);

while(1)
{
mpz_sub_ui(tmp, n, 1);
mpz_urandomm(a, state, tmp);

if (mpz_cmp_ui(a, 1) <= 0)
mpz_set_ui(a, 2);

mpz_powm(tmp, a, k, n);
mpz_sub_ui(tmp, tmp, 1);
mpz_abs(tmp, tmp);
mpz_gcd(GCD, tmp, n);

if (mpz_cmp_ui(GCD, 1) > 0)
{
if (mpz_probab_prime_p(GCD, 10) > 0)
{
gmp_printf("Factor = %Zd\n", GCD);
mpz_div(n, n, GCD);
}
}
if (mpz_cmp_ui(n, 1) == 0)
{
mpz_clear(a);
mpz_clear(GCD);
mpz_clear(tmp);
mpz_clear(n);
mpz_clear(k);
return 0;
}

if (mpz_probab_prime_p(n, 10) > 0)
{
gmp_printf("Factor = %Zd\n", n);
mpz_clear(a);
mpz_clear(GCD);
mpz_clear(tmp);
mpz_clear(n);
mpz_clear(k);
return 0;
}
}

return 0;
}



miércoles, 31 de octubre de 2007

Introducción a las redes Tor

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


viernes, 26 de octubre de 2007

Factorización II: Rho de Pollard

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.


jueves, 25 de octubre de 2007

Factorización I: Introducción

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.




lunes, 24 de septiembre de 2007

Linus Torvalds y C++

Sorprendente la perla que nos deja Linus en referencia al lenguaje C++. No tiene desperdicio.

Dejo aquí una copia (el enlace aquí)

On Wed, 5 Sep 2007, Dmitry Kakurin wrote:
#
# When I first looked at Git source code two things struck me as odd:
# 1. Pure C as opposed to C++. No idea why. Please don't talk about portability,
# it's BS.

*YOU* are full of bullshit.

C++ is a horrible language. It's made more horrible by the fact that a lot
of substandard programmers use it, to the point where it's much much
easier to generate total and utter crap with it. Quite frankly, even if
the choice of C were to do *nothing* but keep the C++ programmers out,
that in itself would be a huge reason to use C.

In other words: the choice of C is the only sane choice. I know Miles
Bader jokingly said "to piss you off", but it's actually true. I've come
to the conclusion that any programmer that would prefer the project to be
in C++ over C is likely a programmer that I really *would* prefer to piss
off, so that he doesn't come and screw up any project I'm involved with.

C++ leads to really really bad design choices. You invariably start using
the "nice" library features of the language like STL and Boost and other
total and utter crap, that may "help" you program, but causes:

- infinite amounts of pain when they don't work (and anybody who tells me
that STL and especially Boost are stable and portable is just so full
of BS that it's not even funny)

- inefficient abstracted programming models where two years down the road
you notice that some abstraction wasn't very efficient, but now all
your code depends on all the nice object models around it, and you
cannot fix it without rewriting your app.

In other words, the only way to do good, efficient, and system-level and
portable C++ ends up to limit yourself to all the things that are
basically available in C. And limiting your project to C means that people
don't screw that up, and also means that you get a lot of programmers that
do actually understand low-level issues and don't screw things up with any
idiotic "object model" crap.

So I'm sorry, but for something like git, where efficiency was a primary
objective, the "advantages" of C++ is just a huge mistake. The fact that
we also piss off people who cannot see that is just a big additional
advantage.

If you want a VCS that is written in C++, go play with Monotone. Really.
They use a "real database". They use "nice object-oriented libraries".
They use "nice C++ abstractions". And quite frankly, as a result of all
these design decisions that sound so appealing to some CS people, the end
result is a horrible and unmaintainable mess.

But I'm sure you'd like it more than git.





Linus

sábado, 15 de septiembre de 2007

Criptografía de Curva Elíptica



Las curvas elípticas son ampliamente usadas en criptografía, especialmente en criptografía asimétrica (o de clave pública). Una de sus mayores ventajas es la velocidad que ofrece, debido a que requiere longitudes de clave mucho menores a las de criptosistemas como RSA.

A continuación se introducen las bases de este tipo de criptografía.


Qués son las curvas elípticas?


En criptografía se habla de curva elíptica en referencia a una ecuación y²=x³+Ax+B que cumple 4A³+27B²≠0. Dando diferentes valores a A y B obtenemos todo un conjunto de curvas que, al ser dibujadas, ofrecen una forma similar. Son ejemplos de curvas elípticas y²=x³-x (izquierda) y y²=x³-x+1 (derecha).



Las curvas elípticas tienen ciertas características que las hacen especiales en el mundo de la criptografía. Una de estas características consiste en la posibilidad de poder generar un punto en una curva partiendo de dos puntos dados (o incluso de uno). Este concepto es muy fácil de entender partiendo de la figura siguiente.





Usamos como puntos de partida P y Q, dos puntos conocidos. Trazaremos una linea entre P y Q. Si la linea corta la curva en un tercer punto, lo reflejaremos a través del eje, dando lugar a un nuevo punto R. Esta operación se representa como R=P+Q. En caso de que la linea que pasa por P y Q no corte a la curva en ningún otro punto, diremos que corta la curva en un punto O en el infinito y representaremos esta operación como P+Q=O.

Partiendo de la suma, no es difícil encontrar un mecanismo que nos permita realizar multiplicaciones de tipo kP, siendo k un escalar. Por ejemplo, imaginemos que queremos realizar la operación 13P, es decir, multiplicar 13 por un punto P. Bastaría con realizar la siguiente secuencia de doblado de puntos:

P, 2P=P+P, 4P=2P+2P, 8P=4P+4P, 13P=8P+4P+P
Este simple mecanismo para generar nuevos puntos dota a una curva elíptica de la posibilidad de realizar operaciones aritméticas sobre ella, base de los criptosistemas que estudiaremos en breve.

En criptografía las curvas elípticas se usan sobre campos finitos (Fq) con q muy grande. Un ejemplo de campo finito podría ser F5={0,1,2,3,4}. De manera que el número 7 representado en el campo finito correspondería a 7 mod 5 = 2.
Cuando se usan campos finitos el número de puntos que hay en una curva tambien es finito. Este numero se llama orden de la curva y se representa como #E. Debemos diferenciarlo del orden de un punto, que se refiere al valor k más pequeño (diferente de 0) que multiplicado por P da O.


El problema del logaritmo discreto (DLP)

La criptografía de Clave Pública basa su fuerza en la dificultad de resolver ciertos problemas matemáticos. Uno de los más usados es el problema del logaritmo discreto (Discrete Logarithm Problem - DLP). Este problema se basa en la dificultad que representa resolver una ecuación de tipo x = ay mod n donde x, a y n son conocidas e y es la variable que se busca. De hecho, para valores de n e y sufientemente grandes es computacionalmente imposible resolver el problema, al menos, con los algoritmos y ordenadores actuales.
El algoritmo más rápido conocido para resolver este problema es el Index Calculus que permite resolverlo en tiempo subexponencial.


El problema del logaritmo discreto en Curvas Elípticas (ECDLP)

Existe una problema similar al problema del logaritmo discreto que puede usarse con Curvas Elípticas. Anteriormente hemos visto como realizar una operación tipo Q=kP de una forma sencilla. Sin embargo, obtener k y P partiendo solo de Q es computacionalmente difícil. De hecho, el algoritmo más rápido que permite encontrar una solución es el algoritmo Rho de Pollard, pero este algorimo es de tiempo exponencial, mucho mas lento que en el caso del ataque a DLP mediante el Index Calculus.
Este hecho es muy importante, pues la dificultad de resolver ECDLP frente a DLP permite que los criptosistemas que se basan en el primero usen claves mucho más cortas. De manera que los sistemas que usan ECDLP requieren mucha menos memoria y capacidad de proceso.
Una clave RSA de 4096 bits ofrece la misma seguridad que una clave de un criptosistema de Curva Elíptica de 313 bits.

Intercambio de Claves de Diffie-Hellman

El intercambio de claves de Diffie-Hellman es un protocolo que permite un intercambio secreto y seguro de claves entre dos partes que no han tenido un contacto previo. Se usa ampliamente en criptografía y se basa en el problema del logaritmo discreto (DLP). Por lo tanto, puede usarse el mismo algoritmo a través del problema ECDLP.

Al algoritmo puede resumirse en los siguientes pasos:

1. Alice y Bob eligen una curva elíptica E sobre un campo finito Fq de manera que el ECDLP sea computacionalmente difícil. También eligen un punto P en dicha curva de manera que su orden sea un número primo grande.

2. Alice elige un entero grande a, calcula PA=aP y envía PA a Bob.

3. Bob elige un entero grande b, calcula PB=bP y envía PB a Alice.

4. Alice calcula aPB=abP

5. Bob calcula bPA=abP


Al finalizar el algoritmo, tanto Alice como Bob disponen de abP. Pero un usario que escuche el canal solo habrá podido obtener PA y PB, los cuales no le permiten calcular abP a menos que resuelva el ECDLP. Alice y Bob solo tendrán que extraer una clave a partir de abP y usarla para enviar datos cifrados. Para tal propósito podrán usar cualquier algoritmo simétrico como DES, AES, etc.

Algoritmo de firma digital (ECDSA)

El algoritmo de firma digital para curvas elípticas está basado en el estandar de firma digital DSA. Este algoritmo ofrece un esquema que permite firmar documentos y verificar las firmas.

Los pasos a seguir para generar claves, firmar y verificar la firma, se muestran a continuación.

Alice genera un par de claves:

1. Alice elige una curva E con orden #E=fr, de manera que r sea un primo grande.

2. Alice busca un punto en la curva de orden r.

3. Alice elige un número aleatorio d situado en el intervalor [2, r-2] y calcula Q=dP.

4. La clave pública corresponde a (E,P,r,Q) y la clave privada a d.



Alice firma un documento M.
(h(M) corresponde al hash de M)

1. Alice elige un número aleatorio k en el intervalo [2, r-2].

2. Se calcula el punto (x, y)=kP

3. R=x mod r

4. s=k¯¹ (h(M) +Rd) mod r, si s es igual cero, empezamos de nuevo.

5. La firma de Alice es (R,s) y se transmite junto con el mensaje M.


Bob verifica la firma de Alice.

1. Bob obtiene la clave pública de Alice.

2. w = s¯¹ mod r

3. u1 = h(M) w mod r

4. u2 = Rw mod r

5. (x, y) = u1P + u2P

6. v = x mod r

7. Si v es igual a R, la firma es válida.


OpenSSL: Un ejemplo práctico de firma digital mediante curvas elípticas.

Des de la versión 0.9.8 la herramienta OpenSSL ofrece algunas opciones para trabajar con curvas elípticas. No están muy documentadas, pero nos servirán para realizar una pequeña demostración del uso de la firma digital.

Para generar un clave ejecutaremos el siguiente comando:

$ openssl ecparam -genkey -name secp224r1 -out key.pem

Ahora tanto la clave pública como la privada se encuentran dentro de key.pem. Podemos extraer la pública con el comando:

$ openssl ec -in key.pem -text -pubout -out pubkey.pem

Ya disponemos de una clave con la que hacer pruebas, por lo que generaremos un mensaje que firmar:

$ echo "El mensaje de prueba de h4ck1t!" > msg.txt

Y lo firmaremos, operación que solo puede realizar el propietario de la clave privada:

$  openssl dgst -sign key.pem -ecdsa-with-SHA1 < msg.txt > msg.sig

Firmado el mensaje, todo usuario que disponga de la clave pública podrá verificar su procedencia:

$ openssl dgst -verify pubkey.pem -ecdsa-with-SHA1 -signature msg.sig < msg.txt
Verified OK


Referencias:

- Elliptic Curves, Number Theory and Cryptography. Lawrence C. Washington. Ed Chapman & HALL/CRC.
- Prime Numbers, a Computational Perspective. Richard Crandall, Carl Pomerance. Ed Springer.
- Criptografía de curva Elíptica, Ataque Rho de Pollard. Daniel Lerch. Hakin9 (6-2007).












martes, 11 de septiembre de 2007

Criptoanálisis: Análisis de frecuencias

Análisis de frecuencias:

El análisis de frecuencias es una forma de criptoanálisis utilizada en cifrados de sustitución, basada en el estudio de la frecuencia de aparición de las letras o símbolos de un criptograma. Este análisis se basa en el hecho de que cada lenguaje dispone de una frecuencia característica de aparición de sus letras o grupos de ellas. Por ejemplo, en inglés es común el uso de la letra E mientras que la X raramente aparece. Lo mismo ocurre en los textos en castellano, donde la E y la A son las letras más habituales.

Aproximadamente la distribución de porcentajes de aparición de cada letra en algunas lenguas comunes es la siguiente:

L       Inglés           Francés         Alemán          Castellano

a       8.167%          7.636%          6.51%           12.53%
b       1.492%          0.901%          1.89%           1.42%
c       2.782%          3.260%          3.06%           4.68%
d       4.253%          3.669%          5.08%           5.86%
e       12.702%         14.715%         17.40%          13.68%
f       2.228%          1.066%          1.66%           0.69%
g       2.015%          0.866%          3.01%           1.01%
h       6.094%          0.737%          4.76%           0.70%
i       6.966%          7.529%          7.55%           6.25%
j       0.153%          0.545%          0.27%           0.44%
k       0.772%          0.049%          1.21%           0.00%
l       4.025%          5.456%          3.44%           4.97%
m       2.406%          2.968%          2.53%           3.15%
n       6.749%          7.095%          9.78%           6.71%
o       7.507%          5.378%          2.51%           8.68%
p       1.929%          3.021%          0.79%           2.51%
q       0.095%          1.362%          0.02%           0.88%
r       5.987%          6.553%          7.00%           6.87%
s       6.327%          7.948%          7.27%           7.98%
t       9.056%          7.244%          6.15%           4.63%
u       2.758%          6.311%          4.35%           3.93%
v       0.978%          1.628%          0.67%           0.90%
w       2.360%          0.114%          1.89%           0.02%
x       0.150%          0.387%          0.03%           0.22%
y       1.974%          0.308%          0.04%           0.90%
z       0.074%          0.136%          1.13%           0.52%


A parte de estudiar la frecuencia de aparición de un símbolo, también podemos fijarnos en la frecuencia de aparición de conjuntos de dos, tres, o más letras. En castellano son frecuentes cadenas de dos letras como DE, LA, EL, EN o palabras de tres como QUE, LOS, DEL, LAS y POR.

A continuación se muestran los conjuntos de dos y tres letras más frecuentes:

En Inglés
Conjuntos de dos letras: TH, HE, AN, IN, ER, RE, ES, ON, EA, TI, AT, ST, EN, ND, OR, TO, NT, ED, IS, AR.
Conjuntos de tres letras: THE, ING, AND, ION, ENT, FOR, TIO, ERE, HER, ATE, VER, TER, THA, ATI, HAT, ERS.

En Francés:
Conjuntos de dos letras: ES, EN, OU, DE, NT, TE, ON, SE, AI, IT, LE, ET, ME, ER, EM, OI, UN, QU.
Conjuntos de tres letras: ENT, QUE, ION, LES, AIT, TIO, ANS, ONT, ANT, OUR, AIS, OUS.

En Alemán
Conjuntos de dos letras: EN, ER, CH, DE, GE, EI, IE, IN, NE, ND, BE, EL, TE, UN, ST, DI, NO, UE, SE, AU, RE, HE.
Conjuntos de tres letras: EIN, ICH, DEN, DER, TEN, CHT, SCH, CHE, DIE, UNG, GEN, UND, NEN, DES, BEN, RCH.

En Castellano:
Conjuntos de dos letras: ES, EN, EL, DE, LA, OS, AR, UE, RA, RE, ER, AS, ON, ST, AD, AL, OR, TA, CO.
Conjuntos de tres letras: QUE, EST, ARA, ADO, AQU, DEL, CIO, NTE, OSA, EDE, PER, IST, NEI, RES, SDE.


Al intentar romper un cifrado mediante análisis de frecuencia nuestro objetivo será identificar la frecuencia de aparición de los símbolos usados. Después buscaremos una equivalencia entre estos símbolos y las letras que más aparecen en la lengua usada intentando encontrar un significado. Nos servirán también las frecuencias de aparición de conjuntos de X letras, así como nuestra imaginación a la hora de rellenar huecos al estilo del juego del ahorcado.

En algunos casos puede ser útil conocer el porcentaje de vocales de cada idioma. En inglés, por ejemplo, el porcentaje de vocales es del 40%, igual que en el alemán. Sin embargo, en francés es del 45% y en castellano del 47%. Estos datos, aunque solo son aproximaciones pueden resultar de gran interés en ciertos criptogramas.


Criptoanálisis de ejemplo

Para experimentar con lo comentado anteriormente, imaginemos un sistema de cifrado por sustitución, de manera que cada letra del mensaje ha sido sustituída por un símbolo. El ejemplo de mensaje cifrado es el siguiente:
3# 16_@!5?6#=_# 2> 23 #6!2 |2 2>16_$_6 15% 13#72 >2162!# 5 |2 /% 45|5 2%_?4#!_15

Para iniciar nuestro criptoanálisis, empezaremos realizando un análisis de frecuencias. Para que este proceso no se haga pesado, adjunto un sencillo programa en C++ que lo hará por nosotros.

#include <iostream>
#include <fstream>
#include <algorithm>
#include <map>


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

if(argc!=3)
{
cout << "Usage: " << argv[0] << " [file] [max group size]" << endl;
return 0;
}

for(int i=0; i<atoi(argv[2]); i++)
{
int c;
map<string,int> freq;
ifstream file(argv[1]);
string group;
while( (c=file.get()) && !file.eof() )
{
if(isspace(c))
continue;
group += string(1,c);

if(group.size()>=i+1)
freq[group.substr(group.size()-i-1, i+1)]++;
}

cout << endl << "-- FREQ SIZE " << i+1 << " --" << endl;
int count = 0;
map<string,int>::iterator it = freq.begin();    
for(;it!=freq.end(); it++)
{
if((*it).second>1)
{
count ++;

cout << (*it).first << ": " << (*it).second << "\t";

if(count%6==0)
cout << endl;
}
}
cout << endl;
}
}


Partiendo del programa y del un fichero con el texto cifrado "cipher.txt" realizamos el analisis de frecuencias:

$ g++ freq.cpp
$ ./a.out cipher.txt 3
-- FREQ SIZE 1 --
!: 4    #: 7    %: 3    1: 6    2: 10   3: 3
4: 2    5: 6    6: 6    >: 3    ?: 2    _: 6
|: 3

-- FREQ SIZE 2 --
15: 2   16: 3   2>: 3   3#: 3   5|: 2   6_: 2
>2: 2   |2: 2

-- FREQ SIZE 3 --
16_: 2  2>2: 2


Si observamos el análisis de frecuencias podemos ver que los símbolos que más se repiten son '2' y '#', seguidos de '_', '1', '5' y '6'. Por lo que siguiendo la distribución de porcentajes frecuentes es probable que se correspondan con las letras 'a', 'e', 'i', etc.
Es importante tener en cuenta que esto solo nos da una pista de cuál podría ser el valor de cada símbolo, pero no nos lo dice de forma exacta. Por este motivo será necesario probar varias hipótesis.

Empezaremos suponiendo que '2' corresponde a 'e' y '#' corresponde a 'a'. Si nuestra hipótesis falla, continuaremos probando al revés.
Sustituimo en el texto cifrado:
3A 16_@!5?6A=_A E> E3 A6!E |E E>16_$_6 15% 13A7E >E16E!A 5 |E /% 45|5 E%_?4A!_15

Observando el principio del texto cifrado "3A" y la cuarta palabra "E3" deducimos que '3' corresponde a la letra 'L'. Sustituimos de nuevo.

LA 16_@!5?6A=_A E> EL A6!E |E E>16_$_6 15% 1LA7E >E16E!A 5 |E /% 45|5 E%_?4A!_15

También pueden resultar buenas pistas la tercera palabra "E>" y la sexta "|E". Estas nos indican que ">" podría corresponder a 'S' o 'N', y '|' probablemente corresponderá a 'D'. Vea la frecuencia de grupos de dos letras.
Además, si nos basamos en las suposiciones anterioriores, el grupo '/%' que corresponde a una palabra de dos letras que no contiene ni 'A' ni 'E'. Será pues una de las siguientes: NO, UN, SU, LO, SI, MI, ...

También es una buena pista el '5' solitario, que muy probablemente corresponderá a una 'y' o una 'o'. Pero viendo en la octava palabra '15%' deducimos que dificilmente corresponderá a una 'Y'.

En base a las observaciones anteriores, una buena hipotesis podría corresponder a las siguientes sustituciones: '5' por 'o', '|' por 'D' y '>' por 'S'.
LA 16_@!O?6A=_A ES EL A6!E DE ES16_$_6 1O% 1LA7E SE16E!A O DE /% 4ODO E%_?4A!_1O

Llegados a este punto, más de unos sería capaz de resolver el mensaje utilizando solamente su imaginación. Pero en lugar de dar la solución, vamos a explorar otra técnica interesante. Esta corresponde a atacar las palabras sin descifrar con un diccionario. Como ejemplo usaremos una lista de palabras en castellano que se puede descargar de:

http://lemarios.olea.org/lemario-espanol-2002-10-25.txt.gz

NOTA: Esta lista contiene acentos y ñ, que es recomendable sustituir para poder seguir los siguientes pasos.


Después de descargar y descomprimir la lista de palabras estudiemos que opciones tenemos para acabar de descifrar el mensaje. Una palabra que tiene posibilidades es '1LA7E', una palabra de 5 letras de las cuales conocemos tres. Tambien es interesante atacar la palabra que viene a continuación 'SE16E!A'.

Podemos hacerlo con dos sencillos comandos grep:
$ grep "^.la.e$" lemario-espanol-2002-10-25.txt
alabe
clase
clave
glase
llave
olaje
$ grep "^se..e.a$" lemario-espanol-2002-10-25.txt
secreta
secuela
segueta
septena
serreta

Sin duda, las palabras que buscamos son "CLAVE SECRETA". Así que continuamos con la sustitución:
LA CR_@TO?RA=_A ES EL ARTE DE ESCR_$_R CO% CLAVE SECRETA O DE /% 4ODO E%_?4AT_CO

La última palabra puede confundirnos, pero está claro cuál es la segunda. En cualquier caso:
$ grep "^cr..to.ra..a$" lemario-espanol-2002-10-25.txt
criptografia.
$ grep "^e....at.co$" lemario-espanol-2002-10-25.txt
enigmatico
enzimatico
estomatico

Con lo que la resolución del mensaje es trivial:

"La criptografia es el arte de escribir con clave secreta o de un modo enigmatico"


Finalmente el mensaje ha quedado descifrado, pero hay que tener en cuenta que aquí no se han expuesto todas las posibilidades. Es normal, cuando se inicia el criptoanálisis, que se tomen algunas hipótesis incorrectas. En estos casos, no queda más remedio que volver a empezar.


Referencias:
- Cryptanalysis a study of ciphers and their solution. Helen Fouché Gaines.




domingo, 26 de agosto de 2007

Los cifrados Zodiac

A finales de la década de los 60 un asesino en serie conocido como Zodiac cometió varios asesinatos en el norte de California. Zodiac enviaba cartas a la prensa en tono desafiante, algunas de las cuales contenían ciertos criptogramas como el que se muestra a continuación:


340 Cipher



Tres cartas de Zodiac fueron recibidas por el Vallejo Times Herald, el San Francisco Chronicle y el San Francisco Examiner el 1 de agosto de 1969. En ellas Zodiac se hacía responsable de tres asesinatos e incluía un criptograma que supuestamente contenía su identidad. En dichas cartas se exigía su impresión en primera plana, o de lo contrario mataría a una docena de personas ese mismo fin de semana.

El 8 de agosto de 1969, Donald y Bettye Harden descifraron el criptograma que debía contener la identidad de Zodiac. No era así.

I LIKE KILLING PEOPLE BECAUSE IT IS SO MUCH FUN IT IS MORE FUN THAN KILLING WILD GAME IN THE FORREST BECAUSE MAN IS THE MOST DANGEROUS ANAMAL OF ALL TO KILL SOMETHING GIVES ME THE MOST THRILLING EXPERENCE IT IS EVEN BETTER THAN GETTING YOUR ROCKS OFF WITH A GIRL THE BEST PART OF IT IS THAT WHEN I DIE I WILL BE REBORN IN PARADICE AND ALL THE I HAVE KILLED WILL BECOME MY SLAVES I WILL NOT GIVE YOU MY NAME BECAUSE YOU WILL TRY TO SLOI DOWN OR STOP MY COLLECTING OF SLAVES FOR MY AFTERLIFE EBEORIETEMETHHPITI


Carta al Vallejo Times Herald



Carta al San Francisco Chronicle




Carta al San Francisco Examiner







La historia que rodea al asesino está llena de incógnitas, desde su identidad hasta la solución de ciertos criptogramas. Por ejemplo, el criptograma mostrado al principio, conocido como criptograma 340, continúa sin resolver.

La reciente película "Zodiac" de David Fincher narra la historia de este conocido asesino en serie.


domingo, 19 de agosto de 2007

Buscando colisiones en SHA-1

El algoritmo SHA-1 es uno de los algoritmos de hash más importantes, por ser ampliamente usado en criptografía. Su función como algoritmos de hash, consiste en aceptar una entrada de longitud arbitraria y retornar un resumen (digest) de una longitud fija.

Entre las características principales de los algoritmos de hash destaca la necesidad de que las funciones sean de un solo sentido, es decir, que no se pueda obtener información de los datos origen a partir del resument resultado.
Otra característica importante es la resistencia a las colisiones, pues no deben existir dos entradas que produzcan el mismo resumen resultado. Pero lo cierto es que esta última característica es inalcanzable, desde el momento en que la longitud de la entrada puede ser superior a la de la salida.

Una forma de encontrar colisiones consiste en utilizar el ataque de cumpleaños o birthday attack, aunque este requiere 2^(n/2) operaciones de hash para encontrar una colisión. Impracticable en algoritmos como SHA-1.

Otra forma de hacerlo consiste en usar un ataque dedicado a SHA-1 que intente explotar sus debilidadades. Cierto trabajo de este estilo puede encontrarse en Finding Collisions in the Full SHA-1.


Por otra parte, la Universidad de Graz (Australia) ha puesto en marcha un proyecto dedicado a encontrar colisiones en SHA-1. Para tal propósito usa la plataforma distribuida de software libre BOINC, de la universidad de California en Berkeley. Esta plataforma permite usar los tiempos muertos de proceso para colaborar con el proyecto.

En Kriptopolis, han creado un equipo para participar en la búsqueda de colisiones. Puedes unirte a él descargando el soft de BOINC y siguiento las instrucciones de instalación de Kriptopolis.

sábado, 28 de julio de 2007

Codificación Base 64

Base 64 en un sistema de codificación que permite representar datos binarios usando únicamente los caracteres imprimibles ASCII. Este sistema ha sido usado ampliamente para codificar los correos electrónicos, entre otras cosas.

A continuación se muestra un ejemplo de codificación en Base 64.



Para usar Base 64 en C se puede optar por hacerlo a través de una librería como openssl o por implementar directamente el algoritmo. Veremos los dos casos.


Base 64 y OpenSSL:

Para usar Base 64 desde la librería OpenSSL debemos incluir la cabecera "openssl/evp.h". Las funciones que nos pemiten codificar y descodificar B64 son EVP_EncodeBlock() y EVP_DecodeBlock(), respectivamente.
A continuación aparecen dos funciones: base64_encode() y base64_decode(). Ambas reciben como parámetro la cadena a codificar o descodificar y su longitud, y retornan una cadena con el resultado. Esta cadena apunta a una zona de memoria reservada con malloc(), por lo que queda en manos del programador liberarla.


unsigned char *base64_encode (unsigned char *buffer, unsigned int len)
{                                                                         
unsigned char *ret = (unsigned char *) malloc ((((len+2)/3)*4)+1);
EVP_EncodeBlock (ret, buffer, len);
ret[(((len+2)/3)*4)] = 0;
return ret;
}

unsigned char *base64_decode (unsigned char *buffer, unsigned int *len)
{                                                                         
unsigned char *ret = (unsigned char *) malloc (((strlen(buffer)+3)/4)*3);
*len = EVP_DecodeBlock (ret, buffer, strlen(buffer));
return ret;
}

Una implementación de Base 64:

Existen muchas implementaciones del algoritmo usado para codificar y descodificar en Base 64. A continuación pego una de Christophe Devine que se encuentra licenciada bajo GPL.


/**
* \file base64.h
*/
#ifndef _BASE64_H
#define _BASE64_H

#ifdef __cplusplus
extern "C" {
#endif

#define ERR_BASE64_BUFFER_TOO_SMALL             0x0010
#define ERR_BASE64_INVALID_CHARACTER            0x0012

/**
* \brief          Encode a buffer into base64 format
*
* \param dst      destination buffer
* \param dlen     size of the buffer (updated after call)
* \param src      source buffer
* \param slen     amount of data to be encoded
*
* \return         0 if successful, or ERR_BASE64_BUFFER_TOO_SMALL.
*                 *dlen is always updated to reflect to amount of
*                 data that was written (or would have been written)
*
* \note           Call this function with *dlen = 0 to obtain the
*                 required buffer size in *dlen
*/
int base64_encode( unsigned char *dst, int *dlen,
unsigned char *src, int  slen );

/**
* \brief          Decode a base64-formatted buffer
*
* \param dst      destination buffer
* \param dlen     size of the buffer (updated after call)
* \param src      source buffer
* \param slen     amount of data to be decoded
*
* \return         0 if successful, ERR_BASE64_BUFFER_TOO_SMALL, or
*                 ERR_BASE64_INVALID_DATA if an invalid char is found.
*                 *dlen is always updated to reflect to amount of
*                 data that was written (or would have been written)
*
* \note           Call this function with *dlen = 0 to obtain the
*                 required buffer size in *dlen
*/
int base64_decode( unsigned char *dst, int *dlen,
unsigned char *src, int  slen );

/**
* \brief          Checkup routine
*
* \return         0 if successful, or 1 if the test failed
*/
int base64_self_test( int verbose );

#ifdef __cplusplus
}
#endif






/*
*  RFC 1521 base64 encoding/decoding
*
*  Copyright (C) 2006-2007  Christophe Devine
*
*  This library is free software; you can redistribute it and/or
*  modify it under the terms of the GNU Lesser General Public
*  License, version 2.1 as published by the Free Software Foundation.
*
*  This library is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
*  Lesser General Public License for more details.
*
*  You should have received a copy of the GNU Lesser General Public
*  License along with this library; if not, write to the Free Software
*  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
*  MA  02110-1301  USA
*/

#ifndef _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_DEPRECATE 1
#endif

#include "xyssl/base64.h"

static const int base64_enc_map[64] =
{
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd',
'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
'y', 'z', '0', '1', '2', '3', '4', '5', '6', '7',
'8', '9', '+', '/'
};

static const int base64_dec_map[128] =
{
127, 127, 127, 127, 127, 127, 127, 127, 127, 127,
127, 127, 127, 127, 127, 127, 127, 127, 127, 127,
127, 127, 127, 127, 127, 127, 127, 127, 127, 127,
127, 127, 127, 127, 127, 127, 127, 127, 127, 127,
127, 127, 127,  62, 127, 127, 127,  63,  52,  53,
54,  55,  56,  57,  58,  59,  60,  61, 127, 127,
127,  64, 127, 127, 127,   0,   1,   2,   3,   4,
5,   6,   7,   8,   9,  10,  11,  12,  13,  14,
15,  16,  17,  18,  19,  20,  21,  22,  23,  24,
25, 127, 127, 127, 127, 127, 127,  26,  27,  28,
29,  30,  31,  32,  33,  34,  35,  36,  37,  38,
39,  40,  41,  42,  43,  44,  45,  46,  47,  48,
49,  50,  51, 127, 127, 127, 127, 127
};

/*
* Encode a buffer into base64 format
*/
int base64_encode( unsigned char *dst, int *dlen,
unsigned char *src, int  slen )
{
int i, n;
int C1, C2, C3;
unsigned char *p;

if( slen == 0 )
return( 0 );

n = ( slen << dlen =" n" n =" (" i =" 0," p =" dst;" c1 =" *src++;" c2 =" *src++;" c3 =" *src++;">> 2 ) & 0x3F];
*p++ = base64_enc_map[((( C1 &  3 ) <<>> 4 )) &amp;amp;amp;amp;amp; 0x3F];
*p++ = base64_enc_map[((( C2 & 15 ) <<>> 6 )) &amp;amp;amp;amp;amp; 0x3F];
*p++ = base64_enc_map[C3 & 0x3F];
}

if( i < c1 =" *src++;" c2 =" ((i">> 2 ) & 0x3F];
*p++ = base64_enc_map[((( C1 & 3 ) <<>> 4 )) &amp;amp;amp;amp;amp; 0x3F];
*p++ = ((i + 1) < dlen =" p" p =" 0" i =" j" n =" 0;">= 2 &&
src[i] == '\r' && src[i + 1] == '\n' )
continue;

if( src[i] == '\n' )
continue;

if( src[i] == '=' && ++j > 2 )
return( ERR_BASE64_INVALID_CHARACTER );

if( src[i] > 127 || base64_dec_map[src[i]] == 127 )
return( ERR_BASE64_INVALID_CHARACTER );

if( base64_dec_map[src[i]] < n ="=" n =" (">> 3;

if( *dlen < dlen =" n;" j =" 3," n =" x" p =" dst;"> 0; i--, src++ )
{
if( *src == '\r' || *src == '\n' )
continue;

j -= ( base64_dec_map[*src] == 64 );
x  = ( x << n ="=" n =" 0;">> 16 );
if( j > 1 ) *p++ = (unsigned char) ( x >> 8 );
if( j > 2 ) *p++ = (unsigned char )  x;
}
}

*dlen = p - dst;

return( 0 );
}

static const char _base64_src[] = "_base64_src";

#if defined(SELF_TEST)

#include 
#include 

static const unsigned char base64_test_dec[64] =
{
0x24, 0x48, 0x6E, 0x56, 0x87, 0x62, 0x5A, 0xBD,
0xBF, 0x17, 0xD9, 0xA2, 0xC4, 0x17, 0x1A, 0x01,
0x94, 0xED, 0x8F, 0x1E, 0x11, 0xB3, 0xD7, 0x09,
0x0C, 0xB6, 0xE9, 0x10, 0x6F, 0x22, 0xEE, 0x13,
0xCA, 0xB3, 0x07, 0x05, 0x76, 0xC9, 0xFA, 0x31,
0x6C, 0x08, 0x34, 0xFF, 0x8D, 0xC2, 0x6C, 0x38,
0x00, 0x43, 0xE9, 0x54, 0x97, 0xAF, 0x50, 0x4B,
0xD1, 0x41, 0xBA, 0x95, 0x31, 0x5A, 0x0B, 0x97
};

static const unsigned char base64_test_enc[] =
"JEhuVodiWr2/F9mixBcaAZTtjx4Rs9cJDLbpEG8i7hPK"
"swcFdsn6MWwINP+Nwmw4AEPpVJevUEvRQbqVMVoLlw==";

/*
* Checkup routine
*/
int base64_self_test( int verbose )
{
int len;
unsigned char *src, buffer[128];

if( verbose != 0 )
printf( "  Base64 encoding test: " );

len = sizeof( buffer );
src = (unsigned char *) base64_test_dec;

if( base64_encode( buffer, &len, src, 64 ) != 0 ||
memcmp( base64_test_enc,  buffer, 88 ) != 0 )
{
if( verbose != 0 )
printf( "failed\n" );

return( 1 );
}

if( verbose != 0 )
printf( "passed\n  Base64 decoding test: " );

len = sizeof( buffer );
src = (unsigned char *) base64_test_enc;

if( base64_decode( buffer, &len, src, 88 ) != 0 ||
memcmp( base64_test_dec,  buffer, 64 ) != 0 )
{
if( verbose != 0 )
printf( "failed\n" );

return( 1 );
}

if( verbose != 0 )
printf( "passed\n\n" );

return( 0 );
}
#else
int base64_self_test( int verbose )
{
return( 0 );
}
#endif


#endif /* base64.h */




Referencias:

- http://es.wikipedia.org/wiki/Base64
- http://xyssl.org/code/source/base64
- OpenSSL




.

El manuscrito Voynich

El manuscrito Voynich es un libro ilustrado escrito, en un lenguaje incomprensible, hace más de 500 años. El nombre de dicho manuscrito proviene de Wilfrid M. Voynich, quien lo adquirió en 1912. Aunque ha sido objeto de estudio demuchos criptógrafos, nadie ha podido descifrar absolutamente nada. Existe la teoría de que el manuscrito Voynich no es más que un fraude, pero aun así, sigue siendo uno de los enigmas sin resolver más conocidos de la criptografía.




Images from the Voynich Manuscript



Se han realizado análisis del texto que muestran patrones similares a las de los lenguajes conocidos. Por ejemplo, la entropía es similar a la de lenguas como el latín o el inglés. Algunas palabras aparecen solo en ciertas secciones, mientras que otras aparecen repetidas una y otra vez a lo largo de todo el manuscrito. Sin embargo existen algunos aspectos del texto que lo hacen diferenciarse de los lenguajes europeos, como por ejemplo, el número de letras de longitud de las palabras. En cualquier caso, si se trata de un montaje, sin duda es un trabajo meticuloso.


Referencias:
- http://es.wikipedia.org/wiki/Manuscrito_Voynich
- http://manuscritovoynich.blogspot.com/

domingo, 22 de julio de 2007

Modos de cifrado: ECB, CBC, CTR, OFB y CFB.

Los algoritmos de cifrado de bloque como DES o AES separan el mensaje en pedazos de tamaño fijo, por ejemplo de 64 o 128 bits. La forma en que se gestionan estos pedazos o bloques de mensaje, se denomina "modo de cifrado". Existen muchos modos de cifrado diferentes, a continuación hablaremos de los más importantes.


ECB - Electronic Code Book Mode:

ECB ha sido estandarizado por el NIST (U.S. National Institute for Standards and Technology). Este modo de cifrado es el más simple de todos, pues se limita a partir el mensaje en bloques y cifrarlos por separado.





Entre las ventajas de este método destaca la posibilidad de romper el mensaje en bloques y cifrarlos en paralelo o el acceso aleatorio a diferentes bloques.

Sin embargo, las desventajas de este modo de cifrado son enormes, por lo que se usa cada vez menos. El hecho de cifrar los bloques por separado implica que cuando se cifre un bloque con cierto valor, siempre se obtendra el mismo resultado. Esto hace posible los ataques de diccionario.
Además, cuando se cifran varios bloques y se envían por un canal inseguro, es posible que un adversario elimine ciertos bloques sin ser detectado, o que capture algunos bloques y los reenvíe más adelante.


CBC - Cipher Block Chaining Mode:

CBC ha sido estandarizado por el NIST (U.S. National Institute for Standards and Technology). Este modo de cifrado es una extensión de ECB que añade cierta seguridad. El modo de cifrado CBC divide el mensaje en bloques y usa XOR para combinar el cifrado del bloque anterior con el texto plano del bloque actual. Como no se dispone de un texto cifrado con el que combinar el primer bloque, se usa un vector de inicialización IV (número aleatorio que puede ser publicamente conocido). El uso del vector de inicialización es importante, pues de no usarlo, podría ser susceptible de ataques de diccionario. También es necesario que el IV sea aleatorio y no un número secuencial o predecible.



Para descifrar el mensaje usaremos el mismo procedimiento a la inversa:




Entre las desventajas de este modo de cifrado destaca la necesidad de realizar el cifrado de forma secuencial (no puede ser paralelizado). Tambien hay que tener en cuenta la posibilidad de realizar ataques de reenvío de un mensaje entero (o parcial).


CTR - Counter Mode:


Mientras que ECB y CBC son modos basados en bloques, CTR simula un cifrado de flujo. Es decir, se usa un cifrado de bloque para producir un flujo pseudo aleatorio conocido como keystream. Este flujo se combina con el texto plano mediante XOR dando lugar al cifrado.
Para generar el keystream se cifra un contador combinado con un número aleatorio (nonce) mediante ECB y se va incrementando. El valor del contador puede ser públicamente conocido, aunque es preferible guardarlo en secreto. Es necesario que el valor de nonce+contador lo conozcan ambos lados de la comunicación.




Entre las ventajas de CTR destaca la posibilidad de precalcular el keystream (y/o trabajar en paralelo), el acceso aleatorio al keystream o que revela poquísima información sobre la clave.

Como desventajas hay que tener en cuenta que reutilizar un contador en la misma clave puede ser desastroso, pues se generará de nuevo el mismo keystream.
Modificar bits en el texto plano es muy sencillo, pues modificando un bit del cifrado se modificará el bit del texto plano correspondiente (Bit-flipping attacks). Por lo que es adecuado usar este modo de cifrado junto con una verificación de la integridad del mensaje.


OFB - Output Feedback Mode:

OFB ha sido estandarizado por el NIST (U.S. National Institute for Standards and Technology). Como CTR es otro cifrado de flujo. En este caso el keystream se genera cifrando el bloque anterior del keystream, dando lugar al siguiente bloque. El primer bloque de keystream se crea cifrando un vector de inicialización IV.




OFB comparte muchas de las características de CTR, pero CTR tiene beneficios adicionales, por lo que OFB se usa bastante poco.
En OFB se pueden precalcular los keystream (aunque no se puede realizar en paralelo) y a diferencia de CTR no da problemas al ser usado con cifrados de bloque de 64 bits. Además, como en el caso de CTR, revela muy poca información sobre la clave.

Tambien comparte con CTR sus desventajas: reutilizar un contador en la misma clave puede ser desastroso y permite Bit-flipping attacks.


CFB - Cipher Feedback Mode:


CFB ha sido estandarizado por el NIST (U.S. National Institute for Standards and Technology) y es muy similar a OFB. Para producir el keystream cifra el último bloque de cifrado, en lugar del último bloque del keystrema como hace OFB.



Como en OFB reutilizar un contador en la misma clave puede ser desastroso y permite Bit-flipping attacks. En CFB el cifrado no puede ser paralelizado, pero el descifrado si.
Igual que en el caso anterior, es preferible usar CTR.


Referencias:
- Block cipher modes of operation - Wikipedia.
- Secure Programming Cookbook, Ed O'Reilly. Viega, Messier.


sábado, 21 de julio de 2007

Hash mediante C y OpenSSL


OpenSSL es una conocida librería que implementa ciertos algoritmos usados en criptografía. Aunque su nombre pareza indicar lo contrario, no es una librería usada únicamente para desarrollar canales SSL, pero esta es una de sus principales funciones. A continuación veremos como usar OpenSSL para implementar algoritmos de hash.

OpenSSL proporciona también un binario que permite usar criptografía desde la linea de comandos. Como el caso que nos ocupa son los algoritmos de hash, veamos primero como usar openssl para tal propósito.

Primero crearemos un fichero de ejemplo y calcularemos su hash con el algoritmo MD5:


$ echo test > test.txt
$ openssl md5 test.txt
MD5(test.txt)= d8e8fca2dc0f896fd7cb4cb0031ba249



Para usar cualquier otro algoritmo de hash (siempre que sea soportado por OpenSSL) usaremos el mismo método. Por ejemplo, para SHA1:


openssl sha1 test.txt
SHA1(test.txt)= 4e1243bd22c66e76c2ba9eddc1f91394e57f9f83



Para usar las funciones de hash de OpenSSL desde el lenguaje C, necesitaremos incluir la cabecera "openssl/evp.h" en nuestras fuentes y llamar a la función OpenSSL_add_all_digests(). A continuación usaremos EVP_get_digestbyname() para obtener el algoritmo de hash que queremos utilizar: md5, sha1, etc. Finalmente, las funciones EVP_DigestInit(), EVP_DigestUpdate() y EVP_DigestFinal() nos permitirán calcular el hash.

Ejemplo:


unsigned char *simple_digest(char *alg, char *buffer, 
unsigned int len, int *olen)
{
EVP_MD *m;
EVP_MD_CTX ctx;
unsigned char *ret;

OpenSSL_add_all_digests ();
if (!(m = (EVP_MD*) EVP_get_digestbyname(alg)))
return NULL;

if (!(ret = (unsigned char *) malloc(EVP_MAX_MD_SIZE)))
return NULL;

EVP_DigestInit(&ctx, m);
EVP_DigestUpdate(&ctx, buffer, len);
EVP_DigestFinal(&ctx, ret, olen);

return ret;
}




La función simple_digest() permite calcular el hash de una cadena pasada como parámetro "buffer" mediante el algoritmo "alg". Pero en el ejemplo anterior en el que usábamos la herramienta openssl, calculábamos el hash de un fichero entero. Para hacerlo, necesitaremos abrir el fichero, ponerlo en un buffer en memoria y llamar a simple_digest(). A continuación pongo un ejemplo completo:



#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <openssl/evp.h>

#define READSIZE 1024

unsigned char *
simple_digest(char *alg, unsigned char *buffer, size_t len, size_t * olen)
{
EVP_MD *m;
EVP_MD_CTX ctx;
unsigned char *ret;

OpenSSL_add_all_digests();
if(!(m = (EVP_MD *) EVP_get_digestbyname(alg)))
return NULL;

if(!(ret = (unsigned char *)malloc(EVP_MAX_MD_SIZE)))
return NULL;

EVP_DigestInit(&ctx, m);
EVP_DigestUpdate(&ctx, buffer, len);
EVP_DigestFinal(&ctx, ret, olen);
return ret;
}

void
print_hex(unsigned char *bs, size_t n)
{
int i;

for(i = 0; i < n; i++)
printf("%02x", bs[i]);
}

unsigned char *
read_file(FILE * f, size_t *len)
{
unsigned char *buffer = NULL, *last = NULL;
unsigned char inbuffer[READSIZE];
int tot, n;

tot = 0;
for(;;)
{
n = fread(inbuffer, sizeof(unsigned char), READSIZE, f);
if(n > 0)
{
last = buffer;
buffer = (unsigned char *)malloc(tot + n);
memcpy(buffer, last, tot);
memcpy(&buffer[tot], inbuffer, n);

if(last)
free(last);
tot += n;

if(feof(f) > 0)
{
*len = tot;
return buffer;
}
}
else
{
if(buffer)
free(buffer);
break;
}
}
return NULL;
}

unsigned char *
process_file(char *algorithm, FILE * f, size_t *olen)
{
size_t filelen;
unsigned char *ret, *contents = read_file(f, &filelen);

if(!contents)
return NULL;

ret = simple_digest(algorithm, contents, filelen, olen);
free(contents);
return ret;
}

int
process_stdin(char *algorithm)
{
size_t olen;
unsigned char *digest = process_file(algorithm, stdin, &olen);

if(!digest)
return 0;

print_hex(digest, olen);
printf("\n");
free(digest);
return 1;
}

void
usage(char *progname)
{

printf("Usage: %s [ md2 | md4 | md5 | sha | sha1 ] [ Files ] \n\n",
progname);
exit(0);
}

int
main(int argc, char *argv[])
{
int i;

/* Sin parametros */
if(argc < 2)
usage(argv[0]);

/* Verificamos los algoritmos */
if((strcmp(argv[1], "md2") != 0) &&
(strcmp(argv[1], "md4") != 0) &&
(strcmp(argv[1], "md5") != 0) &&
(strcmp(argv[1], "sha") != 0) && (strcmp(argv[1], "sha1") != 0))
usage(argv[0]);


/* Un solo parametro, entrada estandar */
if(argc == 2)
{
if(!process_stdin(argv[1]))
perror("stdin");
}

/* Lee y procesa todos los parametros recibidos */
else
{
for(i = 2; i < argc; i++)
{

FILE *file = fopen(argv[i], "rb");
size_t olen;
unsigned char *digest;

if(!file)
{
perror(argv[i]);
return -1;
}

digest = process_file(argv[1], file, &olen);

if(!digest)
{
fclose(file);
return -1;
}

fclose(file);
print_hex(digest, olen);
printf("  %s\n", argv[i]);
free(digest);
}
}
return 1;
}




Finalmente, podemos verificar el correcto funcionamiento de nuestra herramienta comparandola con el binario openssl.


$ gcc -lssl myhash.c -o myhash

$ ./myhash md5 test.txt
d8e8fca2dc0f896fd7cb4cb0031ba249  test.txt

$ openssl md5 test.txt
MD5(test.txt)= d8e8fca2dc0f896fd7cb4cb0031ba249

$ ./myhash sha1 test.txt
4e1243bd22c66e76c2ba9eddc1f91394e57f9f83  test.txt

$ openssl sha1 test.txt
SHA1(test.txt)= 4e1243bd22c66e76c2ba9eddc1f91394e57f9f83



Referencias:
- Network security with OpenSSL, Ed O'Reilly. Viega, Messier, Chandra.

domingo, 15 de julio de 2007

Integer Overflow en Java

En el artículo anterior sobre Integer Overflow, explicaba el concepto y mostraba algunos ejemplos en C. Pues bien, es curioso ver como un lenguaje como Java, considerado muy seguro, también permite este tipo de ataques. Veamos un sencillo ejemplo:


public class ShortOverflow
{
public static void main(String args[])
{
if(args.length<1)         
return;       

short num = Integer.valueOf(args[0]).shortValue();       
System.out.println("num: "+num);       

if(num>100)
System.out.println("num > 100");
else
System.out.println("num < 100");    
}
} 
La versión de máquina virtual usada es la siguiente:
$ java -version
java version "1.5.0_07"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_07-b03)
Java HotSpot(TM) Client VM (build 1.5.0_07-b03, mixed mode, sharing)
Si ejecutamos el ejemplo vemos como se produce el overflow sin que se produzca ninguna excepción:
$ javac ShortOverflow.java
$ java ShortOverflow 100
num: 100
num < 100

$ java ShortOverflow 101
num: 101
num > 100

$java ShortOverflow 100000
num: -31072
num < 100
Atención! se usa la clase Integer, no la clase Short que sí controla la excepción. Por lo que el problema se produce al realizar el cast de int a short, en la función shortValue(). Lo mismo ocurre si utilizamos el tipo Byte:
public class ByteOverflow
{
public static void main(String args[])
{
if(args.length<1)         
return;       

byte num = Integer.valueOf(args[0]).byteValue();       
System.out.println("num: "+num);       

if(num>100)
System.out.println("num > 100");
else
System.out.println("num < 100");    
}
}
$ javac ByteOverflow.java
$ java ByteOverflow 100
num: 100
num < 100

$ java ByteOverflow 101
num: 101
num > 100

$ java ByteOverflow 1000
num: -24
num < 100

Sin embargo, el desbordamiento no se produce si se usa Integer.valueOf("...").intValue(), Short.valueOf("...").shortValue() o similar:
public class IntegerOverflow
{
public static void main(String args[])
{
if(args.length<1)
return;

int num = Integer.valueOf(args[0]).intValue();

System.out.println("num: "+num);

if(num>100)
System.out.println("num > 100");
else
System.out.println("num < 100");

}
}
$ javac IntegerOverflow.java
$ java IntegerOverflow 10
num: 10
num < 100

$ java IntegerOverflow 100000
num: 100000
num > 100

$ java IntegerOverflow 1000000000000000
Exception in thread "main" java.lang.NumberFormatException: For input string: "1000000000000000"
at java.lang.NumberFormatException.forInputString(NumberFormatException.java:48)
at java.lang.Integer.parseInt(Integer.java:459)
at java.lang.Integer.valueOf(Integer.java:553)
at IntegerOverflow.main(IntegerOverflow.java:9)

Krampo en Kriptopolis proporciona una par de enlaces interesantes. En el primero se documenta el comportamiento de shortValue(): http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Number.html#shortValue() En un, muy interesante, segundo enlace se habla del tema: http://mindprod.com/jgloss/overflow.html
Why does Java ignore overflow? Most computer hardware has no ability to automatically generate an interrupt on overflow. And some hardware has no ability to detect it. Java would have to explicitly test for it on every add, subtract and multiply, greatly slowing down production. Further ex-C programmers are very used to this cavalier ignoring of overflow, and commonly write code presuming that high order bits will be quietly dropped. The Pentium has hardware overflow detect but no hardware interrupt. So if Java were to support overflow detect, inside the JVM implementation would need to add a JO *jump on overflow" instruction after every add and subtract, and special code to look at the high order bits of the 32x32->64 bit multiply. 64/32->32 bit division might need special handling.
Para finalizar, veamos un ejemplo ficticio donde se podría explotar este overflow. Supongamos un programa en Java que se utiliza para realizar recargas a teléfonos móviles. Este programa cargará una comisión de un euro en la recarga, y posteriormente, realizará dicha recarga.
public class RecargaMovil
{
public static void main(String args[])
{
if(args.length!=2)
{
System.out.println("Uso: prog [telefono] [importe]");
return;
}

// Aqui se encuentra el error del programador (o vulnerabilidad)
short importe = Integer.valueOf(args[1]).shortValue();
if(importe < = 10)
{
// Quitamos 1 euro de comision;)
importe -= 1;

if(importe<3)
{
System.out.println("Importe demasiado pequeño");
return;
}

System.out.println("Realizando recarga de "+importe+
" euros a "+args[0]);
// Realizar recarga ...
}
else
{
System.out.println("No se permite hacer recargas de mas de 10 euros");
}
}
}
$ java RecargaMovil 93123123 9
Realizando recarga de 8 euros a 93123123

$ java RecargaMovil 93123123 15
No se permite hacer recargas de mas de 10 euros

Si observamos con detenimiento el programa veremos la existencia de un overflow en "importe", al pasar de int a short. Dado que un short permite el almacenamiento de 2^16=65536 valores, o 2^15=32768 por admitir valores con signo, veamos como desbordarlo.
$ java RecargaMovil 98234948 -98302
Importe demasiado pequeño

$ java RecargaMovil 98234948 -98303
Importe demasiado pequeño

$ java RecargaMovil 98234948 -98304
Realizando recarga de 32767 euros a 98234948
Donde "importe" se desborda y nos permite hacer una recarga de 32767 euros:)

sábado, 14 de julio de 2007

Integer Overflow

Un Integer Overflow se produce cuando una operación aritmética intenta almacenar un valor numérico demasiado grande para la variable que lo contiene. De esta forma, si añadimos 1 al valor máximo que una variable puede almacenar, nos encontraremos con resultados curiosos. Veamos que ocurre en un sistema Linux x86.


int main()
{
unsigned short c = 65535;
printf("%d\n", c);
c++;
printf("%d\n", c);
return 0;
}



$ gcc ex1.c
$ ./a.out
65535
0

Como vemos en el ejemplo, al incrementar una variable que ya está en su valor máximo, esta se desborda, empezando de nuevo en el valor cero.
Podemos conocer el valor máximo que se puede almacenar en una variable del lenguaje C usando "sizeof":


int main()
{
printf("size of char: %d bytes\n", sizeof(char));
printf("size of short: %d bytes\n", sizeof(short));
printf("size of int: %d bytes\n", sizeof(int));
printf("size of float: %d bytes\n", sizeof(float));
return 0;
}


$ gcc ex2.c
$ ./a.out
size of char: 1 bytes
size of short: 2 bytes
size of int: 4 bytes
size of float: 4 bytes


Así, por ejemplo, en un char podremos guardar valores menores que 2^8, en un short valores menores que 2^16 y en un int valores menores que 2^32.

En el caso de las variables unsigned, cuando se produce un desbordamiento, nos encontramos con algo similar. Pues si intentamos almacenar un valor negativo en una variable sin signo, se realizará la conversión correspondiente. Por ejemplo, si en una variable "short" podemos almacenar valores menores que 2^16, en una variable "unsigned short" solo podremos almacenar la mitad. Pues se usaran los 2 bytes tanto para almacenar valores positivos como negativos. De esta manera, asignar un valor -1 a un "unsigned short" corresponderá a almacenar el valor 65535, almacenar -2 corresponderá a 65534, y así sucesivamente.


int main()
{
unsigned short c = -1;
printf("%d\n", c);
c++;
printf("%d\n", c);
return 0;
}



$ gcc ex3.c
$ ./a.out
65535
0

No resulta nada complicado hacerse a la idea de como una vulnerabilidad de este tipo puede ser explotada. Por ejemplo, modificando el flujo de ejecución de un programa. En el caso siguiente, se pasa una condición "if" que no debería.


int main(int argc, char *argv[])
{
if(argc != 2)
{
printf("Usage: %s num\n", argv[0]);
return -1;
}

size_t num = atoi(argv[1]);

if(num>100)
printf("num > 100\n");
else
printf("num < 100\n);

return 0;
}



$ gcc ex4.c
$ ./a.out 1
num < 100
$ ./a.out 101
num > 101
$ ./a.out -1
num > 100



Para finalizar, veamos un ejemplo de buffer overflow en el que se muestra cómo usar la longitud de una cadena para escribir fuera del buffer. En este caso la variable que permite el overflow es len, dado que existe la posibilidad de que la longitud de la cadena sea zero. Entonces, el valor de len es -1, o lo que viene a ser lo mismo, 255 por ser una variable "unsigned" de 8 bits. Por este motivo, el memcpy copiará 255 bytes a ptr, unos cuantos más de los necesarios. Realmente lo que se desborda es el heap, por lo que se trata, concretamente, de un heap overflow.


int main(int argc, char *argv[])
{
if(argc<=1)      
return -1;   
char *ptr = malloc(strlen(argv[1]));  
int *login_ok = malloc(sizeof(int));  
*login_ok=0;    
printf("size: %d\n", strlen(argv[1]));  
uint8_t len = strlen(argv[1]) -1;   
memcpy(ptr, argv[1], len+1);  
printf("Login: %d\n", *login_ok);   

if(*login_ok)  
{     
printf("Access Accept\n");  
}  
else  
{     
printf("Access Denied\n");  
}  
return 1;
}  
$ gcc ex5.c
$ ./a.out hola
size: 4
Login: 0
Access Denied

$ ./a.out adiossssssssssssssssssssss
size: 26
Login: 0
Access Denied

$ ./a.out ""
size: 0
Login: 3618355
Access Accept