sábado, 28 de julio de 2007

Codificación Base 64

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

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



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


Base 64 y OpenSSL:

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


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

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

Una implementación de Base 64:

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


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

#ifdef __cplusplus
extern "C" {
#endif

#define ERR_BASE64_BUFFER_TOO_SMALL             0x0010
#define ERR_BASE64_INVALID_CHARACTER            0x0012

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

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

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

#ifdef __cplusplus
}
#endif






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

#ifndef _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_DEPRECATE 1
#endif

#include "xyssl/base64.h"

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

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

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

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

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

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

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

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

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

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

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

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

*dlen = p - dst;

return( 0 );
}

static const char _base64_src[] = "_base64_src";

#if defined(SELF_TEST)

#include 
#include 

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

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

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

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

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

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

return( 1 );
}

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

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

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

return( 1 );
}

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

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


#endif /* base64.h */




Referencias:

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




.

El manuscrito Voynich

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




Images from the Voynich Manuscript



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


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

domingo, 22 de julio de 2007

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

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


ECB - Electronic Code Book Mode:

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





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

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


CBC - Cipher Block Chaining Mode:

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



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




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


CTR - Counter Mode:


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




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

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


OFB - Output Feedback Mode:

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




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

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


CFB - Cipher Feedback Mode:


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



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


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


sábado, 21 de julio de 2007

Hash mediante C y OpenSSL


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

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

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


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



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


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



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

Ejemplo:


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

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

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

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

return ret;
}




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



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

#define READSIZE 1024

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

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

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

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

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

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

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

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

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

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

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

if(!contents)
return NULL;

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

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

if(!digest)
return 0;

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

void
usage(char *progname)
{

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

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

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

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


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

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

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

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

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

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

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




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


$ gcc -lssl myhash.c -o myhash

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

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

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

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



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

domingo, 15 de julio de 2007

Integer Overflow en Java

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


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

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

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

$ java ShortOverflow 101
num: 101
num > 100

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

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

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

$ java ByteOverflow 101
num: 101
num > 100

$ java ByteOverflow 1000
num: -24
num < 100

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

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

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

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

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

$ java IntegerOverflow 100000
num: 100000
num > 100

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

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

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

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

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

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

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

$ java RecargaMovil 98234948 -98303
Importe demasiado pequeño

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

sábado, 14 de julio de 2007

Integer Overflow

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


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



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

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


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


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


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

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


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



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

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


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

size_t num = atoi(argv[1]);

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

return 0;
}



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



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


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

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

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

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