基于MILP搜索的ANU算法积分分析.pdf

第 ３８卷第 ４期 计 算 机 应 用 研 究 Ｖｏｌ３８Ｎｏ４
２０２１年 ４月　 ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ Ａｐｒ．２０２１
基于 ＭＩＬＰ搜索的 ＡＮＵ算法积分分析
袁　征１，朱　亮１，２，赵晨曦１，２，刘宗甫１，２
（１．北京电子科技学院，北京 １０００７１；２．西安电子科技大学 通信工程学院，西安 ７１００７１）
摘　要：ＡＮＵ算法是由 Ｂａｎｓｏｄ等人发表在 ＳＣＮ２０１６上的一种超轻量级的 Ｆｅｉｓｔｅｌ结构的分组密码算法。截至
目前，没有人提出针对该算法的积分攻击。为了研究 ＡＮＵ算法抗积分攻击的安全性，根据 ＡＮＵ算法的结构建
立起基于比特可分性的 ＭＩＬＰ模型。对该模型进行求解，首次得到 ＡＮＵ算法的 ９轮积分区分器；利用搜索到的 ９
轮区分器以及轮密钥之间的相关性，对 １２８ｂｉｔ密钥长度的 ＡＮＵ算法进行 １２轮密钥恢复攻击，能够恢复 ４３ｂｉｔ
轮密钥。该攻击的数据复杂度为 ２６３．５８个选择明文，时间复杂度为 ２８８．４２次 １２轮算法加密，存储复杂度为 ２３３个存
储单元。
关键词：ＡＮＵ算法；积分区分器；比特可分性；混合整数线性规划
中图分类号：ＴＰ３０９．２　　　文献标志码：Ａ　　　文章编号：１００１３６９５（２０２１）０４０３９１１７１０４
ｄｏｉ：１０．１９７３４／ｊ．ｉｓｓｎ．１００１３６９５．２０２０．０５．０１３６
ＩｎｔｅｇｒａｌｃｒｙｐｔａｎａｌｙｓｉｓｏｎＡＮＵｂａｓｅｄｏｎＭＩＬＰ
ＹｕａｎＺｈｅｎｇ１，ＺｈｕＬｉａｎｇ１，２，ＺｈａｏＣｈｅｎｘｉ１，２，ＬｉｕＺｏｎｇｆｕ１，２
（１．ＢｅｉｊｉｎｇＥｌｅｃｔｒｏｎｉｃｓＳｃｉｅｎｃｅ＆ＴｅｃｈｎｏｌｏｇｙＩｎｓｔｉｔｕｔｅ