cksumutilidad Unix)Una suma de comprobación 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 se utilizan a menudo para verificar la integridad de los datos , pero no se confía en ellas para verificar la autenticidad de los datos . [1]
El procedimiento que genera esta suma de verificación se llama 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. [2] 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 previamente, existe una probabilidad muy alta de que los datos no hayan sido alterados o corrompidos 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 comprobación adecuada. Las sumas de comprobación se utilizan como primitivas criptográficas en algoritmos de autenticación más amplios. Para sistemas criptográficos con estos dos objetivos de diseño específicos [ se necesita aclaración ] , 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 de computadora , bytes individuales , etc.). Algunos códigos de corrección de errores se basan en sumas de verificación especiales que no sólo detectan errores comunes sino que también permiten recuperar los datos originales en ciertos casos.
El algoritmo de suma de verificación 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 la exclusiva bit a bit o (XOR) de todas esas palabras. El resultado se adjunta al mensaje como una palabra adicional. En términos más simples, para n =1 esto significa agregar un bit al final de los bits de datos para garantizar que haya un número par de unos. Para comprobar la integridad de un mensaje, el receptor calcula la exclusiva bit a bit de todas sus palabras, incluida la suma de comprobación; Si el resultado no es una palabra que consta de n ceros, el receptor sabe que ocurrió un error de transmisión. [3]
Con esta suma de verificación, cualquier error de transmisión que invierta un solo bit del mensaje, o un número impar de bits, se detectará como una suma de verificación incorrecta. Sin embargo, un error que afecte a dos bits no se detectará 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 aleatoriamente de forma independiente, la probabilidad de que no se detecte un error de dos bits es 1/ n .
Una variante del algoritmo anterior consiste en sumar todas las "palabras" como números binarios sin signo, descartando los bits desbordados y añadiendo el complemento a dos del total como suma de comprobación. Para validar un mensaje, el receptor agrega todas las palabras de la misma manera, incluida la suma de verificación; 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 modular profesional se utiliza en SAE J1708 . [4]
Las simples sumas de comprobación 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 puestos a 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 considerando 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.
La idea de la suma de comprobación difusa se desarrolló para la detección de correo no deseado mediante la creación de bases de datos cooperativas de múltiples ISP de correo electrónico sospechoso de ser spam. El contenido de dicho spam a menudo puede variar en sus detalles, lo que haría que la suma de verificación normal fuera ineficaz. Por el contrario, una "suma de comprobación difusa" reduce el cuerpo del texto a su mínimo característico y luego genera una suma de comprobación de la forma habitual. Esto aumenta en gran medida las posibilidades de que 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 verificación difusa enviada excede un cierto umbral, la base de datos señala que esto probablemente indica spam. Los usuarios del servicio ISP también generan una suma de verificación difusa en cada uno de sus correos electrónicos y solicitan el servicio por probabilidad de spam. [5]
Un mensaje de m bits de longitud puede verse como una esquina del hipercubo de m dimensiones . El efecto de un algoritmo de suma de comprobación que produce una suma de comprobación de n bits es asignar cada mensaje de m bits a una esquina de un hipercubo más grande, con dimensión m + n . Las esquinas de 2 m + n de este hipercubo representan todos los posibles mensajes recibidos. Los mensajes recibidos válidos (aquellos que tienen la suma de control correcta) forman un conjunto más pequeño, con sólo 2 m de esquinas.
Un error de transmisión de un solo bit corresponde entonces a un desplazamiento desde una esquina válida (el mensaje correcto y la suma de control) a una de las m esquinas adyacentes. Un error que afecta a k bits mueve el mensaje a una esquina que está a k pasos de su esquina correcta. El objetivo de un buen algoritmo de suma de comprobación es separar las esquinas válidas lo más posible entre sí, para aumentar la probabilidad de que los errores de transmisión "típicos" acaben en una esquina no válida.
Tema general
Error de corrección
Funciones hash
Sistemas de archivos
Conceptos relacionados
