inmensia

Siguiendo los pasos que detallé en mi anterior post, he conseguido programar una pequeña clase que aplica el algoritmo MD5 sobre un bloque de datos de entrada y genera su hash correspondiente. Ejecutando una pequeña batería de pruebas, comprobando el resultado obtenido con el generado por otras herramientas, he podido verificar que el código funciona correctamente en el entorno que lo estoy probando, y con el volumen de datos que espero, es decir, en MSVC 9 y con apenas unos pocos caracteres correspondientes a las claves de entrada a las cuentas. A pesar de ser funciones muy sencillas, fijándome detenidamente en la implementación, he anotado unas cuantas cosas que debería revisar si en un futuro quiero utilizarlas en un entorno de producción: portabilidad, seguridad, escalabilidad, y velocidad. Creo que la función puede ofrecer resultados distintos en función de si la máquina utiliza la convención big-endian o little-endian. Probablemente debería borrar el buffer intermedio que utilizo para proporcionar un extra de seguridad. La longitud calculada en bits puede exceder el tamaño de la variable que utilizo para almacenar su cálculo con bloques extremadamente grandes. Y es más, para un gran volumen de datos los requerimientos de memoria se disparan al reservarse tantos bytes extra como tenga el bloque pasado como argumento. Bufff... demasiadas cosas para algo tan aparentemente simple, pero la experiencia ha merecido la pena.

Retornando al tema de la seguridad, y pensando en como funciona el algoritmo MD5, es claro que no es la solución definitiva. Uno de los problemas más evidentes que tiene se basa en su filosofía de funcionamiento. Dada una misma cadena de texto siempre se retorna el mismo código hash. Tomando un diccionario de palabras es fácil generar los hashs para todas ellas y seguir el camino contrario. Es decir, capturar de alguna forma un código hash, y buscar la palabra a la que corresponde dicho código. De hecho, hay webs en Internet que ofrecen ese tipo de servicio. Como tradicionalmente las personas tendemos a utilizar palabras fáciles de recordar para las claves, entonces existe cierta probabilidad de encontrar alguna clave de alguien que no haya tenido especial cuidado a la hora de elegirla. Para resolver este problema se debe forzar a los usuarios a escoger claves que impliquen cierta dificultad. Las reglas más habituales son obligar a que tengan un mínimo de caracteres, que incluyan números o caracteres especiales, que no contengan el mismo carácter repetido más de ciertas veces, que no sean iguales a los nombres de los usuarios u otras palabras evidentes, y así sucesivamente.

Buscando un poco más acerca de este tema, encontré algunas técnicas para añadir un plus de seguridad a la hora de proteger las passwords de los usuarios en las comunicaciones con el servidor. La que me pareció más interesante fue la opción de que el servidor generara una clave secreta de forma aleatoria, que enviara esta clave al cliente, y que el cliente tuviera que devolvérsela al servidor codificada junto con la password del usuario. De esta forma se evita que un hash capturado pueda reutilizarse, ya que una clave secreta aleatoria sólo es válida para una conexión concreta, no para todas. HMAC (keyed-Hash Message Authentication Code) es un tipo de código para la autentificación de mensajes que puede adaptarse al proceso que acabo de describir, que se encuentra definido en el RFC 2104, y que puede utilizarse conjuntamente con cualquier función de encriptación basada en la iteración sobre bloques, como MD5, motivo por lo que me decidí a implementarlo también.

HMAC llama H a la función de encriptación (MD5 en mi caso), B a la longitud en bytes de los bloques que procesa H en cada iteración (64 bytes en el caso de MD5), L a la longitud en bytes del hash generado por H (16 bytes en el caso de MD5), y K a la clave secreta. Impone que la longitud inicial de K sea menor o igual que B, de forma que si la longitud de K es mayor que B entonces se puede aplicar H sobre K para obtener una nueva K de longitud L. Lo que no se recomienda en ningún caso es que K tenga una longitud menor de L, ya que esto restaría efectividad al método. Una vez obtenida una K del tamaño adecuado, esta ha de complementarse con ceros por la derecha hasta que alcance la longitud de B bytes.

A continuación se definen dos constantes. La primera llamada ipad, una cadena de B bytes que contienen todos ellos el valor 0x36. La segunda llamada opad, una cadena de B bytes que contienen todos ellos el valor 0x5C.

El proceso de codificación en si mismo consiste en ejecutar la siguiente función sobre el bloque de datos que se quiere proteger al que se denota como text:

Es decir, primero se hace XOR entre ipad y K. A continuación se concatena con text. Se aplica la función H de encriptación. Al resultado de H se le concatena el XOR entre K y opad. Y se vuelve a aplicar la función H otra vez para obtener el resultado final.

Es claro que el resultado de esta función será un bloque de L bytes, es decir, la longitud de los hashs que genera H, ya que es el último paso que se aplica. De igual forma que deber ser claro que los valores "K XOR opad" y "K XOR ipad" pueden calcularse una única vez al principio cuando el servidor mande la clave secreta, y reutilizarlos para comprobar la autenticidad de una serie de mensajes, y no sólo el de validación de password. Aunque, para mayor seguridad, se recomienda que el servidor cambie la clave secreta de un cliente varias veces a lo largo del tiempo dentro de una misma conversación.

Siguiendo las indicaciones dadas es fácil desarrollar una función que evalúe HMAC sobre MD5. Aunque siempre queda la posibilidad de tomar código existente. Hay una implementación disponible en prácticamente cualquier lenguaje de programación, tanto de MD5 como de HMAC. Incluso los gestores de base de datos como MySQL y PostgreSQL soportan los métodos de encriptación más populares de forma nativa a modo de funciones SQL (1 y 2). Además, en bastantes proyectos de código abierto pueden encontrarse implementaciones sólidas y altamente probadas, como dentro de los fuentes de OpenSSL por ejemplo.

Para terminar, comentar que MD5 no es el método más recomendado hoy en día, todo lo contrario, en prácticamente todos los sitios que he acabado visitado se recomendaba el uso de otros métodos como SHA-1 (RFC 3174) o RIPEMD-160.

Hace unos cuantos posts comenté la necesidad de guardar en la base de datos la clave del usuario codificada utilizando algún sistema de encriptación. Para romper un poco la monotonía de tanta teoría acerca del diseño de estas últimas semanas decidí intentar escribir mi propia clase para realizar la encriptación. No obstante, habida cuenta de que mi única experiencia práctica previa al respecto había sido el uso de la función MD5 que implementa PHP, casi me decantaba a priori por utilizar alguna librería gratuita disponible en C++, el lenguaje con el que voy a trabajar. Sin embargo, buscando información por Internet me he llevado la grata sorpresa de comprobar que los sistemas más populares de encriptación en realidad se basan en algoritmos que resultan sencillos de implementar.

El algoritmo del MD5 (Message-Digest algorithm 5) por ejemplo, descrito en el RFC 1321, consiste en la ejecución de cinco simples pasos. Admite como entrada un bloque de información a codificar de cualquier longitud dada, y devuelve un código hash de 128 bits (16 bytes) que normalmente suele representarse en hexadecimal como una cadena de texto legible de 32 bytes. Su uso más común, además de la codificación de claves de usuario, ha sido tradicionalmente la firma de aplicaciones, es decir, proporcionar un código único (el hash) que garantice que un fichero es realmente el fichero que dice ser. Desgraciadamente este último uso ha dejado de ser práctico hoy en día, ya que existen métodos que añadiendo bytes extras a un archivo cualquiera consiguen que genere un código hash concreto. Al parecer el algoritmo es susceptible a las colisiones y han conseguido sacar partido de esa debilidad. No obstante, aún sigue siendo una alternativa válida para la codificación de claves.

Los cinco pasos del algoritmo son los siguientes:

1) Añadir bits de relleno al bloque de información a codificar. Con este paso se busca hacer la longitud del bloque en bits (no bytes) congruente con 448 módulo 512. Es decir, que le falten 64 bits para ser múltiplo exacto de 512 bits (448 = 512 – 64). Esto debe hacerse siempre, incluso aunque la longitud inicial ya cumpla esta condición. Para extender el bloque se añadirá primero un bit a 1, y luego el resto a 0 hasta completar el tamaño que sea necesario.

Pensando en bytes, que es como normalmente se trabaja, lo que pide este paso es que el tamaño del bloque sea congruente con 56 módulo 64. Es decir, que le falten 8 bytes para ser múltiplo entero de 64 bytes.

El hecho de que este paso tenga que aplicarse siempre es lo que hace que incluso las cadenas vacías tengan un hash.

2) Añadir la longitud del bloque de información a codificar al propio bloque de información. En este paso lo que se hace es añadir la longitud inicial del bloque en bits (no bytes) al final del resultado del paso anterior. La longitud se agrega en formato little-endian (primero los bytes menos significativos) con un tamaño máximo de 8 bytes. Si la longitud ocupa más de 8 bytes entonces los más significativos simplemente se pierden sin que ello suponga ningún problema para el algoritmo.

En este paso, al añadir los 8 bytes que se reservaron en el paso anterior, se consigue que el bloque sea múltiplo entero de 64 bytes.

3) Inicializar las variables intermedias de trabajo. Para el cálculo del hash se utilizan cuatro variables intermedias enteras de 32 bits denotadas como A, B, C y D. Cada una de ellas toma un valor inicial constante predefinido:

4) Procesar la información en bloques de 16 enteros de 32 bits. A resultas de los dos primeros pasos, el bloque de información acaba teniendo una longitud que es un múltiplo entero de 512 bits (64 bytes), por lo que se puede trabajar con él tomando bloques de 16 palabras enteras sin signo de 32 bits (4 bytes) cada una (4 * 16 = 64).

En este punto el algoritmo define cuatro funciones denotadas como F, G, H e I, que admiten tres enteros sin signo de 32 bits y generan otro entero sin signo de 32 bits:

El propósito de estas funciones es extraer las características diferenciales del bloque de información, operando a nivel de bit, con el objetivo de generar el hash que lo identifique de forma unívoca. El propósito concreto de cada una, así como la base matemática en la que se sustenta todo el proceso queda fuera de mi comprensión.

Las funciones se aplican dentro de un bucle en el que se van leyendo enteros sin signo de 32 bits del bloque, en tandas de 16 en 16, con el propósito de generar unos nuevos valores que se irán sumando a las variables A, B, C y D. Para preservar el valor original de las variables se guardan en una variables auxiliares al principio de cada iteración:

Llegado este punto el algoritmo presenta cierta dificultad por la forma en que está descrito, agravado por el hecho de que el propio RFC contiene una errata (hay una "t" en lugar de una "i" en un par de líneas). Después de leerlo un par de veces, se entiende que hay que realizar 64 operaciones dentro del bucle en cada iteración. Aplicando la función F en las 16 primeras operaciones, la G en las 16 segundas, la H en las terceras, y la I en las cuartas.

En el documento se utiliza una tupla en la forma [abcd k s i] para señalar las 16 operaciones a realizar con cada función (de izquierda a derecha, y de arriba hacia abajo):

La forma en la que ha de interpretarse las tuplas es la siguiente:

Para las primeras 16 operaciones FUNCTION sería F, para las 16 segundas G, y así sucesivamente. BUFFER[k] es simplemente el elemento k-ésimo dentro del bloque de 16 enteros sin signo que se esté procesando en ese momento dentro del bucle. SIN[i] es el valor absoluto de la parte entera del seno (la conocida función trigonométrica) de i (en radianes) multiplicado por 4.294.967.296 (2 elevado a 32). Este término mosquea un poco al principio, pero puede encontrarse los valores precalculados en un apéndice del propio RFC, que incluye un implementación completa en C. Por último, "<<<" es una rotación circular hacia la izquierda (lo que sale por la izquierda vuelve a entrar por la derecha) de tantos bits como indique "s".

Es decir, expandiendo las tuplas se obtiene:

Finalmente se suman los valores obtenidos con los previos salvaguardados y se procede con la siguiente iteración:

5) Componer el resultado final. El código hash resultante es la concatenación de A, B, C y D, empezando con el byte menos significativo de A y terminando con el más significativo de D.

yEns me ha mandado hoy un correo pidiendo algo de promoción para plusdeporte, su nuevo proyecto web. Una página de promoción de noticias deportivas que sigue el estilo marcado por el conocido digg, popularizado al castellano por menéame, y que ha servido de referencia para muchos portales especializados como puede ser el caso de pixélame. Webs colaborativas 2.0.

El aspecto de la página es muy claro, directo, y con una combinación de colores que a mi particularmente me gusta bastante. Cada tipo de elemento (título, texto, enlace, ...) es facilmente distinguible y sigue la tónica habitual de este tipo de webs, por lo que es muy fácil manejarse rápidamente por ella. No aporta nada nuevo al género, pero su finalidad la cumple con creces, aunque me gustaría algo más de feedback por parte de la página al votar una noticia.

Técnicamente, mirando el código HTML de la página, e invocando el validador, veo que canta una etiqueta que no está cerrada, pero no supone mayor problema. Todo está montado a base de CSS, incluyendo un bonito recordatorio de que "IE is out there". Para el JavaScript veo que han utilizado jQuery con esa forma suya tan particular de encadenar comandos.

En su divertido FAQ, donde entre cosas nos cuentan que en realidad lo que pretendían con la web era dominar el mundo pero que Google se les ha adelantado, he encontrado una url a un mini-blog de seguimiento del desarrollo de la propia página. Después me he dado cuenta de que existe un enlace directo en el menú principal, ¿pero quién se fija en esas cosas hoy en día?

Adrián me comenta en su correo que ha hecho la web partiendo de cero, con ayuda de Iván Guardado, utilizando PHP y MySQL. Teniendo en cuenta lo cuidado del aspecto y la fluidez con la que se mueve el conjunto sólo resta felicitarlos por el trabajo realizado.

¡Buena suerte chicos!

Hace tres meses ya de mi último juego, así que va siendo hora de que me ponga manos a la obra con el siguiente. Esta vez me gustaría pasar más tiempo trabajando el apartado gráfico. Algo complicado, ya que normalmente mis objetivos/preferencias son de carácter técnico y no artístico.

Tenía pensado hacer algo de tipo "tuberías", como los populares "Candy Train" (no encuentro el link, supongo que ya lo habrán descatalogado) o Rocket Mania de PopCap. Siempre me ha gustado la simplicidad, en lo referente a su jugabilidad, de esos dos programas. Acerca del primero de ellos, recuerdo que es una idea que incluso a mi se me ocurrió una día que viajaba en tren. Cuando llegué a casa busqué por Internet para ver si existía algo parecido. Después de seguir un par de enlaces pude comprobar que no era precisamente el colmo de la originalidad lo que se me había ocurrido.

Para mi juego, tengo apuntadas varias ambientaciones distintas sobre las que poder trabajar. La primera es bastante obvia, la he llamado "One Way!", y consistiría en construir una carretera por la que circule un coche. E incluso mejor, un taxis, e incluso un autobús, ya que entonces se podría jugar (nunca mejor dicho) con conceptos como "parada" o "viajero" para establecer objetivos fáciles de identificar por los jugadores. Las señales de tráfico o los semáforos también podrían estar bien, sobre todo porque son señalizaciones con un significado conocido por todos y que no requerirían mayor explicación. La mayor dificultad para mi reside en el dibujado de un vehículo desde una perspectiva aérea, sobre todo con diversos ángulos de giro.

Otra alternativa que se me ocurrió, a la que llamo "Jungle Path", consistiría en sustituir la carretera por una especie de liana, y el autobús por un mono que se moviera por ella. Los objetivos serían probablemente la recolección de comida, algún de tipo de fruta, y evitar a otros animales salvajes. Naturalmente con este diseño se me plantea el mismo problema que antes, ya que la creación de los gráficos se me hace aún más complicada que con la opción anterior. Para simplificar creo que me bastaría con algún tipo de representación simbólica, como una especie de token con las cabezas de los animales por ejemplo.

El tercer diseño, por nombre "Cheese Maze", utilizaría un laberinto clásico como escenario, con ratones blancos a modo de cobayas como protagonistas y trozos de queso como objetivos. Curiosamente, aunque no acabo de concretarla, esta es la única opción para la que me he atrevido a hacer algo. Por una parte el laberinto, generado aleatoriamente, que se puede ver en la primera imagen de este post, tal y cual lo dibuja el prototipo actualmente. Teniendo en cuenta que está hecho en JavaScript no me puedo quejar del resultado, sobre todo por la continuidad de las paredas y las sombras, aunque hay mucho que pulir todavía. También he intentado dibujar un ratón, segunda imagen de este post, aunque el resultado no acaba de convencerme.

Tengo algunas otras ideas sobre el asunto, pero es bastante probable que opte por una solución mucho más sencilla y acabe utilizando unas simples tuberías o mangueras para hacer pasar agua de un lado a otro del tablero, desde un grifo hasta una boca de riego o algo parecido. No me siento muy positivo hoy, creo que esto va ir para largo.

Trabajar todos estos gráficos píxel a píxel suele llevarme mucho tiempo, y no pocos ajustes, hasta llegar a obtener un resultado que acabe de gustarme. El proceso que sigo es bastante básico y es el que siempre sugieren todos los tutoriales. Primero busco imágenes de referencia, después dibujo el contorno con las formas básicas (line-art), a continuación escojo la paleta de colores, los aplico prestando atención a la posición de las luces, y por último remato los detalles. Suena sencillo, pero me cuesta un mundo, será cuestión de practicar más a menudo. A escala tan pequeña todos y cada uno de los pixeles individualmente cuentan por si solos una barbaridad. Un simple píxel fuera de su sitio puede estropear el suave curso que se supone debería seguir una línea de contorno, por no mencionar como un simple cambio de tonalidad puede suponer el éxito o fracaso de un gráfico. Siempre he pensado que para apreciar mejor estas pequeñas obras de arte hay que ampliarlas de tamaño, para ver detalles que con sus dimensiones normales lucen fantásticas, y comprobar que se han resuelto con tan solo cuatro o cinco pixeles de distinto color. Hay mucho material increíble que puede encontrarse por Internet. Y es que parece que la masificación en el uso de dispositivos móviles ha hecho resurgir este noble arte del píxel-art que parecía destinado a quedar relegado a un segundo plano por el hoy omnipresente 3D.

Este post podría llevar perfectamente por título "Listas de valores, y otras alternativas", pero creo que el que le he puesto es más divertido. Incluso habrá hecho que alguno lea hasta aquí.

Es algo bastante común que a la hora de crear un personaje se pueda elegir el sexo del mismo, pudiendo seleccionar normalmente entre hombre y mujer. Una elección sencilla. Sin embargo, para almacenar ese valor en una base de datos existen muchas posibles alternativas que merecen la pena ser estudiadas.

En un diseño relacional tradicional, siguiendo el libro al pie de la letra, crearíamos una tabla de sexos y una relación (foreign key) con la tabla de personajes. Esta elección, que parece de lo más natural, en realidad pocas veces es la escogida. Aunque este es uno de los pilares básicos sobre los que se apoyan las base de datos relacionales, la normalización, raramente acaba de asimilarse para conceptos tan sencillos como el "sexo", en el que sólo se puede elegir entre dos valores posibles prefijados de antemano.

Una alternativa bastante común a la creación de una nueva tabla es utilizar una columna de tipo texto, en la propia tabla de personajes en este caso, que almacene un carácter para distinguir entre "hombre" y "mujer". En castellano podría ser "H" y "M", por ejemplo, aunque más de uno podría distinguir la "H" como inicial de "hembra" (algo políticamente incorrecto, al parecer). De igual forma que una persona de habla inglesa podría asumir que la "M" es una abreviatura de "male", sobre todo recordando el hecho de que yo estoy utilizando nombres en inglés para las tablas y columnas. Pero esta elección no sólo plantea el problema de elegir que letras utilizar, sino que obliga a que la decisión que se tome esté bien documentada. Por que, ¿qué ocurre cuando la tabla está vacía?, ¿sabría alguien ajeno al proceso de diseño decir qué valores debería contener esa columna? No.

Para evitar las confusiones que plantea la solución anterior, puede escogerse un enfoque algo distinto basándose en el hecho que sólo hay dos posibles valores donde elegir, tomándose el tipo de la columna como "Boolean". De esta forma, una columna de nombre "IS_MALE" eliminaría toda ambigüedad. Desgraciadamente "Boolean" no es un tipo estándar y no debería utilizarse aunque se encuentre soportado. A modo de anécdota, comentar que a veces se toma un camino intermedio entre esta solución y la anterior, definiendo una columna "IS_MALE" de tipo texto que puede tomar el valor "T" o "F", o sea, "true" o "false". El mismo perro con distinto collar.

Algunos gestores de base de datos permiten definir reglas de validación (check constraints) sobre los valores que puede contener una columna concreta, de forma que sólo pueda almacenarse en ella valores que se encuentren dentro de un rango dado. De esta forma, cualquier intento de insertar o actualizar un registro con un valor fuera de dicho rango hace que el gestor retorne un error. Esto presenta la ventaja además de que el modelo queda auto-documentado al formar parte, la propia validación, de la definición de la tabla. El inconveniente es que no todos los gestores soportan este tipo de validaciones. Algunos, como MySQL, simplemente las parsean correctamente, pero no fuerzan su cumplimiento, y sugieren métodos alternativos como tipos "enumerados" (enums).

Otro tema que se plantea a la hora de utilizar una solución u otra es la ocupación, el tamaño de almacenamiento requerido para la columna, ya sea en memoria o disco. Si se utiliza una tabla propia con una foreign key entonces hay sumar 4 bytes por personaje. Para un juego con cien cuentas registradas, con 4 personajes por cuenta, no debería suponer mayor problema con los estándares de almacenamiento actuales. E incluso para un millón de cuentas la cifra sigue siendo ridícula, sobre todo porque nunca se instanciarán todos los jugadores a un mismo tiempo en un mismo servidor. No obstante, si se detecta que la ocupación es un factor crítico, entonces se puede disminuir a 1 byte por registro utilizando la solución de la columna de texto. E incluso más, se puede reducir a 1 bit por registro almacenando el sexo del personaje en una columna cuyo contenido se trate como un colección de flags, en donde cada bit, o conjunto de ellos, tenga un significado concreto.

A mi particularmente me parece que empezar diseñando un modelo relacional con flags es un claro ejemplo de "optimización temprana". Hay mucha gente que tiene una especie de fijación en la cantidad de bits desaprovechados a priori. Está bien pensar en ello, conocer al enemigo, pero siempre con una perspectiva del contexto y del dominio. Si las pruebas de volumen aconsejan optimizar la ocupación de la información, entonces se deberían plantear otra clase de alternativas, como por ejemplo tener dos tipos distintos para las claves primarias. Un tipo estándar de 4 bytes para las tablas con un gran número de registros, y otro tipo con menos requerimientos de ocupación, incluso de 1 byte, para las tablas con un número pequeño de registros. Lo que no se puede hacer de partida es renunciar a diseñar un modelo normalizado.

Para evitar divagar en exceso, hace unos cuantos posts atrás comenté la necesidad que tenía de basarme en una temática concreta para hacer el modelo, en vez de intentar hacer algo demasiado genérico. Yo elegí un juego ambientado en el salvaje oeste, y más concretamente con referencias a la nación india. En este caso sólo se podría elegir entre hombre y mujer a la hora de crear personajes. Se crearía una tabla de sexos, con dos registros, y cada personaje apuntaría al registro adecuado. Lo curioso es que la idea de crear una tabla para contener sólo dos registros estáticos es algo que parece molestar a mucha gente. Lo que hay que ver es las posibilidades que ofrece, sobre todo porque los requerimientos siempre cambian. Por ejemplo, puede decidirse que las características intrínsecas de cada personaje, como su fuerza inicial, vengan determinadas por su sexo, lo que se solventaría añadiendo atributos a la nueva tabla de una forma bastante natural. O puede decidirse que algunos tipos de clases (razas) tengan otro género (hermafrodita), o carecer completamente de él (asexuado), lo que se solventaría simplemente incluyendo nuevos registros en la tabla.

Aún así, hay bastantes expertos que recomiendan juntar todas las tablas con escasos registros y atributos comunes en una única tabla "listas de valores", con un ID, un tipo, y una descripción, aunque representen conceptos distintos. El problema surge en el momento que es necesario añadir un atributo específico para un concepto concreto, momento en que se rompe el esquema, y es necesario crear una tabla nueva para esa lista concreta que necesita dicho atributo y cambiar todas las referencias que pudieran existir. Tarea que normalmente es bastante tediosa de realizar cuando el sistema se encuentra ya en producción, y que puede llegar a suponer tener que realizar una parada del mismo.