2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I know, but unfortanly I havn't meantion that I have to transmite the checksum and it should be as short as possible. $\endgroup$ – ge45mue Jan 11 '18 at 7:19
  • $\begingroup$ @Zlatan, I can only answer based on what was written in your post, so it's important to mention all requirements in your question. If you left something out, you can edit your question. Note: you can truncate SHA256 to any desired length, and that should solve your problem. $\endgroup$ – D.W. Jan 11 '18 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.