El Blog de Daniel Lerch

Sockets multiplataforma con GTK+

2012-01-26T18:33:00.000+01:00

Recientemente hemos visto como realizar compilación cruzada con GTK+. Esto nos permite escribir aplicaciones que se ejecutan en diferentes plataformas, almenos a nivel gráfico.

Vamos a ver ahora como usar sockets TCP, algo que habitualmente suele estar muy ligado a una plataforma concreta. GTK+ (de hecho es GLIB) nos proporciona una API para acceder a la red. Esta API, al igual que GTK+ es multiplataforma.

Escribiremos un cliente TCP sencillo, que se conectará a un puerto, escribirá un mensaje, y leerá la respuesta.

Primero incluimos las cabeceras habituales en un programa C, junto con las cabeceras de GTK+.

#include <stdio.h>
#include <string.h>
#include <gtk/gtk.h>

Necesitamos las siguientes variables;

GError *err = NULL;
GSocket *sock = NULL;
GInetAddress *iaddr = NULL;
GSocketAddress *saddr = NULL;
GCancellable *cancel = NULL;

Usamos las siguientes funciones para inicializar las variables que contienen las direcciones de red. Lògicamente con la IP y puerto que convenga:

g_type_init();
iaddr = g_inet_address_new_from_string("192.168.1.1");
saddr = g_inet_socket_address_new(iaddr, 23);

Abrimos el socket y nos conectamos a el:

sock = g_socket_new(
   G_SOCKET_FAMILY_IPV4,
   G_SOCKET_TYPE_STREAM,
   G_SOCKET_PROTOCOL_TCP,
   &err);

f(!g_socket_connect(sock, saddr, cancel, &err))
{
   printf("Cannot connect\n");
   return -1;
}

Y finalmente, enviamos y recibimos datos:

   char buf[256];
   strncpy(buf, "lst\n", sizeof(buf));
   g_socket_send(sock, buf, strlen(buf), cancel, &err);
   g_socket_receive(sock, buf, sizeof(buf), cancel, &err);

   printf("received:\n%s\n", buf);

Sencillo, ¿no?

Sockets TCP con Bash

2012-01-25T17:25:00.000+01:00

Es muy habitual, cuando se escriben scripts en Bash, recurrir a herramientas como "netcat" para realizar comunicaciones de red. Sin embargo, aunque no es muy conocido, Bash soporta sockets.

Veamos como conectarnos, por ejemplo, a google.

Abrimos el socket y le asociamos el descriptor 3. Recordemos que 0, 1 y 2 se usan habitualmente para la entrada y salida estándard y para la salida de error.

$ exec 3<>/dev/tcp/www.google.com/80

A continuación, enviamos un mensaje por el socket:

$ echo "GET /" >&3

Y finalmente, leemos la respuesta del servidor:

$ cat <&3

HTTP/1.0 302 Found
Location: http://www.google.es/
Cache-Control: private
Content-Type: text/html; charset=UTF-8
Set-Cookie: PREF=ID=a38d7ed8770f70cb:FF=0:TM=1327418982:LM=1327418982:S=0tgHEV7GxJaC6Wl7; expires=Thu, 23-Jan-2014 15:29:42 GMT; path=/; domain=.google.com
Date: Tue, 24 Jan 2012 15:29:42 GMT
Server: gws
Content-Length: 218
X-XSS-Protection: 1; mode=block
X-Frame-Options: SAMEORIGIN
...

Compila en Linux y ejecuta en Windows con GTK+

2012-01-24T15:14:00.000+01:00

Vamos a ver como realizar una compilación cruzada con las librerías de GTK+. Esto nos permitirá compilar el programa en Linux y ejecutarlo en Windows, por lo que podremos tener programas funcionando en Windows sin tener que usarlo.

Lo primero que tenemos que hacer es instalar el compilador mingw. En mi distribución vale con:

sudo apt-get install mingw32

A continuación tenemos que descargar las librerías necesarias de windows en nuestro Linux. Podemos encontrarlas en

$ wget http://ftp.gnome.org/pub/gnome/binaries/win32/glib/2.28/glib-dev_2.28.8-1_win32.zip
$ wget http://ftp.gnome.org/pub/gnome/binaries/win32/atk/1.32/atk-dev_1.32.0-2_win32.zip
$ wget http://ftp.gnome.org/pub/gnome/binaries/win32/pango/1.29/pango-dev_1.29.4-1_win32.zip
$ wget http://ftp.gnome.org/pub/gnome/binaries/win32/dependencies/cairo-dev_1.10.2-2_win32.zip
$ wget http://ftp.gnome.org/pub/gnome/binaries/win32/dependencies/libpng-dev_1.4.3-1_win32.zip
$ wget http://ftp.gnome.org/pub/gnome/binaries/win32/dependencies/gettext-runtime-dev_0.18.1.1-2_win32.zip
$ wget http://ftp.gnome.org/pub/gnome/binaries/win32/gtk+/2.24/gtk+-dev_2.24.8-1_win32.zip
$ wget http://ftp.gnome.org/pub/gnome/binaries/win32/dependencies/fontconfig-dev_2.8.0-2_win32.zip
$ wget http://ftp.gnome.org/pub/gnome/binaries/win32/gdk-pixbuf/2.24/gdk-pixbuf-dev_2.24.0-1_win32.zip

Descomprimiremos los zip dentro del directorio donde se instala mingw. Habitualmente:

/usr/i586-mingw32msvc/

Entramos en dicho directorio y realizamos algunos ajustes:

sed -i 's|^prefix=.*$|prefix=/usr/i586-mingw32msvc|g' lib/pkgconfig/*.pc
cd ./lib
for f in *.lib;
   do mv $f lib${f%%lib}a;
done

En mi caso faltaba un archivo en pkgconfig, lo he corregido con:

$ cp /usr/lib/i386-linux-gnu/pkgconfig/freetype2.pc  pkgconfig/

Pero podría estar ubicado en otro sitio en otras distros.

Llegados a este punto ya deberíamos poder compilar tanto para windows como para linux.

Si compilamos con el siguiente comando:

i586-mingw32msvc-gcc main.c `PKG_CONFIG_LIBDIR=/usr/i586-mingw32msvc/lib/pkgconfig PKG_CONFIG_PATH=/usr/i586-mingw32msvc/lib/pkgconfig pkg-config --cflags --libs gtk+-2.0`

generaremos un ejecutable para Windows. En este caso "a.exe".

Y si compilamos con este comando:

gcc main.c `pkg-config --cflags --libs gtk+-2.0 gmodule-export-2.0`

Obtendremos un ejecutable para Linux "a.out". Ya tenemos pues, nuestro sistema de compilación cruzada preparado.

Ya podemos trasladar nuestro ejecutable a Windows y probarlo. Para que funcione es necesario haber instalado GTK+ para Windows.

Esteganografía LSB en imágenes bitmap

2012-01-21T12:04:00.002+01:00

Uno de los métodos más populares de Esteganografía consiste en modificar el valor del bit menos significativo de cada píxel, el LSB (Least Significant Bit). En este artículo vemos como hacerlo en imágenes de tipo bitmap, es decir, aquellas que estan estructuradas como matrices de números donde cada número representa un píxel (eso solo es cierto en imágenes en escala de grises. En imágenes en color existen varias representaciones como la RGB donde cada píxel está representado por tres valores, correspondientes a la cantidad de color rojo, la cantidad de color verde y la cantidad de color azul).

El motivo de usar el LSB es que su alteración no sueles ser perceptible visualmente (a menos que la imagen sea muy baja resolución)

Inserción secuencial:

El método más sencillo consiste en separar los bytes que forman el mensaje en bits individuales. A continuación se recorren los píxeles de la imagen modificando su LSB de manera que quede igual que el del mensaje. Supongamos que queremos esconder un mensaje que empieza por 'H'. El valor en binario de la letra 'H' es 1001000. Por lo tanto tendremos que insertar:

1 0 0 1 0 0 0

Imaginemos ahora que los primeros 8 píxeles de la imagen corresponden a los bytes:

100 101 101 102 102 101 103

El primer píxel, correspondiente al valor 100 se representa en binario como 1100100. Dado que tenemos que modificar su LSB y ponerlo a uno, como el primer bit del mensaje, tendremos 1100101, que corresponde al valor de píxel 101. La operación es muy sencilla, si tenemos un valor de píxel par y queremos insertar un cero, no modificaremos el valor del píxel, pero si queremos insertar un uno, le sumaremos uno. Si por el contrario tenemos un píxel impar y queremos insertar un uno, no modificaremos su valor, pero si queremos insertar un cero, le restaremos uno.

Así, el primer byte queda como 101, el segundo como 100, el tercero como 100, etc

101 100 100 103 102 100 102

Para leer el mensaje solo tendremos que extraer los LSB de todos los píxeles.

Inserción aleatoria:

Insertar el mensaje de forma secuencial no es una forma muy acertada de hacerlo. Esto permite al atacante extraer el mensaje, por lo que, si no está cifrado, solo tiene que verificar que es legible (en una imagen sin mensaje oculto no lo sería).

Por este motivo es más aconsejable usar un generador pseudoaleatorio PRNG basado en una clave o contraseña, que eliga aleatoriamente los píxels en los que incrustar datos. De esta manera no bastaría con una simple extracción de todos los LSB.

Reducción del bitrate:

Aún y la enorme dificultad de conseguir el mensaje que ha sido ocultado usando un PRNG (necessitaríamos adivinar la contraseña), el objetivo de la esteganografía es hacer el mensaje indetectable, no indescifrable (de eso se encarga la criptografía). Por ello tenemos que intentar que la distribución estadística de los píxeles de la imagen se vea alterada lo menos posible. Si usamos bitrate 1, es decir, si modificamos todos los píxeles de la imagen, la distribución estadística se verá tan alterada que sermoes detectados sin demasiada dificultad. Por ello es conveniente reducir en la medida de lo posible el bitrate de inserción.

Los ataques existentes en la actualidad a los sistemas LSB son tan sofisticados que detectan alteraciones por encima de bitrates de 0,03. Es decir, que si no queremos ser detectados, deberíamos modificar como mucho el 3% de la imagen y hacerlo de forma aleatoria.

Introducción a Arduino Ethernet: Hello World

2012-01-20T22:28:00.001+01:00

Arduino es una plataforma de Hardware abierto cada vez más popular. Permite, de forma sencilla, realizar montajes electrónicos y programarlos. Recientemente ha aparecido en escena Arduino Ethernet, que a diferencia de los anteriores (Arduino Uno y Arduino Duemilanove, entre otros) tiene conexión RJ45 y soporte TCP/IP.

En este post vamos a realizar una breve introducción a Arduino Ethernet, viendo como dar los primeros pasos.

El programador:

A difernecia de los arduinos anteriores, que tenían una conexión USB que permitía cargar el firmware y depurar, el Arduino Ethernet solo tiene la conexión RJ45. Por ello es necesario usar el conector de la foto para programarlo:

Para poder usar este conector es necesario usar un programador. Existen multitud en el mercado. Por ejemplo este de Atmel.

Otra opción más económica consiste en usar el adaptador a USB.

El programa:

El programa más sencillo que se puede hacer con Arduino, y que nos muestre su funcionamiento, es hacer parpadear un led. Concretamente el led 13, que es el único que tiene. Seria el equivalente al típico "Hello World". El programa es el siguiente:

void setup()
{
   pinMode(13, OUTPUT);
}

void loop()
{
   digitalWrite(13, HIGH);
   delay(1000);
   digitalWrite(13, LOW);
   delay(1000);
}

El entorno de Arduino llama a la función setup() al iniciar. Aprovechamos esta función para configurar el pin 13 como salida. La función loop() es llamada indefinidamente, por lo que en ella ponemos el cuerpo del programa. Lo que hacemos es encender el led, esperar un segundo, apagar el led y esperar de nuevo.

Cargar el firmware:

Una vez tenemos el programa podemos cargarlo al Arduino de dos formas, en función de si disponemos del adaptador USB o del programador.

En el primer caso podemos usar el software de Arduino. Es la forma más sencilla, simplemente escribimos el programa en el entorno de programación y lo cargamos con la opción "Upload".

Si queremos usar el programador, la forma más sencilla de hacerlo consiste en usar el entorno de programación de Arduino para compilar el programa y el programa avrdude para subir el firmware. Podemos hacerlo con el siguiente comando:

sudo avrdude -c avrispmkII -p m328p -u -U flash:w:firmware.hex -P usb

Donde firmware.hex es el archivo generado por el entorno de programación de Arduino.

Resultados:

Si todo ha funcionado como es debido, veremos como el led de la placa parpadea. Ya tenemos nuestro "Hello World"!

Esteganografía moderna

2012-01-19T22:02:00.001+01:00

La primera aparición de la Esteganografía en medios digitales la realizó G. J. Simmons en 1983 [1]. En el se habla de las posibles implicaciones políticas de enviar datos a través de canales encubiertos y se plantea el problema del prisionero.

El problema del prisionero:

Alice y Bob son encarcelados en celdas separadas. Pueden comunicarse y quieren planear una fuga, pero sus mensajes son monitorizados por el carcelero Eve. Si Eve descubre que Alice y Bob están intercambiando mensajes secretos no dejará que vuelvan a comunicarse. Por ello, Alice y Bob recurren a la Esteganografía para comunicarse.

En el problema el prisionero hay que destacar que Eve cortará la comunicación si detecta que Alice y Bob se comunican de manera secreta. No es necesario que Eve tenga acceso al mensaje, sólo que lo detecte. Así, un sistema de Esteganografía se considerará roto si puede ser detectada la existencia de un mensaje. No es necesario acceder a su contenido, esto formaría parte del Estegoanálsisis forense (extracción del mensaje) y del criptoanálisis (descifrado del mensaje).

En el problema del prisionero se asume que Eve conoce el algoritmo usado para esconder los datos pero no la clave. Este es un requisito tomado de la Criptografía, que forma parte de los conocidos Principios de Kerchhoff

Referencias:

[1] G. J. Simmons. The prisoner's problem and the subliminal channel. D. Chaum editor, advances in Criptology, CRYPTO '83, pages 51-67, Santa Barbara, CA, August 22-24, 1983. New York: Plenum Press.

Control del Árbol de Navidad con OpenDomo

2010-12-29T17:07:00.001+01:00

Vemos en OpenDomo un video donde se muestra paso a paso como usar el Kit de desarrollo de OpenDomo para controlar un árbol de Navidad. Aunque serviría para controlar cualquier dispositivo eléctrico.

Os dejo la URL del video.

Cryptoland

2010-11-11T20:00:00.000+01:00

Cryptograms, puzzles, programming and other challenges.

http://twitter.com/#!/cryptoland

OpenDomo 0.8.3 publicado

2010-06-13T13:31:00.004+02:00

La versión 0.8.3 de OpenDomo ha visto la luz recientemente. Para el que todavía no lo sepa, OpenDomo es un sofware de domótica completamente libre, que permite entre otras cosas, controlar dispositivos eléctricos o disponer de un sistema de videovigilancia. Así que si no lo has probado todavía, a qué esperas!!!

A continuación dejo una lista de los cambios más importantes, respecto a la versión anterior.

La distribución incluye:

Kernel linux versión 2.6.33
Kit de herramientas busybox versión 1.16.1 (toolchain actualizado a 2010.05)
odpkg, odcgi, odcommon y oddiscovery preinstalados en el sistema base

Además de incluir gran parte de los paquetes habituales, las principales novedades son:

Nueva arquitectura de gestión de discos con libata, el nuevo controlador del kernel de linux
Múltiples actualizaciones de las herramientas del sistema base, con importantes mejoras de estabilidad
Cherokee incluido en el repositorio local, para un mayor rendimiento y seguridad en las conexiones
Nuevo formato unificado de configuración, empezando por los archivos network.conf y opendomo.cfg, afectando también a la videovigilancia
Scripts de uso común optimizados para un máximo rendimiento en equipos pequeños
División por zonas soportada por odvideo y odcontrol, permitiendo configurar las cámaras y dispositivos que se encuentran en cada una de ellas
Actualización manual desde ISO soportada, permitiendo una mejor transición entre versiones
Interfaz web parcialmente reescrita incorporando funciones complementarias en Javascript. Scripts de configuración de la interfaz integrados y temas visuales renovados. Caché habilitada, reduciendo en un 20% la transferencia por HTTP
Posibilidad de almacenar librerías y archivos log en disco, permitiendo la instalación de paquetes de gran tamaño sin riesgo de agotar el ramdrive
Mejoras en la gestión de almacenaje, permitiendo el arranque desde CD/ISO, almacenando la configuración en disco

Acceso 'tipo BSD' al histórico de Bash

2010-06-10T20:00:00.000+02:00

Una cosa que siempre añoré de la shell de los sistemas BSD es la posiblidad de recorrer el histórico de comandos que empiezan con los caracteres tecleados en consola. En ocasiones mucho más práctico que el Ctrl+R habitual de Bash.

Pues bien, ahora puedo tenerlos los dos :)

Solo es necesario añadir a /etc/inputrc estas dos lineas.

"\e[5~": history-search-backward

"\e[6~": history-search-forward

Lo que le dará a Bash esta interesante funcionalidad con las teclas RePag y AvPag.

Criptograma 30/05/010

2010-05-30T23:00:00.002+02:00

CSQSQ TLTDR UTOHT CRVHP WYETU SWSHT RYSHP
LETYT OSVSW RHHPW YETRE LTOCT PVHCT PVXXX

Criptograma 19/02/10

2010-02-19T08:27:00.000+01:00

Después de algun tiempo de descanso, vamos con uno de facilito:

LDDOF ENADR AOCSL ASSGX APENU GZLEO DDYEL CAAAR HALSE AATMU
INAOA LMTIA URAUR DRAIC NEDLH ASORM MTNSZ OLSSH AIAOO AACEO

Criptograma 30/07/09: Solución

2009-12-31T13:46:00.001+01:00

Viendo que acaba el año y el criptograma continúa inexpugnable, aquí os dejo la solución.

CIFRADO:
BPJTALUJBPUPRFBIISASIYRTJTMSAKGMCPCRRPPBALC
AAKTPSOCUPFAPKIFKRNOPRSKABPUPSMDFSOKETCPFCP

CLAVE:
CRISIS

MENSAJE:
EN LOS MOMENTOS DE CRISIS SOLO LA IMAGINACION
ES MAS IMPORTANTE QUE EL CONOCIMIENTO
ALBERT EINSTEIN

Aprovecho para desearos un feliz comienzo de año!

Criptograma 30/07/09: Pista

2009-10-25T18:24:00.004+01:00

Dado que se resiste, y ni el increible Altair consigue dar con la solución, ahí va una pista.

Se trata de un cifrado Playfair.

Criptograma 30/07/09

Criptograma 16/07/09: Solución

2009-10-25T18:18:00.002+01:00

Cada par de letras del criptograma correspondía a una letra del mensaje en claro. Tomando esto como hipótesis se podía recurrir a un análisis de frecuencias tradicional.

Enhorabuena Altair.

HO LA BU HO DE MI MA HO LA SI TU MA
E S M E J O R E S T A R

CE TU NA NA TU BI MI CI RU TU MA HO
C A L L A D O Y P A R E

CE HO MA SI MI RU SI MI RE FA HO DO
C E R T O N T O Q U E H

TU BL NA TU MA CI BI HO LA RU HO SS
A B L A R Y D E S P E J

TU MA NA TU LA BI FA BI TU LA BI HO
A R L A S D U D A S D E

GR UX RU UX SI UX GU TU BU HO RU SI
F I N I T I V A M E N T

HO RR MA MI FA YY MI BU TU MA YY
E G R O U X O M A R X

ssh en batch sin expect

2009-09-04T10:02:00.003+02:00

Ssh y scp no permiten pasar la contraseña como parámetro, lo que complica las cosas a la hora de automatizar tareas. Normalmente se suele recurrir a dos tipos de soluciones: distribuir claves sin password y/o usar expect. La primera no siempre es posible, pues a veces no se tiene el control del servidor. La segunda es más habitual, aunque en ocasiones no se dispone de 'expect', problema con el que me he encontrado recientemente en el proyecto OpenDomo.

Como consecuencia he desarrollado la herramienta sshbatch, que permite realizar comandos ssh y scp pasando la passwd como parámetro.

Dejo aquí una copia del programa en C y un enlace al grupo de OpenDomo donde expliqué como funciona.

Cómo funciona el exploit sock_sendpage()

2009-08-16T08:22:00.013+02:00

Tavis Ormandy y Julien Tinnes, del equipo de seguridad de Google, han descubierto un bug en el kernel Linux que nadie ha sido capaz de ver en los últimos ocho años. Este bug, que afecta a todas las versiones del kernel desde la 2.4.4 a la 2.4.37.4 y desde la 2.6.0 a la 2.6.30.4 permite escalar privilegios en el sistema. En este artículo vamos a analizar su funcionamiento.

Primer error:

Todo comienza en la función sock_sendpage() situada en net/socket.c. El problema reside en la llamada a sendpage() pues no se ha verificado que el puntero esté inicializado.

static ssize_t sock_sendpage(struct file *file, struct page *page,
              int offset, size_t size, loff_t *ppos, int more)
{
   struct socket *sock;
   int flags;

   sock = file->private_data;

   flags = !(file->f_flags & O_NONBLOCK) ? 0 : MSG_DONTWAIT;
   if (more)
      flags |= MSG_MORE;

   return sock->ops->sendpage(sock, page, offset, size, flags);
}

A continuación, dejo una copia de la función sock_splice_read() que no tiene nada que ver ni con el bug ni con el exploit, pero nos sirve para ver como se podría haber evitado la vulnerabilidad. En esta función se verifica el puntero a la función mediante unlikely() antes su llamada.

static ssize_t sock_splice_read(struct file *file, loff_t *ppos,
                 struct pipe_inode_info *pipe, size_t len,
            unsigned int flags)
{
   struct socket *sock = file->private_data;

   if (unlikely(!sock->ops->splice_read))
      return -EINVAL;

   return sock->ops->splice_read(sock, ppos, pipe, len, flags);
}

Segundo error:

Hemos visto que no se verifica si el puntero a sendpage() esta correctamente inicializado. Sera necesario ahora, encontrar situaciones en las que el puntero a la función sendpage() no se haya inicialiado.

Tavis Ormandy y Julien Tinnes en su investigación localizaron deficiencias en la incialización del puntero para la macro SOCKOPS_WRAP, definida en include/linux/net.h, que incluye PF_APPLETALK, PF_IPX, PF_IRDA, PF_X25 y PF_AX25. Tambien encontraron deficiencias en otros protocolos como PF_BLUETOOTH, PF_IUCV, PF_INET6 (con IPPROTO_SCTP), PF_PPPOX y PF_ISDN.

Veamos por ejemplo el caso del protocolo bluetooth. En net/bluetooth/bnep/sock.c nos encontramos con la estructura bnet_sock_ops en la que vemos que no se inicializa sendpage con sock_no_sendpage(), por lo que quedará apuntando a NULL.

static const struct proto_ops bnep_sock_ops = { 
        .family         = PF_BLUETOOTH,
        .owner          = THIS_MODULE,
        .release        = bnep_sock_release,
        .ioctl          = bnep_sock_ioctl,
#ifdef CONFIG_COMPAT
        .compat_ioctl   = bnep_sock_compat_ioctl,
#endif
        .bind           = sock_no_bind,
        .getname        = sock_no_getname,
        .sendmsg        = sock_no_sendmsg,
        .recvmsg        = sock_no_recvmsg,
        .poll           = sock_no_poll,
        .listen         = sock_no_listen,
        .shutdown       = sock_no_shutdown,
        .setsockopt     = sock_no_setsockopt,
        .getsockopt     = sock_no_getsockopt,
        .connect        = sock_no_connect,
        .socketpair     = sock_no_socketpair,
        .accept         = sock_no_accept,
        .mmap           = sock_no_mmap
};

El caso de SOCKOPS_WRAP es mas sutil, pues en net/ipx/af_ipx.c todo parece correcto. Podemos ver la inicialización en la última linea.

static const struct proto_ops SOCKOPS_WRAPPED(ipx_dgram_ops) = {
        .family         = PF_IPX,
        .owner          = THIS_MODULE,
        .release        = ipx_release,
        .bind           = ipx_bind,
        .connect        = ipx_connect,
        .socketpair     = sock_no_socketpair,
        .accept         = sock_no_accept,
        .getname        = ipx_getname,
        .poll           = datagram_poll,
        .ioctl          = ipx_ioctl,
#ifdef CONFIG_COMPAT
        .compat_ioctl   = ipx_compat_ioctl,
#endif
        .listen         = sock_no_listen,
        .shutdown       = sock_no_shutdown, /* FIXME: support shutdown */
        .setsockopt     = ipx_setsockopt,
        .getsockopt     = ipx_getsockopt,
        .sendmsg        = ipx_sendmsg,
        .recvmsg        = ipx_recvmsg,
        .mmap           = sock_no_mmap,
        .sendpage       = sock_no_sendpage,
};

Sin embargo, si estudiamos con detenimiento la macro SOCKOPS_WRAP en include/linux/net.h vemos que mietras otras llamadas se inicializan correctamente, no se realiza la inicialización de sendpage.
No pego el código por que es demasiado largo, consultar en include/linux/net.h y ver que la última inicialización es la de mmap(), olvidando sendpage().

Cómo explotarlo?
Lo primero que necesitaremos para explotar esta vulnerabilidad es una función que podamos ejecutar en espacio de usuario que use sock_sendpage(). Hay muchas funciones que lo hacen, una de ellas es sendfile().

Tavis Ormandy y Julien Tinnes y proponen como secuencia válida de llamadas para forzar el uso de sendpage(), la siguiente:

/* ... */
int fdin = mkstemp(template);
int fdout = socket(PF_PPPOX, SOCK_DGRAM, 0);

unlink(template);

ftruncate(fdin, PAGE_SIZE);

sendfile(fdout, fdin, NULL, PAGE_SIZE);
/* ... */

Cuando se ejecute la función sendpage(), si esta no está inicializada y apunta a NULL, el kernel intentará ejecutar las instrucciones que hay en la dirección 0. Podemos aprovechar esto mapeando la dirección 0 y almacenando allí las instrucciones que queremos que ejecute el kernel. Así, cuando se intente ejecutar sendpage() realmente se ejecutará nuestro código en espacio de kernel. Podremos escalar privilegios haciendo que el código almecando en la dirección 0 ponga nuestros uid a cero (root).

Este tipo de bugs son muy comunes en el kernel Linux y se conocen como bugs por 'NULL pointer dereference'. Ya vimos aquí uno de estos con el exploit vmsplice.

En las referencias dejo un ejemplo de exploit.

referencias:

- http://www.securityfocus.com/archive/1/505751
- http://blog.cr0.org/2009/08/linux-null-pointer-dereference-due-to.html
- exploit: http://www.frasunek.com/proto_ops.tgz

Criptograma Principiantes 05/08/09

2009-08-05T14:00:00.000+02:00

RJ BZR KWPSJHLMHZR CJMJLRLG LAJVJMJZR AL BK NJRNK VZWNK LG PSL BZR UWZOWKNKAZWLR LRMWJTLG UWZOWKNKR, LB UWJNLW UKQKWZ MKWUJGHLWZ PSL UKRKRL UZW KPSJ ALRHWSJWJK BK MJXJBJFKMJZG.

OLWKBA ILJNTLWO

Criptograma 30/07/09

2009-07-30T13:48:00.002+02:00

BPJTALUJBPUPRFBIISASIYRTJTMSAKGMCPCRRPPBALC

AAKTPSOCUPFAPKIFKRNOPRSKABPUPSMDFSOKETCPFCP

El impresionante Robot Asimo de Honda

2009-07-24T22:13:00.001+02:00

Empezó siendo un robot torpón que a duras penas andaba. Después nos sorprendió subiendo escalareas... e incluso corriendo. Increible lo que estan consiguiendo los ingenieros de Honda.

Criptograma 16/07/09

2009-07-16T01:08:00.001+02:00

HOLAB UHODE MIMAH OLASI TUMAC ETUNA NATUB IMICI RUTUM
AHOCE HOMAS IMIRU SIMIR EFAHO DOTUB LNATU MACIB IHOLA
RUHOS STUMA NATUL ABIFA BITUL ABIHO GRUXR UUXSI UXGUT
UBUHO RUSIH ORRMA MIFAY YMIBU TUMAY YXXXX

Comandos útiles para Vim

2009-07-09T08:27:00.007+02:00

" las funciones de autocompletado buscan en los directorios indicados

: set path=/usr/include,/usr/local/include

" Habilita el coloreado de sintaxis

: syntax on

" habilita el auto indentado

: set autoindent

" habilita el auto indentado inteligente

: set smartindent

" Define 3 espacios para el indentado

:set shiftwidth=3

" Convierte tabulados en espacios. Deshabilitar con :set noexpandtab

: set expandtab

" Hace que los tabuladores sean de tres espacios

: set tabstop=3

" Plega bloques delimitados por {{{ }}}. Usando fdm=syntax no se necesitan marcas

: set fdm=marker

" Establece los nivels de anidamiento para plegar código.

: set foldnestmax=1

" Marca el parentesis/llave que abre y el que cierra al situarse encima.

: set showmatch

" La marca habilitada con 'showmatch' dura un segundo.
: set matchtime=1

" Aparecen indicadores con el numero de linea, de columna, etc.

: set ruler

" Cuando se abre un archivo coloca el cursor en su posicion del ultimo cierre

if has("autocmd")

au BufReadPost * if line("'\"") > 0 && line("'\"") <= line("$")

\| exe "normal! g'\"" | endif

endif

" Pinta los resultados de la busqueda

: set hlsearch

" Cierra un bloque delimitado por {{{ }}}.
" Se abre pulsando el espacio sobre el bloque.
: foldclose

" Entra en modo insercion a continuacion de la posicion actual
a

" Entra en modo insercion en la posicion actual
i

" Deshace los cambios
u

" Rehace los cambios

:redo

" Guarda los cambios

:w!

" Guarda los cambios en el fiechero 'file'
:w! file

" Sale sin guardar

:q!

" Mueve el cursor al final del fichero
G

" Mueve el cursor al principio del fichero

" Mueve el cursor a la linea N

N G

" Entra en modo visual. Seleccion a nivel de columnas.

ctrl + v

" Entra en modo visual. Seleccion de todo el texto.

ctrl + v v

" Corta/borra el texto seleccionado

" Copia el texto seleccionado

" Pega el texto del portapapeles

" Sustituye from por to, pidiendo confirmacion
:%s/from/to/gc

" Sustituye from por to, pidiendo confirmacion de un texto seleccionado.

:'<,'>s/from/to/gc

" Ir al principio de la linea

" Ir al final de la linea

" Ir a la palabra siguiente

" Busca palabras como la situada debajo del cursor

" Abre la pagina man de la función sobre la que se encuentra el cursor

" Salta a la definición/declaración de la variable sobre la que se encuentra el cursor

" Salta al parentesis/llave asociado al parentesis/llave sobre el que se encuentra el cursor

" Abre una pestaña con el fichero 'file'

: tabnew file

# Salta de una pestaña a otra

" Divide la ventana en dos abriendo el fichero 'file'

: split file

" Salta de una ventana a otra

Ctrl+w w

" Autocompleta la palabra

Ctrl + p

Ctrl + n

Estamos dentro de VMWare?

2009-07-06T07:31:00.000+02:00

A continuacion dejo un programa que permite detectar si nuestro servidor se encuentra dentro de una maquina virtual VMWare. Utiliza una tecnica descubierta por Ken Kato que consiste en encontrar el Backdoor I/O port. Este puerto es el que utiliza VMWare para comunicarse con la maquina virtual. Como dicho puerto no existe en un servidor normal su deteccion indica que nos encontramos bajo VMWare.

/*
 * 4tphi-vmchk.c
 * Detects if you are in a VMWare virtual machine.
 *
 * Written by Andrew Hintz 
 * and AAron Walters
 * Fortify Research Laboratories 
 *
 * "Oft at the hives of his tame bees
 * They would their sugary thirst appease."
 *
 * This program is based on info and code from:
 * http://chitchat.tripod.co.jp/vmware/
 * by chitchat_at_lycos.jp
 *
 * Notes:
 * The program can be run as a normal user.
 * We tested the program only in x86 Linux.
 * The m4dn3ss lives on!
 */

#include <stdio.h>
#include <stdlib.h>
#include <sys/signal.h>

#if __INTSIZE == 2 /* 16 bit environment */
typedef unsigned int uint16;
typedef unsigned long uint32;
#else /* 32 bit environment */
typedef unsigned short uint16;
typedef unsigned int uint32;
#endif /* __INTSIZE */

void segfault()
{
  printf("Not running inside VMware.\n");
  exit(1);
}

int main()
{
  uint32 verMajor, verMinor, magic, dout;

  signal(SIGSEGV, segfault);

  __asm__ __volatile__ 
   (
   "mov $0x564D5868, %%eax; /* magic number */"
   "mov $0x3c6cf712, %%ebx; /* random number */"
   "mov $0x0000000A, %%ecx; /* specifies command */"
   "mov $0x5658, %%edx; /* VMware I/O port */"
   "in %%dx, %%eax;"
   "mov %%eax, %0;"
   "mov %%ebx, %1;"
   "mov %%ecx, %2;"
   "mov %%edx, %3;"
    : "=r"(verMajor), "=r"(magic), "=r"(verMinor), "=r"(dout)
    );

  if (magic == 0x564D5868) 
  {
    printf("Running inside VMware. ");
    printf("(Version %lu,%lu)\n", verMajor, verMinor);
    /* I'm not really sure what the versions mean. */
  }

  return 0;

}

OpenDomo visto desde un iPod touch

2009-06-17T23:40:00.004+02:00

Dejo una foto de un sistema OpenDomo controlado desde un iPod Touch, en el se accede al sistema de videovigilancia.
Cortesía de Isidro, uno de los desarrolladores principales de OpenDomo.

Enlace original:
http://www.opendomo.com/drupal/node/55

Control de sensores e interruptores con OpenDomo

2009-06-17T23:28:00.001+02:00

Recientemente he publicado un manual en OpenDomo que explica como controlar sensores e interruptores.
Por fin opendomo puede usarse en sistemas reales, aunque esté todavía en fase alpha.

Dejop un enlace al manual:

¿Cómo controlar sensores e interruptores con OpenDomo y Micropik PS3X8?

Criptograma 11/04/09: Solución

2009-06-12T07:31:00.004+02:00

Se trataba de un autocifrado, cuya clave era nada más y nada menos que "AUTOCIFRADO" ;)

Aquí tenéis un ejemplo de como se hace el cifrado:

SIHEVISTOMASLEJOSESPORQUEESTOYSENTADOSOBREHOMBROSDEGIGANTESISAACNEWTON

AUTOCIFRADOSIHEVISTOMASLEJOSESPORQUEESTOYSENTADOSOBREHOMBROSDEGIGANTES

======================================================================

SCASXQXKOPOKTLNJAWLDARIFINGLSQHSEJUHSKHPPWLBFBUCKRFXMNOZUVGAVEGKTEJMSF

y un ejemplo de como se descifra:

SCASXQXKOPOKTLNJAWLDARIFINGLSQHSEJUHSKHPPWLBFBUCKRFXMNOZUVGAVEGKTEJMSF

AUTOCIFRADO

===========

SIHEVISTOMA

           SIHEVISTOMA

           ===========

           SLEJOSESPOR

                      SLEJOSESPOR

                      ===========

                      QUEESTOYSEN

                                 QUEESTOYSEN

                                 ===========

                                 TADOSOBREHO

                                            TADOSOBREHO

                                            ===========

                                            MBROSDEGIGA

                                                       MBROSDEGIGA

                                                       ===========

                                                       NTESISAACNE

                                                                  NTES

                                                                  ====

                                                                  WTON

Habéis perdido el interés o es que era muy difícil?! :)

Librerías para Visión Artificial

2009-06-07T22:27:00.001+02:00

Excelente colección de código que implementa diferentes técnicas de visión artificial. Desde algoritmos 'sueltos' hasta librerías completas.

http://www.cs.cmu.edu/~cil/v-source.html

OpenBSD en el escritorio

2009-05-13T22:56:00.007+02:00

OpenBSD es un Sistema Operativo centrado en la seguridad. Es muy apreciado en el mundo de los servidores no tan solo por su seguridad, si no por su gran estabilidad y su política de 'corrección' del código.

Desde hace algún tiempo he ido viendo posts de gente que lo usaba como entorno de escritorio. lo que me ha llevado a hacer mis propias pruebas. Esta no es su mejor baza, ni mucho menos. Pero si se quiere una roca como Sistema Operativo, hay que tenerla en cuenta.

En este post explico el procedimiento para instalar OpenBSD en el escritorio. No es Ubuntu, así que no esperéis nada parecido, pero tampoco resulta excesivamente complicado. Usaré OpenBSD 4.5 (la última en el momento de escribir el post) en una arquitectura AMD64. El que tenga otra arquitectura solo tendrá que sustituir en las URL amd64.

Instalación del sistema base

Descargamos la imagen y la quemamos en un CD:

ftp://ftp.openbsd.org/pub/OpenBSD/4.5/amd64/install45.iso

Arrancamos desde el CD y seguimos los pasos que se nos indican. En general, aunque es unainstalación en modo texto, no supone mucho problema: configuración de teclado, red, etc.

Lo que sí puede resultar difícil si no se está acostumbrado es el particionado de disco. Si no se sabe lo que se esta haciendo lo mejor es usar el disco entero para OpenBSD, o la pérdida de datos estará garantizada.

Esta parte está explicada en detalle en el siguiente enlace, en el punto 4.5.2:

http://www.openbsd.org/faq/faq4.html

Selección de paquetes

Durante la instalación se nos solicitarán los paquetes que queremos instalar. Los seleccionaremos todos, o como mínimo, los paquetes relacionados con las X.

Ejecutando las X

En estos momentos tenemos un sistema base con las X, las cuales podemos ejecutar mediante el comando startx. Si no funcionan correctamente tendremos que revisar /etc/X11/xorg.conf y adaptarlo a nuestro sistema.

Instalando GNOME

Habrá quien quiera instalar KDE. Googlead un poco, no creo que sea muy diferente. Aquí instalaremos GNOME.

Para poder instalar binarios de forma cómoda tendremos que establecer la variable de entorno PKG_PATH. Lo haremos añadiendo:

export PKG_PATH=ftp://ftp.openbsd.org/pub/OpenBSD/4.5/packages/amd64/

en el fichero ~/.profile. Así quedara configurada al reiniciar.

Ahora, para instalar GNOME haremos:

$ pkg_add gnome-session

Y para que GNOME arranque al iniciar el sistema pondremos en /etc/rc.local
/usr/local/bin/gdm -nodaemon

Creación de usuarios

Ejecutaremos:
$ adduser

Este nos irá preguntando lo típico: nombre de usario, shell a usar, contraseña, etc.

Si queremos que el usuario se pueda convertir en root con el comando 'su' necesitaremos añadirlo al grupo wheel. Lo haremos con:

$ moduser -G wheel usuario

Y con esto, ya tenemos un espléndido OpenBSD en nuestro escritorio.

Solo faltará instalar los paquetes que creamos necesarios como:

$ pkg_add openoffice-3.0.1p2
$ pkg_add firefox-i18n-es-ES-3.0.6

etc.

Factorización en tiempo polinómico!?

2009-05-12T12:50:00.001+02:00

Claus P. Schnorr ha presentado en el Eurocrypt 2009 "Average Time Fast SVP and CVP Algorithms: Factoring Integers in Polynomial Time".

Habría que ver el impacto que puede tener este documento en la criptografía de clave pública. Pero si es correcto, podría representar el fin de RSA.

Se ha iniciado un hilo de discusión en sci.crypt.research.

Free Mathematics Books

2009-05-09T23:18:00.004+02:00

Estupenda colección de libros de matemáticas distribuidos gratuitamente:

http://www.e-booksdirectory.com/mathematics.php

The P-versus-NP page

2009-05-07T23:42:00.005+02:00

Dejo un enlace a una página estupenda que recopila todos los intentos de demostrar el problema P?=NP.

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Después de todo, hay un suculento premio para el que lo consiga.

Criptograma 11/04/09

2009-05-05T00:56:00.000+02:00

Pista: Autocifrado

 SCASXQX KOPOKTL NJAWLDA RIFINGL SQHSEJU 

HSKHPPW LBFBUCK RFXMNOZ UVGAVEG KTEJMSF

  

Criptograma 07/04/09: Solución

2009-04-23T20:00:00.000+02:00

Una combinación de transposición y sustitución. Primero había que transponer las letras del criptograma:

TRJVMFPTTFIEPFNCCFSFFTTDIVBDOIOBBSDZJNEJPSDBPSOEEPPTTWPFKDP
FTTEBPOTUPFSTFEKFBITBZCVMOBBSTNPBMEBBMNFFOEHFVTBFFWTJQHPOSF

Cogiendolas con un periodo de dos: una si, una no, ... Obteníamos:

TJMPTIPNCSFTIBOOBDJEPDPOEPTPKPTEPTPSFKBTZVOBTPMBMFOHVBFTQPS
RVFTFEFCFFTDVDIBSZNJSBSEPTWFDFTBOUFTEFIBCMBSNBEBNFEFTFWJHOF

Finalmente con un desplazamiento de una letra en el abecedario inglés:

SILOSHOMBRESHANNACIDOCONDOSOJOSDOSOREJASYUNASOLALENGUAESPOR
QUESEDEBEESCUCHARYMIRARDOSVECESANTESDEHABLARMADAMEDESEVIGNE

Evitar timeouts en conexiones ssh

2009-04-22T14:05:00.002+02:00

echo "ServerAliveInterval 60" >> ~/.ssh/config

Y se acabaron los timeouts por inactividad.

Gracias Jordi!

Criptograma 05/04/09: Solución

2009-04-21T20:00:00.001+02:00

Observando los números con atención se veía que 'todos' se podían descomponer en, únicamente, dos números primos. Dado que había un total de 26 números primos, se podía deducir que había un primo por letra del abecedario inglés.

La asignación era la siguiente:

A: 002, B: 003, C: 005, D: 007, E: 011, F: 013, G: 017, 

H: 019, I: 023, J: 029, K: 031, L: 037, M: 041, N: 043, 

O: 047, P: 053, Q: 059, R: 061, S: 067, T: 071, U: 073, 

V: 079, W: 083, X: 089, Y: 097, Z: 101

El problema añadido del criptograma, era que al asignar cada letra a su número primo correspondiente las letras podían quedar desordenadas, pues dependía del orden en que se colocaban los dos factores. Aun así, después de la sustitución, no ser dificil finalizar el criptograma.

Despues de factorizar los números originales quedaba como:

37  2  5  23  11  43  5  23  2  43  47  43  47  67  19  2

11  43  67  11  43  2  7  47  2  73  43  67  23  37  2  37

47  5  73  61  2  11  67  47  43  47  37  47  41  2  67  67

73  3  37  23  41  11  7  11  37  2  23  43  71  11  37  23

17  11  43  5  23  2  11  7  17  2  61  2  37  37  2  43

53  47  11 101

Y finalmente, después de sustituir:

LACIENCIANONOSHAENSENADOAUNSILALOCURAESONO

LOMASSUBLIMEDELAINTELIGENCIAEDGARALLANPOEX

Catástrofe!!

2009-04-20T17:39:00.000+02:00

Oracle compra Sun Microsystems, y con ella MySQL, Java, OpenOffice, OpenSolaris, VirtualBox, ...

Esta noche voy a tener pesadillas.

Criptograma 26/03/09: Solución

2009-04-19T20:00:00.001+02:00

Volvíamos con Kasiski, esta vez con una clave un poquito más larga...

VRBCI UGJZB JMCJK EVMBF ZSCNX
NIWAN CEGYI UVIQV FRWUZ ANWEH
VLPAT EUQUH RPIIW ONWQB EWXXX
RCVAN CCDHH PKMBF FTJYL HCKSE
EMCAN NFIBB HYTLB EPLCI ZZXLY
UGZOQ VPGYU APWBB RPPAX NVMBB
XYHNT QWMIA FXTHZ AUCDE FTXUY
EPWOY RKTHM EPWUH JXPKN EWVCG
VRVUL URZCC ZEUYM OFWGG FHDMF
EOQFN EQPFL ANDCY FWRCX GQASF
EEIOK ANIPP UIUAA ILSZZ FTFLL

CLAVE: REPUTACION

ENMIP UEBLO SINPR ETENS IONTE
NGOMA LAREP UTACI ONHAG ALOQU
EHAGA ESIGU ALTOD OLOCO NSIDE
RANMA LYONO PIENS OPUES HACER
NINGU NDANO QUERI ENDOV IVIRF
UERAD ELREB ANONO ALAGE NTENO
GUSTA QUEUN OTENG ASUPR OPIAF
ENOAL AGENT ENOGU STAQU EUNOT
ENGAS UPROP IAFET ODOST ODOSM
EMIRA NMALS ALVOL OSCIE GOSES
NATUR ALABC DEFGH IJKLM OPQRS

Criptograma 20/03/09: Solución

2009-04-17T20:00:00.002+02:00

Como ya se decía en la pista del criptograma se trataba de un cifrado Vigenere susceptible al ataque Kasiski.

BEAOSERIPMXAQUTLXTDMTLDDTCXABIEAEABEAOSIYEGOCMJCWAHVTCTS

NLDOAVXDPBPMJCWAHMPSIRPBPJPNXNDNDTTPXECSTSFUTSXNSICEGOKI

KIGAHJJNIATLTSUUTROONEAAWOGRDAQRTTTPPSDYPVTRPSROBOAAKISA

IESEEAGAQUTNDSBOBECTDSIEPLOAGAHSDBGEAOHPDBGEHYBEOQJICOHQ

JECOWACSPBXDDDTSROALPRBEAOSERIPMXAQUTLXTDMTLDDTCXABIEAEA

BEAOSIYEGOCMJCWAHVTCTSNLDOAVXDPBPMJCWAHMPSAAKISATSAURHPD

TSEIPDPDPNPDXEIEPYJDPAHICOBAHYHIIUHOAOCOPDTLPNIAHTTIGACD

TJPNSOPTGAHAIRPSPNSABURHPCWOSAAESUGOAAIITRGAIOSATLHOAITL

BAGSDNEAGAPQJEALDSFUTHPNHAQISOHECTPRHEHOQRTLDSSEBAHMTLDD

TCXABIPBJEAIIOBEAOSERIPMXPPPPMTLDDXJTRDNBURHPSKEREHYAOWE

DLKISASOHITMERTMPSYOHEPGJSIICGDYIIHOAOPBRDTFVHXJZLBNDPFR

CLAVE : PAPA

MELODECIAMIABUELITOMELODECIAMIPAPAMELODIJERONMUCHASVECES

YLOOLVIDABAMUCHASMASTRABAJANINONOTEPIENSESQUESINDINEROVI

VIRASJUNTAELESFUERZOYELAHORROABRETEPASOYAVERASCOMOLAVIDA

TEDEPARABUENOSMOMENTOSTEALZARASSOBRELOSPOBRESYMEZQUINOSQ

UENOHANSABIDODESCOLLARMELODECIAMIABUELITOMELODECIAMIPAPA

MELODIJERONMUCHASVECESYLOOLVIDABAMUCHASMASLAVIDAESLUCHAD

ESPIADADANADIETEAYUDAASINOMASYSITUSOLONOADELANTASTEIRAND

EJANDOATRASATRASANDAMUCHACHODALEDUROLATIERRATODAELSOLIEL

MARSONPARAAQUELLOSQUEHANSABIDOSENTARSESOBRELOSDEMASMELOD

ECIAMIABUELITOMELODECIAMIPAPAMELODIJERONMUCHASVECESYLOHE

OLVIDADOSIEMPREMASJOSEAGUSTINGOYTISOLOABCDEFGHIJKLMNOPQR

Vectores Dinámicos en C

2009-04-13T00:07:00.008+02:00

Si queremos usar vectores dinámicos en C necesitamos recurrir a funciones de manejo de memoria de la familia *alloc(). En este post explico cómo hacerlo de forma sencilla y añado algunas macros que facilitan la tarea.

Para empezar necesitaremos declarar el vector. Lo haremos como apuntador a NULL, creando así, un vector vacío. Necesitaremos también una variable que almacene el tamaño del vector, es decir, la cantidad de elementos que contiene.

Como ejemplo crearemos un vector de números enteros.

int *v = NULL;
size_t v_size = 0;

Tenemos un vector vacío, por lo que el siguiente paso no puede ser otro que añadir elementos. Lo haremos mediante realloc(), función que permite reasignar el tamaño reservado en memoria.

v_size++;
v = realloc(v, sizeof(int)*v_size);
v[v_size-1] = 5;

De esta manera podemos añadir tantos elementos como creamos oportuno. El acceso a ellos se realizará mediante la tradicional indexación de vectores v[i], donde i es el índice del vector. Así podremos acceder al contenido de las diferentes posiciones del vector tanto para leerlas como para escribir en ellas.

Finalmente, tendremos que liberar la memoria asignada al vector mediante la función free().

free(v);

A continuación pego un ejemplo completo del uso de vectores dinámicos con las sentencias comentadas anterioremente. Añado tambien un ejemplo de uso de la función qsort() que permite ordenar el vector.

#include <stdio.h>
#include <stdlib.h>


int cmp(const void *a, const void *b)
{
   int *ia, *ib;

   ia = (int *) a;
   ib = (int *) b;

   return (*ia - *ib);
}

int main()
{
   /* Declaracion del vector y de su tamaño */
   int *v = NULL;
   size_t v_size = 0;


   /* Añade un elemento al vector con valor 5 */
   v_size++;
   v = realloc(v, sizeof(int)*v_size);
   v[v_size-1] = 5;

   /* Añade un elemento al vector con valor 3 */
   v_size++;
   v = realloc(v, sizeof(int)*v_size);
   v[v_size-1] = 3;

   /* Añade un elemento al vector con valor 1 */
   v_size++;
   v = realloc(v, sizeof(int)*v_size);
   v[v_size-1] = 1;

   /* Mofifica el valor del primer elemento del vector */
   v[0] = 2;

   /* Ordena el contenido del vector */
   qsort(v, v_size, sizeof(int), cmp);

   /* Muestra los elementos del vector */
   int i;
   for(i=0; i<v_size; i++)
      printf("%d ", v[i]);
   printf("\n");

   /* Libera la memoria asignada */
   free(v);

   return 0;
}

La sintaxis usada es un poco engorrosa, principalmente cuando se trata de añadir elementos a un vector. Esto puede solucionarse mediante el uso de macros. A continuación pego un ejemplo usando macros. En el puede verse también cómo pasar un vector como parámetro a una función.

#define VECTOR(v_var,v_size_var,type) \
   type *v_var = NULL; \
   size_t v_size_var = 0;

#define VECTOR_ADD(v_var,v_size_var,type,value) \
   (v_size_var)++; \
   v_var = realloc(v_var, sizeof(type)*(v_size_var)); \
   v_var[v_size_var-1] = value;
   
#define VECTOR_FREE(v_var) if(v_var) free(v_var);


void add_elements(int *v, size_t *v_size)
{
   VECTOR_ADD(v, *v_size, int, 3);
   VECTOR_ADD(v, *v_size, int, 5);
   VECTOR_ADD(v, *v_size, int, 7);
}  

int main()
{
   VECTOR(v, v_size, int);
   VECTOR_ADD(v, v_size, int, 2);
   
   add_elements(v, &v_size);

   int i;
   for(i=0; i<v_size; i++)
      printf("%d ", v[i]);
   printf("\n");
   
   VECTOR_FREE(v);

   return 0;
}

Para finalizar, solo recordar que el punto fuerte de los vectores es el acceso directo a los elementos (solo es necesaria una operación - O(1) ). Esto permite por ejemplo ordenar los elementos del vector a gran velocidad.

Por el contrario son costosas las inserciones de elementos. Pueden añadirse con facilidad al final, pero insertar un elemento en el medio, obliga a recolocar todos los demás elementos. Si se requiere una estructura de datos que permita estas operaciones es mejor recurrir a las listas dinámicas.

Criptograma 01/04/09: Solución

2009-04-10T00:43:00.004+02:00

Se trataba de un cifrado de sustitución homofónica que usaba dos valores para cada letra. A contnuación, la solución propuesta por Izzec.

Mis felicitaciones, Izzec!

dEbo decir que soy un priNcipiante en esto, y que a pesar de Haberme informadO sobRe Algunos aspectos de la criptografía tengo que decir que no tengo aún una haBilidad adqUirida. aún así mE gusta, y con coNstancia, en mi tiempo libre le dedico lo suficiente pAra intentar saber semana tras semana (aunque siemPre se nOs adelante altaiR) que nos escondes en los cripTogramas, daniel.
    bUeno el método que seguí fue Bastante sencilLo la verdad. en primera instancia hice una lectura rápida de los númerOs, y me di cuenta que todos eran curiosamente impares. alGo me Hizo pensar en esE momento que serían números impares sustituidos por letras. así que me puse a contar caDa númEro impar las veces que aparecía en dicho criptograma (esto no me serviría de mucho más adelante). hecho esto los clasifique por orden ascendente 002 (el único que no era impar) -003-005, etc. y me di cuenta que eran primos.así que los reordené todos de forma ascendente de tal forma que quedasen cuadrados con el alfabeto (sin utilizar la ñ). adjunto eJemplo;

    002   A     003   b    005   c     007   D   011   e     013   f     017   g    019   h    023   i      029   j      ¿? k         037   l

    041   m    043   n    047 O     053   p    059   q    061   r     067 s      071   t     073   U    ¿? v         ¿? w        089 x

    097 y     ¿? z         103 a      107 b     109 c      113 d     127 e      ¿?   f        ¿? g        139 h      149 i       ¿?   j

    ¿?   k      163 l        167 m      173 N      179 o      ¿? p        191 q     193 r      197 s      199 t      211 u     ¿?   v

    ¿? w      ¿? x       233 y     ¿?   z      241 a      ¿?   b     257 C     263 d     269 e      ¿? f       ¿? g      ¿? h

    283 i       ¿?   j       ¿? k       311 l       313 m     317 n     331 o     ¿? p        ¿? q       349 R      353 s      359 t

    367 u

Y luego lo demás fue cambiar las cifras Por las leTras. El texto queda así:

l a d i f e r e N c

    i a q u e e x i s t

    e e n t r e l o s h

    o M b r e s n e c I

    o s y l o s h o m B

    r e s d e t a L e n

    t O s u e l e s e r

    q u e l o s p r i m

    e r o s d i c e n n

    e c e d a d e s y l

    o s s e G u n d o s

    l a s c o m e t e n

    m a r i a n o j o s

    e d e l a r r a

Lo habéis leído con atención? ;)

Búsqueda de Patrones en Cifrados de Sustitución

2009-04-08T00:56:00.002+02:00

Cuando se realiza el criptoanálisis de un cifrado de sustitución monoalfabética, suele ser necesario encontrar palabras que encajen en ciertos patrones de letras. Por ejemplo, en un patroón como AACBBDA encajarían palabras como arrollar, guerrillero o encarrillar. Muchas veces, para encontrar estas palabras no es suficiente con nuestra imaginación y conocimiento de la lengua, por lo que suele ser útil recurrir al ordenador.

A continuación, pego un programa que permite realizar este tipo de búsquedas de forma muy sencilla.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void remove_nl(char *str)
{
   if(str[strlen(str)-1]=='\n')
      str[strlen(str)-1]=0;
}

int match_pattern(char *match, const char *pattern, size_t pattern_len)
{
   int i,j;

   for(i=0; i<pattern_len; i++)
   {
      for(j=i; j<pattern_len; j++)
      {
         if(pattern[i]==pattern[j])
            if(match[i]!=match[j])
               return 0;

         if(pattern[i]!=pattern[j])
            if(match[i]==match[j])
               return 0;
      }
   }

   return 1;
}

int main(int argc, char *argv[])
{
   char word[64];
   char *pattern = NULL;
   int pattern_len = 0;

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

   pattern = argv[2];
   pattern_len = strlen(pattern);

   FILE *file = fopen(argv[1], "r");
   if(!file)
   {
      perror("fopen()");
      exit(0);
   }

   while(!feof(file))
   {
      fgets(word, sizeof(word), file);
      remove_nl(word);

      char *substr = word;

      while(strlen(substr)>=pattern_len)
      {
         if(strlen(substr)<pattern_len)
            break;

         char match[pattern_len];
         strncpy(match, substr, pattern_len);
         match[pattern_len]=0;

         if(match_pattern(match, pattern, pattern_len))
            printf("%s\n", word);

         substr++;
      }
   }


   fclose(file);

   return 0;
}

Para el patrón del ejemplo bastarí con compilar el programa con:

$ gcc pattern.c -o pattern

Y ejecutarlo con:

$  ./pattern ../dict/spanish AACBBDA
acurrullar
aporrillarse
arrollar
arrullar
aturrullar
barrillar
barrillera
barrillero
carrillera
cerrillar
churrillera
churrillero
churrullera
churrullero
corrillera
corrillero
desarrollar
descarrillar
emborrullarse
emparrillar
encarrillar
guerrillero
marrullera
marrulleria
marrullero
pantorrillera
zarzaparrillar

Espero que os sirva para vuestros cripoanalisis!

Criptograma 07/04/09

2009-04-07T22:41:00.002+02:00

TRJVMFPTTFIEPFNCCFSFFTTDIVBDOIOBBSDZJNEJPSDBPSOEEPPTTWPFKDP
FTTEBPOTUPFSTFEKFBITBZCVMOBBSTNPBMEBBMNFFOEHFVTBFFWTJQHPOSF

Criptograma 05/04/09

2009-04-05T23:44:00.000+02:00

0074 0115 0473 0115 0086 2021 3149 0038 0473 0737 0086
0329 0146 2881 0851 0074 0235 4453 0022 3149 2021 1739
0082 4489 0219 0851 0451 0077 0074 0989 0781 0621 0187
0215 0046 0077 0034 0122 1369 0086 2491 1111

Podéis enviar vuestro procedimiento de solución a dlerch (en gmail) o publicar un comentario.

The General Number Field Sieve

2009-04-05T22:53:00.001+02:00

Actualmente, el algoritmo de factorización más rápido que existe. Dejo aquí mi colección de papers.

Antecedents
- The Factorization of the Ninth Fermat Number , A.K. Lenstra, H.W. Lenstra, M.S. Manasse, and J.M. Pollard (1993).
- The Number Field Sieve , A. K. Lenstra, M. S. Manasse, J. M. Pollard (1990).

Introduction to the GNFS algorithm
- An Introduction to the General Number Field Sieve , Matthew E. Briggs (1998).
- A Beginner's Guide To The General Number Field Sieve , Michael Case.
- The Number Field Sieve , Peter Stevenhagen.
- The Number Field Sieve , Steven Byrnes.

Polynomial Selection
- Polynomial Selection for the Number Field Sieve Factorisation Algorithm , Brian Murphy (1999).
- On quadratic polynomials for the number field sieve , Brian Murphy and Richard P. Brent (1998).
- Rotations and Translations of Number Field Sieve Polynomials Jason Gower (2003).
- The multiple-lattice number field sieve , Daniel J Bernstein.

Sieve
- Continued Fractions and Lattice Sieving , Jens Franke, Thorsten Kleinjung.

Filtering
- Strategies in filtering in the number field sieve , S. Cavallar (2000).

Linear Algebra
- Solving Large Sparse Linear Systems over Finite Fields , B. A. LaMacchia and A. M. Odlyzko (1991).
- A Block Lanczos Algorithm for Finding Dependencies over GF(2) , Peter L. Montgomery.
- Solving large sparse linear systems over finite fields , B. A. Lamacchia, A. M. Odlyzko (1991).

Square Root
- A Montgomery-like square root for the Number Field Sieve , Phong Nguyen, Ecole Normale Superieure (1998).
- Computing a Square Root for the Number Field Sieve , Jean-Marc Couveignes (1993).
- Square Roots of Products of Algebraic Numbers , Peter L. Montgomery.

Cómo diferenciar entre cifrados de transposición y de sustitución

2009-04-03T12:58:00.010+02:00

En criptoańalisis de cifrados clásicos, el primer problema con el que se enfrenta el criptoanalista es el desconocimiento del tipo de cifrado usado en el criptograma.

En criptografía clásica existen dos grandes grupos de sistemas de cifrado: los cifrados de sustitución y los cifrados de transposición.

Los primeros son aquellos en los que cada letra es sustituida por otra letra o símbolo. En los segundos, en cambio, no hay sustitución, pues solo se realiza una mezcla de las letras.

Mientras que en el caso de los cifrados de sustitución, nuestro objetivo será averiguar que símbolo corresponde a cada letra, en los cifrados de transposición tendremos que encontrar el patrón de 'mezcla' utilizado.

Características del Texto Cifrado:

Dado que en los cifrados de transpoción, únicamente se mezclan letras, en el resultado cifrado tendremos las misma letras que en el mensaje en claro. Así pues se mantendrán los porcentajes de vocales y de consonantes de la lengua usada.

Sin embargo, en los cifrados de sustitución, cada símbolo será sustituido por otro, de manera que no se mantendrá la distribución de vocales y consonantes.

Técnicas disponibles:

Las características del texto cifrado nos ofrecen dos técnicas para distinguir entre cifrados de sustitución y cifrados de transposición: El porcentaje de vocales y el análisis de frecuencias.

El porcentaje de vocales en castellano, ronda el 47%. Así pues, si contamos las vocales y las consonantes del criptograma y nos encontramos con un procentaje similar, sabremos que no se han realizado sustituciones y que con alta probabilidad nos encontramos ante un cifrado de transposición.

Si, por otra parte, los porcentajes que obtenemos están lejos del 47%, probablemente se trate de un cifrado de sustitución.

Para afiinar un poco más realizaremos un análisis de frecuencias. Sabemos que, por ejemplo, en castellano, las letras más frecuentes son la 'a' y la 'e'. Si estas se corresponden con la 'a' y la 'e' del criptagrama, más probabilidades a favor del cifrado por transposición. Si por el contrario, las más frecuentes son letras de baja frecuencia en castellano, como la 'x' o la 'k', dificilmente se tratará de un cifrado de transposición. Podremos suponer entonces que letras de aparición frecuente han sido sustituidas por 'x' y 'k'.

Ejemplos de Criptogramas Anteriores:

Vamos a apoyar la información expuesta con algunos criptogramas propuestos anterioremente.

Criptograma 28/03/09:

OTUOBLBNOA LIERYBHAEO ATAMSIEOYS AHRNPIRMUI URNPBENCIP

NIMOAUNEAR UJALBREAUN EAEZUNSVUA RLTQETABAM ASTCASAESA

SHSOBUVNAA IZCUAAEDON SONOBAUNYA UORALMNVES XDETOOSLNO

CORDDSTOAN RAAOTODHD

El porcentaje de vocales es del 45%.

Las letras más frecuentes son la 'a', la 'o', la 'n', la 'e' y la 's'.

Así pues, queda claro que se trata de un cifrado de transposición.

Criptrograma del 2008:

ADZMO YHADG TIYMM ZCAUG CZYJA DYJTG LKSKM DKOZJ
OKEIG JHKAC EZSGQ HYZOG EZMVG HAZSG MYJOZ MNJEG
SZENH GHEIZ JHKDG COMKS ZCCAB IYFAJ GSZMY JOGMN
JZEON FNHGH CNACO ZEYME GHADY JABNT KVZHY VGEAM
DYEMA YMPIA YCOZD ARKCC NYCOG DARKC ZSGMY JOZMP
IACYA COGEY MEZSK JAMEY UKCSG MZGOM ZAMGD YJABN
TKTKD SYZMG DAJYB NTKEI ZJHKA COGHY CKMHA JZHKS
MYSGM ZMCAE KJOMG YDEIZ JHKAC OGCYT IMKAJ OKHZC
SGMOY CAFNO ZMDYH IMGJO AIJON YBSKE IZJHK ACBGC
XIYMO ACNOI KSKJY JOAON YJAIJ OYBSA MZBYJ OKEKD
AMNEK NJOYJ OGNMM NOZMD ACNYC GMMKT ZJOAO MGOZH
YXKBA JOGMC IYTKO NCBKC NDZCO MKSGC AJYBN TZCCA
VGDDZ JUNYJ SMASG MZHGC OMZCI JGMYK MTZJN QGENK
JNJOA JOZHY CKMHA JGMDZ CCNYC OGJIJ NHZCC NABUM
GDZHN CYJCN KJAJO MYCIC XNDGC ZOGEZ GDAJY BNTKE
IZJHK JKACO GSMYS ZMGHK WZSGM AEYEI ZJHKJ KOAYC
SAMGY COZCC KJDGC EDZFA CHYDG FNEOK MNZSG MZADY
COMGO ATZCI JOQIY DGMOA HYDZT IAMMG

El porcentaje de vocales es del 23%.

Las letras más frecuentes son la 'm', la 'z', la 'g', la 'y' y la 'a'.

Así pues, queda claro que se trata de un cifrado de sustitución.

Criptograma 28/03/09: Solución

2009-04-02T00:04:00.011+02:00

El criptograma corresponde a una doble transposición. Ha sido resuelto únicamente por Altair, que me ha enviado su solución. La adjunto a continuación.

En primer lugar decirte que no soy experto en criptografia, simplemente me gusta y paso algún buen rato intentando descifrar mensajes. He leído un poquito a nivel básico, pero no tengo mas formación sobre estos temas, ni tampoco herramientas potentes, es mas casi no tengo herramientas.

Lo que si tengo claro es que para descifrar un mensaje, se ha de tener en cuenta todo lo que sepamos sobre el mensaje, las circunstancias en las que el mensaje se genera, la personalidad y gustos de autor, en fin, cualquier cosa relacionada con lo que queremos descifrar.

En este caso, los dos mensajes anteriores, eran poesías que había cantado Paco Ibáñez, y en los comentarios se habían hecho referencias a el y a los poetas que los habían compuesto, incluso yo te había hecho un comentario sobre la canción “A galopar”.

Esto era algo que tenia en mente cuando comencé con el mensaje. Miré la frecuencia de aparición de las letras, y ví podía cuadrar con la frecuencia normal en castellano, pero probando sustituciones no llegaba a nada.

Examinando el mensaje con atención ví “fragmentos” de palabras SONOBA, CORD, UJALBR, RNPBENCIP … Esto me hizo suponer que lo que habías hecho era mover las letras de su posición inicial. ¿Pero como?, probaba a mover las columnas de lugar pero no me salía nada en claro, las filas no creía que estuvieran cambiadas, porque todos los “fragmentos” los habia encontrado en horizontal. Y aquí es donde viene la suerte, o la intuición, como quieras llamarlo. Los fragmentos, me hicieron pensar en “erase se una vez un principe malo …..”. Estaban prácticamente las palabras Bruja, CORDeros, Soñaba (Sonoba) etc. En ese momento estaba casi convencido de que el texto era ese poema, pero no sabia por donde empezar con el método de cifrado, porque las trasposiciones que probaba no me llevaban a ninguna parte. Para asegurarme de que el texto era el que yo creía, busque el poema y calculé la frecuencia de aparición de cada letra. Solo había tres pequeñas diferencias, en el cripto habia una N mas que en el poema, en el el poema había una Ñ que no estaba en el criptograma, y en el criptograma había una X. Las dos primeras diferencias estaban claras, no habias usado un alfabeto con Ñ, tu alfabeto era de 26 letras y la Ñ la codificabas como N. Con esto, la frecuencia de las letras cuadraba perfectamente excepto por la X.

Pensé que la X podía ser algún signo de puntuación, un punto, un guión, algo así, pero no me convencía porque en el poema original había mas de un signo, y no tenia sentido que pusieras uno si y los otros no. La otra alternativa era un carácter de relleno, la X. Esta última posibilidad me llamo la atención, porque normalmente un carácter se pone porque nos faltan letras para completar un grupo, y en este caso el ultimo bloque solo tenía 9 letras y no 10 como los demás. Era contradictorio. Pensé que podía ser una variante del que habías puesto de la rejilla de Cardano, pero tampoco encontraba un patrón. Además, las letras no formaban un cuadrado …
Aquí me quedé atascado, hasta que se me ocurrió contar las letras que había y ¡Bingo¡ 169 caracteres, o sea 13x13.

Lo reordené en un cuadrado de estas dimensiones descarte rapidamente la rejilla. Al mirar el mensaje ordenado así, estaba claro que habías jugado con las filas y las columnas. Como estaba seguro de cual era el texto ya fue fácil reordenar las columnas y las filas.

Más o menos, este fue el proceso que seguí.

Adjunto también el proceso usado en el cifrado, paso a paso.

Para poder realizar una transposición doble, basada en una clave, es necesario poder representar el texto en un cuadrado. El lado del cuadrado se corresponderá con la longitud de la clave:6 1 7 12 2 4 5 3 13 8 9 10 11.

Realizamos primero la transposición de las columnas:

6 1  7 12  2  4  5  3  13 8  9 10 11

======================================

E  R  A  S   E  U  N  A   V  E  Z   U  N

L  O  B  I  T  O  B  U   E  N  O   A  L

Q  U  E  M   A  L  T  R   A  T  A   B  A

N  T  O  D   O  S  L  O   S  C  O   R  D

E  R  O  S   Y  H  A  B   I  A  T   A  M

B  I  E  N   U  N  P  R   I  N  C   I  P

E  M  A  L   O  U  N  A   B  R  U  J  A

H  E  R  M   O  S  A  Y   U  N  P   I  R

A  T  A  H   O  N  R  A   D  O  T   O  D

A  S  E  S   T  A  S  C   O  S  A   S  H

A  B  I  A   U  N  A  V   E  Z  C   U  A

N  D  O  Y   O  S  O  N   A  B  A   U  N

M  U  N  D   O  A  L  R   E  V  E   S  X

  

TRANSPOSICION DE COLUMNAS

R E A U N E A E Z U N S V

O T U O B L B N O A L I E

U A R L T Q E T A B A M A

T O O S L N O C O R D D S

R Y B H A E O A T A M S I

I U R N P B E N C I P N I

M O A U N E A R U J A L B

E O Y S A H R N P I R M U

T O A N R A A O T O D H D

S T C A S A E S A S H S O

B U V N A A I Z C U A A E

D O N S O N O B A U N Y A

U O R A L M N V E S X D E

A continuación realizamos la transposición de las filas.

6   R E A U N E A E Z U N S V

1   O T U O B L B N O A L I E

7   U A R L T Q E T A B A M A

12  T O O S L N O C O R D D S

2   R Y B H A E O A T A M S I

4   I U R N P B E N C I P N I

5   M O A U N E A R U J A L B

3   E O Y S A H R N P I R M U   

13  T O A N R A A O T O D H D

8   S T C A S A E S A S H S O

9   B U V N A A I Z C U A A E

10 D O N S O N O B A U N Y A 

U O R A L M N V E S X D E

  

TRANSPOSICION DE FILAS

O T U O B L B N O A L I E

R Y B H A E O A T A M S I

E O Y S A H R N P I R M U

I U R N P B E N C I P N I

M O A U N E A R U J A L B

R E A U N E A E Z U N S V

U A R L T Q E T A B A M A

S T C A S A E S A S H S O

B U V N A A I Z C U A A E

D O N S O N O B A U N Y A

U O R A L M N V E S X D E

T O O S L N O C O R D D S

T O A N R A A O T O D H D

De donde obtenemos el mensaje cifrado:

OTUOBLBNOA LIERYBHAEO ATAMSIEOYS AHRNPIRMUI URNPBENCIP

NIMOAUNEAR UJALBREAUN EAEZUNSVUA RLTQETABAM ASTCASAESA

SHSOBUVNAA IZCUAAEDON SONOBAUNYA UORALMNVES XDETOOSLNO

CORDDSTOAN RAAOTODHD

Desde aquí, mis felicitaciones a Altair.

Criptograma 01/04/09

2009-04-01T23:24:00.010+02:00

037 002 007 023 013 011 061 127 043 005 
149 103 059 073 269 011 089 283 067 071 
127 269 173 199 193 011 163 047 197 019 
179 041 003 349 127 353 317 269 109 023 
331 067 097 311 047 197 139 179 167 107 
061 011 353 113 127 359 241 037 269 043 
071 331 067 211 011 163 127 197 269 193 
191 367 011 311 047 353 053 349 149 313 
127 061 179 067 263 283 257 269 173 317
011 005 127 007 002 113 269 197 233 037 
331 353 067 011 017 073 043 263 047 197 
163 103 353 109 179 041 127 199 269 173 
167 241 193 023 002 317 331 029 047 067 
011 007 127 311 103 349 061 241

Criptograma 28/03/09

2009-03-28T00:15:00.001+01:00

   OTUOBLBNOA LIERYBHAEO ATAMSIEOYS AHRNPIRMUI URNPBENCIP
   NIMOAUNEAR UJALBREAUN EAEZUNSVUA RLTQETABAM ASTCASAESA
   SHSOBUVNAA IZCUAAEDON SONOBAUNYA UORALMNVES XDETOOSLNO
   CORDDSTOAN RAAOTODHD

Military Cryptanalysis

2009-03-27T22:55:00.007+01:00

Desde hace ya bastante tiempo, en la web de la NSA está disponible la conocida obra de William F. Friedman "Military Cryptanalysis". Dejo un enlace:

http://www.nsa.gov/public_info/declass/military_cryptanalysis.shtml

Criptograma 26/03/09

2009-03-26T20:21:00.001+01:00

Y después del aperitivo Kasiski, el plato fuerte!

VRBCI UGJZB JMCJK EVMBF ZSCNX

NIWAN CEGYI UVIQV FRWUZ ANWEH

VLPAT EUQUH RPIIW ONWQB EWXXX

RCVAN CCDHH PKMBF FTJYL HCKSE

EMCAN NFIBB HYTLB EPLCI ZZXLY

UGZOQ VPGYU APWBB RPPAX NVMBB

XYHNT QWMIA FXTHZ AUCDE FTXUY

EPWOY RKTHM EPWUH JXPKN EWVCG

VRVUL URZCC ZEUYM OFWGG FHDMF

EOQFN EQPFL ANDCY FWRCX GQASF

EEIOK ANIPP UIUAA ILSZZ FTFLL

Criptograma 20/03/09

2009-03-20T20:12:00.010+01:00

Para practicar Kasiski ...

BEAOSERIPMXAQUTLXTDMTLDDTCXABIEAEABEAOSIYEGOCMJCWAHVTCTS

NLDOAVXDPBPMJCWAHMPSIRPBPJPNXNDNDTTPXECSTSFUTSXNSICEGOKI

KIGAHJJNIATLTSUUTROONEAAWOGRDAQRTTTPPSDYPVTRPSROBOAAKISA

IESEEAGAQUTNDSBOBECTDSIEPLOAGAHSDBGEAOHPDBGEHYBEOQJICOHQ

JECOWACSPBXDDDTSROALPRBEAOSERIPMXAQUTLXTDMTLDDTCXABIEAEA

BEAOSIYEGOCMJCWAHVTCTSNLDOAVXDPBPMJCWAHMPSAAKISATSAURHPD

TSEIPDPDPNPDXEIEPYJDPAHICOBAHYHIIUHOAOCOPDTLPNIAHTTIGACD

TJPNSOPTGAHAIRPSPNSABURHPCWOSAAESUGOAAIITRGAIOSATLHOAITL

BAGSDNEAGAPQJEALDSFUTHPNHAQISOHECTPRHEHOQRTLDSSEBAHMTLDD

TCXABIPBJEAIIOBEAOSERIPMXPPPPMTLDDXJTRDNBURHPSKEREHYAOWE

DLKISASOHITMERTMPSYOHEPGJSIICGDYIIHOAOPBRDTFVHXJZLBNDPFR

Criptograma II 04/02/09: Solución

2009-03-17T20:31:00.006+01:00

El criptograma es una aplicación de los antiguos criptogramas de tipo rejilla. Podemos pensar en ellos como una hoja de papel cuadriculada en la que se realizan diversos agujeros. Aplicando esta rejilla sobre otro papel escribiremos el mensaje en los agujeros. Finalmente, el papel donde se encuentra el mensaje, lo rellenaremos con letras aleatorias.

Así pues, la rejilla sera nuestra clave. Pues aplicandola sobre la "sopa de letras" podremos leer el mensaje en los agujeros.

En nuetro criptograma, se usa la partida mencionada de Kasparov como rejilla, usando la posición final de la partida, cuando en la jugada 19 Kasparov se rinde.

En la posicion final quedan ocupadas las siguientes casillas:

   X . X . . . . X
   X . . X X . X .
   . . X . . . . X
   . X . X . X . .
   . . X X . . . .
   . . . X . X X .
   . X . . . X X X
   X . . . . . X .

Y esta es la rejilla que descifra el mensaje.

Si ordenamos el criptograma:

   KALU MNIA ASAT UPBA RTAM EPIR CAUD NANN
   HUNI EEVO ALAK MTOI EKSS GLAA TFAG RIUT

en un cuadro de 8x8, como un tablero de ajedrez:

   K A L U M N I A
   A S A T U P B A
   R T A M E P I R
   C A U D N A N N
   H U N I E E V O
   A L A K M T O I
   E K S S G L A A
   T F A G R I U T

Aplicando nuestra rejilla, obtenemos nuestro mensaje:

   K . L . . . . A
   A . . T U . B .
   . . A . . . . R
   . A . D . A . .
   . . N I . . . .
   . . . K . T O .
   . K . . . L A A
   T . . . . . U .

Mensaje: KLAATU BARADA NIKTO

Las celebres palabras de Gort.

.

OpenDomo visto desde una PSP

2009-02-14T00:05:00.010+01:00

Oriol Palenzuela nos muestra en su artículo "Accediendo a OpenDomo desde dispositivos móviles", cómo se ve OpenDomo desde la PSP.

Adjunto las capturas:

Documentación sobre la Mente y la Consciencia

2009-02-11T23:46:00.021+01:00

El siguiente enlace contiene una gran colección de enlaces a documentación sobre la mente y la consciencia. Sin duda, una mina para todo aquel interesado en la vertiente más pura de la Inteligencia Artificial. No esperéis encontrar muchos algoritmos ;)

MindPapers: A Bibliography of the Philosophy of Mind and the Science of Consciousness

También pueden consultarse únicamente los enlaces a documentos on-line.

.

Cómo agilizar conexionex SSH

2009-02-06T07:47:00.001+01:00

Dejo aquí una pequeña receta que permite agilizar las conexiones ssh, de manera que solo pedirá la contraseña la primera vez. A partir de ese momento las conexiones usarán el mismo canal multiplexado.

Solo hay que añadir en ~/.ssh/config lo siguiente:

Host *
ControlMaster auto
ControlPath ~/.ssh/master-%r@%h:%p

Criptograma II 04/02/09

2009-02-04T19:00:00.001+01:00

Altair se los come como rosquillas, así que ahí va otro.
No será por falta de criptogramas ...

Pista: Deep Blue - Kasparov, 1997, Game 6

KALU MNIA ASAT UPBA RTAM EPIR CAUD NANN
HUNI EEVO ALAK MTOI EKSS GLAA TFAG RIUT

Criptograma 04/02/09

2009-02-04T07:54:00.005+01:00

No me gusta dejar a los lectores sin 'material' para romperse el coco. Por suerte, aún y con la rapidez de Altair, todavía me quedan unos cuantos criptogramas en la manga.

Que os divirtáis!

TCZVAUAOOQOVNVDMULIAIOPEUTG
DELSMAUALEEETJECJENOELOONSR
RUNYCUIONJEUFONIUNARYEVNODI
SGETREEERROMRRCOSDENOODOEQA
NNOYRURUVUTEEONIGOGLNCRLDLA
EOTAOAUNLISLSNUAEAOEINPRDDS
CSSOAETAOONMMAVLGESANEORNLS

El criptograma del 2008: solución

2009-02-03T07:02:00.008+01:00

Finalmente nadie ha sido capaz de resolver el criptograma del 2008.

Lo cierto es que de entrada, no era nada fàcil, aunque hay que decir que la pista que di facilitaba bastante las cosas. A continuación voy a poner un ejemplo de como resolver el criptograma partiendo de la pista.

Pista:
Es un texto de Sun Tzu 'El Arte de la Guerra'.

A parte de probar todos les textos del libro:) se podía probar a sustituir "el arte de la guerra" como frase inicial, y partir de ella:

elartedelaguerraCeUaCaeJeleJgaLKSKrlKtaJ
tKEuaJdKeCEaSaQdeataEarVadeaSareJtarNJEa
SaENdadEuaJdKlaCtrKSaCCeBueFeJaSareJtarN
JaEtNFNdadCNeCtaEerEadeleJeBNgKVadeVaEer
leEreerPueeCtaleRKCCNeCtaleRKCaSareJtarP
ueCeeCtaEerEaSKJerEeUKCSaraatraeraleJeBN
gKgKlSearaleJeBNgKEuaJdKeCtadeCKrdeJadKS
reSararCeEKJtraelEuaJdKeCtaCegurKeJtKdaC
SarteCeFNtarleduraJteuJtNeBSKEuaJdKeCBaC
XuerteCNtuKSKJeJtetNeJeuJteBSeraBeJtKEKl
erNEKNJteJtaNrrNtarleCNeCarrKgaJtetratad
eXKBeJtarCuegKtNCBKCNlaCtrKSaCeJeBNgaCCe
VallaJUNeJSreSaradaCtraCuJareKrgaJNQaENK
JNJteJtadeCKrdeJarlaCCNeCtaJuJNdaCCNeBUr
aladNCeJCNKJeJtreCuCXNlaCataEaaleJeBNgKE
uaJdKJKeCtaSreSaradKWaSareEeEuaJdKJKteeC
SeraeCtaCCKJlaCElaFeCdelaFNEtKrNaSaraele
CtrategaCuJtQuelartedelaguerra

Un buen indicio de que al hacer esto vamos bien encaminados sería ver que la frase final también es "el arte de la guerra". Ademas, dado que los últimos criptogramas siempre han sido de tipo frase-autor es de esperar que la 'u' que aparece antes de "el arte de la guerra" del final del criptograma, corresponda a "Sun Tzu".

elartedelaguerraseUasaenelengaLKSKrlKtan
tKEuandKesEaSazdeataEarVadeaSarentarNnEa
SaENdadEuandKlastrKSasseBueFenaSarentarN
naEtNFNdadsNestaEerEadeleneBNgKVadeVaEer
leEreerPueestaleRKssNestaleRKsaSarentarP
ueseestaEerEaSKnerEeUKsSaraatraeraleneBN
gKgKlSearaleneBNgKEuandKestadesKrdenadKS
reSararseEKntraelEuandKestasegurKentKdas
SarteseFNtarleduranteuntNeBSKEuandKesBas
XuertesNtuKSKnentetNeneunteBSeraBentKEKl
erNEKNntentaNrrNtarlesNesarrKgantetratad
eXKBentarsuegKtNsBKsNlastrKSaseneBNgasse
VallanUNenSreSaradastrasunareKrganNzaENK
nNntentadesKrdenarlassNestanunNdassNeBUr
aladNsensNKnentresusXNlasataEaaleneBNgKE
uandKnKestaSreSaradKWaSareEeEuandKnKtees
SeraestassKnlasElaFesdelaFNEtKrNaSaraele
strategasuntzuelartedelaguerra

En este punto, observando las sustituciones ya vemos que se trata de un cifrado de sustitución homofónica.

A partir de aquí resulta sencillo terminar de resolver el criptograma. Solo es necesario ir mirando las palabras incompletas e intentar completarlas con un poco de imaginación.

Por ejemplo, en las lineas 6-7 encontramos:

atraeraleneBNgK

de lo que podemos deducir que B=m, N=i, K=o.

Tambien podemos ver que E=c a partir de "Euando", que S=p de "escaSaz", que U=b de "seUasa", etc.

Finalmente, este es el resultado (he añadido los signos de puntuación que no estan en el criptograma):

El arte de la guerra se basa en el engaño. Por lo tanto, cuando es capaz de atacar, ha de aparentar incapacidad; cuando las tropas se mueven, aparentar inactividad. Si está cerca del enemigo, ha de hacerle creer que está lejos; si está lejos, aparentar que se está cerca. Poner cebos para atraer al enemigo. Golpear al enemigo cuando está desordenado. Prepararse contra él cuando está seguro en todas partes. Evitarle durante un tiempo cuando es más fuerte. Si tu oponente tiene un temperamento colérico, intenta irritarle. Si es arrogante, trata de fomentar su egotismo. Si las tropas enemigas se hallan bien preparadas tras una reorganización, intenta desordenarlas. Si están unidas, siembra la disensión entre sus filas. Ataca al enemigo cuando no está preparado, y aparece cuando no te espera. Estas son las claves de la victoria para el estratega.

Sun Tzu, 'El Arte de la Guerra'

Alguno se preguntará como resolverlo sin la pista. Pues bien, es bastante complicado. de entrada no nos podemos fiar de las frecuencias, por ser homofónico, así que solo nos queda probar palabras. Dado que no sabemos de que trata el criptograma el tema se complica.
El único punto donde nos podemos agarrar es en la frecuencia de ciertos bloques de letras o en patrones comunes en castellano, como puden ser las LL. A partir de aquí, imaginación y un poco de ayuda del ordenador para aplicar fuerza bruta.

Fuentes:

http://www.gorinkai.com/textos/suntzu.htm

Criptograma 31/01/09

2009-01-31T20:00:00.002+01:00

BRGOK OJBJT MJVQL
LJLQV QTQMB JOGAJ
KTFQL GJLVJ MJCQO
QSJVF LKOJW RQQVB
JLLQB FJTJM JCQYL
JIKOJ OJTKM OUTRF 
C

Nueva web de OpenDomo

2009-01-29T08:42:00.015+01:00

Despues de tener que dejar el antiguo hosting y de una problemática migración en la que el maldito Joomla nos impidió restaurar la base de datos de forma correcta, OpenDomo se pasa a Drupal.

De momento estamos muy contentos con el, así que os invito a echarle un vistazo.

Bash: printf() en color

2009-01-27T19:11:00.006+01:00

El siguiente código permite escribir 'en color' en terminales bash.

#include <stdio.h>

#define COLOR_RED "\e[31m"
#define COLOR_B_RED "\e[31;1m"
#define COLOR_GREEN "\e[32m"
#define COLOR_B_GREEN "\e[32;1m"
#define COLOR_YELLOW "\e[33m"
#define COLOR_B_YELLOW "\e[33;1m"
#define COLOR_BLUE "\e[34m"
#define COLOR_B_BLUE "\e[34;1m"
#define COLOR_MAGENTA "\e[35m"
#define COLOR_BRIGHT "\e[1m"
#define COLOR_CYAN "\e[36m"
#define COLOR_NONE "\e[m"

int main(int argc, char *argv[])
{
    printf(COLOR_RED "hello world\n" COLOR_NONE);
    printf(COLOR_B_RED "hello world\n" COLOR_NONE);
    printf(COLOR_GREEN "hello world\n" COLOR_NONE);
    printf(COLOR_B_GREEN "hello world\n" COLOR_NONE);
    printf(COLOR_YELLOW "hello world\n" COLOR_NONE);
    printf(COLOR_B_YELLOW "hello world\n" COLOR_NONE);
    printf(COLOR_BLUE "hello world\n" COLOR_NONE);
    printf(COLOR_B_BLUE "hello world\n" COLOR_NONE);
    printf(COLOR_CYAN "hello world\n" COLOR_NONE);
    printf(COLOR_MAGENTA "hello world\n" COLOR_NONE);
    printf(COLOR_BRIGHT "hello world\n" COLOR_NONE);
    return 0;
}

Criptograma 17/01/2009

2009-01-17T10:42:00.001+01:00

IGCBIHKHEGEATNGZGPBZBSGINBZLBZUFBIUPSGKUZPSGZEBFPUIMBFEBFTBSLB,VTBMTBEBZ UKTSSHSMUKGFRBKBF, FHZUKUZMBVTB~GFKUFGFVTBUKTSSBZLUEUFIUFEHGF.

QBZJGNHZCSGZWIHZ

Inteligencia Artificial: los chatbots

2008-12-14T20:00:00.027+01:00

Actualmente dedico la mayor parte de mi tiempo libre al proyecto OpenDomo, lo que me resta tiempo para investigar sobre seguridad y criptografía, que siempre han sido mis hobbies principales. Así pues, a partir de ahora, la temática del blog girará alrededor de OpenDomo, tratando de seguridad, Inteligencia Artificial, electrónica o lo que se cueza en ese momento en dicho proyecto.

Con este objetivo y el de ampliar un poco los horizontes del blog, he decidido crear una nueva sección de Inteligencia Artificial, donde iré publicando pequeños artículos de todo tipo, tal y como he ido haciendo con las seguridad informática.

Parecería lógico empezar esta entrada sobre Inteligencia Artifical con una definición del concepto, pero resulta que el tema es motivo de conflicto. Dado que no existe una definición totalmente aceptada he decido tirar de la más polémica: la usada en el Premio Loebner.

En 1950, Alan Madison Turing en su artículo Computing Machinery and Intelligence se planteó si las máquinas podían llegar a pensar, y en caso de poder hacerlo, cómo podríamos saberlo. La conclusión de Turing fué que sabremos que una máquina piensa cuando sus respuestas sean indistinguibles de las de un humano.

Así, en 1990 Hugh Loebner implementaba un Test de Turing, en el que se ofrecía 100.000$ y una medalla de oro a la primera computadora cuyas respuestas fuesen indistinguibles de las de un humano. Daba origen así al Premio Loebner.

Con el objetivo de ganar dicho galardon y marcar un antes y un después en la historia de la IA son muchos los que lo han intentado. Bastan unas pocas búsquedas en google para encontrar gran cantidad de chatbots.

Si bien es cierto que desarrollar un buen chatbot es realmente difícil, hasta el punto de que hoy por hoy, ninguno ha conseguido pasar el test de Turing, es sorprendente lo fácil que es crear un bot que 'de el pego'.

Adjunto uno que he hecho en shellscript en unas pocas lineas.

#!/bin/bash

DATABASE=database

touch $DATABASE

while true; 
do
   read -p "humano: " line
   echo $line >> database
   
   data_size=`wc -l $DATABASE | cut -d' ' -f1`
   nline=$(( $RANDOM % $data_size + 1 ))
   new_line=`tail -$nline $DATABASE | head -1`
   echo "bot: $new_line"
done

Como es lógico, no se puede esperar mucha inteligencia de este bot, pero aun y así, se desprenden conversaciones sorprendentes.

Empezando con una base de datos simple como la siguiente:

$ cat database
Hola
Que tal estas?
Me llamo bot y soy un Bot
Como te llamas?

He tenido la siguiente conversación:

humano: Hola
bot: Me llamo bot y soy un Bot
humano: Hola Bot
bot: Hola
humano: Quieres conversar conmigo?
bot: Hola Bot
humano: No, bot eres tu
bot: Que tal estas?
humano: bien
bot: Me llamo bot y soy un Bot
humano: ya lo se
bot: Como te llamas?
humano: Dani
bot: Hola Bot
humano: ese eres tu
bot: ese eres tu
humano: no, tu
bot: Hola
humano: me estas mosqueando ...
bot: me estas mosqueando ...
humano: por que te mosqueas?
bot: Como te llamas?
humano: Dani
bot: Dani
humano: Si, dime
bot: Hola Bot
humano: que no, que soy Dani
bot: Me llamo bot y soy un Bot
humano: vale, captado
bot: por que te mosqueas?
humano: es que eres muy pesado
bot: no, tu
humano: yo no soy pesado!
bot: Si, dime
humano: Que no soy pesado
bot: Que no soy pesado
humano: que no
bot: ya lo se
humano: ah, bueno
bot: Quieres conversar conmigo?
humano: eso estamos haciendo
bot: vale, captado
humano: entonces, de que quieres hablar?
bot: Dani
humano: Si
bot: me estas mosqueando ...
humano: ui!
bot: vale, captado

Aunque la conversación carece de sentido, lo cierto es que no resulta del todo inverosímil. El problema con este tipo de bots y otros de más sofisticados pero que usan las mismas técnicas, es que no llegan a comprender las frases. Se dedican simplemente a realizar construcciones habituales y a repetir frases. Sin duda, no parece la técnica adecuada para superar el Test de Turing.

Cómo crear usuarios en C / Linux

2008-12-07T09:31:00.003+01:00

En ocasiones necesitamos crear usuarios desde un programa en C y aunque podría bastar haciendo una llamada a 'useradd' siempre es más elegante usar las llamadas al sistema. En este artículo voy a explicar cómo crear un usuario con su correspondiente registro en /etc/passwd y en /etc/shadow.

Lo primero que necesitamos es una estructura donde guardar los datos que almacenaremos en /etc/passwd, para usar esta estructura 'struct passwd' necesitaremos la cabecera 'pwd.h'.

struct passwd p;

p.pw_name = "myusername";
p.pw_passwd = "x";
p.pw_uid = 1000;
p.pw_gid = 1000;
p.pw_gecos = "Test User";
p.pw_dir = "/home/myusername";
p.pw_shell = "/bin/sh";

A destacar la 'x' en pw_passwd, pues recordemos que estamos usando shadow passwords y por lo tanto la password se guardará en /etc/shadow. Respecto a los demas campos, a elegir.

Aun así, es interesante ver como podemos escoger un id para un usuario para no repetirlo.

struct passwd *pw = NULL;
int min = 1000;
int max = 65000;

f = fopen("/etc/passwd", "r");

/* check user and get valid id */
while ((pw = fgetpwent(f)))
{
if (strcmp(pw->pw_name, p.pw_name) == 0)
{
perror("user_add(): user exists");
exit(0);
}

if ((pw->pw_uid >= p.pw_uid) && (pw->pw_uid <>pw_uid >= min))
{
p.pw_uid = pw->pw_uid + 1;
}
}

fclose(f);

Ya tenemos la entrada de /etc/passwd preparada, así que la añadiremos al fichero de la siguiente manera:

f = fopen("/etc/passwd", "a+");
if(!f)
{
perror("user_add(): cannot open /etc/passwd");
exit(0);
}

if (putpwent(&p, f) == -1)
{
perror("user_add(): putpwent() error");
exit(0);
}

fclose(f);

Vayamos ahora a por las shadow. El proceso es similar al anterior, solo que ahora usaremos una estructura 'struct spwd sp;' para la cual necesitamos la cabecera 'shadow.h'.
Además ha llegado el momento de crear la contraseña, para lo que usaremos la función 'crypt()'. Esta a su vez, necesita una salt, que la crearemos tal y como vemos a continuación.

struct timeval tv;
static char salt[40];

salt[0] = '\0';

gettimeofday (&tv, (struct timezone *) 0);
strcat(salt, l64a (tv.tv_usec));
strcat(salt, l64a (tv.tv_sec + getpid () + clock ()));

if (strlen (salt) > 3 + 8)
salt[11] = '\0';

Esta forma de crear la salt es bastante común, aunque hay otros enfoques válidos. Al final, se trata de genererar diferentes salt cada vez que se crea un usuario.

Vamos ahora a rellenar la estructura shadow:

#define DAY (24L*3600L)
#define WEEK (7*DAY)
#define SCALE DAY
...
struct spwd sp;
sp.sp_namp = p.pw_name;
sp.sp_pwdp = (char*)crypt(passwd, salt);
sp.sp_min = 0;
sp.sp_max = (10000L * DAY) / SCALE;
sp.sp_lstchg = time((time_t *) 0) / SCALE;
sp.sp_warn = -1;
sp.sp_expire = -1;
sp.sp_inact = -1;
sp.sp_flag = -1;

El segundo campo corresponde a la contraseña cifrada en DES, de la forma tradicional y poco segura. Este parámetro se puede mejorar usando otras funciones de cifrado.
Los parámetros siguientes indican los dias de cambios de password, expiración de la cuenta, etc. Ver detalles mediante 'man shadow'.

Finalmente, solo nos queda añadir el registro en /etc/shadow:

f = fopen("/etc/shadow", "a+");
if(!f)
{
perror("user_add(): cannot open /etc/shadow");
exit(0);
}

if (putspent(&sp, f) == -1)
{
perror("user_add(): putspent() error");
exit(0);
}

fclose(f);

Algunos cambios interesantes son usar una función de cifrado más segura, bloquear los archivos /etc/passwd y /etc/shadow antes de abrirlos, y verificar en /etc/shadow que no existe ningun registro que coincida con el que vamos a añadir, tal y como hemos hecho con /etc/passwd. Tambien quedaría realizar una gestión del grupo, como por ejemplo, crearlo si es necesario. En cualquier caso quedan cubiertos los objetivos de este artículo, ver como se hece en leguaje C para crear un usuario de Linux.

A propósito, borrar un usuario consisitiría, simplemente, en eliminar la linea correspondiente de /etc/passwd y /etc/shadow. Así pues, que nadie me pida que explique cómo hacer un programa en c para borrar usuarios ;)

Simulador de la máquina Enigma

2008-11-30T18:00:00.002+01:00

Dejo un enlace a un simulador de máquina Enigma:

http://enigmaco.de/enigma/enigma.swf

OpenDomo publica sus primeras screenshots

2008-11-30T10:42:00.006+01:00

.
Hace cerca de tres años fundé el proyecto OpenDomo con el objetivo de crear un sistema libre de domótica y seguridad para el Hogar. Ahora OpenDomo, aunque aun lejos de su primera versión estable, publica sus primeras screenshots.

http://www.opendomo.com/images/startup.png
http://www.opendomo.com/images/login.png
http://www.opendomo.com/images/principal.png
http://www.opendomo.com/images/configurar.png
http://www.opendomo.com/images/paquetes.png
http://www.opendomo.com/images/instalarpaquetes.png
http://www.opendomo.com/images/installpackage.png

Espero que os gusten!
.

Multicast sender/listener

2008-11-22T10:05:00.002+01:00

Dejo un ejemplo de como hacer multicast en C/Linux.

sender.c - el envío de mensajes

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>


#define PORT 9999
#define GROUP "225.0.0.37"

int main(int argc, char *argv[])
{
struct sockaddr_in addr;
int fd;
char *message="ieps!";

if((fd=socket(AF_INET,SOCK_DGRAM,0)) < 0)
{
perror("socket()");
exit(EXIT_FAILURE);
}

memset(&addr,0,sizeof(addr));
addr.sin_family=AF_INET;
addr.sin_addr.s_addr=inet_addr(GROUP);
addr.sin_port=htons(PORT);

while(1)
{
if(sendto(fd, message, strlen(message),
0, (struct sockaddr *) &addr,
sizeof(addr)) < 0)
{
perror("sendto()");
exit(EXIT_FAILURE);
}

sleep(1);
}

return 0;
}

listener.c - recepción de mensajes

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <arpa/inet.h>


#define PORT 9999
#define GROUP "225.0.0.37"

int main(int argc, char *argv[])
{
struct sockaddr_in addr;
int fd, nbytes;
unsigned int addrlen;
struct ip_mreq mreq;
char msgbuf[256];
u_int yes=1;

if((fd=socket(AF_INET,SOCK_DGRAM,0)) < 0)
{
perror("socket");
exit(1);
}

if (setsockopt(fd, SOL_SOCKET, SO_REUSEADDR,
&yes, sizeof(yes)) < 0)
{
perror("setsockopt() SO_REUSEADDR");
exit(1);
}

memset(&addr, 0, sizeof(addr));
addr.sin_family=AF_INET;
addr.sin_addr.s_addr=htonl(INADDR_ANY);
addr.sin_port=htons(PORT);

if(bind(fd,(struct sockaddr *) &addr,
sizeof(addr)) < 0)
{
perror("bind");
exit(1);
}

mreq.imr_multiaddr.s_addr=inet_addr(GROUP);
mreq.imr_interface.s_addr=htonl(INADDR_ANY);

if(setsockopt(fd, IPPROTO_IP, IP_ADD_MEMBERSHIP,
&mreq, sizeof(mreq)) < 0)
{
perror("setsockopt");
exit(1);
}


while(1)
{
addrlen=sizeof(addr);
if ((nbytes=recvfrom(fd, msgbuf,
sizeof(msgbuf), 0, (struct sockaddr *)
&addr, &addrlen)) < 0)
{
perror("recvfrom");
exit(1);
}

puts(msgbuf);
}

return 0;
}

El Ataque Rho de Pollard

2008-11-19T07:00:00.004+01:00

Actualizado 19-11-2008

En un artículo anterior hablamos de la Criptografía de Curva Elíptica, dando una breve introducción al tema.

La revista hakin9 ha publicado en su web un artículo que escribí para la edición de Julio de 2007. El artículo, titulado "Criptografía de Curva Elíptica: Ataque Rho de Pollard" explica la teoría de las curvas elípticas e implementa un ataque en C++.

Se puede descargar el artículo directamente de la web de la revista, o obtener el enlace de mi web.

En cualquier caso, ahí va un enlace directo.

Power Over Ethernet Casero

2008-11-16T12:05:00.002+01:00

Existe un estándar que define la forma de usar cableado de red que incluye alimentación elétrica. Aunque actualmente no resulta sencillo encontrar dispositivos que lo implementen. Por este motivo dedico un post a realizar una implementación casera. Yo lo he usado con éxito en instalaciones de camaras web.

Si utilizamos para el cableado la norma 568B el esquema de colores queda como sigue:

PIN COLOR TIPO
------------------------------
1 Blanco/Naranja TX D1+
2 Naranja TX D1-
3 Blanco/Verde RX D2+
4 Azul Libre
5 Blanco/Azul Libre
6 Verde RX D2-
7 Blanco/Marron Libre
8 Marron Libre

La idea consiste en usar alguno de los pares libres para transmitir el voltaje necesario para la camara. Por ejemplo, en mis instalaciones de camaras web (uso cámaras Axis 206 que necesitan 5V y unos 500mA cada una) no hay ningún problema de interferencias, pero con más de 50V podríamos tener sorpresas.

Como he indicado en el listado anterior, los pares libres son el Blanco/Azul - Azul y el Banco/Marrón - marrón. Se trata, simplemente, de usar uno de esos pares para la alimentación del dispositivo.
En principio, resulta más sencillo crimpar el RJ45 con todos los cables y despues cortar el par que nos interesa para la alimentación. Aunque con un poco de práctica no resulta complicado crimpar solo los cables necesarios, y la instalación siempre queda más 'mona'.

Bueno, aquí queda el código de colores. A ver quien nos cuenta sus experiencias!

Volúmenes cifrados con OpenSSL

2008-11-09T14:45:00.001+01:00

Cada vez hay más productos que se venden como 'criptografía fàcil' para todo tipo de usuarios. Estos te permiten montar un volumen de datos de forma realmente sencilla y cifrarlos con criptografía fuerte. Pero no es el propósito de este artículo repasar ni estudiar dichos productos. Aquí, siguiendo la folosofía del blog, lo que haremos es crear un sistema propio.

Usaremos la herramienta openssl que nos permitirá lidiar con el cifrado y algunos comandos unix para el manejo del volumen.

Creando un nuevo volumen

Para crear un volumen usaremos la herramienta 'dd' que nos permitirá crear un archivo vacío de cierto tamaño. Como ejemplo creamos un volumen de 100MB.

$ dd if=/dev/zero of=volume bs=1M count=100

A continuación necesitaremos crear el sistema de ficheros. Por ejemplo, ext3:

$ mkfs.ext3 volume

y finalmente cifraremos con blowfish. En este paso openssl nos pedirá la contraseña con la que queremos cifrar el sistema.

$ openssl enc -blowfish -in volume -out volume.ciph

Abrir el volumen

Para abrir el volumen solo tendremos que descifrar-lo con

$ openssl enc -blowfish -d -in volume.ciph -out volume

paso en el que se nos pedirá la contraseña de cifrado. A continuación, para acceder al volumen, lo montaremos.

$ mount volume /mnt -o loop

De esta manera, todo lo que guardemos en /mnt quedará almacenado en nuestro volumen de cifrado.

Cerrar el volumen

Una vez hemos terminado de trabajar con nuestro volumen de datos procedemos a cerrarlo y dejarlo cifrado hasta la proxima vez.

Para tal proposito, desmontaremos el volumen:

$ umount -l /mnt

lo cifraremos

$ openssl enc -blowfish -in volume -out volume.ciph

y borraremos la copia sin cifrar

$ rm -f volume

Comentarios finales

Hemos visto como, de forma muy sencilla, y sin recurrir a nada más que los comandos habituales de cualquier sistema unix, podemos tener nuestro propio sistema de volumenes cifrados.

Lógicamente, se le pueden añadir muchas mejoras, como automatizar los comandos con sencillos scripts del estilo create_volume.sh, open_volume.sh, etc o añadir seguridad al sistema, por ejemplo sustituyendo 'rm' por una herramienta de borrado seguro como 'shred'.

En este caso, sustituir

$ rm -f volume

por

$ shred volume

aunque el tiempo autmentará considerablemente.

¿Qué pasa con atoll()?

2008-10-06T15:51:00.008+02:00

Como programador de sistemas UNIX a veces me encuentro con algunas cosas curiosas con las APIs. Hoy, sin ir mas lejos, me he vuelto loco intentando hacer funcionar atoll().

En una parte de un viejo programa, se manejaba un identificador de menos de 32 bits. Ese identificador, que provenía de una máquina Cisco en formato cadena, estaba declarado como 'int' y se transformaba mediante atoi().

Por necesidades ligadas al crecimiento de la empresa, ahora el identificador debía poder almacenar hasta 56 bits.

En pocos segundos tenía el programa funcionando con un identificador declarado como 'long', pero ooops! no funcionaba. De hecho, se comportaba como un 'int'.

El sistema, un CentOS 5.2, el compilador, gcc 4.1.2, sin problemas conocidos. Así que me dediqué a hacer algunas pruebas:

$ cat test1.c

#include<stdio.h>
int main()
{
/* 2^31 = 2147483648 */

char *str="2147483648";
long long i;

i = atoll(str);

printf("%ld\n", i);
}

$ gcc test1.c
$ ./a.out
-2147483648

Overflow, exactamente igual que un 'int'.
Me dirijo al man de atoll() y me encuentro con esto:

"The atol() and atoll() functions behave the same as atoi()"

y efectivamente. La culpa es de la función de conversión, pues con una función my_atoll() personalizada, no existe tal problema:

$ cat test2.c

#includes<stdio.h>
long long my_atoll(char *str)
{
long long res;

res = 0;
for (; *str; str++)
res = 10*res + (*str - '0');

return res;
}


int main()
{
/* 2^31 = 2147483648 */

char *str="2147483648";
long long i;

i =my_atoll(str);


printf("%lld\n", i);
}

$ gcc test2.c
$ ./a.out
2147483648

Sorprendente ...

Linus Torvalds y OpenBSD

2008-09-22T10:25:00.011+02:00

Recojo otra de las lindezas de Linus. Es que es para coleccionarlas ...
ref: http://article.gmane.org/gmane.linux.kernel/706950

From: Linus Torvalds linux-foundation.org>
Subject: Re: [stable] Linux 2.6.25.10
Newsgroups: gmane.linux.kernel
Date: 2008-07-15 16:13:03 GMT (9 weeks, 5 days, 16 hours and 5 minutes ago)
On Tue, 15 Jul 2008, Linus Torvalds wrote:
>
> So as far as I'm concerned, "disclosing" is the fixing of the bug. It's
> the "look at the source" approach.

Btw, and you may not like this, since you are so focused on security, one
reason I refuse to bother with the whole security circus is that I think
it glorifies - and thus encourages - the wrong behavior.

It makes "heroes" out of security people, as if the people who don't just
fix normal bugs aren't as important.

In fact, all the boring normal bugs are _way_ more important, just because
there's a lot more of them. I don't think some spectacular security hole
should be glorified or cared about as being any more "special" than a
random spectacular crash due to bad locking.

Security people are often the black-and-white kind of people that I can't
stand. I think the OpenBSD crowd is a bunch of masturbating monkeys, in
that they make such a big deal about concentrating on security to the
point where they pretty much admit that nothing else matters to them.

To me, security is important. But it's no less important than everything
*else* that is also important!

Linus

Liberar la HTC Touch

2008-09-14T09:47:00.011+02:00

Recientemente me he visto en la obligación de liberar mi HTC Touch. Es sencillo y útil, así que, aunque existen muchos tutoriales en la red, dejo aquí los pasos a sequir.

Descargar y ejecutar Cert_SPCS.cab en la PDA.
Descargar y ejecutar EnableRapi.cab en la PDA.
Descargar Touch_Unlock.exe en el PC.
Conectar la HTC con el PC mediante ActiveSync (USB).
Ejecutar el Touch_Unlock.exe, el cual generará un archivo unlock_code.txt.
Apagar la HTC Touch, introducir la SIM de otro operador e iniciar.
Solicitará el pin de la nueva SIM, introducirlo.
Solicitará un código de red, introducir los primeros 8 dígitos de unlock_code.txt.

La HTC Touch debería estar desbloqueada.

Estas cosas no funcionan siempre. así que en caso de no poder desbloquear el móvil en dos o tres intentos, mejor no continuar.

El Criptograma del 2008

2008-09-07T10:45:00.003+02:00

Actualización:
El criptograma se resiste, así que pasa de ser "El criptograma del verano" a ser "El criptograma del año". Lo dejaré hasta enero y si nadie lo consigue, pondré la solución. Aunque tengo fe en vosotros ...

Viendo que los criptogramas semanales duran bien poco, he decidido poner un reto un poco más complejo para que os podáis estrujar las neuronas durante las aburridas tardes de verano.

En linea con los criptogramas anteriores, se trata de un sistema que en su momento fué ampliamente utilizado.


ADZMO YHADG TIYMM ZCAUG CZYJA DYJTG LKSKM DKOZJ
OKEIG JHKAC EZSGQ HYZOG EZMVG HAZSG MYJOZ MNJEG
SZENH GHEIZ JHKDG COMKS ZCCAB IYFAJ GSZMY JOGMN
JZEON FNHGH CNACO ZEYME GHADY JABNT KVZHY VGEAM
DYEMA YMPIA YCOZD ARKCC NYCOG DARKC ZSGMY JOZMP
IACYA COGEY MEZSK JAMEY UKCSG MZGOM ZAMGD YJABN
TKTKD SYZMG DAJYB NTKEI ZJHKA COGHY CKMHA JZHKS
MYSGM ZMCAE KJOMG YDEIZ JHKAC OGCYT IMKAJ OKHZC
SGMOY CAFNO ZMDYH IMGJO AIJON YBSKE IZJHK ACBGC
XIYMO ACNOI KSKJY JOAON YJAIJ OYBSA MZBYJ OKEKD
AMNEK NJOYJ OGNMM NOZMD ACNYC GMMKT ZJOAO MGOZH
YXKBA JOGMC IYTKO NCBKC NDZCO MKSGC AJYBN TZCCA
VGDDZ JUNYJ SMASG MZHGC OMZCI JGMYK MTZJN QGENK
JNJOA JOZHY CKMHA JGMDZ CCNYC OGJIJ NHZCC NABUM
GDZHN CYJCN KJAJO MYCIC XNDGC ZOGEZ GDAJY BNTKE
IZJHK JKACO GSMYS ZMGHK WZSGM AEYEI ZJHKJ KOAYC
SAMGY COZCC KJDGC EDZFA CHYDG FNEOK MNZSG MZADY
COMGO ATZCI JOQIY DGMOA HYDZT IAMMG

Feliz criptroanálisis.

Cifrados de sustitución homofónica

2008-08-15T14:12:00.007+02:00

En los cifrados de sustitución tradicionales, cada letra del texto plano era sustituída por un simbolo diferente. El problema de este tipo de criptosistema lo vimos en detalle en Criptoanálisis: Análisis de frecuencias.

Al sustituir cada letra por un símbolo diferente, la frecuencia de las letras del texto original se mantiene en el criptograma. Des esta manera, conociendo la frecuencia en la que aparecen las letras en la lengua origen, podemos obtener algunas pistas que nos permitiran resolver el criptograma.

Los cifrados de sustitución homofónica suponen una vuelta de tuerca más a los cifrados de sustitución tradicionals. El objetivo de este sistema consiste en disminuir el efecto de las frecuencias en el criptograma resultante. Así pues, si sabemos que las letra A es la letra más frecuente, podemos sustituir esta letra por símbolos diferentes.

Veamos un ejemplo:

Texto Plano:
ESTO ES UN CRIPTOGRAMA DE EJEMPLO

Frecuencias:
E: 4, S: 2, T:2, O:3, U:1, N:1, C:1, R: 2, I: 1, P: 2:, G: 1, A: 2, M: 2, J: 1, D: 1, L: 1.

Como vemos en el texto plano, las frecuencias habituales son 1 y 2. Destaca pues la E con frecuencia 4 y la O con frecuencia 3.

Así pues, en el momento de asignar sustitutos a cada una de las letras del texto plano, asignaremos más de un sustituto a nuestras letras más frecuentes. Por ejemplo, usaremos E: A,I y O: X, Y. Para las demás letras usaremos un solo símbolo como en un sistema de sustitución tradicional.

Criptrogama:
ABCXIBDEFGHJCYKGLMLNIAOIMJlX

Si ahora estudiamos la frecuencia de las letras solo obtendremos frecuencias de 1 y 2 letras, lo que nos ofrecerá pocas pistas del texto plano original.

Lógicamente, este tipo de criptosistemas es más seguro cuantas más sustituciones se usan para cada letra. El objetivo siempre será tergiversar la distribución de frecuencias del lenguaje original.

Cuando se realizan varias sustituciones por letra nos encontramos con que es necesario disponer de más símbolos que los que proporciona el abecedario. Podemos usar caracteres como @, #, ¿, ?, etc. Aunque normalmente lo más práctico suele ser usar números.

A continuación dejo una utilidad de Simon Singh que permite cifrar/descifrar sistemas homofónicos mediante números: Homophonic Cipher

Criptograma Semanal 09/08/08

2008-08-09T10:40:00.004+02:00

UKALNOIYUAURMXURQYVAVAGWNEAGUQYVEAGUAMVGVATXUYQVADXUAKV AMWURMWVAKNHYVAVIYWY.

VKIUYQAUWREQUWR

Criptograma Semanal 02/08/08

2008-08-02T10:38:00.004+02:00

LEG VR AHW CW SBEDBWPWOHER VX IRW OWBBVBW VRQBV CEX HRDVRHVBEX AV XEJQFWBV HRQVRQWRAE OBVWB PVKEBVX SBEDBWPWX W SBIVZW AV HAHEQWX G VC IRHTVBXE, HRQVRQWRAE SBEAIOHB PWGEBVX HAHEQWX. SEB WLEBW, VC IRHTVBXE VXQW DWRWAE.

BHOM OEEM

Esteganografía: El canal Alpha

2008-07-30T08:03:00.005+02:00

En este primer artículo sobre esteganografía veremos como ocultar mensajes dentro de una imagen. Para ello usaremos el lenguaje C y accederemos a imágenes en formato PNG a través de la librería libpng.

Para probar los ejemplos es necesario descargar el programa steg.c que he desarrollado y la imagen de Tux que viene a continuación:

NOTA: Haz clic en la imagen para obtener la original, pues blogspot al redimensionar la imagen se carga su transparencia.

El canal Alpha:

Algunos formatos de imágen como puede ser PNG guardan cada píxel en RGBA. Lo que significa que se guarda información para R (cantidad de color rojo), G (cantidad de color verde), B (cantidad de color azul) y A (opacidad de la imagen).

Representar el color de un píxel mediante un formato RGB es algo ampliamente conocido, así que no entraremos en más detalles. Vamos a centrar nos en la A de RGBA, lo que se conoce como el canal Alpha.

El canal alpha contiene la información referente a la opacidad de la imagen, es decir, cuan transparente es.
En PNG, por ejemplo, se usa un byte en cada píxel para el canal alpha, de manera que, si este tiene valor 0, la imagen es completamente transparente, si tiene valor 255 la imagen no tiene transparencia y para valores entre 0 y 255 el nivel de transparecia cambia gradualmente.

Así pues, si un píxel de cierto color RGB tiene el canal alpha a cero, no se verá. Lo que nos permite ocultar datos en los bytes destinados a R, G y B siempre que sea un píxel transparente.

Acceso a la imagen PNG:

En el programa de ejemplo podemos ver dos funciones "read_png()" y "write_png()". No entraremos en detalle sobre estas dos funciones. Basta decir que la primera carga la imagen en las estructuras de datos de libpng y la segunda escribe el contenido de estas estructuras de datos en una nueva imagen.

Por lo tanto el procedimiento a seguir será leer la imagen, realizar las modificaciones pertinentes y escribir de nuevo la imagen.

Para acceder a los diferentes bytes que componen RGBA lo haremos a traves de las funciones "get_value()" y "set_value()". Mientras que la primera nos permite obtener el valor de R, G, B o A, "set_value()" nos permite modificarlo. Así pues:

- get/set_value(x, y, 0, ...) accede al byte que define R
- get/set_value(x, y, 1, ...) accede al byte que define G
- get/set_value(x, y, 2, ...) accede al byte que define B
- get/set_value(x, y, 3, ...) accede al byte que define A

Ocultando un fichero:

Para ocultar un fichero, el programa tendrá que leer cada byte del fichero a ocultar y escribirlo en un píxel de la imagen PNG donde el canal alpha este a cero. Como ejemplo pego parte de la función "hide_file()":

FILE *f = fopen(msg_file, "r");
if(!f)
error("[hide_file] fopen()");

for(y = 0; y < height; y++)
{
for(x = 0; x < width; x++)
{
if(get_value(x, y, 3)==0)
{
char c1=0;
char c2=0;
char c3=0;

if(!feof(f)) c1 = fgetc(f);
if(!feof(f)) c2 = fgetc(f);
if(!feof(f)) c3  = fgetc(f);

set_value(x, y, 0, c1);
set_value(x, y, 1, c2);
set_value(x, y, 2, c3);
}
}
}

fclose(f);

Extraer el fichero oculto:

De manera similar a cómo hemos ocultado el fichero en el apartado anterior, podemos extraer la información oculta. Veamos un pedazo de "unhide_file()":

FILE *f = fopen(msg_file, "w+");
if(!f)
error("[unhide_file] fopen()");

for(y = 0; y < height; y++)
{
for(x = 0; x < width; x++)
{
if(get_value(x, y, 3)==0)
{
char c1 = get_value(x, y, 0);
char c2 = get_value(x, y, 1);
char c3 = get_value(x, y, 2);

if(c1==0 || c2==0 || c3==0)
{
fclose(f);
return;
}

fprintf(f, "%c%c%c", c1, c2, c3);
set_value(x, y, 0, 0);
set_value(x, y, 1, 0);
set_value(x, y, 2, 0);
}
}
}

fclose(f);

Ejemplo de uso del programa:

Visto el código básico utilizado, podemos empezar a ocultar ficheros. Veamos un ejemplo.

Primero ocultamos un mensaje:

$ gcc steg.c -o steg -lpng
$ echo "Esto es un mensaje de ejemplo" > msg.txt
$ ./steg hide tux.png tux_steg.png msg.txt

Si abrimos la imagen tux_steg.png veremos que nuestros ojos no detectan ninguna modificación.

Ahora obtenemos el mensaje oculto:

$ ./steg unhide tux_steg.png tux_clean.png msg2.txt
$ cat msg2.txt
Esto es un mensaje de ejemplo

Un poco de cifrado:

Actualmente el mensaje esta oculto, pero no es difícil extraerlo, por lo que no estaría mal añadir un poco de cifrado. Lo haremos con la herramienta openssl.

Primero ciframos el archivo:

$ openssl enc -blowfish -in msg.txt -out msg.ciph
enter bf-cbc encryption password:
Verifying - enter bf-cbc encryption password:

A continuación lo codificamos en base64 y lo ocultamos:

$ openssl base64 -in msg.ciph -out msg.cb64
$ ./steg hide tux.png tux_steg.png msg.cb64

En este punto podemos verificar que la imagen con el mensaje oculto no muestra información adicional.

Extraemos el mensaje oculto y lo descodificamos en base64:

$ ./steg unhide tux_steg.png tux_clean.png msg2.cb64
$ openssl base64 -d -in msg2.cb64 -out msg2.ciph

Desciframos el archivo:

$ openssl enc -blowfish -d -in msg2.ciph -out msg2.txt
enter bf-cbc decryption password:

y voilà:

$ cat msg2.txt
Esto es un mensaje de ejemplo

Debilidades del sistema:

Ocultar la información en el canal alpha de la imagen no es precisamente la mejor técnica que se puede usar en esteganografía. De hecho tiene un inconveniente importante: la facilidad con la que se puede saber que hay un mensaje oculto.

Por ejemplo, simplemente poniendo el byte del canal alpha a 255, al visualizar la imagen veríamos las zonas de información con píxeles de diferentes colores.

A continuación dejo un ejemplo de la imagen de Tux, con un fichero oculto y con el canal alpha a 255. En ella vemos la existencia de información oculta en la primera mitad de la imagen.

El mensaje está cifrado, por lo que el atacante no podrá acceder a su contenido. Pero sí podrá detectar el uso de esteganografía, lo que no deja al sistema en muy buen lugar:)

Criptograma Semanal 26/07/08

2008-07-26T10:00:00.004+02:00

NE XEGQUWE HR NEB WHREB OAPHEXRPLENRB HR NE CWRPCWE BQP RBRPCWENXRPLR BRPCWNNEB G, ZQU URSNE SRPRUEN ZARHRP BRU RVZURBEHEB RP AP NRPSAEIR CQXZURPBWDNR ZEUE LQHQB.

ENDRUL RWPBLRWP

Superado bsgame#1 de Blind Security

2008-07-24T14:10:00.007+02:00

El 1 de Julio Blind Security empezaba el I Torneo de Seguridad Informática BlindSec.

Despues de varias intentonas y de encallarme considerablemente en los niveles 9 y 10 he superado el bsgame#1 entre los 10 primeros, lo que me hace ganador de una bonita camiseta ;)

A todo el que le guste romperse el coco con retos informáticos y quiera aprender, le recomiendo encarecidamente que lo intente, dado que el reto continuará abierto.

A mi me ha servido, entre otras cosas, como perfecta excusa para entrar en el terreno de la esteganografía. De hecho, tan pronto como el torneo sea superado (10 finalistas) publicaré un artículo sobre el tema a partir de algunos programas que desarrollé para pasar el nivel 9.

Insisto, si te gusta la seguridad informática y el hacking ético, no lo dudes, pásate por el torneo.

Los cifrados de Feynman

2008-07-20T23:05:00.004+02:00

El conocido físico Richard Feynman recibió tres mensajes codificados de los científicos de Los Alamos, y después de no poder descifrarlos el mismo, los compartió con sus alumnos de Caltech. Actualmente solo se ha conseguido descifrar el primero de los mensages.

Los tres mensajes cifrados son:

1. Easier
MEOTAIHSIBRTEWDGLGKNLANEA
INOEEPEYSTNPEUOOEHRONLTIR
OSDHEOTNPHGAAETOHSZOTTENT
KEPADLYPHEODOWCFORRRNLCUE
EEEOPGMRLHNNDFTOENEALKEHH
EATTHNMESCNSHIRAETDAHLHEM
TETRFSWEDOEOENEGFHETAEDGH
RLNNGOAAEOCMTURRSLTDIDORE
HNHEHNAYVTIERHEENECTRNVIO
UOEHOTRNWSAYIFSNSHOEMRTRR
EUAUUHOHOOHCDCHTEEISEVRLS
KLIHIIAPCHRHSIHPSNWTOIISI
SHHNWEMTIEYAFELNRENLEERYI
PHBEROTEVPHNTYATIERTIHEEA
WTWVHTASETHHSDNGEIEAYNHHH
NNHTW

2. Harder
XUKEXWSLZJUAXUNKIGWFSOZRAWURO
RKXAOSLHROBXBTKCMUWDVPTFBLMKE
FVWMUXTVTWUIDDJVZKBRMCWOIWYDX
MLUFPVSHAGSVWUFWORCWUIDUJCNVT
TBERTUNOJUZHVTWKORSVRZSVVFSQX
OCMUWPYTRLGBMCYPOJCLRIYTVFCCM
UWUFPOXCNMCIWMSKPXEDLYIQKDJWI
WCJUMVRCJUMVRKXWURKPSEEIWZVXU
LEIOETOOFWKBIUXPXUGOWLFPWUSCH

3. New Message
WURVFXGJYTHEIZXSQXOBGSV
RUDOOJXATBKTARVIXPYTMYA
BMVUFXPXKUJVPLSDVTGNGOS
IGLWURPKFCVGELLRNNGLPYT
FVTPXAJOSCWRODORWNWSICL
FKEMOTGJYCRRAOJVNTODVMN
SQIVICRBICRUDCSKXYPDMDR
OJUZICRVFWXIFPXIVVIEPYT
DOIAVRBOOXWRAKPSZXTZKVR
OSWCRCFVEESOLWKTOBXAUXV
B

Veamos como resolver el primero de los mensajes.

Se trata de un cifrado de transposición, el cual colocaremos en grupos de cinco letras:

M E O T A
I H S I B
R T E W D
G L G K N
L A N E A
I N O E E
P E Y S T
N P E U O
O E H R O
N L T I R
O S D H E
O T N P H
G A A E T
O H S Z O
T T E N T
K E P A D
L Y P H E
O D O W C
F O R R R
N L C U E
E E E O P
G M R L H
N N D F T
O E N E A
L K E H H
E A T T H
N M E S C
N S H I R
A E T D A
H L H E M
T E T R F
S W E D O
E O E N E
G F H E T
A E D G H
R L N N G
O A A E O
C M T U R
R S L T D
I D O R E
H N H E H
N A Y V T
I E R H E
E N E C T
R N V I O
U O E H O
T R N W S
A Y I F S
N S H O E
M R T R R
E U A U U
H O H O O
H C D C H
T E E I S
E V R L S
K L I H I
I A P C H
R H S I H
P S N W T
O I I S I
S H H N W
E M T I E
Y A F E L
N R E N L
E E R Y I
P H B E R
O T E V P
H N T Y A
T I E R T
I H E E A
W T W V H
T A S E T
H H S D N
G E I E A
Y N H H H
N N H T W

Ahora podemos leer el mensaje de abajo a arriba empezando por el final.

El mensaje resultante es:

Whan that Aprill, with his shoures soote
The droghte of March hath perced to the roote
And bathed every veyne in swich licour,
Of which vertu engendred is the flour;
Whan Zephirus eek with his sweete breeth
Inspired hath in every holt and heeth
The tendre croppes, and the yonge sonne
Hath in the Ram his halfe cours yronne,
And smale foweles maken melodye,
That slepen al the nyght with open eye-
(So priketh hem Nature in hir corages);
Thanne longen folk to goon on pilgrimag

.

Sockets en shellscript con xinetd

2008-05-31T20:00:00.004+02:00

Existe la posibilidad de crear aplicaciones sencillas "tipo servidor" con scripts de shell. Vamos a ver un ejemplo en el que se configurará el daemon xinetd para abrir un socket y poner un programa a la escucha. En nuestro caso el programa en cuestión será un script, aunque podría utilizarse cualquier otro lenguaje de programación.

Configurando Xinetd:
Generalmente disponcremos de un archivo de configuración de xinetd similar al siguiente:

$ cat /etc/xinetd.conf
#
# Simple configuration file for xinetd
#
# Some defaults, and include /etc/xinetd.d/

defaults
{
instances               = 60
log_type                = SYSLOG authpriv
log_on_success          = HOST PID
log_on_failure          = HOST
cps                     = 25 30
}

includedir /etc/xinetd.d

Este indica la inclusión de los scripts situados en /etc/xinet.d/.

ls -lh /etc/xinetd.d/
total 100K
-rw-r--r--    1 root     root          563 nov 19 17:53 chargen
-rw-r--r--    1 root     root          580 nov 19 17:53 chargen-udp
-rw-r--r--    1 root     root          419 nov 19 17:53 daytime
-rw-r--r--    1 root     root          438 nov 19 17:53 daytime-udp
-rw-r--r--    1 root     root          341 nov 19 17:53 echo
-rw-r--r--    1 root     root          360 nov 19 17:53 echo-udp
-rw-r--r--    1 root     root          318 jun 23  2002 finger
-rw-r--r--    1 root     root          370 sep  1  2002 imap
-rw-r--r--    1 root     root          365 sep  1  2002 imaps
-rw-r--r--    1 root     root          453 sep  1  2002 ipop2
-rw-r--r--    1 root     root          359 sep  1  2002 ipop3
-rw-r--r--    1 root     root          275 jul  5  2002 ntalk
-rw-r--r--    1 root     root          335 sep  1  2002 pop3s
-rw-r--r--    1 root     root          361 jun 24  2002 rexec
-rw-r--r--    1 root     root          378 jun 24  2002 rlogin
-rw-r--r--    1 root     root          431 jun 24  2002 rsh
-rw-r--r--    1 root     root          317 jun 25  2002 rsync
-rw-r--r--    1 root     root          312 nov 19 17:53 servers
-rw-r--r--    1 root     root          314 nov 19 17:53 services
-rw-r--r--    1 root     root          392 ago 11  2002 sgi_fam
-rw-r--r--    1 root     root          263 jul  5  2002 talk
-rw-r--r--    1 root     root          305 jul 23  2002 telnet
-rw-r--r--    1 root     root          497 nov 19 17:53 time
-rw-r--r--    1 root     root          518 nov 19 17:53 time-udp
-rw-r--r--    1 root     root          276 ago 16  2002 vsftpd

Editando cualquiera de estos archivos puede verse la estructura que siguen los scripts. Para nuestro propósito debemos crear uno de estos scritps, por ejemplo el siguiente:

service nuevoservicio
{
port            = 6666
socket_type     = stream
wait            = no
user            = nobody
server          = /usr/local/bin/NuestroServidor.sh
log_on_success  += USERID
log_on_failure  += USERID
disable         = no
}

El puerto escogido para la escucha debe estar especificado en el archivo /etc/services, en nuestro caso, el puerto 6666, no está especificado, por lo tanto añadimos la siguiente línea a /etc/services:

nuevoservicio 6666/tcp   # Nuestro servicio de prueba

Sencillo, ¿no?.

Ahora solo necesitamos crear el script "NuestroServidor.sh" y colocarlo en /usr/local/bin.

Podemos probar con el clásico:

#!/bin/bash

echo "Hello World!"

Para que el servidor funcione correctamente debemos asegurarnos de que dispone de permisos de ejecución para todos los usuarios.

finalmente reiniciamos xinetd:

$ /etc/rc.d/init.d/xinetd restart
Parando xinetd:                                            [  OK  ]
Iniciando xinetd:                                          [  OK  ]

Podemos probar con:

$ telnet localhost 6666
Trying 127.0.0.1...
Connected to hackerbox (127.0.0.1).
Escape character is '^]'.
Hello World!
Connection closed by foreign host.

El programa llamado por xinetd podría haberse desarrollado en cualquier otro lenguaje de programación: C, Perl ... Lo interesante de esta forma de hacerlo es que permite la creación de servicios simples en un tiempo récord. Aunque no se debe olvidar que en estos sistemas la seguridad no es uno de sus fuertes. Con cuidado!

Enrutamiento básico en Linux

2008-05-25T12:09:00.010+02:00

Actualmente existen gran cantidad de herramientas basadas en GNU/Linux, *BSD y similares que permiten montar un router de una forma más o menos sencilla. Algunas de ellas incluso tienen bonitas interfaces gráficas que nos facilitan la tarea. Si nos movemos al terreno comercial, la oferta crece.

Sin embargo en este artículo no vamos a tratar sobre estas herramientas si no sobre los cimientos que las sustentan. Vamos a ver como usar una máquina Linux para las tareas básicas de enrutamiento.

Lo primero que necesitaremos es configurar las interfaces de red. Para esto utilizaremos la herramienta "ifconfig" disponible en cualquier SO Unix. A continuación tendremos que establecer rutas; utilizaremos "route". Y finalmente, con el daemon "routed" configuraremos el protocolo de enrutamiento RIP.

La herramienta ifconfig
Para configurar las interfaces del sistema utilizaremos la herramienta "ifconfig". Esta herramienta viene con cualquier SO de la familia Unix, y suele estar ubicada en "/sbin". Los parámetros para configurar una interfaz mediante "ifconfig" son los siguientes:

/sbin/ifconfig [interface] [IP] netmask [máscara] broadcast [broadcast]

Veamos un ejemplo, configuremos la interface eth0 con la IP 192.168.1.2:

/sbin/ifconfig eth0 192.168.1.2 netmask 255.255.255.0 broadcast 192.168.1.255

La herramienta route
De la misma forma que utilizamos "ifconfig" para configurar las interfaces, disponemos de "route", para configurar rutas. La herramienta "route", ubicada en "/sbin" recibe los siguientes parámetros:

/sbin/route -[net|host] [IP] netmask [gw [IP]] dev [interface]

Una forma típica de llamara a "route" es la utilizada para configurar un gateway por defecto. Veamos la forma de hacerlo:

/sbin/route add -net 0.0.0.0 netmask 0.0.0.0 gw 192.168.1.1

Hemos añadimo una ruta de manera que los paquetes destinados a cualquier red (0.0.0.0) se dirijan al gateway 192.168.1.1. Hay otra forma de hacerlo más utilizada:

/sbin/route add default gw 192.168.1.1

Entendiendo como "default": "-net 0.0.0.0 netmask 0.0.0.0".

Hemos configurado un gateway por defecto. Ahora configuremos una ruta normal. Por ejemplo, enrutemos todos los paquetes destinados a 192.168.78.0 al gateway 192.168.1.1:

/sbin/route add -net 192.168.78.0 netmask 255.255.255.0 gw 192.168.1.1

El daemon routed
A diferencia de lo que pasaba con "ifconfig" y "route", el daemon "routed" no viene instalado por defecto en el SO Linux. Pero no es difídil de conseguir e instalar.

Una vez instalado se ubica en "/sbin" o en "/usr/sbin". Ejecutarlo es fácil:

/usr/sbin/routed

Pero, ¿para que sirver routed?

El daemon "routed" es la implementación del protocolo RIP (Routing Information Protocol). La finalidad del protocolo RIP consiste en comunicar la estructura de la red a los routers vecinos. Esto soluciona el problema del mantenimiento de rutas en redes grandes, donde sería del todo imposible añadir y borrar rutas en función del estado de la red. Script de ejemplo
Según lo que se ha visto hasta ahora, configurar el enrutamiento básico en Linux es de lo más sencillo. Primero configuramos las interfaces, a continuación habilitamos un ruta por defecto y finalmente arrancamos el demonio "routed". Veamos un Script de ejemplo:

#!/sbin/bash

# Habilitamos la redirección de paquetes
echo 1 > /proc/sys/net/ipv4/ip_forward

# Configuramos las interfaces
/sbin/ifconfig eth0 192.168.1.2 netmask 255.255.255.0 broadcast 192.168.1.255
/sbin/ifconfig eth1 192.168.2.1 netmask 255.255.255.0 broadcast 192.168.2.255
/sbin/ifconfig eth2 192.168.3.1 netmask 255.255.255.0 broadcast 192.168.3.255

# Gateway por defecto
/sbin/route add default gw 192.168.1.1

# Arrancamos routed
/usr/sbin/routed

La escultura Kryptos

2008-05-18T21:20:00.012+02:00

En los exteriores de las oficinas de la CIA en Langley (Virgina) podemos encontrar una escultura hecha por James Sanborn hacia 1990.

En esta enorme "ese" de bronce (tiene cuatro metros de altura) se esconden cuatro mensajes cifrados, escritos en inglés con errores gramaticales y todo;)

Los cuatro mensajes cifrados de la escultura son los siguientes:


EMUFPHZLRFAXYUSDJKZLDKRNSHGNFIVJ
YQTQUXQBQVYUVLLTREVJYQTMKYRDMFD
VFPJUDEEHZWETZYVGWHKKQETGFQJNCE
GGWHKK?DQMCPFQZDQMMIAGPFXHQRLG
TIMVMZJANQLVKQEDAGDVFRPJUNGEUNA
QZGZLECGYUXUEENJTBJLBQCRTBJDFHRR
YIZETKZEMVDUFKSJHKFWHKUWQLSZFTI
HHDDDUVH?DWKBFUFPWNTDFIYCUQZERE
EVLDKFEZMOQQJLTTUGSYQPFEUNLAVIDX
FLGGTEZ?FKZBSFDQVGOGIPUFXHHDRKF
FHQNTGPUAECNUVPDJMQCLQUMUNEDFQ
ELZZVRRGKFFVOEEXBDMVPNFQXEZLGRE
DNQFMPNZGLFLPMRJQYALMGNUVPDXVKP
DQUMEBEDMHDAFMJGZNUPLGEWJLLAETG


ABCDEFGHIJKLMNOPQRSTUVWXYZABCD
AKRYPTOSABCDEFGHIJLMNQUVWXZKRYP
BRYPTOSABCDEFGHIJLMNQUVWXZKRYPT
CYPTOSABCDEFGHIJLMNQUVWXZKRYPTO
DPTOSABCDEFGHIJLMNQUVWXZKRYPTOS
ETOSABCDEFGHIJLMNQUVWXZKRYPTOSA
FOSABCDEFGHIJLMNQUVWXZKRYPTOSAB
GSABCDEFGHIJLMNQUVWXZKRYPTOSABC
HABCDEFGHIJLMNQUVWXZKRYPTOSABCD
IBCDEFGHIJLMNQUVWXZKRYPTOSABCDE
JCDEFGHIJLMNQUVWXZKRYPTOSABCDEF
KDEFGHIJLMNQUVWXZKRYPTOSABCDEFG
LEFGHIJLMNQUVWXZKRYPTOSABCDEFGH
MFGHIJLMNQUVWXZKRYPTOSABCDEFGHI


ENDYAHROHNLSRHEOCPTEOIBIDYSHNAIA
CHTNREYULDSLLSLLNOHSNOSMRWXMNE
TPRNGATIHNRARPESLNNELEBLPIIACAE
WMTWNDITEENRAHCTENEUDRETNHAEOE
TFOLSEDTIWENHAEIOYTEYQHEENCTAYCR
EIFTBRSPAMHHEWENATAMATEGYEERLB
TEEFOASFIOTUETUAEOTOARMAEERTNRTI
BSEDDNIAAHTTMSTEWPIEROAGRIEWFEB
AECTDDHILCEIHSITEGOEAOSDDRYDLORIT
RKLMLEHAGTDHARDPNEOHMGFMFEUHE
ECDMRIPFEIMEHNLSSTTRTVDOHW?OBKR
UOXOGHULBSOLIFBBWFLRVQQPRNGKSSO
TWTQSJQSSEKZZWATJKLUDIAWINFBNYP
VTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR


NGHIJLMNQUVWXZKRYPTOSABCDEFGHIJL
OHIJLMNQUVWXZKRYPTOSABCDEFGHIJL
PIJLMNQUVWXZKRYPTOSABCDEFGHIJLM
QJLMNQUVWXZKRYPTOSABCDEFGHIJLMN
RLMNQUVWXZKRYPTOSABCDEFGHIJLMNQ
SMNQUVWXZKRYPTOSABCDEFGHIJLMNQU
TNQUVWXZKRYPTOSABCDEFGHIJLMNQUV
UQUVWXZKRYPTOSABCDEFGHIJLMNQUVW
VUVWXZKRYPTOSABCDEFGHIJLMNQUVWX
WVWXZKRYPTOSABCDEFGHIJLMNQUVWXZ
XWXZKRYPTOSABCDEFGHIJLMNQUVWXZK
YXZKRYPTOSABCDEFGHIJLMNQUVWXZKR
ZZKRYPTOSABCDEFGHIJLMNQUVWXZKRY
ABCDEFGHIJKLMNOPQRSTUVWXYZABCD

Aunque tanto la NSA como la propia CIA resolvieron el acertijo, la primera persona que anunció públicamente las tres primeras partes fué James Gillogly, en 1999. Por lo que se sabe, la cuarta parte continúa todavía sin resolver.

Solución a la Primera Parte:
(Vigenere clave alfabeto: kryptos, clave: palimpsest)

BETWEEN SUBTLE SHADING AND THE ABSENCE OF LIGHT LIES THE NUANCE OF IQLUSION

Solución a la Segunda Parte:
(Vigenere clave alfabeto: kryptos, clave: Abscissa)

IT WAS TOTALLY INVISIBLE HOWS THAT POSSIBLE ? THEY USED THE EARTHS MAGNETIC FIELD X THE INFORMATION WAS GATHERED AND TRANSMITTED UNDERGRUUND TO AN UNKNOWN LOCATION X DOES LANGLEY KNOW ABOUT THIS ? THEY SHOULD ITS BURIED OUT THERE SOMEWHERE X WHO KNOWS THE EXACT LOCATION ? ONLY WW THIS WAS HIS LAST MESSAGE X THIRTY EIGHT DEGREES FIFTY SEVEN MINUTES SIX POINT FIVE SECONDS NORTH SEVENTY SEVEN DEGREES EIGHT MINUTES FORTY FOUR SECONDS WEST X LAYER TWO

Solución a la Tercera Parte:

SLOWLY DESPARATLY SLOWLY THE REMAINS OF PASSAGE DEBRIS THAT ENCUMBERED THE LOWER PART OF THE DOORWAY WAS REMOVED WITH TREMBLING HANDS I MADE A TINY BREACH IN THE UPPER LEFT HAND CORNER AND THEN WIDENING THE HOLE A LITTLE I INSERTED THE CANDLE AND PEERED IN THE HOT AIR ESCAPING FROM THE CHAMBER CAUSED THE FLAME TO FLICKER BUT PRESENTLY DETAILS OF THE ROOM WITHIN EMERGED FROM THE MIST X CAN YOU SEE ANYTHING Q (?)

Referencias:
- http://www.elonka.com/kryptos
- Kryptos en la CIA.

Hugo Scolnik: Avances en la Factorización Entera

2008-03-30T10:48:00.008+02:00

El pasado 3 de diciembre se celebró el II Día Internacional de la Seguridad en la Información (DISI 2007). En el, Hugo Scolnik presentó un nuevo algoritmo de factorización, que aunque está por terminar, no tiene mala pinta.

A continuación dejo los enlaces (Criptored) a la presentación y el vídeo de la conferencia:

Presentación PDF.

Estos archivos pueden descomprimirse en Línux con el siguiente comando:

$ cat *.z* > video.zip && unzip video.zip

En el foro de Kriptopolis, alguien que firmaba como "Hugo Scolnik" ponía un ejemplo sencillo de factorización:

Enviado por anónimo el 4. Enero 2008 - 8:42.
Pues ahi va un ejemplo pequeño para ilustrar el tema
Sea n = 507527
Los targets únicos son (23 en total):
(1,0,3) , (1,0,4), (4,1,5),....,(649,576,720)
Esto significa que x^2 = 1+3t(1) = 1+4t(2)=...= 649+720t(23)
con t(23) = 88 se consigue la soluciòn
Con respecto a y^2 tenemos que puede escribirse como 576+720u(23) con u(23) = 793
Obviamente con n grande es impracticable buscar los valores de t o de u.
Ahora, (n + 649 -576)/720 = 705 y algunos targets ùnicos de 705 son
(0,1,4) , (0,1,8), (0,1,16)
Llamaremos (a1,b1,c1) al target ùnico elegido del primer nivel, o sea (649,576,720) y
(a2,b2,c2) al del segundo nivel
Si usamos el primero con la fòrmula x^2 =a1+c1a2+c1c2t = 649+2880t correcto con t = 22
Si usamos el segundo obtenemos x^2 = 649+5760t correcto con t = 11
Pero el tercero da x^2= 649+11520t que es FALSO (deberìa dar x^2 = 6409+11520t)
¿Còmo corregir 649 ? Habrìa que sumarle deltax2 = 5760 = 8c1 (siempre es un mùltiplo de c1)
Para y^2 obtenemos y^2= b1+c1b2+c1c2u
En el primer caso y^2 = 1296+2880u correcto con u = 198
En el segundo caso y^2 = 1296+5760u correcto con u = 99
El tercero falla pues da y^2 = 1296+11520u y deberìa ser 7056+11520u
La correcciòn es deltay2 = 5760 que es igual a deltax2
Varios de los teoremas que mostrè ràpidamente tienen que ver con las correcciones, su relaciòn con las ecuaciones
diofánticas, etc. Casos muy interesantes son los simètricos, donde aparecen en el nivel k > 1 targets ùnicos
idènticos a los del primer nivel (al parecer siempre existen pero todavìa no nos dedicamos a demostrarlo porque
hay otras prioridades). Para ellos se pueden demostrar varios resultados muy interesantes, y ahora los estoy
usando para la exploraciòn de las ramas provenientes de las posibles elecciones de targets.
Cordialmente
Hugo Scolnik

Publicidad web: Automatizando clics

2008-02-23T21:39:00.011+01:00

Aunque la automatización del movimiento del mouse y la realización de clics tiene cientos de aplicaciones lícitas, a nadie se le escapa la posibilidad de usarlo para realizar clics fraudulentos en la los anuncios contextuales de la web.

La primera pregunta que se plantea uno ...

... es qué medidas de seguridad adoptarán las empresas que, como por ejemplo Google (Adsense), ofrecen este servicio.

Es lógico pensar que si todos los clics vienen desde la misma IP no se tendrán en cuenta. Pero esta barrera es fácil saltársela con sistemas de navegación anónima como Tor.

Pero las empresas que se dedican a estas cosas, que no son tontas, no dan esos clics por válidos.

Hasta aqui todo bien, pues sigue la lógica que cabría esperar.

El problema se produce en el momento que estas empresas deciden considerar al propietario de la web que recibe los clics como culpable de los mismos, eliminándole la cuenta.

Este hecho produce una consecuencia terrible: la aparición de un ataque de denegación de servicio.

La segunda pregunta que se plantea uno ...

... es cuanto se puede tardar en desarrollar un programa que mueva el mouse a una posición (x,y) y realice un clic sobre ella.

Después de googlear un poquito y realizar algunas pruebas la conclusión es extremecedora ... En unos 20 minutos el programa esta listo.

Cómo mover el mouse con XLib:

A continuación pego una función que mueve el puntero del mouse a la posición X,Y pasada como parámetro.

void mouse_move(int x, int y)
{
Display *display = XOpenDisplay(0);
Window root = DefaultRootWindow(display);
XWarpPointer(display, None, root, 0, 0, 0, 0, x, y);
XCloseDisplay(display);
}

Cómo hacer clic con XLib:

A continuación pego una función que hace clic sobre la posición actual del mouse. Para realizar clic con el botón derecho se usa button=0.

void mouse_click(int button)
{
Display *display = XOpenDisplay(NULL);
XEvent event;
memset(&event, 0x00, sizeof(event));
event.type = ButtonPress;
event.xbutton.button = button;
event.xbutton.same_screen = True;
XQueryPointer(display, RootWindow(display, DefaultScreen(display)), 
&event.xbutton.root, &event.xbutton.window, &event.xbutton.x_root,
&event.xbutton.y_root, &event.xbutton.x, &event.xbutton.y,
&event.xbutton.state);
event.xbutton.subwindow = event.xbutton.window;

while(event.xbutton.subwindow)
{
event.xbutton.window = event.xbutton.subwindow;
XQueryPointer(display, event.xbutton.window, &event.xbutton.root,
&event.xbutton.subwindow, &event.xbutton.x_root,
&event.xbutton.y_root, &event.xbutton.x, &event.xbutton.y,
&event.xbutton.state);
}

if(XSendEvent(display, PointerWindow, True, 0xfff, &event)==0)
fprintf(stderr, "XSendEvent()\n");

XFlush(display);
usleep(100000);

event.type = ButtonRelease;
event.xbutton.state = 0x100;

if(XSendEvent(display, PointerWindow, True, 0xfff, &event)==0)
fprintf(stderr, "XSendEvent()\n");

XFlush(display);
XCloseDisplay(display);
}

El programa:

Vistas las funciones anteriores resulta trivial desarrollar un programa:

int main(int argc, char* argv[])
{
if(argc!=3)
{
printf("Usage: %s [x coord] [y coord]\n\n", argv[0]);
return 0;
}

int x = atoi(argv[1]);
int y = atoi(argv[2]);
mouse_move(x, y);
mouse_click(0);
return 0;
}

Solo queda decir que las librerias necesarias de XLib son X11/Xlib.h y X11/Xutil.h
Y que el programa se compila con:

$ gcc click.c -lX11

Conclusiones:

La publicidad web genera mucho dinero, lo que la hace atractiva para todo intento de uso fraudulento. Sin embargo las empresas que se dedican a esto saben lo que hacen y no resulta sencillo tomarles el pelo.
Lo que quiero decir con esto es que el intento de ganar dinero haciendo clics en publicidad propia dificilmente llegará a buen término, por lo que no se lo recomiendo a nadie.

Para finalizar un comentario para las empresas que se dedican a cancelar la cuenta del usuario que recibe clics fraudulentos: mala idea.

Cómo funciona el exploit vmsplice

2008-02-17T19:49:00.007+01:00

Despues del revuelo ocasinado por el bug vmsplice() en el kernel Linux vamos a realizar un pequeño análisis de su funcionamiento. Para el que no lo sepa, la explotación del bug vmsplice permite a un usuario del sistema convertirse en root. Esto ocurre en los kernels que van desde la versión 2.6.17 a la 2.6.24.1.

Algunos exploits disponibles son:

http://www.milw0rm.com/exploits/5092
http://www.milw0rm.com/exploits/5093

Veamos un ejemplo con el segundo exploit:

$ uname -r
2.6.23

$ gcc exploit.c
$ ./a.out
-----------------------------------
Linux vmsplice Local Root Exploit
By qaaz
-----------------------------------
[+] addr: 0xc011481b
[+] root
$ id
uid=0(root) gid=0(root) grupos=501(user)

La llamada al sistema vmsplice:

vmsplice es una llamada al sistema que puede ser accedida desde espacio de usuario mediante syscall().

syscall(__NR_vmsplice, fd, iov, nr_segs, flags);

Encontramos su implementación en fs/splice.c, en las fuentes del kernel Linux:



asmlinkage long sys_vmsplice(
   int fd, const struct iovec __user *iov,unsigned long nr_segs, unsigned int flags){...}

Nos interesa prestar atención a los parámetros recibidos por la llamada al sistema, pues son los que el usuario puede controlar al llamar a la función.

Cuando un usuario llama a sys_vmsplice() se produce la siguiente secuencia de llamadas:

- sys_vmsplice() - vmsplice_to_pipe() - get_iovec_page_array()

Dado que el bug se encuentra en get_iovec_page_array() nos interesará saber qué parámetros de la misma puede controlar el usuario. Es decir, qué parámetros de sys_vmsplice() llegan hasta get_iovec_page_array() y si estos parámetros pasan por algun filtro durante el proceso.

Si leemos con atención las funciones implicadas vemos que desde la llamada a sys_vmsplice() hasta la ejecución de la función vulnerable get_iovec_page_array() se mantienen los parámetros: iov y nr_segs.

La función get_iovec_page_array():

La función get_iovec_page_array() es la función vulnerable que el exploit aprovecha para obtener privilegios de root. Como se ha comentado en el apartado anterior, el usuario puede controlar los parámetros iov y nr_segs de esta función.

Observemos el siguiente código de la función vulnerable:



struct iovec entry;
...

if(copy_from_user_mmap_sem(&entry, iov, sizeof(entry)))
   break;

...

len = entry.iov_len;

...

npages = (off + len + PAGE_SIZE - 1) >> PAGE_SHIFT;

if (npages > PIPE_BUFFERS - buffers)
   npages = PIPE_BUFFERS - buffers;
   
error = get_user_pages(current, current->mm,(unsigned long) base, npages, 0,    0,&pages[buffers], NULL);

"iov" es copiada en "entry" y el valor de "iov_len" asignado a la variable "len". Por lo tanto, el usuario tiene el control de la variable "len".
A continuación se calcula "npages" mediante off + len + PAGE_SIZE - 1.

En la función get_user_pages() se asume que npages es como mínimo 1. Dado que "len" no debe ser 0, off + len + PAGE_SIZE - 1 siempre será mayor o igual que PAGE_SIZE. Sin embargo, si "len" tiene un valor cercano a UINT32_MAX, entonces npages podría valer 0 (integer overflow).

Como consecuencia get_user_pages() podría retornar más de PIPE_BUFFERS entradas, lo que como veremos a continuación, produce un buffer overflow.

A continuación, en get_iovec_page_array(), viene el siguiente código:



for (i = 0; i < error; i++) 
{
   const int plen = min_t(size_t, len, PAGE_SIZE - off);
   partial[buffers].offset = off;partial[buffers].len = plen;
   off = 0;
   len -= plen;buffers++;
}

El tamaño del array "partial" es PIPE_BUFFERS pero como hemos comentado, el valor de "error" será superior a este. Por lo tanto, las estructuras de datos que se encuentren a continuación de "partial" serán sobreescritas con "off" y "plen".

Normalmente la víctima de esta sobreescritura es el array "pages" que contiene punteros. En este caso, por ejemplo, se podria sobreescribir "pages" con valores NULL.

Cómo ejecutar código arbitrario:

Normalmente cuando el Kernel intenta acceder a un puntero NULL se obtiene una excepción que finaliza el proceso. Pero existe una técnica que puede ser usada por el atacanta para que en lugar de obtener un error se ejecute código arbitrario. Esta técnica consiste en mapear la dirección 0 y guardar allí datos que permitiran el control del usuario y la ejecución de código en el contexto del kernel.

Posibles soluciones:

Sin duda la mejor solución al problema consiste en actualizar el kernel o aplicar el parche correspondiente. Pero en casos de que eso no sea posible, por ejemplo, por la imposibilidad de reiniciar la máquina, puede usarse el siguiente módulo:

http://home.powertech.no/oystein/ptpatch2008/ptpatch2008.c

Referencias:
- Informe de McAfee Labs
- http://www.coseinc.com/coseinc_linux_advisory_3.pdf

Factorización IV: El Método de Curva Elíptica

2008-01-13T14:35:00.001+01:00

El siguiente artículo es el cuarto de una serie dedicada a la factorización de números enteros. Hasta ahora se han visto los algoritmos básicos de factorización como Pollard P-1, que aunque pueden parecer rápidos, tienen complejidad exponencial, lo que los incapacita para factorizar números relativamente grandes. También se han introducido algunos de los conceptos necesarios para profundizar en el tema que nos permitirán, en este artículo y en los siguientes, estudiar los tres algoritmos más rápidos de factorización. Estos son el Método de Curva Elíptica (ECM), La Criba Cuadrática (QS) y la Criba en el Campo de Números (NFS), los tres de complejidad subexponencial. Empezaremos por el Método de Curva Elíptica.

En el artículo Criptografía de Curva Elíptica dimos una introducción a este peculiar tipo de curvas y su aplicación a la criptografía. A continuación iremos un poco más lejos y veremos como aprovechar esta herramienta matemática para factorizar números enteros grandes.

Para entender el siguiente artículo es necesario disponer de unos conocimientos básicos de curvas elípticas. En caso contrario, es recomendable leer primero el artículo mencionado anterioremente.

El Teorema de Lagrange:

Si aplicamos el Teorema de Lagrange a las curvas elípticas no encontramos con algo interesante que nos conducizará al método de factorización mediante curvas elípticas.

Si P es un punto en una curva elíptica E, entonces el orden de P dividirá el orden de E.

Recordemos que el orden de E, representado como #E, corresponde al número de puntos que hay en una curva E. Mientras que el orden de P, corresponde al valor k más pequeño (diferente de O) tal que kP = O.

Imaginemos que queremos factorizar un número N. Si encontramos una curva E definida sobre N, cuyo orden sea B-smooth, para un valor de B suficientemente pequeño, nos encontraremos con que B!P = O.

Esto ocurre debido a que #E es B-smooth y el orden de P debe ser un divisor de #E, tal y como nos indica el Teorema de Lagrange.

Factorización:

Encontrar un valor k tal que kP=O, en una curva mod N, es equivalente a encontrar un factor de N.

Esto ocurre por que durante el proceso de cálculo de kP se realizan operaciones que necesitan que cierto número d tenga inversa d^(-1). Para que d sea invertible debe cumplirse que el máximo común divisor entre d i el módulo sea igual a 1.

Pero ¿qué ocurre si d no tiene inversa? pues que el máximo común divisor entre d y el módulo N es diferente de 1. Con lo que tenemos un factor de N!

Imaginemos que queremos factorizar 4453. En este caso buscaríamos curvas aleatorias hasta encontrar una cuyo orden fuese B-smooth. Por ejemplo y²=x³+10x-2 mod 4453.

Ahora calcularíamos, kP para un valor pequeño de K. Empezemos por 2P para, por ejemplo P=(1,3).

(3x²+10) / 2y = 13 / 6 mod 4453 (derivada)

Para calcular 13/6 necesitamos calcular 6^(-1). Dado que MCD(6, 4452) podemos hacerlo: 6^(-1) = 3711, con lo que obtenemos:

13 / 6 = 3713 mod 4453
x = 3713²-2 = 4332
y = -3713(x-1)-3 = 3230

Para calcular 3P hacemos 2P + P:

(3230-3) / (4332-1) = 3227/4331.

Igual que en el cálculo anterior, para poder calcular 3227/4331 es necesario que 4331 tenga inversa, es decir, que MCD(4331, 4453) sea 1. Pero si realizamos el cálculo vemos que MCD(4331, 4453)=61. Con lo que hemos encontrado un factor de N.

Complejidad:

El método de factorización mediante curvas elípticas és muy rápido. De hecho, cuando deseamos factorizar números enteros grandes i sabemos que undo de los factores es mucho menor que el otro, este método es el más rápido.

Veamos a continuación por que és tan rápido.

El teorema de Hasse nos dice que el orden #E satisface la siguiente ecuación:

p+1-2 sqr(p) < #E < p+1-2 sqr(p)

Esto nos da una cierta idea del intervalo en el que puede moverse el valor #E. De esta manera sabemos que al generar una curva aleatoria, estamos obteniendo un valor entre este rango, de manera que si es B-smooth, conseguiremos factorizar N.

El número estimado de operaciones que necesitaremos realizar para encontrar una curva B-smooth es el siguiente:

exp(sqr(2) + O(1) + sqr(lnp ln lnp)

Como vemos, el número de operaciones necesarias es subexponencial, esto proviene del hecho de que la complejidad de encontrar números smooth es también subexponencial. Lo mismo ocurre con los algoritmos QS y NFS.

Software:

Actualmente la implementación libre más rápida de ECM es GMP-ECM, disponible en:

http://www.komite.net/laurent/soft/ecm/

Referencias:
- Elliptic Curves, Number Theory and Cryptography. Lawrence C. Washington.
- Prime Numbers, A Computational Perspective. Crandall & Pomerance.

Factorización III: P-1 de Pollard

2007-11-21T20:25:00.001+01:00

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

Introducción a las redes Tor

2007-10-31T20:41:00.001+01:00

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

Factorización II: Rho de Pollard

2007-10-26T08:37:00.002+02:00

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.

Factorización I: Introducción

2007-10-25T07:41:00.001+02:00

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.

Linus Torvalds y C++

2007-09-24T19:15:00.001+02:00

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

Criptografía de Curva Elíptica

2007-09-15T11:36:00.001+02:00

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 = a^y 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).

Criptoanálisis: Análisis de frecuencias

2007-09-11T21:10:00.002+02:00

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.

Los cifrados Zodiac

2007-08-26T22:07:00.001+02:00

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.

Buscando colisiones en SHA-1

2007-08-19T20:21:00.001+02:00

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.

Codificación Base 64

2007-07-28T20:45:00.002+02:00

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

2007-07-28T15:46:00.001+02:00

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/