信息技术科学奖

  王小云 密码学家。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圈的差分概率的乘积。基本修改技术可以使修改后的两个明文在第一圈的差分以1的概率成立。因此经过基本明文修改技术后碰撞概率仅相当于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函数的碰撞路线示意图: