Publicación técnica
Cómo calcular el checksum
Los checksums de distintos tipos se utilizan habitualmente en los protocolos de comunicación de datos para permitir al destinatario de un mensaje determinar, de forma rápida y sencilla, si es probable que los datos se hayan corrompido durante la transmisión. Si sumas todos los bytes de un mensaje y obtienes (sin tener en cuenta el desbordamiento) que la suma es 96, y añades ese número al mensaje antes de enviarlo, el destinatario puede repetir tu suma con los primeros N – 1 bytes del mensaje y comparar el resultado con el último byte para comprobar si es 96. Si lo es, el destinatario puede inferir que, probablemente (es discutible), el mensaje no se alteró durante el envío.
Encontrarás una amplia variedad de técnicas de checksum en uso común. Tres de las más populares son el checksum convencional, el LRC (longitudinal redundancy check) y el CRC (cyclic redundancy check). Este último no es realmente un checksum en el sentido habitual, sino un ejemplo de hash unidireccional que pertenece a la familia de los «generadores congruenciales lineales».
Fíjate en que, antes, he dicho que estas técnicas de integridad de datos pueden indicarte si los datos «probablemente se han corrompido». Ninguna técnica de checksum es 100 % infalible en el caso general, para datos de longitud arbitraria. Pero algunas técnicas son claramente mejores que otras.
Veamos cómo calcular el LRC, el checksum y el CRC utilizando JavaScript.
Cómo calcular el checksum de la forma tradicional
El checksum convencional de 8 bits es justo lo que parece: una suma de los valores de todos los bytes de la entrada, descartando cualquier desbordamiento (procedente de las operaciones de acarreo). En JavaScript:
Se espera que la entrada de esta función sea una cadena hexadecimal con un aspecto similar a «48656C6C6F20776F726C6421» (que, en este caso, es la versión hexadecimal de la cadena ASCII «Hello world!»). Si utilizamos «48656C6C6F20776F726C6421» como entrada de la función anterior, la salida será «5d», que es el valor hexadecimal de la suma final de 8 bits.
El código es muy sencillo. Empezamos (en la línea 3) analizando la entrada hexadecimal en fragmentos de dos nibbles mediante la expresión regular /../g, que significa «encuentra subcadenas que coincidan con el patrón “cualquier carácter seguido de cualquier carácter” (eso es lo que significan los dos puntos) y hazlo de forma global (eso es lo que indica la “g”)». El resultado es un array, s, de valores hexadecimales de dos dígitos.
En la línea 5 entramos en un bucle (utilizando el constructo de iteración forEach ) en el que convertimos la versión en cadena de un valor hexadecimal de dos nibbles en un número real con el que podemos operar. En la línea 7 hacemos la suma propiamente dicha. Ten en cuenta que el número sum es, en esencia, un entero de 32 bits a nivel interno, lo que significa que nuestro valor final podría ser mucho mayor que 255. Cuando terminemos el bucle, debemos asegurarnos de restringir la suma a un valor de 8 bits. Lo hacemos en la línea 9, con el AND lógico contra 255. Al mismo tiempo, convertimos de nuevo a hexadecimal utilizando el método toString() con un argumento de 16 (lo que significa que queremos usar radix-16 o «base 16» en la representación final del número).
En las líneas 10 y 11 tenemos que comprobar que el valor hexadecimal final tenga una longitud de dos nibbles. La operación toString(16) de JavaScript devuelve un valor de un solo dígito para valores inferiores a 10. En ese caso, debemos anteponer un «0» a la respuesta.
Si quieres probar el código, copia y pega el código anterior en tu consola de JS (en Chrome, usa Mayús-Cmd-J para abrir la consola) y añade al final (fuera de la función) la línea CHECKSUM(«48656C6C6F20776F726C6421»). Al pulsar Intro, la consola debería mostrar «5d» como valor devuelto.
Cómo calcular el checksum con LRC
El longitudinal redundancy check (LRC) es una variante del checksum de 8 bits, que se diferencia únicamente en que la «suma» se realiza mediante XOR, en lugar de una suma numérica.
En la línea 6 puedes ver el operador XOR en el sitio (^=).
Como el XOR nunca se desborda, no tenemos que restringir el resultado final a 8 bits con un AND. Simplemente comprobamos que tenga una longitud de dos nibbles y devolvemos el valor final.
Si pruebas el código en la consola con la cadena mostrada anteriormente, deberías obtener como resultado «21».
Crítica del checksum y el LRC
Ni el checksum ni el LRC pueden considerarse robustos frente a la corrupción de mensajes. Por ejemplo, considera el mensaje original («48656C6C6F20776F726C6421»); supón que cambiamos los dos últimos bytes del mensaje de 6421 a 6520. ¡Tanto el LRC como el checksum permanecen sin cambios! (Simplemente hemos puesto un bit a ON en un byte anterior y hemos puesto el mismo bit a OFF en uno posterior, creando dos cambios que se cancelan mutuamente al calcular el checksum).
Del mismo modo, piensa en lo que ocurre si inviertes el mensaje (es decir, lo recorres en sentido inverso byte a byte, de modo que empiece por 21 y termine en 48). De nuevo, el LRC y el checksum se mantienen iguales que en el mensaje original. Esto se debe a que el XOR y la suma son conmutativos. A + B siempre será igual a B + A.
Considera también que, dado que un LRC o checksum de 8 bits solo puede tener 256 valores diferentes, hay 1 probabilidad entre 256 de que cualquier mensaje produzca exactamente el mismo LRC (o checksum) que otro mensaje elegido al azar.
En general, es muy fácil «engañar» a los algoritmos de checksum y LRC, por lo que no son realmente muy fiables para la comprobación de la integridad de los mensajes.
Afortunadamente, existen algoritmos mejores que el LRC o el checksum para la verificación de la integridad, pero conllevan un coste en términos de carga computacional.
Cómo calcular el checksum con CRC
Cuando la verificación de la integridad realmente importa, en general necesitas utilizar algún tipo de hash no conmutativo. A menudo, esto implica un hash criptográfico, como SHA-1 o MD5, pero estos son computacionalmente intensivos y pueden considerarse «excesivos» en muchas situaciones.
Un buen equilibrio entre carga computacional y fiabilidad puede encontrarse en el Cyclic Redundancy Check, que existe en varias versiones, aunque el CRC de 16 bits que se describe a continuación es suficiente (y bastante popular) para mensajes cortos (de hasta unos 4 kilobytes).
El CRC es un tema interesante, pero el espacio impide ofrecer aquí un tratamiento exhaustivo. (Consulta Google). Baste decir, desde un punto de vista práctico, que un CRC de dos bytes proporciona una muy buena sensibilidad a los volteos de bits aleatorios en los datos y es poco probable que dé falsos positivos con datos que contengan múltiples volteos de bits. Por ello, y porque es fácil de implementar en hardware o software y se ejecuta muy rápidamente con muy poca memoria, lo encontrarás utilizado en una gran variedad de entornos de comunicación de datos, como los controladores de unidades de disco (donde los errores de disco se detectan a menudo mediante CRC), módems y pequeños dispositivos electrónicos (incluidos todos los lectores de tarjetas de crédito de la serie ViVOpay de ID TECH).
El siguiente código JavaScript muestra cómo calcular un valor de CRC de 16 bits (devuelto como cuatro nibbles de hex-ASCII).
El CRC implementa un algoritmo de hash que puede describirse en lenguaje sencillo como:
- Establezca el valor inicial de crc en 0xFFFF — Línea 10
- Tome un byte de los datos de entrada (como un número de 8 bits) — Línea 13
- Desplace a la derecha el valor actual de crc 8 bits — Línea 14
- Aplique XOR entre el crc desplazado a la derecha y el byte de entrada — Línea 14
- Utilice el valor resultante j (solo los 8 bits inferiores) como desplazamiento en la tabla para consultar un «byte de sustitución» en la tabla conocida como crcTable — Línea 15
- Desplace el valor de crc 8 bits a la IZQUIERDA y aplíquele XOR con el «byte de sustitución» — Línea 15
- Repita estas operaciones, comenzando desde la Línea 13, utilizando el siguiente byte de entrada
- Una vez procesada toda la entrada de este modo, aplique XOR al resultado con cero y conserve los 16 bits inferiores del crc — Línea 17
Utilizamos una pequeña rutina auxiliar para convertir el número final de entero a cadena hexadecimal:
Si carga ambas funciones (numToHex y CRC) en la consola JS de su navegador y ejecuta CRC( "48656C6C6F20776F726C6421" ), debería obtener un CRC de «BD22» para los datos de entrada «Hello world!».
A modo de ejercicio, puede probar a invertir un bit de la entrada para ver qué ocurre con la salida. Por ejemplo, si utiliza nuestra cadena «Hello world!» como entrada y cambia el último byte de los datos de 21 a 20, el CRC cambia a «AD03», que no guarda relación alguna con «BD22». Si cambia los dos últimos bytes a «6520», se obtiene un CRC de «9E32». (Recuerde que este mismo cambio no alteraba el LRC ni el checksum.)
Considere una cadena que representa diez bytes cero (nulos). El valor LRC de dicha cadena sería cero. El checksum, evidentemente, también sería cero. Pero el CRC sería E139.
Debería poder comprobar con bastante facilidad que invertir la entrada produciría un CRC completamente distinto al obtenido con la entrada en su dirección original. (Lo cual no sucedía con el LRC ni con el checksum.) El CRC no es conmutativo, debido a la forma en que los 8 bits superiores del CRC se combinan mediante XOR con el byte de entrada antes de desplazar todo a la izquierda (lo cual es similar al funcionamiento del encadenamiento de bloques de cifrado (cipher block chaining) , salvo que en este caso el tamaño del «bloque de cifrado» es de 8 bits).
Cabe señalar que, si bien el CRC es una función hash unidireccional, no se trata de un hash criptográfico propiamente dicho, ya que en realidad resulta bastante sencillo calcular un «valor de corrección» que, añadido a los datos, haría que una alteración determinada de los mismos diese como resultado el CRC final deseado. (Esto no es así con los denominados hashes criptográficos, en los que resulta difícil calcular un «factor de corrección» que devuelva un bloque de datos alterado al hash deseado.) Por ello, el CRC es adecuado para detectar daños no intencionados en los datos.
Conclusión
No faltan algoritmos de «comprobación de integridad» que se pueden emplear para supervisar la corrupción de los paquetes de datos. En algunos casos, basta con un simple checksum o LRC. Pero en situaciones que implican volúmenes de datos no triviales y un requisito estricto de integridad, prácticamente hay que recurrir a un hash de tipo «generador congruencial lineal» . La familia de algoritmos CRC se ha ajustado y optimizado para ofrecer una buena capacidad de discriminación de la integridad, combinada con facilidad de implementación, ejecución rápida y bajos requisitos de memoria, lo que hace que el CRC resulte atractivo para una amplia variedad de escenarios de verificación de datos, desde discos duros hasta lectores de tarjetas de crédito.