攻破NIST后量子密码标准候选算法HK17研究

发布时间:2019-10-25  |  来源:数学机械化重点实验室

美国国家标准与技术研究院(National Institute of Standards and Technology,NIST)于2016年面向全球征集抗量子密码算法标准。经过近一年的征集及形式审查,NIST于2017年12月公布了69个算法作为首轮候选算法。随后,NIST启动了对入选算法的评估工作。在组织人力对入选算法进行内部评估的同时,NIST也面向全球公开征集对这些算法的外部评估。密钥交换算法是非常重要的一类密码学算法,主要是为通信双方建立临时的通信密钥,在现实中有极为广泛的应用。设计抗量子的密钥交换算法,不仅在将来可以用于应对量子计算机的威胁,而且也有助于保护当下加密的通讯内容,即使在将来量子计算机出现后,依然不能够被破解。

 

HK17是由Hecht和Kamlofsky提交到NIST的密钥交换算法,其主要基于经典的Diffie-Hellman框架,并利用八元数等超复数,来实现密钥交换。八元数由Grave和Cayley分别于1844和1845年独立发明。设计者认为,由于八元数不满足交换性和结合律,因此对其密钥交换算法最好的攻击,是穷搜建立的临时密钥,而穷搜在经典计算机模型下复杂性可以达到O(p^8),其中p为HK17所选取的有限域的大小。

 

然而,注意到每一个八元数都满足一个二次方程,Burnstein和Lange提出可以通过更有效的穷搜,将攻击复杂度从提交者声称的O(p^8)降到O(p),但对于HK17的规模较大的参数,其攻击在现实中尚不能实现。特别是,HK17的所有操作可以在关于log p的多项式时间内完成,因此,理论上,Burnstein和Lange的攻击依然是指数时间攻击,只是降低了HK17算法的安全性,但不能彻底攻破。与此同时,潘彦斌等[1]独立给出了针对HK17的时间复杂度为O?(log p)的多项式时间攻击,主要做法是对八元数的每个坐标建立方程,再利用线性化的技术得到了有限域上具有4个未知数的8个线性方程,从而用有限域上线性方程组的求解来代替遍历,从而完全攻破了该密码算法。利用此方法,他们首次在现实中实现了对HK17所有参数下的成功攻击。

 

基于上述攻击,提交者主动撤回了HK17算法。

[1] Haoyu Li,Renzhang Liu, Qutaibah M. Malluhi, Yanbin Pan, Yongge Wang, and Tianyuan Xie: Breaking HK17 in Practice. In Proc. Of ISIT 2019.