信息技術科學獎

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

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

 

國際通用Hash函數的破解

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

1)MDx類Hash 函數破解理論與技術

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

2)SHA-x類的碰撞攻擊 

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

3)第二原根的攻擊

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

  三輪Hash函數的碰撞路線示意圖:

友情鏈接: 國家科學技術獎勵工作辦公室、民政部民間組織管理局、中國社會組織網、諾貝爾獎、何梁何利基金、陳嘉庚紀念館、陳嘉庚國際學會
1996 - 2014 中國科學院 版權所有  備案序號:京ICP備05002857號   Email: 第五人格人物大全 聯系我們