He visto CRC de 8 bits, 16 bits y 32 bits.Longitud de datos frente a CRC Longitud
¿En qué punto debo saltar a un CRC más ancho?
Mi reacción visceral es que se basa en la longitud de datos:
EDIT: En cuanto a la página de Wikipedia sobre la CRC y de Lott respuesta, aquí lo que tenemos:
< 64 bytes: 8-bit CRC
< 16K bytes: 16-bit CRC
< 512M bytes: 32-bit CRC
No es un tema de investigación. Es realmente 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 ofrece 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 máxima de bloque total es igual a 2**r − 1". Eso está en pedazos. No necesita investigar mucho para ver si 2**9 - 1 tiene 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.
Esto es preciso y útil si el CRC se usa para detectar cambios en un archivo. Sin embargo, si se usa como resumen para detectar duplicados entre archivos, entonces es más complicado. Específicamente, la paradoja del cumpleaños requiere que tengamos en cuenta la cantidad de valores distintos que esperamos tener. –
@Steven Sudit: Correcto. Tristemente, la pregunta es demasiado vaga para determinar algo sobre el uso del CRC. –
Creo que * cualquier * mensaje más solitario que el ancho CRC (r-1, y no 2^r-1) tendrá múltiples mensajes asignados a la misma suma de comprobación. IOW, cualquier mensaje de más de un byte de largo, tendrá superposición de las asignaciones de CRC8. Creo que (uno de) los desafíos es diseñar el mapeo de tal manera que la distribución de cadenas de mensajes sobre los hashes sea uniforme. – ysap
creo que el tamaño de la CRC tiene más que ver con la forma en singular de un CRC que 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.
El CRC debe ser elegido específicamente para la longitud de los mensajes, no es sólo una cuestión del tamaño de la CDN: http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf
La eficacia 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:
El documento Código de Redundancia Cíclica polinomio de selección para Redes Integradas, por Philip Koopman y Tridib Chakravarty, publised en las actas de la Conferencia Internacional en sistemas fiables y Redes 2004 da una 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
La elección de la longitud CRC versus tamaño del archivo es principalmente relevante en los casos en que uno es más probable que tenga una entrada que difiere de la entrada "corregir" por tres o menos bits que para tener un uno que es masivamente 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.
Si los paquetes son más largos que el período CRC, sin embargo, un error de doble bit no se detectará 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.
El ataque MD5 a finales de 2008 es un ejemplo de libro de texto del problema con un CRC que es demasiado uniforme o demasiado pequeño: http://www.win.tue.nl/hashclash/rogue-ca/ – bzlm
CRC no es un algoritmo hash. Es una forma de ver si un bit fue volteado inadvertidamente. No veo la conexión al enlace MD5. Voy a mirar de nuevo. – Robert
@bzlm MD5 no tiene nada que ver con eso. Los CRC no se resistirán a tales ataques en absoluto, sino que se utilizan para detectar errores aleatorios, no ataques maliciosos. – starblue