Как я мог угадать алгоритм контрольной суммы?
Вопрос
Давайте предположим, что у меня есть несколько пакетов с 16-битной контрольной суммой в конце.Я хотел бы угадать, какой алгоритм контрольной суммы используется.
Для начала, из данных дампа я вижу, что изменение одного байта в полезной нагрузке пакета полностью меняет контрольную сумму, поэтому я могу предположить, что это не какой-то простой XOR или sum.
Тогда я попробовал несколько вариаций CRC16, но без особой удачи.
Этот вопрос может быть более предвзят к криптографии, но меня действительно интересуют любые простые для понимания статистические инструменты, чтобы выяснить, какой CRC это может быть.Я мог бы даже обратиться к рисование различных алгоритмов CRC если все остальное потерпит неудачу.
Предыстория истории:У меня есть последовательный RFID-протокол с какой-то контрольной суммой.Я могу без проблем воспроизводить сообщения и интерпретировать результаты (без проверки контрольной суммы), но я не могу отправлять измененные пакеты, потому что устройство сбрасывает их на пол.
Используя существующее программное обеспечение, я могу изменить полезную нагрузку RFID-чипа.Однако уникальный серийный номер неизменяем, поэтому у меня нет возможности проверить все возможные комбинации.Несмотря на то, что я мог бы генерировать дампы значений, увеличивающиеся на единицу, но этого недостаточно, чтобы сделать исчерпывающий поиск применимым к этой проблеме.
дамп файлов с данными доступны, если самого вопроса недостаточно :-)
Нужна справочная документация? БЕЗБОЛЕЗНЕННОЕ РУКОВОДСТВО По АЛГОРИТМАМ ОБНАРУЖЕНИЯ ОШИБОК CRC это отличная ссылка, которую я нашел после того, как задал вопрос здесь.
В конце концов, после очень полезного намека в принятом ответе, чем это CCITT, я использовал этот калькулятор CRC, и xored сгенерировал контрольную сумму с известной контрольной суммой, чтобы получить 0xffff, что привело меня к выводу, что окончательный xor равен 0xffff instread из 0x0000 CCITT.
Решение
Существует ряд переменных, которые следует учитывать при определении 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.
Другие советы
Вам пришлось бы попробовать все возможные алгоритмы проверки суммы и посмотреть, какой из них выдает тот же результат.Однако нет никакой гарантии, какой контент был включен в контрольную сумму.Например, некоторые алгоритмы пропускают пробелы, что приводит к разным результатам.
Хотя я действительно не понимаю, зачем кому-то хотеть это знать.
Это может быть не CRC, а код, исправляющий ошибки, такой как Reed-Solomon.
Коды ECC часто составляют значительную долю от размера исходных данных, которые они защищают, в зависимости от частоты ошибок, с которой они хотят справиться.Если размер сообщений превышает примерно 16 байт, 2 байта ECC будет недостаточно, чтобы быть полезными.Так что, если сообщение большое, вы, скорее всего, правы, что это какой-то CRC.
Я пытаюсь решить аналогичную проблему здесь, и я нашел довольно аккуратный веб-сайт, который возьмет ваш файл и запустит для него контрольные суммы с помощью 47 различных алгоритмов и покажет результаты.Если алгоритм, используемый для вычисления вашей контрольной суммы, является любым из этих алгоритмов, вы просто найдете его в списке контрольных сумм, полученном с помощью простого текстового поиска.
Веб-сайт является https://defuse.ca/checksums.htm