Subterranean-SAE 算法的条件立方攻击

美国国家标准与技术研究院(NIST)于2018年开始征集轻量级认证加密和哈希算法标准,其中Subterranean 2.0密码套件是晋级到第二轮的32个候选算法之一.Subterranean-SAE是Subterranean 2.0密码套件中的一种认证加密工作模式.2019年,刘富康等人对4轮空白轮(4 blank rounds)的Subterranean-SAE算法进行了基于条件立方的密钥恢复攻击,此攻击有效的前提假设是:当条件变量满足条件时输出代数次数为64,否则为65.但刘富康等人并没有验证该假设是否成立.借助三子集可分性理论,本文首次提出了在初始状态未知场景下评估输出代数次数的新技术,并将该技术成功应用于4轮空白轮Subterranean-SAE算法.实验结果表明,4轮空白轮Subterranean-SAE算法32个输出比特的代数次数上界为63,因此刘富康等人的密钥恢复攻击实际为区分攻击.进一步,本文提出降低立方维数、扩展立方变量选取范围的策略,并成功改进了Subterranean-SAE算法条件立方的搜索方法.利用此方法我们共搜索到24组33维立方并以此构造条件立方攻击,攻击的数据和时间复杂度分别为2^{41.8}和2^{124}.本文的条件立方攻击能够通过实验验证其有效性,并且能够正确恢复128比特密钥.在nonce不重用场景下,这是首次实现4轮缩减轮数Subterranean-SAE算法的全密钥恢复攻击.值得注意的是,本文缩减轮数的攻击并不会对Subterranean-SAE算法构成实质安全性威胁,但有助于加深对其安全性的理解.