王小云:让网络社会更安全可信

2011-4-11 09:23 来源: 科学时报
1539 收藏到BLOG

 

  2005年,一位中国女科学家的名字震动了全球密码学界。

  她带领博士生于红波提出对两大用于数字签名经典Hash(哈希或者杂凑)算法体系(MD5和SHA-1)的破解策略,导致标准制定者美国标准技术研究所(NIST)不得不提前弃用SHA-1,启动新算法的设计。

  她就是密码研究者王小云。

  王小云的密码破解研究始于在山东大学期间获得国家自然科学基金的资助,她为此默默钻研了整整10年。如今,已是清华大学杨振宁讲座教授的王小云对密码算法的设计工作进展如何,下一个5年她又准备迎接怎样的挑战?

  从“破坏者”到“立法者”

  密码设计和破解的挑战总是交替进行,二战时那种靠转轮机械加密和手工查字典式解密的传统密码学早已成为历史,取而代之的是必须靠计算机才能处理的复杂算法。今天大量涉及商业机密、国家安全和个人隐私的原始数据只有经过加密和认证算法的转换后,才能在网上传输和存储。

  2010年12月10日,经过长达5年的征集、设计和评估,美国安全局和美国标准技术研究所宣布进入最后一轮的5种候选算法,提交者分别来自意大利、美国、瑞士、新加坡和丹麦,王小云团队没有参加。

  7天后,中国国家密码管理局在网站发布公告,正式公开中国版的新一代数字签名算法——SM3密码杂凑算法。包括术语定义、函数及算法描述、运算示例在内共11页。这是中国首度公开商用密码算法,王小云是专家组组长。

  “其实新算法我们早已经设计好了,并提交给国家密码管理局,但没有投出去发表。相信我们这个算法比国际上征集到的更有优势和特色。”王小云说。

  这正是王小云最擅长的领域——哈希函数的分析与设计。

  “哈希函数是数字签名里最基础、最核心的技术。无论你用何种数字签名,里面一定有一个哈希函数。它可以是MD5,可以是SHA-1,也可以是SM3或者SHA-3。”王小云说,“可以说我后来的成果都是从中积累而成。”

  谈到国家自然科学基金的支持,王小云充满感激。正是这种从最基础开始作研究的态度和“板凳甘坐十年冷”的毅力,使她对哈希函数潜心钻研十年终结硕果。

  王小云介绍说,一个算法的推出往往需要很长时间,而新的密码体系在研发初期都要经历一定阶段的保密。从综合各方面对于安全性的需求,到开展主体设计、优化、再设计,再到实施评估和测试,直到经过反复修订后形成最终的规范文本,这个周期通常需要好几年。“这是一个设计——分析——再设计的循环过程。”王小云说。而在各种密码算法的研发中,哈希函数的周期可能是最长的,至少需要5年时间。等到一定的保密期过后,为促进学术研究,最终一般都会公布。相比之下,标准由谁掌握更为重要。

  “一些新分析方法的出现,对密码学的研究也具有很重要的推动作用。”王小云说。如果说设计方面主要是为了满足国家网络安全的需要,分析方面,王小云则完全是站在国际学术界前沿来做的。而与此同时,王小云还带领年轻团队对她自己提出的SHA-1碰撞攻击进行了改进,继2005年给出破解效率为2的69次方运算的理论碰撞攻击后,2006年她将这一效率提高到了2的61次方。

  扎实的基础是团队信心所在

  在密码学里,加密和认证是两个完全不同的概念。加密的目的是保护数据本身的安全,使非法用户即使取得加密过的资料,也无法获取正确的资料内容。而认证的目的主要是确认用户的真实性,使系统可以依据不同的用户身份给予不同的权限。哈希函数主要用于数据认证中的数字签名,而数据加密和其他认证技术还有分组密码和流密码两种策略。作为对称密码的三大方向,三者之间有区别也有融合。

  目前世界上最流行的分组密码算法标准AES发布于2000年,用这种算法加密的数据常与另一种分组密码MAC码(消息认证码)同时传输。在运用AES对数据加密的同时,由于MAC码中往往携带有与身份有关的信息,接收方还可通过它进行校验,以验证数据的真实性。这样便可以同时完成加密和认证。有趣的是,这种采用分组方法MAC码也可以通过哈希函数构建,这就为用哈希函数方法实施攻击提供了可能。

  2009年,王小云带领博士生王薇、贾珂婷等人,在哈希函数分析的基础上提出了一种MAC破解策略。首次提出了“区分带差分路线的碰撞或几乎碰撞一般方法”,并在该年度密码学界的顶级会议——欧洲密码学大会上,给出了一个复杂度为2的97次方的有效攻击。该方法适用于对好几类重要MAC码的攻击。这无论对MAC码还是哈希函数本身的设计,无疑又提出了新的要求。

  据介绍,这种方法的秘诀在于“成功避开了哈希函数第一圈差分路线存在大量条件而造成的无概率优势的分析障碍”。对此,王小云作了一个形象的比喻:上面是安全的AES,下面是安全的AES,中间是MAC。她抓起笔迅速画了一张示意图,说:“这就好像四周都是铜墙铁壁,似乎根本无法穿透。”如果按照传统思维,到这里工作就无法进行下去了。但王小云换了思路,她采用一种“诱导”策略,对AES实施了欺骗,使程序“绕过AES,直接‘空降’到MAC里面,对MAC里的认证信息进行收集,实施破解”。该方法曾吸引了前来访问的图灵奖得主Shamir的浓厚兴趣。

  流密码是对称密码里的另一重要领域,常用于移动通信中的数据加密。2004年开始,欧洲启动了一项流密码标准工程eStream,经过公开征集,第二轮有10多个参赛算法入选。王小云带领博士生张海纳对参赛算法进行了跟踪分析,在一次会议上给出了针对其中两个算法——ABC V3 和TSC-4——的弱密钥攻击,当即导致这两项算法被直接淘汰。并且后者是当时国际上针对TSC-4的唯一有效攻击。“这主要是我的博士生所做的工作。”王小云高兴地说。

  在国家自然科学基金的支持下,现代密码学特别是对称密码里的三个重要方向——哈希函数、分组密码、流密码全部在王小云团队里建立了起来,而且实现了很好的融合。在王小云看来,其实这些不同的密码分析方法并不必拘泥于教科书上的分类,在一定层次上都是可以交叉的。“关键是要能进入一定的深度后再来看,就很容易打通。”“另外很重要的一点,经过几年的训练,我们的博士生已经成长起来。”这可以说是王小云这5年来所做的主要工作,也是她今后工作的信心所在。

  从“格”开始,迎接量子时代

  2008年举行的新兴量子密码学工作组国际会议公布了一些关于量子计算领域和量子密码学的有趣结合。不仅为经典密码学提供了一些量子计算可能的攻击,同时也给出了一些能抵抗量子计算的特别密码算法。其中一个被称作“格”的新密码体制再度引起了王小云的关注。

  实际上,王小云和“格”的初次相遇是在20多年前。“这是我一直比较惦记的一个方向。”王小云回忆说。

  那还是上世纪80年代末在山东大学念书时,她的老师潘承洞院士交给她一篇关于“低密度攻击”的论文,论文针对经典的背包密码体制给出了一个攻击,但运用的方法却是王小云从未听说过的。

  “当时我都没看懂”,王小云说。本来是针对基于旧密码体制提出来的问题,结果却催生了一个新的密码体制。一贯敏锐的直觉提醒她,这个方法将来或许会很有用。但由于当时她的主要精力在哈希函数上面,对“格”的好奇心只好先放下,这“心结”在她心里一搁就是20多年,直到她对哈希函数的研究取得阶段性成果。

  1977年,Rivest、Shamir和Adleman三位科学家联合将一个数论难题运用于密码学,缔造了历史上第一个公钥密码体制,三人因此分享了2002年的图灵奖。该算法也被以三人的首字母命名。他们巧妙利用了将一个大整数逆向分解为两个较小整数的乘积时,运算难度远远超过计算后者乘积这一原理。当大整数足够大时,由于因子分解过程接近于无穷长,从而保证了密码的不可破解。

  当三位聪明的设计者提出这一密码系统时,超级计算机每秒钟已可运算百万次,他们估计,照此速度可在4小时之内对一个50位整数进行因子分解,但要分解一个100位的数要花几乎一个世纪。因此即使考虑到计算速度可以再提高百万倍,基于200位数的密码也足够用了。然而,最新的统计数据却表明,现在连512位的RSA算法都已经不安全了,要升级到1024位才够用。正在发展的超级计算机运算能力和设计者们当时的考虑实在相去甚远。

  王小云说,格密码体制在应用上最重要的优点,就是可以抵抗量子计算。“如果量子计算机研制成功,那么其他密码体制都可能被破解,但格密码体制却破解不了。这一点已被国际密码学界公认,所以‘格’也被称为‘后量子时代’的密码体制。”

  现在,王小云已经和法国密码学界的重镇——法国巴黎高等师范学院开展了互访,准备联合探究这一新的密码体制。图灵奖得主Shamir也和她就该研究方向保持着密切交流。而Shamir正是以格的理论实施低密度攻击的第一人。

  在王小云指导下,她的学生在两三年前已开始进入这一领域,沉下心来钻研相关数学著作。“一开始确实比较难,但现在我们已经逐渐把它吃透了”,王小云相信自己的直觉。“只要坚持做下去,一定会有收获的。”

  这种深夯基础的一贯做法起了效果。在一本介绍“格数学”的经典著作中,对于一个数学命题的证明,该书作者用了整整一章,“后来我们的小组用几行就解决了”,谈起这个,王小云的喜悦溢于言表。

  和15年前相比,现在的王小云或许少了些年轻恣意,多了份担子和责任。但无论如何,这注定她的下一个5年又将是一场充满风险和乐趣的长跑。

  王小云

  清华大学高等研究院杨振宁讲座教授、密码理论与技术研究中心主任;山东大学数学与系统科学学院教授;中国密码学会密码数学理论专委会主任。