Elephant-Delirium算法安全性分析.docx

? ? Elephant-Delirium算法安全性分析 ? ? 侯铖安,刘美成 (1. 中国科学院信息工程研究所 信息安全国家重点实验室,北京 100093;2. 中国科学院大学 网络空间安全学院,北京 100093) 现代密码学发展至今，已经衍生出对称密码学和非对称密码学(公钥密码学)两大方向。它们的主要区别是在对称密码算法中，发送者和接收者共享同一个秘密密钥；而在非对称密码中，双方需要分别使用不同而又紧密相关的2个密钥。对称密码算法在效率方面具有显著的优势，而非对称密码算法则可以提供丰富的安全功能。只有将对称密码算法与非对称算法结合起来，才能满足人们对安全和效率的需求。 传输层安全(Transport Layer Security，TLS)协议综合应用了对称密码和非对称密码算法，常用于安全超文本传输协议(Hyper Text Transfer Protocol Secure，HTTPS)，在计算机网络通信安全中起着至关重要的作用。然而，TLS协议中使用的密码算法在设计和实现上存在漏洞，近年来有许多对TLS协议的攻击被提出[1-2]。这些攻击表明现有的密码算法还远远不能满足人们的安全需求。同时也带给密码算法设计者一个重要的设计原则，就是在密码算法中必须同时考虑数据的机密性和完整性，也就是认证加密(Authenticated Encryption，AE)。目前，密码学界已经在研究和标准化认证加密算法方面做出了许多努力。例如，经过 CAESAR竞赛，ASCON算法在安全和效率方面展现出了强大的实力[3]。 在医疗、分布式控制系统、物联网等新兴领域，常常需要将一些资源非常有限的设备进行连接，并协同工作。但目前广泛应用的密码算法大都是为个人电脑或服务器环境而设计，因此，不适用于资源受限的设备。在这样的背景下，轻量级密码算法应运而生。美国标准与技术研究所(National Institute of Standards and Technology，NIST)也开始公开征集、评估和标准化轻量级密码算法(Lightweight Cryptography，LWC)，以用于其他NIST 密码标准无法工作的资源受限场景。2021年3月，经过3轮筛选，NIST公布了包括 ASCON和Elephant 在内的10个算法进入最终的候选列表，并将在接下来一段时间中对这10个算法进行更全面而深入地评估。 Elephant算法是由Beyne等提交到 NIST 的 LWC 竞赛的轻量级认证加密算法[4]，并于 2020年发表在IACRTransactionsonSymmetricCryptology(ToSC)。Elephant 算法具有状态小、并行度高等特性，其底层使用了较为成熟的 Spongent结构和Keccak-f[200]置换，这些优点使得Elephant从LWC竞赛的候选算法中脱颖而出，进入到最终列表的评估。因此，分析Elephant算法的安全性具有十分重要的理论价值和现实意义。目前，除了设计者在理想置换模型下的安全分析之外，Zhou等[5]使用优化插值攻击以298.3的复杂度实现了对8轮 Elephant-Delirium实例的密钥恢复攻击，该结果于2021年4月正式发表在TheComputerJournal上，也是目前为止唯一的第三方分析。本文利用立方攻击的思想改进了这一攻击结果，将时间复杂度降到295.2。除了理论分析，本文还首次实现了对6轮Elephant-Delirium 实例的实际密钥恢复攻击。 1 预备知识 1.1 布尔函数与莫比乌斯变换 (1) 使用莫比乌斯变换可以将一个布尔函数f从它的真值表形式转换为ANF，也可以反过来从ANF转换为真值表。对于一个n元布尔函数，莫比乌斯变换需要n2n-1次异或运算。 1.2 高阶差分攻击与立方攻击 对布尔函数的每一次求导都会降低导数的代数次数[6]。因此，对于任何维数大于该函数的代数次数的子空间，其对应的导数为 (2) 对于一个特定轮数的密码算法，如果能够找到某个输入子空间，使得这个子空间的维数超过输出函数的代数次数，那么对这个输入子空间对应的输出子空间进行求和将恒等于0，也就是得到了一个零和区分器，然后可以利用这个零和区分器来实现密钥恢复攻击。不难看出，输出函数的代数次数对高阶差分攻击至关重要。但一般而言，需要很高的复杂度才能得到输出函数的准确次数。因此，在实际中人们常常只是估计输出函数代数次数的上界。对于一个轮函数的代数次数为d的密码算法，由于第二轮输入的代数次数为d，第二轮的输出函数关于第二轮输入的代数次数也为d，因此，第二轮输出函数关于第一轮输入的代数次数不超过d2，由归纳法可知，经过r轮迭代后的输出函数的代数次数不会超过dr。例如，Keccak-f[200]的代数次数为2，