基于数字映射的ACORN v3的代数度估计

抽象的

ACORN v3是一种轻量级认证加密密码，在2018年3月的CAESAR竞赛中被选为七个决赛选手之一。它适用于轻量级应用程序(资源受限的环境)。利用CRYPTO 2017提出的数字映射技术，提出了一种高效的ACORN v3代数度估计算法。分别对ACORN v3的647、649、670、704和721个初始化轮进行了新的识别攻击。到目前为止，正如我们所知，所有针对ACORN v3的有区别的攻击都是最好的。实验结果验证了算法的有效性和准确性。

1.介绍

ACORN，即ACORN v1 [1]，是一款轻量级认证加密密码，已提交给CaESAR（经过身份验证的加密竞争：安全，适用性和鲁棒性）竞争[2] 2014年。该结构基于非线性反馈换档寄存器。后来，随着微小的修改，它被更新为橡子v2 [3.]和橡子v3 [4通过加强安全。2018年3月，ACORN v3被选为CAESAR大赛的七名决赛选手之一。2019年2月，ACORN v3被列入最终的CAESAR组合，并被推荐用于轻量级应用程序用例(资源受限的环境)。ACORN v3的状态大小为293位。它使用128位的密钥和128位的初始化向量。ACORN v3的初始化包括将密钥和IV加载到状态中，并运行1792步的密码。

1．1.之前对ACORN的攻击

2014年，吴向CAESAR竞赛提交了一份名为ACORN v1的加密密码。之后，出现了一些针对ACORN v1及其调整版本ACORN v2的攻击[5- - - - - -11］．除了这些攻击外，在[12恢复128位密钥，总攻击复杂度为 ，当目标是恢复一个秘密密钥时，503发ACORN v2被攻击了。之后，通过认证的加密密码更新为ACORN v3，对安全性进行了少量修改。

到目前为止，对ACORN v3的几次攻击已经在[13- - - - - -16］．然而，到目前为止，还没有什么攻击比ACORN v3的彻底关键字搜索更好。基于立方体测试人员和d-单项检验，Ghafari和Hu在[17，18]并在676轮橡子V3随着时间的复杂性提出了实际的区分攻击 ．这是迄今为止最著名的区别攻击回合减少变种ACORN v3。近年来，有一些针对ACORN v3的关键恢复攻击被提出。在CRYPTO 2017, Todo等人[19]提出了对647、649和704轮ACORN v3的可能的密钥恢复攻击，在这种攻击中，不能以未知的概率恢复超过1位的密钥 ， ，和 ，分别。Wang等人在[20.，21］．

1．2．数值映射

在Crypto 2017，刘[22开发了一种新技术，叫做数值映射，迭代地估计NFSR内部状态的代数上的上限。基于这种新技术，他开发了一种估算基于NFSR的密码系统的代数度的算法，并在包括颗粒状密码的攻击，包括薄膜，kreyvium和琐事-Sc作为应用。

1.3。我们的贡献

本文提出了一种有效的ACORN v3代数度估计算法。通过应用我们的算法，我们研究了ACORN v3的混合效率。当将所有的key和IV位作为初始输入变量时，结果显示ACORN v3生成的keystream位没有达到最大代数度的最大初始化轮数的下界是669(1792中)。当将所有IV位作为输入变量时，结果显示生成的keystream位没有达到最大代数度的ACORN v3的最大初始化轮数下界为708(1792中)。当将所有IV位的子集作为初始输入变量时，我们将我们的算法应用到ACORN v3以利用新的区分攻击。表中列出了一些针对ACORN v3的轮约化变体的可区分攻击1，并与前人的作品作了比较。如表所示1，我们的结果是到目前为止最着名的密码攻击。请注意，[中的三个密钥恢复攻击[19- - - - - -21]也在表格中列出1．在这些攻击中，恢复的秘密变量通常小于1位，而时间复杂性显着高。由于时间复杂性高，这些攻击是不切实际的，无法通过实验验证，并且关键恢复的成功概率难以估计，因为它们基于一些假设。与他们相比，我们的攻击具有明显更好的时间复杂性。同时，我们的攻击是确定性的，而不是统计，即我们的攻击持有概率1。

为了验证这些密码分析结果，我们对ACORN v3的轮约化变量做了大量的实验。实验结果表明，我们的识别攻击总是与我们的评估结果一致。它们是我们算法精度高的有力证据。

本文的组织结构如下。定义了一些符号，并介绍了数值映射技术2．在部分3.，给出了ACORN v3的代数度估计。本文在第一部分结束4．

2.预先素质

２．１．符号

让是具有两个元素的有限域。表示的n二进域上的-维向量空间 ．让成为所有的集合n-变量布尔函数映射成 ，,让 ．给定布尔函数的代数正规形式(ANF)f超过n变量可以唯一表示 的系数是一个常数和表示我的二进制编码的第一个数字c（所以总和跨越所有单体 ）。的代数度f，表示 ，被定义为 ，在哪里是汉明重c．因此，对于一个多元布尔函数，一个项的次数是该项中各变量的指数的和，那么多元布尔函数的代数次数是该布尔函数中所有项的次数的最大值。

2.2。立方体攻击和立方体测试仪

几乎任何密码学方案都可以用二进制域上的可调整多项式来描述 ，它包含秘密变量(如密钥位)和公共变量(如IV位)。立方体攻击，由Dinur和Shamir提出[23]在Eurocrypt 2009，是针对对称密钥密码系统的一般和强大的密码技术之一。它将流密码的输出位视为未知的布尔多项式 ，在哪里是秘密关键变量和是公共IV变量。给予任何单一哪个是变量的乘积 ，f可以表示为占有的术语的总和我和至少缺少一个变量的项我： 在哪里被称为superpoly的我在f和一组 被称为A.多维数据集．立方体攻击背后的思想是布尔多项式的和 在包含多维数据集变量的所有可能值的多维数据集上完全是 ，而这是一个随机多项式的随机函数。在立方体攻击中，秘密变量中的低度超多边形被利用来恢复密钥，而立方体测试者[24]通过区分从一个随机函数。特别是,superpoly等于一个零常数，如果代数度f在变量中我是否比尺寸小我．因此，从立方体测试仪的角度来看，基于NFSR的密码系统的代数程度的估计是构建区分攻击的有效方式。

2．3．数值映射

在Crypto 2017，刘[22开发了一种新技术，叫做数值映射，迭代地估计NFSR内部状态的代数上的上限。基于这种新技术，他开发了一种估计基于NFSR的密码系统的代数度的算法。让 ．数字映射，表示de，定义为 在哪里 ， 是的代数正规形式的系数f如前所述，和表示的n整数域上的-维向量空间 ．让 是布尔函数n变量和表示 为 ．我们称之为 一个数字学位的h如果对所有 ，在哪里 ．的代数度h总是小于或等于数值h．对于基于nfsr的密码系统，可以使用数值映射迭代估计输出位相对于内部状态的代数度。

3.ACORN v3的代数度估计

在这一节中，我们首先对ACORN v3做一个简单的描述，然后提出一个有效的ACORN v3代数度估计算法来利用新的区分攻击。

3.1。橡子V3的简要说明

本节简要描述经过身份验证的加密密码ACORN v3。ACORN v3的结构如图所示1．ACORN v3的状态大小为293位，表示 在t- 时钟。它通过使用6LFSR的不同长度61,46,47,39,37和59和一个额外的长度寄存器构成。它支持128位键和128位初始化向量。作为经过身份验证的加密方案，Acorn V3通过了4个过程：初始化，处理相关的数据，加密和最终确定。在本文中，我们只关注初始化的过程，因为我们可以攻击的轮数小于1792初始化轮。有关Acorn V3的更多详细信息，我们指的是[4］．

验证加密密码ACORN v3的初始化包括加载128位密钥( ）及128位IV ( ）进入状态，运行1792步的密码。（1)初始化状态到0.（2）让为到127年让为到127年让为让为到1535年（3）为来 ，

在t-th时钟，密码执行状态更新功能: ，给出如下:步骤1．线性反馈更新 第2步．生成keystream位 第3步．产生非线性反馈位 步骤4．用反馈位移位293位寄存器 为

3.2。橡子v3代数估计算法

在本节中，我们将提出一个使用数值映射的ACORN v3的代数度估计的有效算法，如《算法》中描述的那样1．

算法1给出一个数值度 输出功能f后N对初始输入变量进行舍入 作为输出，它给出其后第一个输出位的代数阶的上界N轮。

算法的时间复杂性1主要取决于价值N和更新函数的anf ．由于所有更新功能除了一个二次函数和六个线性功能外，算法1时间复杂度是多少 ．算法1需要存储为 ．由于初始输入变量的数量是橡子V3的常数，因此它导致可忽略的内存复杂性 ．

3．3.实验结果

通过使用算法1，我们将研究ACORN v3的混合效率和利用新的识别攻击对密码。

3.3.1。初始输入变量何时能充分混合?

通过应用算法1，研究了ACORN v3的混合效率。当将所有的key和IV位作为初始输入变量时，结果显示ACORN v3中生成的keystream位没有达到最大代数度的最大初始化轮数至少为669(1792中)。当将所有IV位作为输入变量时，结果显示ACORN v3生成的keystream位没有达到最大代数度的最大初始化轮数至少是708(在1792中)。结果如表所示2．注意，这两个结果都是ACORN v3最大初始化轮数的下界，这样生成的keystream位不会达到最大的代数度。换句话说，没有达到最大代数度的初始化轮数的真正最大值可能会更高。

此外，我们还将IV位的子集作为初始输入变量X并应用算法1到橡子v3。由于IV位被顺序地加载到第二128初始化轮中的内部状态，因此我们是一种自然的合理的想法，即我们选择后部IV位进入立方体。我们考虑在子集上详尽的搜索 所有128个IV位 ．我们发现的一些结果列于表中3.．所有这些结果都在一秒钟内与2.5 GHz Intel Pentium 4处理器的公共PC获得。在表格中3.，立方体大小d意味着立方体 在我们的攻击中被使用。至于676轮ACORN v3，当 ，最好的结果 被发现，这导致实际的区分攻击与时间复杂改进了先前的区分攻击[17的一个因素 ．此外，我们攻击的显著优势是1，而[17]基于有限卡方统计检验，其区别优势肯定小于1。至于721轮ACORN v3，当 ，最好的结果 被发现，这导致了一种有区别的攻击它的时间复杂性 ．这是我们找到的最佳结果。显然，我们的结果是到目前为止对橡子V3的圆形减少变种的最佳攻击。请注意，我们的所有攻击都是确定性的，而不是统计，即我们的攻击持有概率1。

3．3．2．实验

自从 ， ，和在表格中3.通过在一台2.5 GHz Intel Pentium 4处理器的普通PC机上进行半天内随机100个密钥的测试，验证了这些结果。所有在立方体上的647、649和670轮ACORN v3的输出 ， 和 ，分别，总是和为0。这清楚地证明了我们算法的有效性和准确性。

4.结论

本文提出了一种有效的ACORN v3代数度估计算法。通过应用该算法，我们研究了ACORN v3的混合效率，并利用了对ACORN v3的识别攻击。分别对ACORN v3的647、649、670、704和721个初始化轮进行了新的识别攻击。就我们所知，所有针对ACORN v3的有区别的攻击都是最好的。实验结果验证了算法的有效性和准确性。

数据可用性

没有数据用于支持这项研究。

利益冲突

作者声明他们没有利益冲突。

致谢

该工作得到了中国国家自然科学基金的支持，在Grants 61602514,61802437,61202437,61272488,61202491,61572516,61272041和61772547，国家加密开发基金，授予MMJJ20170125的国家密码开发基金，以及在Grant BX201700153的创新才能的国家博士后计划。

参考

1. H. Wu，“ACORN:一种轻量级认证密码(v1)。凯撒第一轮提交，2014，http://competitions.cr.yp.to/round1/acornv1.pdf．查看在：谷歌学者
2. “认证加密的竞争:安全性、适用性和健壮性”http://competitions.cr.yp.to/index.html．查看在：谷歌学者
3. H. Wu，“ACORN:一种轻量级认证密码(v2)。凯撒第二轮提交，2015，http://competitions.cr.yp.to/round2/acornv2.pdf．查看在：谷歌学者
4. H. WU，“橡子：轻量级认证密码（V3）。凯撒提交，“2016年，http://competitions.Cr.yp.to/round3/Acornv3.pdf.．查看在：谷歌学者
5. 焦磊，张斌，王明，“两种分析流密码的通用方法”，载于ISC 2015. LNC，J.Lopez和C. J. Mitchell，EDS。，Vol。9290，pp。379-396，Springer，Cham，瑞士，2015年。查看在：谷歌学者
6. M. I. Salam, K. K. H. Wong, H. Bartlett, L. Simpson, E. Dawson, J. Pieprzyk，“在认证的加密流cipher acorn中寻找状态冲突”，Tech. Rep, 2015，https://eprint.iacr.org/2015/908．查看在：谷歌学者
7. F. Lafitte, L. Lerman, O. Markowitch，和D. Van Heule，“基于sat的ACORN密码分析”，技术代表，2016年，https://eprint.iacr.org/2016/521．查看在：谷歌学者
8. D. Roy和S. Mukhopadhyay，“关于ACORN的一些结果”，技术代表，2016年，https://eprint.iacr.org/2016/1132．查看在：谷歌学者
9. P. Dey, R. S. Rohit和a . Adhikari，“ACORN单故障全键恢复”信息安全与应用杂志，第29卷，第57-64页，2016。查看在：出版商的网站|谷歌学者
10. D. K. Dalai和D. Roy，“对ACORN-v1和ACORN-v2的国家恢复攻击”NSS 2017信号，严兆强，主编，vol. 10394, pp. 332-345，施普林格，芬兰，2017。查看在：谷歌学者
11. 张晓，冯晓，林丹，“认证密码ACORN v2的故障攻击”，《计算机科学与技术》安全和通信网络，第3834685篇，16页，2017年。查看在：出版商的网站|谷歌学者
12. M. I. Salam，H.Bartlett，E. Dawson，J.Pipprzyk，L.Impson和K. K.-h。Wong，“调查经过身份验证的加密流密码橡子的立方体攻击，”2016年ATIS航站。CCIS，巴顿和G.李，埃德。，卷。651, pp. 15–26, Springer, Singapore, 2016.查看在：谷歌学者
13. A. A. Siddhanti, S. Maitra和N. Sinha，“ACORN v3的某些观察和对TMDTO攻击的影响”空间2017. LNC、S. Ali、JL。丹吉尔和艾森巴斯。，卷。10662, pp. 264–280, Springer, Cham, Switzerland, 2017.查看在：谷歌学者
14. Lin D.，“acorn在非重用设置中的密码分析”，载于Inscrypt 2017。信号，X.陈，D.林和M. Yung，EDS。，Vol。10726，pp.342-361，Springer，Cham，瑞士，2017年。查看在：谷歌学者
15. 张晓，冯晓，林丹，“ACORN v3的故障攻击”电脑杂志(第61卷第1期)8, pp. 1166-1179, 2018。查看在：出版商的网站|谷歌学者
16. A. Adomnicai, L. Masson, J. J. A. Fournier，“针对ACORN的实用代数侧信道攻击”，载于ICISC 2018。信号，K. Lee，Ed。，Vol。11396，PP。325-340，Springer，Cham，瑞士，2018年。查看在：谷歌学者
17. V.A.Ghafari和H. Hu，“一个新的选择IV统计区分框架来攻击对称密码，以及它在橡子-V3和谷物-128a的应用，”2017年，https://eprint.iacr.org/2017/1103.pdf.．查看在：谷歌学者
18. V. A. Ghafari和H. Hu，“攻击对称密码的新选择IV统计区分框架及其在ACORN-v3和Grain-128a中的应用”，中国环境智力与人性化计算杂志，卷。10，没有。6，pp。2393-2400，2018年，https://doi.org/10.1007/s12652-018-0897-x．查看在：谷歌学者
19. Y. Todo, T. Isobe, Y. Hao, W. Meier，“基于除法性质的立方体攻击非黑箱多项式”，载于密码2017。信号，J. Katz和H. Shacham，Eds。，Vol。10403，pp。250-279，Springer，Cham，瑞士，2017年。查看在：谷歌学者
20. Q. Wang, Y. Hao, Y. Todo, C. Li, T. Isobe, and W. Meier， " Improved division property based cube attacks using algebraic properties of superpoly "，载于Crypto 2018，LNCs， H. Shacham和A. Boldyreva, Eds。，卷。10991, pp. 275–305, Springer, Cham, Switzerland, 2018.查看在：谷歌学者
21. Q.王，Y. Hao，Y. Todo，C. Li，T.Iveobe和W.Meier，“改进的分部属性的立方体攻击利用Superpoly（完整版）的代数属性，”2017年，https://eprint.iacr.org/2017/1063．查看在：谷歌学者
22. Liu M.，“基于nfsr的密码系统的程度评估”，载于密码2017。信号，J. Katz和H. Shacham，Eds。，Vol。10403，pp。227-249，Springer，Cham，2017。查看在：谷歌学者
23. I. Dinur和A. Shamir， " Cube attacks on tweakable black box多项式"，在Eurocrypt 2009。信号， A. Joux, Ed.， vol. 5479, pp. 278-299，施普林格，海德堡，德国，2009。查看在：谷歌学者
24. j。Aumasson, I. Dinur, W. Meier，和A. Shamir，“Cube testing and key recovery attacks on reducedround MD6 and trivium，”in工程师2009人。信号， O. Dunkelman, Ed.，第5665卷，1-22页，施普林格，海德堡，德国，2009。查看在：谷歌学者

版权

版权所有©2019 Lin Ding等人。这是分布下的开放式访问文章知识共享署名许可如果正确引用了原始工作，则允许在任何媒体中的不受限制使用，分发和再现。