高效率强壮消息鉴别码的分析与设计

Message authentication code (MAC) is one of important tools in cryptography for protecting data integrity and data origin authentication, having wide applications in the world. Currently, most of such algorithms are designed from pseudorandom primitives. They usually offer high efficiency, but suffer from side channel attacks (SCAs). Some other MACs are constructed from unpredictable primitives, with security not relying on the secrecy of chaining values. Therefore, they are provably secure against SCAs. Unfortunately, the latter are few and current solutions run very slowly. In this program, we would try to analyze and design highly-efficient and strong MACs. On the one hand, we will weaken their security reliance on underlying primitives, and design provably secure algorithms against SCAs; on the other hand, we try to discover new practical requirements and improve algorithm efficiency. By this program, we will investigate MAC models and their relationship, analyze MAC security at both structural level and underlying level, and find out the design principle of highly-efficient and strong MACs. We will try to achieve a series of internationally influential results, and motivate our national standardization on MACs.

消息鉴别码是密码学中保护数据完整性和起源认证的重要工具之一，在现实生活中有着广泛的应用。目前，此类算法大多依据伪随机的底层模块设计，它们通常效率较高，但在侧信道攻击下安全性很弱；少数算法依据不可预测的底层模块设计，它们的安全性不依赖于内部链接值的机密性，在侧信道攻击下安全，但效率较低。本项目致力于分析与设计高效率强壮的消息鉴别码算法，一方面保证算法的可证明安全性，并在此基础上不断弱化算法安全性对底层模块的依赖，设计针对侧信道攻击安全的算法；另一方面研究提高现有算法的运行效率，同时发掘当前的新需求设计更适合于现实应用的算法。通过本项目，我们研究消息鉴别码领域各种安全模型的特点及其相互关系，分析算法的结构对其安全性的影响，研究算法底层基础模块的安全性质，并探讨高效率强壮消息鉴别码算法的设计原理。我们力争取得一批有国际影响力的成果，同时推进我国的标准化建设。

消息鉴别码算法能够保护数据的完整性和认证性，在现实通信中有着广泛的应用，是对称密码领域的一个重要研究方向。目前，此类算法或者安全强度不高（易遭受生日攻击和侧信道攻击），或者实现代价较大（多密钥、多次调用底层模块），难以满足小规模密码算法（比如说64比特分组密码）以及长周期密钥的应用需求。. 本项目致力于设计兼顾高效率和强安全性的消息鉴别码算法。我们以可证明技术为主要手段，结合具体应用环境研究消息鉴别码的安全模型及其相互关系，分析评估算法的整体结构对其算法安全性的影响，考察算法底层基础模块的统计特性，以此探究高效率强壮消息鉴别码算法的设计原理。. 在安全模型层次，我们针对侧信道攻击推出了泄露算法内部状态的安全模型，发现在此模型下绝大多数消息鉴别码算法都不再安全了，少数算法能够借助整体结构的优势保持一定安全性。特别地，我们探讨了CS认证加密模式以及相关密钥攻击下泛杂凑函数的安全性。. 在整体结构层次，我们首先提出了3kf9算法，将传统CBC-MAC的安全性提升至超越生日界；在此基础上，我们进一步优化降低其密钥量，分别提出了1kf9和1k PMAC+两个单密钥超越生日界算法；最后，我们给出了超越生日界消息鉴别码算法的通用构造方法SumMAC，并提出MLPN结构降低其实现代价。最终形成的V2MAC具备目前最优的可证明安全强度q^2L^{d+1}/2^{dn}+q^{d+1}d^{2d}/2^{dn}。在研究过程中，我们还发现了OKH、OCB-ZXY模式的安全漏洞并分别给出了攻击，并和新加坡的团队合作设计了抗相关密钥攻击的SMAC。. 在底层模块层次，我们在泄漏内部状态的模型下研究了Lai-Messay结构的轮安全性，并通过研究分支数上界，构造了一系列软件性能较高的轻量级扩散层，全面总结了对合最优扩散层的特点，并将这一设计理念延伸到了GFS-II型结构。所有这些成果推动了对称密码特别是消息鉴别码算法的研究进展，为后续此类算法的分析与设计打开了突破口。. 截止目前，在本项目资助下我们培养了四名博士生（尚未毕业），发表了5篇学术论文，另有2篇论文已录用，2篇准备投稿，还申请了一份国家专利，完成了既定目标。