Collision-Resistance
CRC32 生日攻擊是否與輸入無關？
我有一個配置表，其中儲存了系統的所有設備和相應的序列號：
|------------------------|---------------------------|--------------------------| | # | Device type (1 byte) | Serial number (4 bytes) | |------------------------|---------------------------|--------------------------| | 1 | 0x11 | 0x???????? | |------------------------|---------------------------|--------------------------| | 2 | 0x00 | 0x00000000 | |------------------------|---------------------------|--------------------------| | 3 | 0x33 | 0x???????? | |------------------------|---------------------------|--------------------------| | 4 | 0x22 | 0x???????? | |------------------------|---------------------------|--------------------------| | 5 | 0x44 | 0x???????? | |------------------------|---------------------------|--------------------------| | 6 | 0x00 | 0x00000000 | |------------------------|---------------------------|--------------------------| | ... | ... | ... | |------------------------|---------------------------|--------------------------| | 30 | 0x11 | 0x???????? | |------------------------|---------------------------|--------------------------| | 31 | 0x00 | 0x00000000 | |------------------------|---------------------------|--------------------------|在配置表中，可能只有四種不同的設備類型。這意味著當我更換設備時，只有序列號會改變。由於系統中插入了新設備，某些行可能為空，並且稍後可能會填充設備類型和序列號。單個設備的儲存行不可預測。
我想通過配置表計算CRC32（只有設備類型和序列號），這意味著 $ n = 2^{1240} + 1 $ 和 $ k << n $ 對於 CRC32 ( $ b = 32 $ 位和 $ k = 2^b $ ）。校驗和的目的是檢測配置的更改（例如，通過恆定設備類型更改序列號）。在序列號的情況下，只有單個位可以更改。我擔心 CRC32 的衝突機率太高，以至於我沒有檢測到配置的變化。
經過一些Google搜尋後，我發現了生日問題：
- https://stackoverflow.com/questions/14210298/probability-of-collision-when-using-a-32-bit-hash/14217471#14217471
- 具有 256 位輸出的雜湊函式發生衝突的機率是多少？
- https://stackoverflow.com/questions/1515914/crc32-collision
我的理解會告訴我CRC32對於我的案例來說已經足夠了。
儘管如此，我仍然有一些問題：
- 我可以使用 CRC32（CRC 不等於雜湊）將生日問題/攻擊應用於此輸入值嗎？
- 生日問題/攻擊是否獨立於固定長度輸入？
- 空行增加校驗和的抗碰撞性的最佳值是多少？
校驗和的目的是檢測配置的更改（例如，通過恆定設備類型更改序列號）。在序列號的情況下，只有單個位可以更改。
實際上，生日問題並不真正適用於 CRC。CRC 不像隨機函式。
出於您的目的，它比隨機函式更好。CRC-32 的特性是，如果您所做的更改僅限於 4 個連續字節，則生成的 CRC 將始終更改。
因此，如果配置中的唯一變化是對單個 4 字節序列號的更改（並且其他所有內容都相同），那麼 CRC-32 將始終檢測到更改（即使更改不止一位，這仍然是正確的）的序列號）。
當然，如果配置中的其他內容髮生了變化（例如，如果兩個序列號發生了變化），則不必如此。