Inteligencia Artificial: los chatbots

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

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

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

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

OpenDomo publica sus primeras screenshots

.
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

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

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

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

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()?

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

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

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.

1. Descargar y ejecutar Cert_SPCS.cab en la PDA.
2. Descargar y ejecutar EnableRapi.cab en la PDA.
3. Descargar Touch_Unlock.exe en el PC.
4. Conectar la HTC con el PC mediante ActiveSync (USB).
5. Ejecutar el Touch_Unlock.exe, el cual generará un archivo unlock_code.txt.
6. Apagar la HTC Touch, introducir la SIM de otro operador e iniciar.
7. Solicitará el pin de la nueva SIM, introducirlo.
8. 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

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

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

UKALNOIYUAURMXURQYVAVAGWNEAGUQYVEAGUAMVGVATXUYQVADXUAKV AMWURMWVAKNHYVAVIYWY.

VKIUYQAUWREQUWR

Criptograma Semanal 02/08/08

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

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

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

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

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

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

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

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

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.
  

• Vídeo principal.
  
• Vídeo parte 1.
• Vídeo parte 2.
• Vídeo parte 3.
• Vídeo parte 4.
• Vídeo parte 5.
• Vídeo parte 6.

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

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

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

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.