Suma de verificación

Efecto de una función típica de la suma de comprobación (la Unix cksum utilidad)

Un checksum es un bloque de datos de pequeño tamaño derivado de otro bloque de datos digitales con el fin de detectar errores que puedan haberse introducido durante su transmisión o almacenamiento. Por sí mismas, las sumas de verificación a menudo se usan para verificar la integridad de los datos, pero no se confía en ellas para verificar la autenticidad de los datos.

El procedimiento que genera esta suma de verificación se denomina función de suma de verificación o algoritmo de suma de verificación. Dependiendo de sus objetivos de diseño, un buen algoritmo de suma de verificación generalmente genera un valor significativamente diferente, incluso para pequeños cambios realizados en la entrada. Esto es especialmente cierto en el caso de las funciones hash criptográficas, que pueden usarse para detectar muchos errores de corrupción de datos y verificar la integridad general de los datos; si la suma de verificación calculada para la entrada de datos actual coincide con el valor almacenado de una suma de verificación calculada anteriormente, existe una probabilidad muy alta de que los datos no se hayan alterado o corrompido accidentalmente.

Las funciones de suma de comprobación están relacionadas con funciones hash, huellas dactilares, funciones de aleatorización y funciones hash criptográficas. Sin embargo, cada uno de esos conceptos tiene diferentes aplicaciones y, por lo tanto, diferentes objetivos de diseño. Por ejemplo, una función que devuelve el inicio de una cadena puede proporcionar un hash apropiado para algunas aplicaciones, pero nunca será una suma de verificación adecuada. Las sumas de verificación se utilizan como primitivas criptográficas en algoritmos de autenticación más grandes. Para sistemas criptográficos con estos dos objetivos de diseño específicos, consulte HMAC.

Los dígitos de control y los bits de paridad son casos especiales de sumas de control, apropiados para pequeños bloques de datos (como números de seguridad social, números de cuentas bancarias, palabras informáticas, bytes individuales, etc.). Algunos códigos de corrección de errores se basan en sumas de verificación especiales que no solo detectan errores comunes, sino que también permiten recuperar los datos originales en ciertos casos.

Algoritmos

Byte de paridad o palabra de paridad

El algoritmo de suma de control más simple es el llamado control de paridad longitudinal, que divide los datos en "palabras" con un número fijo n de bits, y luego calcula el exclusivo o (XOR) de todas esas palabras. El resultado se adjunta al mensaje como una palabra adicional. En términos más simples, esto significa agregar un bit al final de la palabra para garantizar que haya un número par de '1's. Para verificar la integridad de un mensaje, el receptor calcula la exclusiva o de todas sus palabras, incluida la suma de verificación; si el resultado no es una palabra que consta de n ceros, el receptor sabe que ocurrió un error de transmisión.

Con esta suma de verificación, cualquier error de transmisión que cambie un solo bit del mensaje, o un número impar de bits, se detectará como una suma de verificación incorrecta. Sin embargo, no se detectará un error que afecte a dos bits si esos bits se encuentran en la misma posición en dos palabras distintas. Tampoco se detectará el intercambio de dos o más palabras. Si los bits afectados se eligen de forma independiente al azar, la probabilidad de que no se detecte un error de dos bits es 1/n.

Complemento de suma

Una variante del algoritmo anterior es sumar todas las "palabras" como números binarios sin signo, descartando los bits de desbordamiento y agregando el complemento a dos del total como suma de verificación. Para validar un mensaje, el receptor suma todas las palabras de la misma forma, incluyendo el checksum; si el resultado no es una palabra llena de ceros, debe haber ocurrido un error. Esta variante también detecta cualquier error de un solo bit, pero la suma pro modular se usa en SAE J1708.

Dependiente de la posición

Las sumas de comprobación simples descritas anteriormente no detectan algunos errores comunes que afectan a muchos bits a la vez, como cambiar el orden de las palabras de datos o insertar o eliminar palabras con todos los bits establecidos en cero. Los algoritmos de suma de verificación más utilizados en la práctica, como la suma de verificación de Fletcher, Adler-32 y las verificaciones de redundancia cíclica (CRC), abordan estas debilidades al considerar no solo el valor de cada palabra sino también su posición en la secuencia. Esta característica generalmente aumenta el costo de calcular la suma de verificación.

Suma de comprobación difusa

La idea de la suma de comprobación difusa se desarrolló para la detección de spam de correo electrónico mediante la creación de bases de datos cooperativas de varios ISP de correo electrónico sospechoso de ser spam. El contenido de dicho correo no deseado a menudo puede variar en sus detalles, lo que haría ineficaz la suma de comprobación normal. Por el contrario, una "suma de comprobación difusa" reduce el texto del cuerpo a su mínimo característico, luego genera una suma de verificación de la manera habitual. Esto aumenta en gran medida las posibilidades de que los correos electrónicos no deseados ligeramente diferentes produzcan la misma suma de verificación. El software de detección de spam del ISP, como SpamAssassin, de los ISP que cooperan, envía sumas de verificación de todos los correos electrónicos al servicio centralizado, como DCC. Si el recuento de una suma de comprobación difusa enviada supera un cierto umbral, la base de datos indica que esto probablemente indica spam. De manera similar, los usuarios del servicio ISP generan una suma de verificación difusa en cada uno de sus correos electrónicos y solicitan el servicio por una probabilidad de spam.

Consideraciones generales

Un mensaje de m bits puede verse como una esquina de m-hipercubo dimensional. El efecto de un algoritmo de suma de comprobación que produce una suma de comprobación de n-bit es mapear cada m-bit a una esquina de un hipercubo más grande, con dimensión m + n. Las esquinas 2^{m + n} de este hipercubo representan todos los posibles mensajes recibidos. Los mensajes válidos recibidos (aquellos que tienen la suma de verificación correcta) comprenden un conjunto más pequeño, con solo 2^m esquinas.

Un error de transmisión de un solo bit corresponde a un desplazamiento desde una esquina válida (el mensaje correcto y la suma de verificación) a uno de los m adyacentes esquinas Un error que afecta k bits mueve el mensaje a una esquina que es k pasos eliminados de su esquina correcta. El objetivo de un buen algoritmo de suma de comprobación es distribuir las esquinas válidas lo más lejos posible entre sí, para aumentar la probabilidad "típica" los errores de transmisión terminarán en una esquina no válida.