圖解CRC編解碼矩陣及解碼矩陣列坐標“CRC碰撞”

hotpower

實際碰撞很簡單，但必須心中虛構“2個CRC編解碼矩陣”，碰撞會在CRC解碼矩陣的列中產生。
下圖列中會看見“紅藍圈發生的碰撞”。

hotpower

實際很簡單，這要和CRC運算的規則有關系：
CRC運算由初值，權值，明文流和密文流四部分組成。
每次一個完整的CRC運算由初值，權值，一組對應的明文和密文。

特別注意：
CRC運算的結果即密文將作為下次CRC運算的初值或整個CRC運算的校驗和。

為了完成“CRC碰撞”，就至少需要2對明文和密文。
最后1對中的密文就是我們要求碰撞的校驗和。

例如(左移CRC4，權=D，想碰撞A)：

第1步設想的模板:
初值:0  輸入:YZ
權值 D  輸出:XA

根據CRC的性質，輸出中的密文X就是我們準備的“碰撞種子”。

密文X的初值=0，而且又是明文Z的初值。

第2步任選一個“碰撞種子”，如X=8.
初值:0  輸入:YZ
權值 D  輸出:8A

從下圖中的CRC解碼矩陣(CRC逆運算)，可以查表：

明文Y=左移CRC解碼矩陣D[初值0，密文8]=E
初值:0  輸入:EZ
權值 D  輸出:8A

第3步用密文8做為明文Z和密文A和CRC初值得到明文Z
初值:8  輸入:Z
權值 D  輸出:A

從下圖中的CRC解碼矩陣(CRC逆運算)，可以查表：
明文Z=左移CRC解碼矩陣D[初值8，密文A]=B
初值:8  輸入:B
權值 D  輸出:A

經過3次運算就得到了X=8,Y=E,Z=B:

填入
初值:0  輸入:YZ
權值 D  輸出:XA

得到
初值:0  輸入:EB
權值 D  輸出:8A

即第1個“碰撞種子”X=8得到明文EB，校驗和=A

同理再任選一個“碰撞種子”X=9，得到：
初值:0  輸入:6A
權值 D  輸出:9A

故EB和6A后會得到同一個校驗和A，即發生了“CRC碰撞”。

以上分解了“CRC碰撞”的過程，用工具只要填入不同的“碰撞種子”，
點擊“還原”即可得到相同的校驗和及對應的明文流。

hotpower

點擊下載16個CRC4編解碼的貼圖，可從中分析所有CRC的性質

pcbkey

支持一下