Código de redundancia cíclica

JKS [jksware@gmail.com]

CHECKSUMS

Lo mismo sea para transmitir datos a través del puerto serie, para hacer zip / unzip de un fichero o para acceder a un CD, está presente en la programación de un controlador de E/S – incluyendo el BIOS – un conjunto de instrucciones capaz de comprobar la integridad de determinado paquete de datos que se desee preservar: un algoritmo de control de errores encargado de la detección de cualquier variación – por ligera que esta sea - con respecto al contenido digital original, provocada por una falla aleatoria vinculada a la transmisión, almacenamiento, lectura o recepción de los mismos, y nunca debido a una intervención inteligente.

Un algoritmo de control de errores utiliza para detectar la corrupción digital un código que tiene determinada afinidad numérica con la información a procesar en cuestión. Para cada contenido digital existe un único código, mientras que diversos contenidos pueden generar el mismo código de comprobación, a menudo llamado checksum o CRC ( Cyclic Redundancy Check ).

A cada contenido corresponde un código, pero a cada código no le corresponde un contenido. Por lo tanto, si llevamos este pensamiento al sistema cartesiano, podemos deducir que los códigos serían representados en el eje X, y los contenidos en el eje Y. Para una función CRC en la que la variable de entrada es X, el eje Y es dependiente a ésa entrada. Sin embargo, X es totalmente independiente.

En otras palabras, si contamos con un buen algoritmo, una sustitución de un único mísero bit en nuestro mensaje puede ser suficiente para variar por completo el código generado, aunque la información sea de varios kbits de longitud – como sucede con la transmisión de información a través del módem o de las redes TCP/IP, en que cada paquete viaja acompañado de un checksum, y cuya comprobación se realiza por hardware y por software, respectivamente.

ALGORITMO DE UN CRC

Desde el punto de vista práctico la implementación de un algoritmo de comprobación de redundancia cíclica puede ser bastante fácil, en dependencia del objetivo para el cual se desee, y no requiere de grandes conocimientos de álgebra ni cálculo, sino de simples conocimientos de programación linear.

Pero cuando se mira con un carácter más analítico, pasa algo parecido a lo que sucede con los algoritmos de encriptación, que no se puede a simple vista apreciar cuán buenos son o cuán duraderos ante las desavenencias del tiempo pueden ser, a no ser que se prueben en la cotidianidad. Por ejemplo, del CRC-32 están listados en Wikipedia varios estándares que utiliza cada uno diferentes polinomios – que no son más que el juego de bases y exponenciales con que se basa cada algoritmo – cada uno estandarizado en una cuestión determinada en la que otro, muy parecido, falló en hacer bien o con facilidad en un área de la técnica en cuestión.

De aquí se podría pensar que si son transmitidos ambos el contenido digital y el checksum de CRC anexado, y se realiza satisfactoriamente la comprobación es que los datos no han sido modificados. Incorrecto. CRC no es un estándar de encriptación, sino que su utilidad reside exclusivamente en la comprobación de corrupción ocasionada por fenómenos espontáneos, y no por la mano del hombre. Los criptosistemas emplean además de un checksum otro código llamado firma digital, el cual es estampado sobre el mensaje a transmitir, y que guarda relación con el par de claves de un sistema de Claves Públicas, que sí garantiza la seguridad en cuanto a intervención humana se trata ( para leer más acerca de criptosistemas vea Pretty Good Privacy en BlackHat 43) .

La base para los algoritmos de CRC, se basa en separar el contenido digital en paquetes de bits manejables por la máquina – dígase 32 bits – para después pasar ser divididos por el polinomio dado – que debe tener un orden de igual cantidad a la longitud del paquete – por el algoritmo con el cual se trabaje. Se desea obtener de esta división el resto y no el cociente – ya que no se trata de una operación común y corriente en el sistema decimal – y se alcanza mediante el acceso directo a operaciones lógicas en lenguaje ensamblador.

El resto a obtener de la primera operación tendrá un dígito menos que el divisor, por lo que se le agregará el bit correspondiente del dividendo y por supuesto, como el dividendo es mucho más largo – ya que posee el contenido digital propiamente dicho – tras la primera operación lógica XOR se obtiene un resto que es dividido nuevamente por el divisor, a semejanza de una operación normal. La división con resto continúa hasta que se complete la totalidad del mensaje. El resto de la última operación es el checksum del algoritmo. Si cuando se obtenga el mensaje este número ha variado, entonces algo anda mal, y los datos probablemente estén corruptos.

La elección de un buen divisor es el cuerpo de un algoritmo de CRC. Si no se trabaja conscientemente y se elijen números al azar no se contará con la seguridad necesaria. Existen reglas para lograr ése objetivo, pero esas se las dejamos a los matemáticos.

Actualmente se trabaja por hace compatibles estos sistemas de comprobación de checksums con los últimos procesadores de 32 y 64 bits – recordemos que la teoría de la información de la cual surgieron todos estos algoritmos es mucho más vieja y datan de los sesentas – y se hace énfasis en generar tablas que aligeren la carga de trabajo mediante el procesamiento previo del cálculo de los restos de las instrucciones, ya que en la actualidad se cuenta con mucho más espacio en caché y memoria operativa para realizar dichas operaciones.

CHECKSUM = OK

Existen otras muchas técnicas no expuestas aquí que cumplen más o menos igual las funciones, pero la base en todas es la misma, la detección de cambios sencillos que aparejen grandes cambios en el código a generar. Se puede hacer un estudio mucho más detallado de lo que pasa aquí, si te interesa el tema escríbeme a jksware@gmail.com y prometo mandarte un par de documentos muy interesantes debatiendo acerca del uso de algoritmos más sofisticados para generar cheksums con un altísimo rendimiento.

Así que cuando un disco te “de bateo” cuando trates de copiar algo del mismo, o el WinRAR no te deje abrir un fichero comprimido que bajaste porque genera un error de checksum, ya sabes cómo es que la máquina eventualmente se va a dar cuenta del problema, casi cuando está punto de quemarse el lector o derretirse el micro, para evitar mayores complicaciones.

Artículos relacionados