王小云 密碼學(xué)家。1966年8月16日出生于山東諸城。1993年于山東大學(xué)數學(xué)系獲得理學(xué)博士學(xué)位。山東大學(xué)數學(xué)與系統科學(xué)學(xué)院教授。清華大學(xué)長(cháng)江學(xué)者特聘教授。

王小云主要研究領(lǐng)域為密碼算法分析與設計。自1996年以來(lái)主要從事Hash函數的分析與設計，相繼破解了一系列國際通用Hash函數算法。發(fā)表論文約20篇。其中近兩年發(fā)表關(guān)于Hash函數碰撞攻擊的論文7篇。2005年以來(lái)論文被他引149次。SCI刊物引用57次。

?

國際通用Hash函數的破解

　　Hash函數是密碼學(xué)研究領(lǐng)域三類(lèi)主要算法之一，它是數字簽名以及其許多密碼學(xué)應用的關(guān)鍵技術(shù)。自1990年以來(lái)，國際通用的Hash函數算法主要有MD4、HAVAL、 RIPEMD、 RIPEMD-160、 MD5、SHA-1、SHA-2。王小云教授主要破解的算法有MD4、HAVAL-128、 RIPEMD、MD5、SHA-1。Hash函數主要分MDx與SHAx類(lèi)，以下圍繞這兩類(lèi)算法描述Hash函數破解理論的主要突破點(diǎn)及研究成果。

1）MDx類(lèi)Hash 函數破解理論與技術(shù)

• 比特追蹤法? ?
  比特追蹤法是一種獨特、新穎的能有效控制及消除雪崩效應的方法，從而使弱密碼體制達到最小雪崩效應，并具有特殊的輸出差分。該方法首次提出了帶比特進(jìn)位的準確差分的思想，利用比特進(jìn)位以及比特追蹤消除變化比特，從而有效消除算法雪崩效應。利用布爾函數代數特性，推導差分路線(xiàn)以及碰撞路線(xiàn)成立的準確的前提條件。通過(guò)添加控制條件控制算法的額外雪崩，用概率統計方法，最優(yōu)化方法快速尋找Hash函數破解路線(xiàn)。比特追蹤法能夠尋找出多數的Hash函數的一大類(lèi)能夠產(chǎn)生碰撞的的消息對。?
• 確定了碰撞路線(xiàn)的精確的前提條件
  相比于國際上分析Hash函數常用的差分分析，該研究提出不同的差分分析技術(shù)--帶比特進(jìn)位與正負號的模差分分析技術(shù)，不僅給出碰撞差分，而且確定了所有變量差分變化的比特數、比特位置以及比特的準確值。這種精確的差分結合圈函數特性可以推出碰撞差分成立的一組充分條件。一旦推出碰撞差分的前提條件，那么就可以采用兩種明文修改技術(shù)使得多數條件以1的概率成立，從而大大提高碰撞概率。
• 提出了將概率條件轉變成確定條件的明文修改技術(shù)
  通常攻擊方法成功的充分條件分為1/2概率成立的概率條件和1概率成立的確定條件，攻擊方法的效率是由概率條件的個(gè)數確定。為了能提高尋找碰撞的概率，就需要將第二圈的許多概率條件修改成確定條件。為此提出了基本明文修改技術(shù)與高級明文修改技術(shù)。這兩種明文修改技術(shù)在所有被破解的Hash函數算法中起到提高碰撞概率的強功效作用。
  基本明文修改技術(shù)----MDx的碰撞概率等于比特追蹤法找到碰撞差分的概率。一般Hash函數算法包含3-4圈，不妨假設4圈，因此碰撞差分的概率為4圈的差分概率的乘積?；拘薷募夹g(shù)可以使修改后的兩個(gè)明文在第一圈的差分以1的概率成立。因此經(jīng)過(guò)基本明文修改技術(shù)后碰撞概率僅相當于3圈的差分成立概率。
  高級明文修改技術(shù)-----在保證第一圈的前提條件不變的情況下，使得第二圈的多數條件或者部分條件經(jīng)過(guò)修改后滿(mǎn)足碰撞要求。由于Hash函數中每個(gè)明文字都要出現在每一圈的算法中，如何保證明文修改不僅將第二圈的某概率條件轉化成確定條件，又不破壞第一圈以及前面已經(jīng)成立的條件是高級明文修改技術(shù)要解決的關(guān)鍵理論難點(diǎn)。王小云利用局部范圍內的部分碰撞以及小范圍內的差分變化解決了這個(gè)問(wèn)題。
• 提出多個(gè)明文分組構成碰撞的理論與解決方案
  Hash函數總體設計原則是基于迭代法，一次迭代僅壓縮一個(gè)明文分組。在MD4, HAVAL-128,RIPEMD的碰撞分析過(guò)程中，很容易找到一次迭代的碰撞。但是由于MD5的強雪崩效應，很難找到一個(gè)明文分組的碰撞。通過(guò)大量研究，探索出MD5的一種高概率的特殊差分。王小云通過(guò)精確差分的特征分析與比特追蹤法的可擴展性，將多個(gè)具有特殊差分的明文對組合構成一個(gè)碰撞。這一理論直接導致了MD5的破解。

2）SHA-x類(lèi)的碰撞攻擊?

• 解決第一圈不可能差分問(wèn)題
  SHA-0與SHA-1存在一種不可能差分問(wèn)題，使得每一種可能的有效的差分路線(xiàn)在第一圈均有段路線(xiàn)為不可能路線(xiàn)。王小云提出了一種先擴散再收斂的理論使得不可能差分轉化成一種可能的復雜差分。該問(wèn)題的解決將SHA-0的2-4圈的碰撞概率提高約2^{20}倍，僅60圈的SHA-1的碰撞概率提高2^{90}-2^{100}倍。
• 解決碰撞路線(xiàn)的大量的明文比特條件
  由于擴展明文的一比特移位引起SHA-1碰撞路線(xiàn)中含有16個(gè)變量的50個(gè)明文比特條件難以排除，并且成為碰撞路線(xiàn)充分條件中不可忽略的一部分。對于以前MDx類(lèi)Hash函數的破解，碰撞路線(xiàn)的充分條件除了很少幾個(gè)明文比特條件外，幾乎全為鏈接變量的條件。該研究提出了一種可行的解決方案。這種解決方案使得明文比特條件在第一圈中事先成立，并且不降低碰撞路線(xiàn)的概率。

3）第二原根的攻擊

　　一個(gè)安全Hash函數還應具有抗原根性與第二原根性。根據該研究的碰撞攻擊發(fā)現了一種獨特的求解第二原根的方法，即弱密鑰的第二原根與選擇明文的第二原根。其基本思想為：任給隨機明文M1, 找第二原根M2滿(mǎn)足H(M1)=H(M2)是困難的，但是可以修改M1的很少比特得到另外一個(gè)MM1,求H(MM1)的第二原根。這意味著(zhù)該攻擊方法雖然不能夠直接求第二原根，但可以求與該明文很近的另外一個(gè)明文的第二原根。該研究表明，對于MD4而言，不僅找到有意義的碰撞是非常容易的，而且找到任何有意義的原根與第二原根也是容易的。

　　三輪Hash函數的碰撞路線(xiàn)示意圖：