王小云 密碼學(xué)家。1966年8月16日出生于山東諸城。1993年于山東大學(xué)數(shù)學(xué)系獲得理學(xué)博士學(xué)位。山東大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院教授。清華大學(xué)長(zhǎng)江學(xué)者特聘教授。
王小云主要研究領(lǐng)域?yàn)槊艽a算法分析與設(shè)計(jì)。自1996年以來(lái)主要從事Hash函數(shù)的分析與設(shè)計(jì)，相繼破解了一系列國(guó)際通用Hash函數(shù)算法。發(fā)表論文約20篇。其中近兩年發(fā)表關(guān)于Hash函數(shù)碰撞攻擊的論文7篇。2005年以來(lái)論文被他引149次。SCI刊物引用57次。
?
國(guó)際通用Hash函數(shù)的破解
Hash函數(shù)是密碼學(xué)研究領(lǐng)域三類主要算法之一，它是數(shù)字簽名以及其許多密碼學(xué)應(yīng)用的關(guān)鍵技術(shù)。自1990年以來(lái)，國(guó)際通用的Hash函數(shù)算法主要有MD4、HAVAL、 RIPEMD、 RIPEMD-160、 MD5、SHA-1、SHA-2。王小云教授主要破解的算法有MD4、HAVAL-128、 RIPEMD、MD5、SHA-1。Hash函數(shù)主要分MDx與SHAx類，以下圍繞這兩類算法描述Hash函數(shù)破解理論的主要突破點(diǎn)及研究成果。
1）MDx類Hash 函數(shù)破解理論與技術(shù)
- 比特追蹤法? ?
比特追蹤法是一種獨(dú)特、新穎的能有效控制及消除雪崩效應(yīng)的方法，從而使弱密碼體制達(dá)到最小雪崩效應(yīng)，并具有特殊的輸出差分。該方法首次提出了帶比特進(jìn)位的準(zhǔn)確差分的思想，利用比特進(jìn)位以及比特追蹤消除變化比特，從而有效消除算法雪崩效應(yīng)。利用布爾函數(shù)代數(shù)特性，推導(dǎo)差分路線以及碰撞路線成立的準(zhǔn)確的前提條件。通過(guò)添加控制條件控制算法的額外雪崩，用概率統(tǒng)計(jì)方法，最優(yōu)化方法快速尋找Hash函數(shù)破解路線。比特追蹤法能夠?qū)ふ页龆鄶?shù)的Hash函數(shù)的一大類能夠產(chǎn)生碰撞的的消息對(duì)。? - 確定了碰撞路線的精確的前提條件
相比于國(guó)際上分析Hash函數(shù)常用的差分分析，該研究提出不同的差分分析技術(shù)--帶比特進(jìn)位與正負(fù)號(hào)的模差分分析技術(shù)，不僅給出碰撞差分，而且確定了所有變量差分變化的比特?cái)?shù)、比特位置以及比特的準(zhǔn)確值。這種精確的差分結(jié)合圈函數(shù)特性可以推出碰撞差分成立的一組充分條件。一旦推出碰撞差分的前提條件，那么就可以采用兩種明文修改技術(shù)使得多數(shù)條件以1的概率成立，從而大大提高碰撞概率。 - 提出了將概率條件轉(zhuǎn)變成確定條件的明文修改技術(shù)
通常攻擊方法成功的充分條件分為1/2概率成立的概率條件和1概率成立的確定條件，攻擊方法的效率是由概率條件的個(gè)數(shù)確定。為了能提高尋找碰撞的概率，就需要將第二圈的許多概率條件修改成確定條件。為此提出了基本明文修改技術(shù)與高級(jí)明文修改技術(shù)。這兩種明文修改技術(shù)在所有被破解的Hash函數(shù)算法中起到提高碰撞概率的強(qiáng)功效作用。
基本明文修改技術(shù)----MDx的碰撞概率等于比特追蹤法找到碰撞差分的概率。一般Hash函數(shù)算法包含3-4圈，不妨假設(shè)4圈，因此碰撞差分的概率為4圈的差分概率的乘積。基本修改技術(shù)可以使修改后的兩個(gè)明文在第一圈的差分以1的概率成立。因此經(jīng)過(guò)基本明文修改技術(shù)后碰撞概率僅相當(dāng)于3圈的差分成立概率。
高級(jí)明文修改技術(shù)-----在保證第一圈的前提條件不變的情況下，使得第二圈的多數(shù)條件或者部分條件經(jīng)過(guò)修改后滿足碰撞要求。由于Hash函數(shù)中每個(gè)明文字都要出現(xiàn)在每一圈的算法中，如何保證明文修改不僅將第二圈的某概率條件轉(zhuǎn)化成確定條件，又不破壞第一圈以及前面已經(jīng)成立的條件是高級(jí)明文修改技術(shù)要解決的關(guān)鍵理論難點(diǎn)。王小云利用局部范圍內(nèi)的部分碰撞以及小范圍內(nèi)的差分變化解決了這個(gè)問(wèn)題。 - 提出多個(gè)明文分組構(gòu)成碰撞的理論與解決方案
Hash函數(shù)總體設(shè)計(jì)原則是基于迭代法，一次迭代僅壓縮一個(gè)明文分組。在MD4, HAVAL-128,RIPEMD的碰撞分析過(guò)程中，很容易找到一次迭代的碰撞。但是由于MD5的強(qiáng)雪崩效應(yīng)，很難找到一個(gè)明文分組的碰撞。通過(guò)大量研究，探索出MD5的一種高概率的特殊差分。王小云通過(guò)精確差分的特征分析與比特追蹤法的可擴(kuò)展性，將多個(gè)具有特殊差分的明文對(duì)組合構(gòu)成一個(gè)碰撞。這一理論直接導(dǎo)致了MD5的破解。
2）SHA-x類的碰撞攻擊?
- 解決第一圈不可能差分問(wèn)題
SHA-0與SHA-1存在一種不可能差分問(wèn)題，使得每一種可能的有效的差分路線在第一圈均有段路線為不可能路線。王小云提出了一種先擴(kuò)散再收斂的理論使得不可能差分轉(zhuǎn)化成一種可能的復(fù)雜差分。該問(wèn)題的解決將SHA-0的2-4圈的碰撞概率提高約2^{20}倍，僅60圈的SHA-1的碰撞概率提高2^{90}-2^{100}倍。 - 解決碰撞路線的大量的明文比特條件
由于擴(kuò)展明文的一比特移位引起SHA-1碰撞路線中含有16個(gè)變量的50個(gè)明文比特條件難以排除，并且成為碰撞路線充分條件中不可忽略的一部分。對(duì)于以前MDx類Hash函數(shù)的破解，碰撞路線的充分條件除了很少幾個(gè)明文比特條件外，幾乎全為鏈接變量的條件。該研究提出了一種可行的解決方案。這種解決方案使得明文比特條件在第一圈中事先成立，并且不降低碰撞路線的概率。
3）第二原根的攻擊
一個(gè)安全Hash函數(shù)還應(yīng)具有抗原根性與第二原根性。根據(jù)該研究的碰撞攻擊發(fā)現(xiàn)了一種獨(dú)特的求解第二原根的方法，即弱密鑰的第二原根與選擇明文的第二原根。其基本思想為：任給隨機(jī)明文M1, 找第二原根M2滿足H(M1)=H(M2)是困難的，但是可以修改M1的很少比特得到另外一個(gè)MM1,求H(MM1)的第二原根。這意味著該攻擊方法雖然不能夠直接求第二原根，但可以求與該明文很近的另外一個(gè)明文的第二原根。該研究表明，對(duì)于MD4而言，不僅找到有意義的碰撞是非常容易的，而且找到任何有意義的原根與第二原根也是容易的。
三輪Hash函數(shù)的碰撞路線示意圖：
