¿Cómo podría adivinar un algoritmo de suma de verificación?

Question

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

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

Luego probé varias variaciones de CRC16 , pero sin mucha suerte.

Esta pregunta podría estar más sesgada hacia la criptografía, pero estoy realmente interesado en cualquier herramienta estadística fácil de entender para averiguar qué CRC podría ser. Incluso podría recurrir a dibujando diferentes algoritmos CRC si todo lo demás falla.

Historia de fondo: tengo un protocolo RFID en serie con algún tipo de suma de verificación. Puedo reproducir mensajes sin problemas e interpretar resultados (sin verificación de suma de verificación), pero no puedo enviar paquetes modificados porque el dispositivo los deja caer al suelo.

Utilizando 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 que se incrementan en uno, pero no lo suficiente como para que la búsqueda exhaustiva sea aplicable a este problema.

los archivos de volcado con datos están disponibles si la pregunta misma no es suficiente :-)

¿Necesita documentación de referencia? UNA GUÍA SIN DOLOR PARA CRC ALGORITMOS DE DETECCIÓN DE ERRORES es una gran referencia que encontré después de hacer una pregunta aquí.

Al final, después de una sugerencia muy útil en la respuesta aceptada que es CCITT, yo utilizó esta calculadora CRC , y xored generó una suma de verificación con suma de verificación conocida para obtener 0xffff que me llevó a conclusión de que xor final es 0xffff incrustado de 0x0000 del CCITT.

Answer 1

Hay una serie de variables a considerar 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ípicos:

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

Lo primero que debe hacer es obtener algunas muestras cambiando, digamos, el último byte. Esto lo ayudará a calcular la cantidad de bytes en el CRC.

¿Es esto un " casero " algoritmo. 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 le dará una indicación de la dirección.

Para hacerlo más difícil, hay implementaciones que manipulan el CRC para que no afecte el 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 las comunicaciones, aunque CCITT también se usa en algunos sistemas.

Por otro lado, si se trata de etiquetado RFID UHF, existen algunos esquemas CRC: uno de 5 bits y otros de 16 bits. Estos están documentados en los estándares ISO y 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á tu respuesta!

Después de haber revisado sus registros, el CRC es el CCITT. El primer byte 0xd6 está excluido del CRC.

Answer 2

Tendrías que 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 verificación. Por ejemplo, algunos algoritmos omiten espacios en blanco, lo que conduce a resultados diferentes.

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

Answer 3

Puede que no sea un CRC, podría ser un error al corregir un código 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 supera los 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 esté en lo cierto al decir que es algún tipo de CRC.

Answer 4

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

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