密码学顶级智力较量：西电科大胡予濮教授攻破GGH密码

来源: www.snedu.gov.cn

故事得从1976年讲起。这一年，斯坦福大学的密码学家惠特菲尔德·迪菲和马丁·赫尔曼，共同发表了一篇题为《密码学的新方向》的学术论文，首次提出公钥密码体制的思想，引发了密码学史上的革命。同时，他们给出非交互密钥协商的概念，并基于离散对数问题给出了具体的实现。密钥交换的提出，颠覆了人们“不事先进行秘密共享是无法进行保密通信”的传统观念，使得用户可以在一个完全开放的信道上，进行秘密共享，实现保密通信。这一思想上的突破，成为了现今密钥交换系统的基础，被广泛应用于网络通信。与经典密码学相对应，业界将1976年定为现代密码学元年。迪菲与赫尔曼也因此获得美国计算机协会授予的2015年度“图灵奖”。
            然而，迪菲与赫尔曼的工作只是第一步，他们实现了无需交互就可以在公开信道上共享密钥，但仅限于两方。如何将这一机制扩展至三方乃至多方，一直是现代密码学遗留下来没有解决的公开问题。接下来的几十年中，全世界最聪明的密码学者们都在试图解决这个公开问题，然而研究始终未能取得突破性进展。
            直到2000年，密码学家安托尼·尤克斯利用双线性对，设计了第一个非交互的三方密钥交换协议，取得了阶段性突破，但仍无法将这种思想推广到四方以上参与者的密钥交换中。2003年，密码学家丹·波恩和艾力斯·西尔弗伯格提出多线性映射这一概念，并指出多线性映射不但可以解决多方秘密交换这一公开问题，而且还可以用于构造其他更高级的密码应用方案，但他们却无法给出具体的代数实现。在波恩和西尔弗伯格给出“在代数几何领域内不大可能构造出多线性映射”这一悲观结论后的十年间，密码学界关于多线性映射的研究成果寥寥无几。直到2013年的欧密会，三位密码天才提出的GGH方案，才让解决这个问题出现了一道曙光。
            2013年的欧密会上，时为加州大学洛杉矶分校的博士生萨吉·杰瑞格，以及IBM研究员克雷格·金特里和塞·哈勒维，共同提交了一篇论文《基于理想格的候选多线性映射方案》。该论文提出一个分级编码系统概念，并以此在理想格上实现了第一个多线性映射方案（GGH映射，取名于三位作者姓名Garg、Gentry和Halevi的首字母），进而解决了现代密码学遗留的那个公开问题，这篇论文也因此获得当年欧密会的最佳论文奖。
            “GGH多线性映射方案，对密码学界产生了深远影响，迅速在国际密码学界引发了多线性研究的热潮。”胡予濮介绍说。因为这个里程碑式的密码映射方案，不仅为密码学界遗留下来的公开问题找到了答案，也促使了其他近似多线性映射方案的构造，并有望在未来广泛应用于证据加密、广播加密、属性加密、功能加密、聚合签名等多种高级的应用场合，从而将现代密码学大大地向前推动一步！ 但由于多线性映射的特殊性，杰瑞格等人无法直接证明GGH密码方案是安全可行的，所以他们在论文中采取穷举攻击的办法，尝试了所有现存的以及他们自己提出的攻击方法，来间接表明该方案是安全的。”胡予濮介绍说，“2014年5月底，我在日本九州大学进行学术访问时，无意间了解到了这个信息，觉得很有意义，就尝试着要对它进行密码分析，也就是破解。” 

“粗看上去，杰瑞格等人提出的GGH密码映射方案，到处都是漏洞，但你就是无论如何也攻破不了它。”胡予濮回忆他初次接触GGH时说，“GGH提出者均是当今国际上顶尖的密码研究工作者，他们的方案十分完整，已经列举了各种能够想到的攻击方法，并都进行了尝试。”
            从2014年5月底到2015年2月中旬，胡予濮的脑海里全是GGH密码方案，他完全沉醉在格公钥密码、近世代数、数论、概率统计以及离散数学的世界里。“2015年春节，我是在宾夕法尼亚州特拉华河畔费城的女儿家中度过的。我妻子对我女儿说，你看你爸都苍老了许多。”胡予濮说，“一个如此有意思的问题摆在我面前没解决，茶不思饭不想，那是正常的事儿。”
            在攻破GGH密码方案的过程中，最具有纪念意义的这一天，是2015年3月7日。“这天，我一晚上都没睡觉，突然觉得GGH的结构有些不对，半夜就起来开始在纸上验算。”胡予濮兴奋地回忆起当时的情景，“到了第二天早上，还是觉得不对，又躺在床上稍微休息了一会，希望等脑子清醒了继续推算。到了中午时候，我再一步一步进行认真验证，第一次发现了GGH的漏洞确实是存在的！” 即便自己经过多次推导，已经验证了GGH存在漏洞，但胡予濮还是没有轻易下结论说攻破了这一方案。他将演算思路告诉自己的博士生贾惠文，要求他对该过程进行反复推导和验证。最终，他们得出一致结论，攻击过程正确无误，一颗悬着的心终于落地了。
            “有大半年时间，胡老师和我到处碰壁、毫无成果，各种攻击方法尝试了50种之多。有一次，我们甚至都将已经文章投递出去了，但大半夜胡老师发现推导过程有漏洞，让我赶紧撤稿。”论文第二作者，博士生贾惠文感叹地说。
            2015年3月15日，为了确认已经攻破了GGH密码方案，胡予濮将描述了攻击过程的手稿，发给了该方案的三位原作者。3月19日凌晨，该方案的第三作者塞·哈勒维代表三人回函称：“感谢您发送的手稿，您描述的攻击方式，似乎的确打破了我们在GGH一文中提到的多方密钥协商机制。”
            找到了GGH的漏洞，原作者也承认了胡予濮提出的攻击是有效的，但密码学领域的这场智力较量却刚刚开始。原来，塞·哈勒维在信中指出，胡予濮提供的第一版手稿中，攻击第一步所采用的弱离散对数攻击方法，是原文已有的。“回来找资料，发现人家在一个报告中确实提过。”胡予濮说，“但是在攻击的第二步中，我们提出了一种变形的编码/零测试工具，该工具是我们原创性工作，也是攻击的核心技术。”
            2015年4月，胡予濮和贾惠文提出组合精确覆盖问题的概念，对精确覆盖这一NP完备问题进行弱化，同时利用改进的编码/零测试工具，又将基于GGH的证据加密方案攻破。“这一方案作者之一，密码学家阿米特·萨海来信提醒说，我们只是在编码工具公开的情况下才攻破的，这一方案还可以在编码工具隐藏时进行，让我们在正式发表时进行修改。一段时间以后我们进一步深入研究，把编码工具隐藏的那种方案，也给出了有效密码分析，真正做到了无论在什么情况下，基于GGH的证据加密都不安全。”胡予濮回忆。胡予濮将修改后的论文再次给原作者发过去，换来是一片沉默。
            实际上，胡予濮及其博士生的主要成果，可以总结为四个方面：一是攻破了GGH映射的安全性假设；二是攻破了基于GGH映射的非交互多方密钥交换协议；三是攻破了基于GGH映射的第一个证据加密方案（无论编码工具公开还是隐藏）；四是给出GGH映射的两个修改方案，并对它们进行有效攻击。
            “我们的成果是对GGH的一个否定，我们打出的这套组合拳，是对GGH密码映射方案的一次釜底抽薪似的攻击。几乎可以断言，在编码工具公开的情况下，任何基于GGH映射的密码应用都是不安全的；在编码工具隐藏的情况下，至少有一个基于GGH映射的密码应用是不安全的；GGH映射很难进行简单修改来避开我们的攻击。”胡予濮说。

密码学和信息安全有什么关系？密码技术是信息安全的核心技术。胡予濮打了一个比方说，如果把信息安全当作一个有大门、有围墙的院子。要想进院子，办法有多种，可以翻墙进去，也可以推倒墙进去，还可以挖个洞爬进去，但正常合理的办法是把门上的锁打开，然后推开门走进去。密码技术就是大门上的那把锁，锁的质量好不好，虽然决定不了院子是否安全，但却是合法通行的关键。密码技术的不断研究，推动着信息安全技术的发展。
            而密码学自身又如何发展呢？胡予濮介绍说，现代密码学发展，就是密码编码学和密码分析学“相互打架”的过程，也就是设计密码和破解密码两拨人的较量。设计密码的人希望自己的密码体制难以被对手攻破，破解密码的人希望可以破解敌方的所有密码体制。“学术研究上，破解的目的是帮助原有密码变得更加完善，推动现代密码学向前发展。”
            当被询问破解GGH密码方案实际意义何在时，胡予濮介绍说：“GGH可以被看作是一种密码原语，一旦被证明安全可行，就可以在它的基础上构造出许多新的密码体制，极大地丰富未来密码应用的场景。”但胡予濮表示，他很难用一个大家都懂的生活中的场景来解释回答这个问题，他回忆了一段历史：40年前，迪菲与赫尔曼解决的两方密钥交换问题，成为今天整个互联网信息安全传输的基础；而GGH密码映射要想解决的问题，是实现非交互多方密钥交换。换句话说，如果把经典密码学比作“1”，那么迪菲与赫尔曼解决的就是“2”的问题，但却带出了“≥3”该如何解决的难题。如果“≥3”的问题真的彻底解决了，能用到什么场景中，也许我们绞尽脑汁也想不到、想不全。
            胡予濮说，现在的国际密码学界其实就是一个公开的智力角斗场。密码学家都把自己最好的研究成果发表在每年的欧密会和美密会上，但在发表之前，他们往往都会把手稿公布在国际密码研究协会在线论坛，供同行批评指正。胡予濮的手稿自公布以后，吸引了全世界研究多线性映射密码学家的目光。除了上述已经提到的三名原作者和密码学家阿米特·萨海外，还有包括日本东京技术研究所草川恵太研究员、韩国首尔大学池東杓教授，以及一些国内学者的关注。攻破多线性映射其他两个构造方案的研究团队，也对胡予濮的工作给予了肯定，说胡予濮做了他们想做而没做成的事情。
            在谈到接下来的工作时，胡予濮指出，虽然他们在破解GGH密码方案的过程中已经做了不少工作，但一切才刚刚开始，下一步他们还将对基于GGH映射的不可区分混淆进行分析。“我还想给年轻人做个榜样，更想为提高西电密码学的学术地位贡献一份力量。西安电子科技大学的密码学在国内享有盛誉，是中国密码学的发源地，有‘一肖二王’这样的老专家、老前辈，我希望大家把这块金字招牌擦得更亮！”