crc - tener - longitud title

Longitud de datos vs longitud CRC

Question

He visto CRC de 8 bits, 16 bits y 32 bits.

¿En qué punto necesito saltar a un CRC más amplio?

Mi reacción instintiva es que se basa en la longitud de los datos:

1. 1-100 bytes: CRC de 8 bits
2. 101 - 1000 bytes: CRC de 16 bits
3. 1001 - ??? bytes: CRC de 32 bits

EDIT: mirando la página de Wikipedia sobre CRC y la respuesta de Lott, aquí ''lo que tenemos:

<64 bytes: CRC de 8 bits

<16K bytes: CRC de 16 bits

<512M bytes: CRC de 32 bits

Answer 1

Aquí hay una buena evaluación del "mundo real" de CRC-N http://www.backplane.com/matt/crc64.html

Utilizo CRC-32 y comparación de tamaño de archivo y NUNCA, en los miles de millones de archivos revisados, se encuentran con una coincidencia de CRC-32 y colisión de tamaño de archivo. Pero sé que existen algunos, cuando no están forzosamente forzados a existir. (Trucos / exploits pirateados)

Al hacer la comparación, también debe verificar "tamaños de datos". Raramente tendrá una colisión del mismo tamaño de datos, con un CRC coincidente, dentro de los tamaños correctos.

Los datos manipulados deliberadamente, para simular una coincidencia, generalmente se hacen agregando datos extra hasta que el CRC coincida con un objetivo. Sin embargo, eso da como resultado un tamaño de datos que ya no coincide. Intentar utilizar la fuerza bruta o desplazarse por datos aleatorios o secuenciales, del mismo tamaño exacto, dejaría una tasa de colisión realmente estrecha.

También puede tener colisiones dentro del tamaño de datos, solo por los límites genéricos de las fórmulas utilizadas, y las restricciones de uso de bits / bytes y sistemas de base diez, que depende de valores de coma flotante, que se truncan y recortan.

El punto en el que desearía pensar en agrandarse es cuando comienza a ver muchas colisiones que no pueden "confirmarse" como "originales". (Cuando ambos tienen el mismo tamaño de datos, y (cuando se prueban hacia atrás, tienen un CRC coincidente. Inverso / byte o reverso / bits, o compensaciones de bits)

En cualquier caso, NUNCA debe usarse como la ÚNICA forma de comparación, solo para una forma rápida de comparación, para indexar.

Puede usar un CRC-8 para indexar todo Internet y dividir todo en una de las N-categorías. QUIERES esas colisiones. Ahora, con los pedidos previamente ordenados, solo debe verificar uno de los N-directorios, buscando "tamaño de archivo" o "CRC inverso", o cualquier otra comparación que pueda hacer con ese conjunto de datos más pequeño, rápido. ..

Hacer un CRC-32 hacia adelante y hacia atrás con la misma cantidad de datos es más confiable que usar el CRC-64 en una sola dirección. (O un MD5, para el caso).

Answer 2

Creo que el tamaño del CRC tiene más que ver con cuán único CRC necesita en lugar del tamaño de los datos de entrada. Esto está relacionado con el uso particular y la cantidad de elementos en los que está calculando un CRC.

Answer 3

El CRC debe elegirse específicamente para la longitud de los mensajes, no se trata solo del tamaño del CRC: http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

Answer 4

La efectividad de un CRC depende de múltiples factores. No solo necesita seleccionar el TAMAÑO del CRC sino también el POLINOMIO GENERADOR a usar. Existen compensaciones complicadas y no intuitivas que dependen de:

• La tasa de error de bit esperada del canal.
• Si los errores tienden a ocurrir en ráfagas o tienden a extenderse (la ráfaga es común)
• La longitud de los datos a proteger: longitud máxima, longitud mínima y distribución.

El documento Cyclical Redundancy Code Polynominal Selection for Embedded Networks, de Philip Koopman y Tridib Chakravarty, publicado en las actas de la Conferencia Internacional sobre Sistemas y Redes Confiables de 2004 ofrece una muy buena visión general y hace varias recomendaciones. También proporciona una bibliografía para una mayor comprensión.

http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

Answer 5

La elección de la longitud de CRC frente al tamaño de archivo es principalmente relevante en los casos en que es más probable que haya una entrada que difiera de la entrada "correcta" en tres o menos bits que tener una que sea enormemente diferente. Dadas dos entradas que son enormemente diferentes, la posibilidad de una coincidencia falsa será aproximadamente 1/256 con la mayoría de las formas de valor de comprobación de 8 bits (incluido CRC), 1/65536 con la mayoría de las formas de valor de comprobación de 16 bits (incluido CRC) , etc. La ventaja de CRC proviene de su tratamiento de entradas que son muy similares.

Con un CRC de 8 bits cuyo polinomio genera dos períodos de longitud 128, la fracción de los errores de bit simple, doble o triple en un paquete más corto que el que no se detecta no será 1/256, será cero. Del mismo modo con un CRC de 16 bits del período 32768, usando paquetes de 32768 bits o menos.

Sin embargo, si los paquetes son más largos que el período CRC, entonces no se detectará un error de doble bit si la distancia entre los bits erróneos es un múltiplo del período CRC. Si bien eso podría no parecer un escenario terriblemente probable, un CRC8 será algo peor en la captura de errores de doble bit en paquetes largos que en la captura de errores "paquete está totalmente codificado". Si los errores de doble bit son el segundo modo de falla más común (después de los errores de un solo bit), sería malo. Sin embargo, si algo que corrompe algunos datos puede corromper una gran parte, el comportamiento inferior de los CRC con errores de doble bit puede no ser un problema.

Answer 6

No es un tema de investigación. Está muy bien entendido: http://en.wikipedia.org/wiki/Cyclic_redundancy_check

La matemática es bastante simple. Un CRC de 8 bits reduce todos los mensajes a uno de los 256 valores. Si su mensaje tiene más de unos pocos bytes, la posibilidad de que varios mensajes tengan el mismo valor hash sube más y más.

Un CRC de 16 bits, de manera similar, le proporciona uno de los 65.536 valores hash disponibles. ¿Cuáles son las probabilidades de que dos mensajes tengan uno de estos valores?

Un CRC de 32 bits le proporciona aproximadamente 4 mil millones de valores de hash disponibles.

Del artículo de la wikipedia: "longitud de bloque total máxima es igual a 2**r − 1 ". Eso está en pedazos. No necesita hacer mucha investigación para ver que 2**9 - 1 es 511 bits. Usando CRC-8, los mensajes múltiples de más de 64 bytes tendrán el mismo valor de suma de comprobación CRC.