¿Cómo puedo adivinar un algoritmo de suma de comprobación?

Question

Supongamos que tengo algunos paquetes con una suma de comprobación de 16 bits al final. Me gustaría adivinar qué algoritmo de suma de comprobación se utiliza.

Para empezar, a partir de datos de volcado, puedo ver que un cambio de byte en la carga útil del paquete cambia totalmente la suma de comprobación, por lo que puedo suponer que no es un tipo simple de XOR o suma.

Luego probé several variations of CRC16, pero sin mucha suerte.

Esta pregunta puede ser más parcial hacia la criptografía, pero estoy realmente interesado en cualquier herramienta estadística fácil de entender para saber qué CRC podría ser. Incluso podría pasar al drawing different CRC algorithms si todo lo demás falla.

Backgroud story: Tengo un protocolo de RFID en serie con algún tipo de suma de comprobación. Puedo reproducir mensajes sin problemas e interpretar los resultados (sin verificación de suma de comprobación), pero no puedo enviar paquetes modificados porque el dispositivo los descarta.

Usando el software existente, puedo cambiar la carga útil del chip RFID. Sin embargo, el número de serie único es inmutable, por lo que no tengo la capacidad de verificar todas las combinaciones posibles. Aunque podría generar volcados de valores incrementando en uno, pero no lo suficiente como para hacer una búsqueda exhaustiva aplicable a este problema.

dump files with data están disponibles si se pregunta en sí misma no es suficiente :-)

Necesita documentación de referencia?A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS es una gran referencia que encontré después de hacer una pregunta aquí.

Al final, después toque muy útil en la respuesta aceptada de lo que es CCITT, que used this CRC calculator, y XOR generada suma de comprobación con la suma de comprobación conocida para obtener 0xffff que me llevó a la conclusión de que xor final es instread 0xffff del CCITT de 0x0000.

Answer 1

Hay una serie de variables a tener en cuenta para un CRC:

Polynomial 
No of bits (16 or 32) 
Normal (LSB first) or Reverse (MSB first) 
Initial value 
How the final value is manipulated (e.g. subtracted from 0xffff), or is a constant value 

CRC típicas:

LRC: Polynomial=0x81; 8 bits; Normal; Initial=0; Final=as calculated 
CRC16: Polynomial=0xa001; 16 bits; Normal; Initial=0; Final=as calculated 
CCITT: Polynomial=0x1021; 16 bits; reverse; Initial=0xffff; Final=0x1d0f 
Xmodem: Polynomial=0x1021; 16 bits; reverse; Initial=0; Final=0x1d0f 
CRC32: Polynomial=0xebd88320; 32 bits; Normal; Initial=0xffffffff; Final=inverted value 
ZIP32: Polynomial=0x04c11db7; 32 bits; Normal; Initial=0xffffffff; Final=as calculated 

El primero que hay que hacer es conseguir algunas muestras cambiando decir el último byte. Esto lo ayudará a determinar el número de bytes en el CRC.

Este es un algoritmo "hecho en casa". En este caso, puede llevar algo de tiempo. De lo contrario, pruebe los algoritmos estándar.

Intente cambiar el msb o el lsb del último byte, y vea cómo esto cambia el CRC. Esto dará una indicación de la dirección.

Para hacerlo más difícil, hay implementaciones que manipulan el CRC para que no afecte al medio de comunicación (protocolo).

De su comentario sobre RFID, implica que el CRC está relacionado con las comunicaciones. Por lo general, CRC16 se usa para comunicaciones, aunque CCITT también se usa en algunos sistemas.

Por otro lado, si se trata de etiquetado UHF RFID, existen algunos esquemas de CRC: uno de 5 bits y otro de 16 bits. Estos están documentados en los estándares ISO y en las hojas de datos IPX.

IPX: Polynomial=0x8005; 16 bits; Reverse; Initial=0xffff; Final=as calculated 
ISO 18000-6B: Polynomial=0x1021; 16 bits; Reverse; Initial=0xffff; Final=as calculated 
ISO 18000-6C: Polynomial=0x1021; 16 bits; Reverse; Initial=0xffff; Final=as calculated 
    Data must be padded with zeroes to make a multiple of 8 bits 
ISO CRC5: Polynomial=custom; 5 bits; Reverse; Initial=0x9; Final=shifted left by 3 bits 
    Data must be padded with zeroes to make a multiple of 8 bits 
EPC class 1: Polynomial=custom 0x1021; 16 bits; Reverse; Initial=0xffff; Final=post processing of 16 zero bits 

Aquí está su respuesta !!!!

Habiendo trabajado en sus registros, el CRC es el CCITT. El primer byte 0xd6 se excluye del CRC.

Answer 2

Debería probar todos los algoritmos de suma de comprobación posibles y ver cuál genera el mismo resultado. Sin embargo, no hay garantía de qué contenido se incluyó en la suma de comprobación. Por ejemplo, algunos algoritmos saltan espacios en blanco, lo que conduce a diferentes resultados.

Realmente no veo por qué alguien querría saber eso.

Answer 3

Puede que no sea un CRC, podría ser un código de corrección de errores como Reed-Solomon.

Los códigos ECC son a menudo una fracción sustancial del tamaño de los datos originales que protegen, dependiendo de la tasa de error que desean manejar. Si el tamaño de los mensajes es más de aproximadamente 16 bytes, 2 bytes de ECC no serían suficientes para ser útiles. Entonces, si el mensaje es grande, lo más probable es que sea correcto que sea una especie de CRC.

Answer 4

Estoy tratando de descifrar un problema similar aquí y encontré un sitio web bastante limpio que tomará su archivo y ejecutará sumas de comprobación con 47 algoritmos diferentes y mostrará los resultados. Si el algoritmo utilizado para calcular su suma de comprobación es alguno de estos algoritmos, simplemente lo encontrará entre la lista de sumas de comprobación producidas con una simple búsqueda de texto.

El sitio web es https://defuse.ca/checksums.htm