我如何猜测校验和算法？ [英] How could I guess a checksum algorithm?

问题描述

假设我有一些数据包的末尾带有16位校验和。我想猜测使用哪种校验和算法。

Let's assume that I have some packets with a 16-bit checksum at the end. I would like to guess which checksum algorithm is used.

首先，从转储数据中，我可以看到数据包有效负载中的一个字节变化完全改变了校验和，因此我可以假设它不是某种简单的XOR或总和。

For a start, from dump data I can see that one byte change in the packet's payload totally changes the checksum, so I can assume that it isn't some kind of simple XOR or sum.

然后我尝试了 CRC16的几种变化，但运气不佳。

Then I tried several variations of CRC16, but without much luck.

这个问题可能更偏向于加密，但是我对任何易于理解的统计工具来找出这可能是CRC感兴趣。如果其他所有方法都失败了，我甚至可能会转向绘制不同的CRC算法。

This question might be more biased towards cryptography, but I'm really interested in any easy to understand statistical tools to find out which CRC this might be. I might even turn to drawing different CRC algorithms if everything else fails.

背景故事：我有带有某种校验和的串行RFID协议。我可以毫无问题地重放邮件，并解释结果（不进行校验和检查），但是我无法发送修改过的数据包，因为设备将其丢在了地板上。

Backgroud story: I have serial RFID protocol with some kind of checksum. I can replay messages without problem, and interpret results (without checksum check), but I can't send modified packets because device drops them on the floor.

使用现有软件，我可以更改RFID芯片的有效载荷。但是，唯一的序列号是不可变的，因此我无法检查所有可能的组合。尽管我可以生成值递增1的转储，但不足以使详尽搜索适用于此问题。

Using existing software, I can change payload of RFID chip. However, unique serial number is immutable, so I don't have ability to check every possible combination. Allthough I could generate dumps of values incrementing by one, but not enough to make exhaustive search applicable to this problem.

转储包含数据的文件：-）

需要参考文档吗？ A CRC错误检测算法的无痛指南是我在这里提出问题后找到的很好的参考。

Need reference documentation? A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS is great reference which I found after asking question here.

最后，在接受的答案非常有用的提示之后，它是CCITT，我
使用了此CRC计算器，并用已知的校验和对生成的校验和进行异或运算得到0xffff，这使我得出结论，即最终xor是CCITT的0x0000的0xffff插入。

In the end, after very helpful hint in accepted answer than it's CCITT, I used this CRC calculator, and xored generated checksum with known checksum to get 0xffff which led me to conclusion that final xor is 0xffff instread of CCITT's 0x0000.

推荐答案

考虑对于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中的字节数。

The first thing to do is to get some samples by changing say the last byte. This will assist you to figure out the number of bytes in the CRC.

这是自制算法吗？在这种情况下，可能需要一些时间。否则，请尝试使用标准算法。

Is this a "homemade" algorithm. In this case it may take some time. Otherwise try the standard algorithms.

尝试更改最后一个字节的msb或lsb，然后看看如何更改CRC。

Try changing either the msb or the lsb of the last byte, and see how this changes the CRC. This will give an indication of the direction.

为了使操作更加困难，有一些操作CRC的实现，因此不会影响通信介质（协议）。

To make it more difficult, there are implementations that manipulate the CRC so that it will not affect the communications medium (protocol).

从您对RFID的评论来看，它意味着CRC与通信有关。通常，CRC16用于通信，尽管在某些系统上也使用CCITT。

From your comment about RFID, it implies that the CRC is communications related. Usually CRC16 is used for communications, though CCITT is also used on some systems.

另一方面，如果这是UHF RFID标签，则有一些CRC方案-一个5位的和一些16位的。这些都记录在ISO标准和IPX数据表中。

On the other hand, if this is UHF RFID tagging, then there are a few CRC schemes - a 5 bit one and some 16 bit ones. These are documented in the ISO standards and the IPX data sheets.

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中排除。

这篇关于我如何猜测校验和算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！