What is the error-detection-probability of CRC

Question

I have a table which stores all serial numbers of devices in my system:

|------------------------|--------------------------|
|            #           |  Serial number (4 bytes) |
|------------------------|--------------------------|
|            1           |        0x????????        |
|------------------------|--------------------------|
|            2           |        0x????????        |
|------------------------|--------------------------|
|           ...          |            ...           |
|------------------------|--------------------------|
|           31           |        0x????????        |
|------------------------|--------------------------|

If I add a device to the system the position in the table is not predictable. If something in the system changes (e.g. add one or more devices, remove one or more devices, replace a device) I want to detect with a "high" propability that the system change. Therefor I want to use a CRC-32. In my system I have at least always 2 devices but max. 31 devcies. Meaning that the input of the CRC can vary between $2^{64}$ to $2^{992}$ different input streams.

As far as I understand:

• The minimum input should be at least 32 bits
• The most important is to use the right generator polynom. E.g.:
  • CRC-32
  • CRC-32-IEEE
  • CRC-32C
• The selection of generator polynom depends on:
  • Input stream length
  • Error-detection-feasability
  • Collision probablility
• Detection of a single bit error: All CRC's can do this
• Detection of burst errors: All $n$-bit CRC's can detect burst errors up to $n$ consecutive bits. Also meaning appending new $n$-bit to the end of the input stream.

My concerns are the collision probability of the CRC32 is to high and due to that I don't detect a change in the configuration. Therefor I want to calcualte this probabilities and my questions are:

1. Is CRC the right method to use for my use case? If not what would be the best?

2. What is the "best" generator polynom for my use case?

3. How to cacluate the error-detection-feasability or collision probability if more then 32 consecutive bits change?

4. How to cacluate the error-detection-feasability or collision probability if $x$ not consecutive (different locations in the complete input stream) bits change?

Answer 1

There's nothing in your requirements that forces you to use a CRC32. You could use any checksum. If the collision probability for a CRC32seems too high, use a different checksum.

For instance, if you use SHA256, you will never have to worry about collisions -- for all engineering purposes, you can treat them as impossible (something that will never happen in your lifetime). And then you won't need to worry about selecting generator polynomials or anything like that; someone else has done all that work for you. You just use the standard SHA256 algorithm.

---

P.S. Using a basic checksum algorithm will require you to recompute the checksum on the entire table any time you insert or delete one row. If that's too slow, there are a number of schemes to speed that up, such as a Merkle hash tree.