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

Question

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

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

Затем я попробовал несколько вариантов CRC16 , но без особой удачи.

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

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

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

файлы дампа с данными доступны, если сам вопрос не достаточен: -)

Нужна справочная документация? РУКОВОДСТВО ПО БЕЗ БЕЗОПАСНОСТИ К АЛГОРИТМАМ ОБНАРУЖЕНИЯ ОШИБОК CRC - отличная ссылка, которую я нашел после того, как задал вопрос здесь.

В конце концов, после очень полезной подсказки в принятом ответе, чем это CCITT, я использовал этот калькулятор CRC и сгенерировал контрольную сумму xored с известной контрольной суммой, чтобы получить 0xffff, что привело меня к выводу, что окончательное значение xor равно 0xffff в виде экземпляра 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

Типичные CRC:

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

Это может быть не CRC, это может быть код исправления ошибок, такой как Рид-Соломон.

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

Answer 3

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

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

Answer 4

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

Веб-сайт https://defuse.ca/checksums.htm