Как можно угадать алгоритм контрольной суммы?

Question

Предположим, что у меня есть пакеты с 16-разрядной контрольной суммой в конце. Я хотел бы угадать, какой алгоритм контрольной суммы используется.

Для начала из данных дампа я вижу, что изменение одного байта в полезной нагрузке пакета полностью меняет контрольную сумму, поэтому я могу предположить, что это не какой-то простой XOR или сумма.

Затем я попробовал several variations of CRC16, но без большой удачи.

Этот вопрос может быть более предвзятым по отношению к криптографии, но я действительно заинтересован в любых простых для понимания статистических инструментах, чтобы выяснить, какой CRC это может быть. Я мог бы даже обратиться к drawing different CRC algorithms, если все остальное не удастся.

История Backgroud: У меня есть серийный протокол RFID с какой-то контрольной суммой. Я могу воспроизводить сообщения без проблем и интерпретировать результаты (без проверки контрольной суммы), но я не могу отправлять измененные пакеты, потому что устройство бросает их на пол.

Используя существующее программное обеспечение, я могу изменить полезную нагрузку чипа RFID. Однако уникальный серийный номер неизменен, поэтому у меня нет возможности проверять все возможные комбинации. Хотя я мог бы генерировать дампы значений, увеличивающихся на единицу, но недостаточно, чтобы сделать исчерпывающий поиск применимым к этой проблеме.

dump files with data доступны, если сам по себе вопрос не хватает :-)

Нужна справочной документации?A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS отличная рекомендация, которую я нашел после того, как задал вопрос здесь.

В конце концов, после того, как очень полезный намек на принятый ответ, чем это CCITT, я used this CRC calculator, и операции XOR генерируется контрольная сумма с известной контрольной суммой, чтобы получить 0xffff, которые привели меня к выводу, что окончательное исключающее является 0xffff instread из CCITT-х 0x0000.

Answer 1

Есть целый ряд переменных, чтобы рассмотреть для 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 

Типичные ЗПК:

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 

Первое, что нужно сделать, это получить некоторые образцы путем изменения сказать последнего байта. Это поможет вам определить количество байтов в CRC.

Является ли это «самодельным» алгоритмом. В этом случае это может занять некоторое время. В противном случае попробуйте стандартные алгоритмы.

Попробуйте изменить msb или lsb последнего байта и посмотреть, как это изменит CRC. Это даст указание на направление.

Чтобы сделать его более трудным, существуют реализации, которые управляют CRC, чтобы он не влиял на среду связи (протокол).

Из вашего комментария о RFID, это подразумевает, что CRC связан с коммуникациями. Обычно CRC16 используется для связи, хотя CCITT также используется в некоторых системах.

С другой стороны, если это метка UHF RFID, то есть несколько схем CRC - 5-битный и 16-битный. Они документированы в стандартах ISO и в листах данных 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 

Вот ваш ответ !!!!

Проработав ваши журналы, CRC является CCITT. Первый байт 0xd6 исключается из CRC.

Answer 2

Вам нужно будет попробовать все возможные алгоритмы контрольной суммы и посмотреть, какой из них генерирует тот же результат. Однако нет гарантии того, какой контент был включен в контрольную сумму. Например, некоторые алгоритмы пропускают пробелы, что приводит к разным результатам.

Я действительно не понимаю, почему кто-то хочет это знать.

Answer 3

Возможно, это не CRC, это может быть код с исправлением ошибок, подобный Reed-Solomon.

Коды ECC часто являются существенной частью размера исходных данных, которые они защищают, в зависимости от коэффициента ошибок, который они хотят обрабатывать. Если размер сообщений больше, чем около 16 байт, 2 байта ECC недостаточно, чтобы быть полезным. Поэтому, если сообщение велико, вы, скорее всего, правы, это своего рода CRC.

Answer 4

Я пытаюсь взломать подобную проблему здесь, и я нашел довольно аккуратный сайт, который возьмет ваш файл и запустит контрольные суммы на нем с 47 различными алгоритмами и покажет результаты. Если алгоритм, используемый для вычисления вашей контрольной суммы, является любым из этих алгоритмов, вы просто найдете его среди списка контрольных сумм, созданных с помощью простого текстового поиска.

Сайт https://defuse.ca/checksums.htm