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

Question

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

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

Тогда я попробовал несколько вариаций CRC16, но без особой удачи.

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

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

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

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

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

В конце концов, после очень полезного намека в принятом ответе, чем это CCITT, я использовал этот калькулятор CRC, и xored сгенерировал контрольную сумму с известной контрольной суммой, чтобы получить 0xffff, что привело меня к выводу, что окончательный xor равен 0xffff instread из 0x0000 CCITT.

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

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

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

Answer 3

Это может быть не CRC, а код, исправляющий ошибки, такой как Reed-Solomon.

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

Answer 4

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

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