差分攻擊是通過比較分析有特定區別的明文在通過加密後的變化傳播情況來攻擊密碼算法的。差分攻擊是針對對稱分組加密算法提出的攻擊方法，看起來是最有效的攻擊DES的方法（之所以說看起來，是因為差分攻擊需要很大的空間複雜度，實際上可能不如野蠻攻擊具有可操作性）。2000年以前，差分攻擊就被證明對MD5的一次循環是有效的，但對全部4次循環似乎難以奏效。但是隨著對MD5研究的進展，情況有了變化。
基本介紹
- 中文名：差分攻擊
- 外文名：differential cryptanalysis
- 定 義：一種攻擊密碼算法的方法
- 套用學科：密碼學術語
概念,工作原理,
概念
差分攻擊是通過比較分析有特定區別的明文在通過加密後的變化傳播情況來攻擊密碼算法的。差分攻擊是針對對稱分組加密算法提出的攻擊方法，看起來是最有效的攻擊DES的方法（之所以說看起來，是因為差分攻擊需要很大的空間複雜度，實際上可能不如野蠻攻擊具有可操作性）。2000年以前，差分攻擊就被證明對MD5的一次循環是有效的，但對全部4次循環似乎難以奏效。但是隨著對MD5研究的進展，情況有了變化。
2005年，王小雲、來學嘉等使用差分攻擊的思路，提出了對MD5差分的攻擊方法。該方式提出了充分條件的概念，並列出了一系列的充分條件（大約有290個），如果這些充分條件都能得到滿足，那么一定能產生碰撞。於是MD5的強抗碰撞性不能得到滿足，即該攻擊方法可以尋找訊息對
，使得
。不過，這一系列的充分條件很難同時滿足。儘管王小雲、來學嘉等進一步提出了訊息修改算法，通過修改相應比特位的方法來達到滿足這一系列充分條件，但是仍然有37條充分條件不能滿足。這就意味著，從理論上來講，該算法只需測試
條隨機訊息就可以找到完全滿足充分條件的訊息對，從而找到碰撞，即。這是一個相當有意義的成果，意味著任何人在自己的筆記本上都可以計算出碰撞的訊息對。當然，這裡產生碰撞的訊息對是隨機的。
這裡概要描述一下MD5的差分攻擊方法。
和
分別表示兩個不同的512比特的訊息，其中，
各為32比特的字串。記
是
和
之間的差，
。
表示
函式輸出的差分。差分攻擊通過計算合理的後續訊息串使最後輸出的差分為零，最終算法能產生兩個1024比特的訊息串
和
，使得
。該算法在攻擊過程中制定了差分值，算法設計者認為指定的差分值可以使最後完全消除輸出差分的機率較大。
工作原理
MD5算法的連結變數就是最後輸出的函式值，初始狀態的連結變數都是相同的，所以
。
如果確定了1024比特訊息串，根據制定的輸入差分值，也能確定。滿足輸入差分條件後，顯然，並不是任何一對1024比特訊息串和對應的都能滿足輸出差分條件。算法設計者提出了290條充分條件，只有滿足這些充分條件的一對訊息串才能滿足所有的輸入/輸出差分。充分條件是一系列對MD5連結變數的限制條件。由於MD5算法由若干輪計算構成，每輪計算都會更新連結變數，所以不同的輪都有不同的充分條件。這樣，全部的充分條件的數量達到了290條。隨機選取一條訊息，使之滿足全部充分條件的機率是微乎其微的。於是算法設計者進一步提出了訊息修改算法，該算法可以使MD5計算過程中第一輪中所有的充分條件和第二輪中一部分充分條件能夠滿足。經過訊息修改以後，仍然會有37條充分條件不能得到滿足。如果隨機選取的訊息經過訊息修改後不能滿足最後37條充分條件，就重新隨機選取新的訊息，直到滿足所有的充分條件為止。
差分攻擊的算法可以描述如下：
（1）隨機產生512比特的訊息
，作為1024比特訊息串的前半部分；
（2）使用訊息修改算法修改，使之儘量滿足充分條件；
（3）如果所有的充分條件都滿足，則計算MD5的輸出並將其作為後半部分的連結變數，如果不滿足，則回到第（2）步，重新隨機選擇；
（4）隨機產生512比特的訊息
，作為1024比特訊息串的後半部分；
（5）使用和前半部分相同的方法計算後半部分的輸出。需要注意的是，後半部分計算使用的連結變數初始值為前半部分的輸出。
