inmensia

La personalización de los avatares por parte de los propios jugadores es algo que casi todo el mundo da por hecho hoy en día. Prácticamente se podría decir que es una obligación, no una opción. Tener la posibilidad de definir atributos concretos para los personajes permite que los jugadores se identifiquen más con ellos, creando cierto sentido de propiedad o identidad, al tiempo que permite disfrutar de un mismo juego desde puntos de vista distintos alargando la vida útil del mismo.

Las opciones más habituales incluyen la selección de raza, sexo, clase, o de todos ellos, según sea el caso. Esta selección inicial suele determinar tanto el aspecto físico del personaje como las características básicas del mismo referidas a atributos clásicos como fortaleza o agilidad. En el recientemente aparecido Age of Conan – Hyborian Adventures las opciones de creación de personaje permiten incluso definir la apariencia y complexión física de los personajes. Es decir, no sólo se puede elegir el color de piel o la forma del pelo, sino que se puede personalizar el tamaño de algunas partes del cuerpo, como el pecho por ejemplo. Naturalmente todo ello dentro de ciertos límites, no tendría ningún sentido que se pudiera crear un personaje con el pelo de color fucsia en un juego de ambientación medieval, rompería por completo la experiencia de juego. Algo radicalmente distinto a lo que ocurre en Second Life por ejemplo, donde la personalización "extrema" es parte importante de su éxito.

La creación de un personaje de tal o cual tipo a veces conlleva tener que seguir un guión distinto durante el juego, la historia en la que se ve uno inmerso es distinta, pero sobre todo es bastante habitual que implique la adopción de unas características iniciales comunes a todos los personajes de ese tipo, normalmente mejorables a medida que se juega y se van alcanzando una serie de hitos intermedios. No obstante, eso es motivo de queja de algunos jugadores más veteranos que suelen comentar que preferirían poder configurar el detalle de estos valores por si mismos para adaptarlos así mejor a su particular forma de jugar.

Los atributos comunes a todos los personajes pueden perfectamente incluirse como columnas dentro de la tabla de personajes. Evidentemente su número y significado variarán en función del diseño del juego, aunque parece lógico prever que normalmente serán foreign keys a otras tablas para los casos de raza, sexo o clase por ejemplo, mientras que para las características físicas como el color de piel, altura, fortaleza o agilidad es probable que acaben siendo columnas de tipo numérico. Para otro tipo de atributos puede ser más complicado tomar una decisión. La cuestión es decidir si los atributos propios de cada clase, que no se comparten con el resto de clases, deben incluirse como columnas en la propia tabla de personajes, o deben almacenarse en una tabla aparte. O sea, decidir como se modelan las relaciones de "generalización", también conocidas como "herencia".

Supongamos que decidimos que las habilidades de los personajes estén representadas por un tótem que contenga distintos aspecto de su "espíritu", de forma que un guerrero sea un representante del espíritu del oso, del águila, o de cualquier otro tipo de animal característico. De igual forma, supongamos que un hechicero sea un representante del espíritu de la luz, de las sombras, y así sucesivamente. A la hora de almacenar estos atributos en base de datos se puede ampliar la tabla de personajes añadiendo columnas para irles dando cabida a todos ellos. El problema de esta solución es que la mayoría de las columnas nunca tendrán valor, o como mucho un valor numérico de cero, ya que no aplican a todas las clases, sólo a las específicas dentro de las cuales tienen sentido.

El criterio general normalmente aceptado para estos casos, aunque en continua discusión, es evitar tener que almacenar valores nulos en base de datos en la medida de lo posible. Así, si un atributo aplica para una clase, pero no para otra, lo aconsejado es crear una nueva tabla de especialización con esos atributos específicos, aunque sin llegar a crear una tabla específica para cada clase, sobre todo cuando el número de estas es elevado, porque en ese caso se corre el riesgo de acabar teniendo un diseño muy poco flexible que requiera escribir código a medida para la gestión de cada una de ellas.

Otra posibilidad interesante, a medio camino entre las dos anteriores, para evitar crear columnas o tablas en exceso, es tener columnas genéricas cuyo contenido deba interpretarse en función del contexto. Es decir, crear columnas con nombres poco definidos tales como SPIRIT_1, SPIRIT_2, ... e interpretar los valores que contienen como "espíritu del oso" o "espíritu de la luz" en función de si la clase del personaje es la de guerrero o la de hechicero. El inconveniente es que viendo el modelo, sin ninguna información adicional, no se puede saber a priori que significado concreto tiene cada campo, amén de que limita físicamente el número de atributos que se pueden tener a priori.

Este tipo de discusiones sobre alternativas de diseño suelen ser bastantes frecuentes, y por desgracia no hay una solución definitiva. En un modelo lógico se identificaría claramente una entidad "Personaje" y especializaciones de ella como "Guerrero" o "Hechicero". Y probablemente todo el mundo estaría de acuerdo. Pero con el modelo físico ya sería otro cantar. Sobre todo porque es cuando entran en consideración los aspectos más espinosos del asunto inlcuyendo ocupación, rendimiento, escalabilidad, dificultad y costes.

La solución definitiva podría ser el uso de una ODBMS (Object Database Management System), o sea, una base de datos orientada a objetos. Pero como no es el caso de los gestores que utilizo, aunque si haya cierto conato por su parte de implementar herencia, he decidido utilizar una solución intermedia.

En el modelo se pueden ver varias tablas. La primera para los personajes, que contendría los atributos comunes para todos ellos, como su nombre o una referencia a su sexo. La segunda para los tipos de atributos asociables a personajes, como "espíritu del oso" o "espíritu de la luz", que normalmente tendría algunas columnas, que he omitido deliberadamente en la imagen, con su nombre y descripción, o mejor aún, con referencias a la tabla de textos por idioma. Y la tercera para las relaciones entre las dos anteriores y el valor concreto de cada tipo de atributo por personaje.

La primera limitación obvia de este modelo es que estoy suponiendo que todos los atributos han de tener un valor de tipo numérico, lo cual es verdad para mi caso concreto. De igual forma, otra limitación del modelo es que un tipo de atributo sólo puede tener un único valor asociado, lo cual es nuevamente verdad para mi caso concreto. Y evidentemente, los requerimientos de almacenamiento también son más elevados que con algunas de las soluciones propuestas anteriormente, ya que esta requiere guardar la clave primaria de la tabla intermedia de valores, que además resulta estar compuesta por dos campos.

En el aspecto positivo, debe ser claro que este modelo permite añadir cualquier tipo de atributo sin necesidad de introducir cambios en el mismo. Es más, con el uso de tablas intermedias como la que he puesto entre personajes y tipos de atributos, es posible asociar los tipos a objetos, misiones, o cualquier otro tipo de entidad que se quiera. De hecho, en función de la implementación que se realice, ni siquiera haría modificar el software para se tuviera en cuenta automáticamente.

En cuanto a la operativa de uso de la tabla intermedia, es claro que las inserciones sólo deberían realizarse una única vez, durante el proceso de creación del personaje, y puede que ocasionalmente si adquiere una nueva habilidad. Las actualizaciones irán por clave primaria, al igual que las consultas. Los borrados es bastante raro que se produzcan, ya que implicarían la eliminación del personaje de la base de datos, aunque bajo algunas circunstancias se podría permitir el cambio de unas habilidades por otras.

Para terminar, comentar que toda esta problemática se debería aislar en la medida de lo posible del resto del software mediante una buena capa de abstracción. Es decir, probablemente un desarrollador al final sólo quiera poder disponer de un método que retorne el color de ojos de un personaje ( getEyeColor() ), independientemente de cómo se encuentre almacenado este físicamente en base de datos.

Una de las cosas que más me llamó la atención cuando estuve buscando información acerca de cómo se organizaban en la práctica algunos MMORPG comerciales fue el hecho de que muchos desarrolladores hacían mención a procedimientos y funciones escritas en (algún tipo de) PL/SQL. A priori no vi ningún sentido en utilizarlos, ya que normalmente el conjunto de operaciones a realizar contra base de datos se limita a la ejecución de unas pocas sentencias SQL en transacciones de muy corta duración. A saber, insertar un objeto en el inventario, actualizar algún tipo de contador de vida, y así sucesivamente. Sentencias pequeñas que afectan a un registro, o a una cantidad muy pequeña de ellos, donde ni siquiera es de esperar que haya grandes consultas, ya que normalmente las tablas maestras se encontrarán en memoria, en algún tipo de cache, y se accederá por su correspondiente ID, o puntero, dependiendo de la implementación concreta de la capa de persistencia. Incluso algunas consultas, como la búsqueda de personajes cercanos al del jugador, tendrán que resolverse manteniendo en memoria diversos tipos de jerarquías con criterios distintos para poder recorrerlas según interese en cada caso. Además de que normalmente las consultas no son precisamente lo que motiva la creación de procedimientos o funciones PL/SQL.

A fin de encontrar cierta justificación a la necesidad del uso masivo de PL/SQL comencé a buscar los beneficios que pudieran desprenderse de su uso, como si fuera yo el que tuviera que justificar su uso y sus posibles contrapartidas.

Por ejemplo, un motivo práctico de primer orden por el que veo útil la utilización de PL/SQL es la reducción del número de accesos y volumen de información intercambiada entre el cliente y el gestor de base de datos. En operaciones muy habituales, como despojar de un objeto a un enemigo vencido (looting), es mejor realizar una única llamada a un procedimiento PL/SQL pasándole tres parámetros como argumento (un ID del personaje, un ID del enemigo y un ID del objeto) que realizar varias llamadas para la ejecución de varias sentencias en SQL (eliminar objeto del inventario del enemigo, insertar objeto en el inventario del personaje, fin de transacción), obviando las comprobaciones previas (comprobar que el enemigo está muerto, comprobar que el personaje tiene derecho a robar el objeto, comprobar que el enemigo tiene el objeto). Muchas veces no es la ejecución de las sentencias SQL individuales lo que más tiempo demora, sino el número total de sentencias que se tienen que ejecutar cada vez. Una actualización que tarde muy poco tiempo puede estar bien dentro de un determinado contexto, pero si ha de ejecutarse mil veces seguidas entonces puede que ya no lo sea. El tiempo que se tarda en establecer conexión con el servidor de base de datos, en autentificar dicha conexión, y en validar la sentencia a ejecutar, es un tiempo que nunca debería despreciarse alegremente. Hay que lograr que con un única conexión con el servidor se actualicen mil registros, en vez de tener que actualizarlos uno a uno con mil llamadas. En este sentido un procedimiento PL/SQL puede ser de gran ayuda. Aunque sin perder de vista otras opciones que ofrezca el gestor, como bulk arrays, que son actualizaciones masivas, generalmente disponibles a través de algún mecanismo propietario, u optimizaciones, como las caches de últimas sentencias SQL ejecutadas, sobre las que no es necesario volver a aplicar el proceso de parser, algo que normalmente va también implícito en el uso de funciones y procedimientos almacenados.

El uso de PL/SQL también tiene la ventaja de encapsular en el servidor todos los accesos a base de datos, evitando tener que embeber sentencias SQL en el resto del código fuente, aunque esto en realidad dependerá bastante de cómo se monte la capa de abstracción correspondiente. Lo que está claro es que todas las aplicaciones clientes podrán usar ese mismo código, evitando tener que repetirlo en cada programa y distribuirlo en librerías que tengan que mantenerse actualizadas. Además, manteniendo todo el código en la parte del servidor se consigue aislar los detalles específicos del funcionamiento de un determinado gestor, de forma que las posibles migraciones que se quieran realizar una vez iniciado el desarrollo, e incluso con el software en producción, sean menos traumáticas. Naturalmente esta última frase no deja de ser una utopía hoy en día. No hay más que echar un vistazo a la documentación de las distintas bases de datos para darse cuenta que cada cual implementa el lenguaje, e incluso varios de ellos, según sus propias reglas, normalmente incompatibles entre los distintos fabricantes. Más allá de la nomenclatura, o sintaxis de declaración, hay muchos detalles que normalmente obligan a programar de una forma u otra el código según el gestor concreto que se esté utilizando. En MySQL el soporte de esta característica es limitado, y en PostgreSQL tiene algunas particularidades como la gestión de excepciones que fuerzan un ROLLBACK.

La ejecución de procedimientos y funciones, al realizarse en el servidor, proporcionan un extra de seguridad. Con una gestión de permisos adecuada, se puede hacer que todos los accesos al modelo por parte de los clientes se realice de forma exclusiva a través de procedimientos y funciones PL/SQL, evitando que tengan acceso directo a las tablas y a como se encuentran definidas y organizadas estas. Es decir, el concepto de "interface" llevado al modelo de base de datos relacional. "Capas de abstracción" (modelo cebolla) es un término que nos encanta utilizar a los informáticos. Naturalmente la contrapartida de este planteamiento es que el servidor de base de datos deberá hacer más trabajo del que ya normalmente le toca, al trasladarle las reglas de negocio que residen habitualmente en el código de los clientes. Por no mencionar el hecho que hacer grandes desarrollos en la parte servidora puede resultar bastante costoso si el gestor no proporciona las facilidades necesarias para la activación de trazas o realizar labores de depuración online.

Llegado este punto, creo que debería estar claro cuales son las ventajas e inconvenientes más importantes del uso de PL/SQL. Y lo mejor que se puede decir a modo de resumen es que no hay un factor decisivo que decante la balanza de forma clara en cuanto a la necesidad de su uso o no. Creo que la única solución será probar ambas alternativas, o una mezcla de ambas, a fin de determinar si el gestor que estemos utilizando marca una diferencia clara, sin dejar de recordar que las características o rendimiento que ofrezca una base de datos podemos no encontrarla en otra.

Probar, medir, y decidir.

Un español, un francés y un inglés están jugando a un MMORPG cuando ... Lo que parece el comienzo de un buen chiste deja de serlo cuando nos damos cuenta que cada uno de ello habla un idioma distinto, y que nuestro modelo de datos ha de soportar esta pluralidad de lenguas.

El primer paso para abordar esta tarea sería distinguir claramente entre los textos que se distribuirán con la parte cliente, como los asociados a los controles de la interface de usuario por ejemplo, y los que se encontrarán en la parte servidora, como los nombres y descripciones de las misiones, e incluso los que se utilizarán para la habitual web de creación y mantenimiento de cuentas, aunque esto último es harina de otro costal. La idea es que cada jugador pueda leer en su idioma preferido toda la información que se le muestre en su monitor, al tiempo que interactúa con jugadores que la leen en otros idiomas en una especie de traducción simultánea.

Los textos de la parte cliente tradicionalmente se distribuyen junto con los ejecutables que arrancan los jugadores, normalmente en ficheros de recursos con tablas de cadenas de texto identificadas por un ID. En el código fuente, en los scripts, o en los ficheros descriptores de las interfaces, se hacen referencia a esos IDs evitando tener que escribir directamente cualquier tipo de texto estático dentro del programa. Se puede pensar en los ficheros de recursos como en pequeñas base de datos de una tabla por idioma almacenadas en disco local. La selección de un fichero u otro, es decir, de idioma, se realiza habitualmente durante la fase de instalación o a través de una opción de configuración. A veces simplemente los clientes se descargan una versión personalizada para un país concreto sin posibilidad de cambio. Otra veces el propio programa detecta el idioma seleccionado en la configuración local del ordenador y arranca con ese por defecto si está disponible, en caso contrario se fuerza otro predefinido por defecto, o se da la opción de elegir.

El hecho de utilizar ficheros de recursos para la parte cliente debería implicar inmediatamente que todos los textos de la interface de usuario se extraigan de ellos. Lo que no debería ocurrir, o habría que evitar en la medida de lo posible, es que además de textos haya que cambiar gráficos. Un ejemplo típico de esta situación es una ventana intermedia de carga de nivel en la que se haya escrito "Loading" con un bonito juego de caracteres gráficos enlazados dentro de otra imagen. Horror. De igual forma, habría que evitar incrustar textos dentro de las texturas del mundo en que se desarrolle el juego, salvo cuando el contexto lo permita, e incluso lo fomente. Por ejemplo, en una ciudad rusa todo el mundo espera encontrar rótulos, anuncios y señalizaciones en cirílico, es el tipo de detalle que crea ambientación. Pero otra cosa muy distinta es hacer que el avance del juego dependa de la comprensión de esos textos, lo que puede llegar a ser muy frustrante. En algunas ocasiones, cuando no hay más remedio por exigencias del guión, se puede recurrir a decals (calcomanías) para mostrar la información de forma gráfica en el idioma adecuado.

Los textos de la parte servidora pueden ir perfectamente en la base de datos, aunque al ser información de carácter fundamentalmente estático, es probable que se recuperen al arrancar el servidor y se almacenen en algún tipo de cache, algo que intuitivamente se puede pensar también en hacer en la parte cliente, aunque probablemente limitándose al área o zona actual en juego.

El enfoque tradicional para almacenar textos en base de datos es añadir columnas a las tablas que lo necesiten. Por ejemplo, la tabla de misiones puede tener una columna llamada "title", otra "short_description", otra "long_description", ... y así sucesivamente. El problema de este enfoque es que sólo permite tener textos en un determinado idioma a un mismo tiempo. Es decir, si se escriben en inglés, todos los jugadores los verán en inglés. Si se dispone de varios servidores, entonces se pueden cargar los textos en un idioma distinto para cada uno de ellos, permitiendo que los jugadores se conecten a uno u otro según sus preferencias, a costa de una redundancia de información que puede dificultar el mantenimiento de la integridad. Una aberración de este método es añadir tantas columnas como idiomas queramos soportar a cada tabla. Es decir, "title_en", "title_es", "title_fr", ... y extraer el texto de la columna adecuada en función del idioma. He visto desarrollos del modelo físico así, y por razones que deberían ser obvias a estas alturas no lo aconsejo en absoluto.

Un enfoque más acorde a los buenos principios de diseño nos aconsejaría crear una tabla de idiomas, una tabla de textos, una tabla de textos por idioma, y crear foreign keys desde las tablas que lo necesiten.

Este modelo presenta algunas particularidades que deberían captar enseguida nuestra atención, como la ausencia de atributos en la tabla de textos, o las relaciones uno-a-uno con la tabla "quest" (misiones) que he puesto a modo de ejemplo de uso. El hecho de que carezca de atributos es algo circunstancial, en la práctica es probable que se quieran añadir algunas columnas adicionales para indicar el contexto en que se utiliza cada cadena de texto, o algún otro tipo de información necesaria para complementarla de forma dinámica. Más adelante en este mismo post hablaré acerca de esto último. Por su parte, las relaciones uno-a-uno nos indican que un mismo texto sólo se utilizará para una única cosa concreta. Es decir, un texto sólo podrá ser el título de una misión, pero no el nombre de un objeto, por mucho que se llamen igual. Esto ha de hacerse así para reforzar la idea de que cada registro es una entidad distinta, aunque representen cadenas de texto cuyo contenido sea el mismo. Por ejemplo, la palabra "salida" en español debe traducirse al inglés como "exit" o como "out" según el contexto en que se encuentre, por lo que no podemos presuponer a priori que todas las cadenas con un mismo contenido vayan a tener una misma traducción.

Otra solución además de la propuesta podría pasar por crear tantas tablas como idiomas soportemos, pero esto no es más que una ampliación de la solución que se planteaba anteriormente de crear una columna por idioma en cada tabla. En la práctica podría ser útil con una gestión de usuarios adecuada y la creación de sinónimos (alias), pero esto último es algo que desgraciadamente no soportan todos los gestores de base de datos, incluidos MySQL y PostgreSQL. La idea es que se crean tantos usuarios como idiomas haya, y para cada uno de ellos se crea un sinónimo privado, con el mismo nombre para todos ellos, pero que apunte a una tabla distinta en cada caso, de forma que todos creen estar viendo una misma tabla cuando en realidad cada uno de ellos hace referencia a una distinta. El problema que plantea esta solución es que impide la creación de foreign keys, y es algo que se puede conseguir también con tablas privadas por usuario, o vistas normales, a costa quizás de una pérdida de rendimiento, o con vistas materializadas, si el gestor las soporta. Si el único motivo que justifica la utilización de este tipo de soluciones es el volumen de registros de la tabla de textos entonces se debe optar mejor por su particionado, algo para lo que la columna "id_language" parece ser una buena candidata.

Un esquema más complejo, a medio camino entre el almacenamiento de los textos en el servidor o en el cliente, pasaría por hacer que el cliente almacenase las cadenas de forma local, y que el servidor le enviara los IDs correspondientes en cada caso, en vez de los textos completos. Naturalmente esto implicaría que el cliente tendría que actualizarse periódicamente, con los textos nuevos o modificados en base de datos, así como cuando el servidor le enviara un ID que no pudiera resolver localmente.

Por su parte, hay otro tipo de textos, que no están incluidos dentro de la parte cliente o servidora de forma estática, y que son los generados por los jugadores a través de los populares chats. Quizás representen el caso más sencillo, ya que todo lo que se escribe normalmente se digiere tal cual. Aunque en algunos casos hay filtros de palabras según la política concreta de uso del software de cada empresa. Incluso en ocasiones se establece el uso de un único idioma oficial, ya sea de forma global o por servidor.

Para finalizar, comentar que cuando se trabaja con textos en varios idiomas, o generados de forma dinámica, hay que prever además el espacio que ocuparán en tiempo de ejecución. El número de caracteres que compone cada palabra en cada idioma puede llegar a ser muy distinto. Es habitual ver en algunas ocasiones como los textos se "cortan" impidiendo su visualización completa. Otra veces el problema se produce cuando los textos se componen dinámicamente con objeto de incluir dentro de ellos información obtenida en tiempo de ejecución, como por ejemplo el nombre del jugador. Son los típicos argumentos "$1" o "%1" o "{player_name}" que se incluyen dentro de los propias cadenas y que pueden llegar a ver los jugadores cuando falla el sistema de composición, al no poder resolverse correctamente todos los parámetros. En el juego "Portal" de Valve, los desarrolladores sacaron partido de este conocido error haciendo que la voz metálica femenina tan característica que nos acompaña durante el transcurso del juego leyera los textos tal cual, incluido el "put player name here".

Dejo para otra ocasión el uso de distintos juegos de caracteres, o peculiaridades propias de cada idioma, como la escritura de derecha a izquierda por ejemplo.

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.