AEUR：基于uBlock轮函数的认证加密算法设计.pdf

2023 年 8 月 Journal on Communications August 2023 第 44 卷第 8 期 通 信 学 报 Vol.44 No.8AEUR：基于 uBlock 轮函数的认证加密算法设计 杨亚涛1,2，董辉1，刘建韬1，张艳硕1（1.北京电子科技学院电子与通信工程系，北京 100070；2.西安电子科技大学通信工程学院，陕西 西安 710071）摘 要：为了提升认证加密算法的实现效率，同时不降低算法的安全性，基于 uBlock 算法设计了一种新型认证加密算法 AEUR。首先，在分组密码算法 uBlock 轮函数的基础上，将抵抗内部碰撞攻击作为安全性目标，利用混合整数线性规划方法，搜索设计符合安全性目标的通用迭代算法结构 R(t,s)。其次，利用该结构设计了认证加密算法 AEUR，AEUR 由认证加密和解密验证两部分构成，两部分执行过程相同，不需要额外设计操作环节，从而减少算法的资源消耗。再次，通过对比轮数状态值来验证算法的正确性，采用线性攻击、滑动攻击等多种方法分析了算法的安全性。最后，采用 C 语言对算法进行了软件实现，证明所提算法具有良好的软件实现性能。结果表明，以软件运行时间计算，所提算法相比 AEGIS 和 ALE，效率分别提升了 3%和 46%；相比 AES-GCM 和 ACORN，效率分别提升了 74%和 92%，具有较好的综合性能。关键词：认证加密；分组密码 uBlock；安全性分析；软件实现 中图分类号：TN92 文献标志码：A DOI:10.11959/j.issn.1000436x.2023159 AEUR:authenticated encryption algorithm design based on uBlock round function YANG Yatao1,2,DONG Hui1,LIU Jiantao1,ZHANG Yanshuo1 1.Department of Electronic and Communication Engineering,Beijing Electronic Science and Technology Institute,Beijing 100070,China 2.School of Telecommunication Engineering,Xidian University,Xian 710071,China Abstract:In order to improve the efficiency of the implementation of the authenticated encryption algorithm without com-promising the security of the algorithm,a new authenticated encryption algorithm AEUR was designed.Firstly,based on the uBlock round function,with resistance to internal collision attacks as the security objective,a mixed integer linear program-ming approach was used to search for generic iterative component R(t,s)to meet the security objective.Secondly,the authen-ticated encryption algorithm AEUR was designed by using this component.AEUR consisted of two parts:authenticated en-cryption and decrypted verification,both of which performed the same process without the need to design additional opera-tional sessions,reducing the algorithms resource consumption.In addition,the correctness of the algorithm was verified by comparing the corresponding round state values,and the security of the algorithm was analyzed using various analysis me-thods such as linear attacks and sliding attacks.Finally,the algorithm was implemented in C language to prove the AEUR has good performance.The results show that the proposed algorithm has a better overall performance in terms of software runtime,with efficiency improvements of 3%and 46%compared to AEGIS and ALE,and 74%and 92%compared to AES-GCM and ACORN,respectively.Keywords:authenticated encryption,block cipher uBlock,security analysis,software implementation 收稿日期：20230426；修回日期：20230814 基金项目：北京市自然科学基金资助项目（No.4232034）；中央高校基本科研业务费专项资金资助项目（No.328202222）；“通信工程”“电子信息工程”国家级一流本科专业建设点基金资助项目 Foundation Items:Beijing Natural Science Foundation(No.4232034),The Fundamental Research Funds for the Central Universi-ties(No.328202222),National First-Class Under Graduate Dicipline Construction of“Communication Engineering”and“ElectronicInformation Engineering”第 8 期 杨亚涛等：AEUR：基于 uBlock 轮函数的认证加密算法设计 169 0 引言 认证加密（AE,authenticated encryption）算法在信息保护领域作用重大，能够兼顾数据的机密性和完整性。通过将消息认证码和加解密算法结合，可以实现认证标签的单向计算过程，且在加解密环节拥有足够的安全强度，以抵抗常见的密码分析。目前，主流的基于分组密码的认证加密算法主要有 2 种设计方式：一是基于分组密码的认证加密方式，二是在现有的分组密码的基础上进行设计。前者依靠设计可靠模式结构并在底层使用分组密码算法为相关的加解密和认证验证提供服务，但提供服务的过程是不可见的，底层的算法可以相对简单地进行替换，这类典型的认证加密算法有 OCB1（offset codebook）、EAX2（encryption with authen-tication for transfer）、GCM3（galois/counter mode）。随着物联网等信息产业的迅速发展，认证加密算法的需求环境也发生了很大的变化，之前的通用算法和基于分组密码的工作方式类在现有的资源受限环境下的表现不尽如人意，如 RFID（radio frequency identification）环境。直接设计类认证加密算法是指采用已验证安全性和其他性能指标的、成型的分组密码部件来进行认证加密算法的设计。这种设计方式致力于降低算法的实现代价和提升软硬件表现，因其采用消息来更新算法的状态，用于消息认证的实现代价较低。但这些算法的安全性不能通过可证明安全理论来证明，需依靠各种安全性分析方法，常见的此类型的认证加密算法有 AEGIS4、ALE（authenticated lightweight encryption）5、AEZ（advanced encryption standard-easy）6等。为获得更好的认证加密效率与安全性，本文提出了新的方案。本文的贡献如下。1)本文提出了一种认证加密算法通用结构R(t,s)。不同于已有采用 AES（advanced encryption standard）轮函数的直接设计类认证加密算法，该结构基于轻量级分组密码算法 uBlock7设计，以抵抗内部碰撞攻击为安全性目标，使用了混合整数线性规划（MILP,mixed integer linear programming）8方法，搜索确定结构中关键参数 t、s 和算法所使用的置换 P，保证该结构在 10 轮后有不少于 66 个活跃 S 盒。2)基于通用结构 R(t,s)设计了认证加密算法AEUR（authenticated encryption algorithm based on uBlock round function）。AEUR 算法的设计基于uBlock 轮函数和广义 Feistel 结构，以 4 个 uBlock轮函数和置换 P 组成了算法的轮函数，轮函数用来更新状态值，状态值保证算法的正确性。算法处理数据的过程简洁有效，从而优化了算法运行过程，减少了资源消耗。AEUR 算法对多种安全性分析方法具有充分的抵抗能力，为国产密码算法应用提供了一条新的参考途径。3)应用 SSE（streaming SIMD extension）指令集9对 AEUR 算法进行了软件实现。对 AEUR 算法进行实现速率测试，以软件运行时间计算，AEUR算法相比其他同类算法在运算速度上均有不同程度的提升，具有较好的综合性能。1 相关研究 Bellare 等10在 ASIACRYPT 2000 上提出了认证加密这一全新概念，将认证和加解密在同一算法中完成，通过共享一个密钥来实现数据的机密性与完整性。近年来，部分学者拓宽了认证加密算法的应用领域，并基于不同的经典密码算法实现了新的认证加密方式。2002 年，Rogaway11提出了基于相关数据的认证加密（ADAE,associated-data authen-ticated encryption）算法，结合 OCB 和伪随机函数PMAC（parallelizable MAC）构造了 ADAE 算法，这种认证方式在保证了明文信息的保密性和完整性同时也保证了相关数据的完整性。2008 年，Iwata12提出了一种针对区块密码的认证加密模式，其中加密部分由一个 CENC（common encryption）的密钥流生成，并结合了基于分组密码的哈希函数。2010 年，Sarkar13提出了并行认证加密模式，并与 IPMAC（improved parallelizable MAC）结合，获得新的认证加密方案。随着对认证加密领域以及应用环境的不断研究和探索，原有的认证加密方案设计思路不能很好地适应新的应用环境。同时，基于新结构和新思想的方案不断被提出。CAESAR（competition for authenticated encryption:security,applicability,and robustness）竞赛的举办大大推动了认证加密算法设计的发展，其第三轮算法的特点介绍1,4,14-16如表 1 所示。2018 年，张建等17基于 SM4 轮函数设计了认证加密算法 SMAE，该算法利用 MILP 方法构170 通 信 学 报 第 44 卷 造了消息认证码和认证加密算法。2020 年，高国强等18基于 AES 算法底层的轮函数，实现了一种基于 AES 轮函数的认证加密算法 AMRAE。这2 种算法都是基于现有的分组密码轮函数来设计的，但安全性分析与实现效率尚有不足。本文综合前述经验，分析了现有方案的不足，在上述学者的研究思路上进行了扩充改进，采用 2019 年我国第一届密码算法设计竞赛中获得一等奖的分组密码算法 uBlock 设计认证加密算法 AEUR，其在安全性和实现速率方面较 SMAE 和 AMRAE均有不同程度的提升，为国产认证加密算法提供了一种新的参考。2 基础知识 2.1 uBlock 轮函数 uBlock 算法7的分组和密钥长度为 128 bit 和256 bit，记为 uBlock-128/128、uBlock-128/256、uBlock-256/256。本文采用 uBlock-128/128。uBlock 算法对差分分析、线性分析、积分分析、不可能差分分析等密码分析方法都有相应的安全冗余。uBlock 算法的密钥扩展算法可以通过随用随生成的方法得到轮密钥，这样能够减少算法需要的存储空间。在本文中，b表示循环左移b bit，32b表示以 32 bit 为单位循环左移b bit。uBlock 算法整体采用 SPN（substitution per-mutation network）结构，轮函数如图 1 所示。输入n bit 明文x和轮密钥ikR，经异或（）及 S 盒等操作，分别进入向量置换 PLn和 PRn，与ikR异或后，输出n bit 密文Y。uBlock 函数由4n个相同的4 bit S盒构成，如表2所示。图 1 uBlock 算法轮函数 表 2 uBlock 算法 S 盒 x S(x)x S(x)x S(x)x S(x)0 7 4 b 8 f c 0 1 4 5 a 9 e d 3 2 9 6 d a 1 e 2 3 c 7 8 b 6 f 5 PLn和PRn都是16n个字节的向量置换，变换参数如表3所示。AEUR采用PR128，其表达式为 8888128PL:0,10,1 0126701267(,),yy yyyzz zzz 表 3 PL128和 PR128变换参数 向量置换 变换参数 PL128 1,3,4,6,0,2,7,5 PR128 2,7,5,0,1,6,4,3 表 1 CAESAR 竞赛第三轮算法特点 算法 算法类型 算法特点 AEGIS4 直接设计 整体采用序列密码框架，由初始化、加密、标签生成过程构成，底层算法采用 AES算法的轮函数，能够使用 AES 指令集 DEOXYS14 直接设计 利用可调分组密码算法 Deoxys-BC 作为底层算法，以 AES 算法为基础来设计可调分组密码，进一步结合工作方式来设计认证加密算法 ASCON15 直接设计 采用 Sponge 结构中的 Duplex 结构来设计，置换为 SP 结构中的迭代函数，轮函数包含常数加、替换层和扩散层 ACORN16 直接设计 采用序列密码来设计，面向比特，包含 LFSR（linear feedback shift register），具有轻量级硬件实现优势，软件实现性能较好 OCB1 分组密码工作模式 OCB 算法并行运算性好，安全性可以得到证明；但 OCB 不能抵抗初始向量值（Nonce）重用，没有超越生日攻击的安全界 COLM/AES-COPA/ELMD14 分组密码工作模式 利用 AES 分组密码算法来构造，可以通过 AES 指令集实现软件优化 第 8 期 杨亚涛等：AEUR：基于 uBlock 轮函数的认证加密算法设计 171 2.2 混合整数线性规划 MILP8是在一定约束的条件下对目标函数进行优化，遵循线性规划的优化问题方法。用MILP方法对密码算法进行差分分析和线性分析，就是通过设定相应的约束条件，将活跃S盒的个数之和最小设定为目标函数，并对其求解。依据S盒的相关特性结合约束条件，再将最小活跃S盒的数量作为目标函数的构造条件，设计目标函数的数值即所求的最小值。完成上述构造后，就可以用求解器对此MILP问题进行求解。此外，当输入阶段差分和临时变量都被设为0或1时，对于求解器的求解速率更加友好19。3 基于 uBlock 轮函数的通用结构设计 R(t,s)结构以uBlock算法轮函数和广义Feistel结构为基础，其安全性目标为在密钥长度为128 bit时，可以抵抗内部碰撞攻击。其构建过程采用了MILP方法，搜索符合安全性目标的结构参数t、s和置换P，其中，t为uBlock算法的执行次数，s为轮函数输入信息的长度，长度表示消息的块数。3.1 安全目标 因为R(t,s)是基于分组密码算法轮函数和分组密码算法结构所设计的通用结构，不具备算法的完整性，从算法分析的角度来看，可以从某些分析方法的角度来设定其安全性目标。在AEUR算法通用结构的设计中，主要考虑的是对内部碰撞攻击的防御。碰撞攻击20利用生日悖论，分析算法本身或其等效结构，结合与轮密钥之间的对应关系来获得区分属性，继而分析得到密钥信息。碰撞攻击大大减少了原始穷举攻击的计算量。对于R(t,s)结构，当存在2个不同消息的差分时，引入初始差分，经过多轮迭代，内部状态差分为0。R(t,s)的密钥为128 bit，当攻击复杂度大于128 bit时，对该结构的攻击是无效的。uBlock算法使用的4 bit S盒的最大差分概率7为22，为满足上述安全性条件，在进行碰撞攻击时活跃S盒的个数不能少于66个。3.2 通用结构 R(t,s)R(t,s)结构是一种通用的、可迭代的认证加密算法轮函数结构，采用uBlock算法的轮函数，结合广义Feistel结构，如图2所示。置换P是区别于uBlock轮函数的向量置换PLn和PRn的新的置换，322iFZ表示消息，S0S7表示状态值。MesHandl为消息iF与状态值分别进行异或运算。图 2 R(t,s)轮函数结构 定义 1 要对结构R(t,s)的效率进行计量，需要确定一个指标ratets，即处理32 bit的消息块需要的uBlock轮函数的个数。R(t,s)的效率与rate相关性强，需要通过对结构的设计细节进行研究，以选取更高效率的结构。3.3 MILP 模型搜索实验结果 假设置换P基于32 bit，给出t、s和相应约束，结合MILP方法验证是否找到符合条件的置换P。当rate=1时，存在只有一个活跃S盒的差分路径使结构发生内部碰撞17。下面证明rate至少为2时结构R(t,s)才可能避免内部碰撞。在搜索了t=1和t=2的4!和8!个置换后，发现并没有符合安全目标的结构；当t=3时，开始出现满足结构安全的轮函数。对于R(3,1)，找到了多个可用的P，如P=(1,2,3,4,5,6,7,8,9,10,11,0），此时P被设为一个循环移位，进行10轮后，活跃S盒的个数达到70，满足安全性目标，但其rate=3，需要寻找效率值更高的P。在对R(3,2)、R(3,3)、R(4,1)、R(4,2)、R(4,3)、R(4,4)进行搜索后发现，以上结构均存在满足安全性目标的P，其中R(3,3)、R(4,4)的rate=1，效率较高。但是R(3,3)的算法全扩散轮数表现弱于R(4,4)，故选择R(4,4)18。表4列出了部分使R(4,4)符合安全性目标的置换P及其活跃S盒个数。在满足安全性目标的前提下，综合各个结构的实现效率，P5的实现效率和安全性均能够达到通用结构对认证加密算法实现的172 通 信 学 报 第 44 卷 要求，其扩散和混淆特性也满足作为认证加密算法部件的要求，经验证P5的综合性能优于其他置换P，故本文方案选取P5作为通用结构的置换P。表 4 部分使 R(4,4)符合安全性目标的置换 P 及其活跃 S 盒个数 序号 置换 P 活跃 S 盒个数 P0 11,5,7,9,14,8,12,1,15,0,3,2,10,6,13,4 67 P1 6,0,8,13,1,15,5,10,4,9,12,2,11,3,7,14 67 P2 9,7,4,11,6,0,3,8,14,5,2,13,1,15,10,12 66 P3 0,15,11,8,12,9,6,3,13,1,2,4,10,7,5,14 66 P4 7,2,12,5,8,4,6,11,14,9,1,15,13,3,10,0 68 P5 6,11,12,9,10,2,15,3,0,13,1,4,7,14,8,5 66 3.4 通用结构 R(4,4)差分安全性分析 R(4,4)结构的安全目标是抵抗内部碰撞攻击。考虑到该结构作为认证加密算法的主要部件，其安全性需要从更多方面进行检验，可以通过差分分析来实现。差分分析针对明文差分对和相应的密文差分，尽可能地获得更多的密钥信息。对于R(4,4)结构，建立MILP差分模型，搜索该结构的高概率差分路径，该结构中存在异或和移位2种线性操作。在构建差分模型过程中，移位只是单纯地改变了差分值的位置，所以不需要进行多余限制。对于比特异或abc，可以采用等式2abcd21结合R(4,4)结构的差分性质来求解，过程中还需利用MILP进行约束，并用Gurobi求解器求解。按照R(4,4)结构进行差分路径分析，在每一轮都选取差分值与上一轮差分值相同的差分，构成差分路径，最终求得一条长度和精确度符合要求的差分路径概率。搜索结果如表5所示。表 5 R(4,4)结构差分路径概率 轮数 差分路径概率 6 272 7 297 8 2123 9 2152 从上述结果可知，当R(4,4)结构执行9轮时，差分路径概率为2152，满足设定的差分复杂度安全目标128 bit，因此R(4,4)结构从理论上可以抵抗差分分析，且不存在可行的差分路径。4 认证加密算法 AEUR 设计 AEUR算法主要考虑底层算法的选取原则、通用结构设计和整体工作流程与安全性3个方面。首先，对于底层算法uBlock，主要关注其轻量级的设计思路和随用随生成的密钥扩展算法，且能够抵抗内部碰撞攻击。其次，对于通用结构R(t,s)的设计，主要关注其安全性目标和使用MILP方法搜索时的参数结果，且R(t,s)结构可以根据底层算法的安全性需求和运行特点，选择不同的置换P和底层轮函数个数，适用性广泛。最后，对于整体认证加密算法工作流程，主要考虑其认证加密过程和解密过程中对消息数据处理的运算效率和正确性。AEUR算法的设计思路如图3所示。图 3 AEUR 算法的设计思路 AEUR算法采用R(4,4)作为轮函数，密钥、初始向量和随机常数作为状态值的初值，利用轮函数进行状态值的更新，利用状态值对数据进行加解密和生成标签操作。4.1 AEUR 算法认证加密过程 AEUR的输入包括128 bit的密钥1280,1k、初始向量1280,1N、相关数据0(,iAAA 41)dA、041(,)jqMMMM，32,0,1ijA M，其中M为明文，d和q为相关数据和明文填充对应的轮函数轮数。本文中表示异或运算、表示与运算。相关数据包含发送者、发送时间等信息。AEUR算法的输出为密文C，C的长度与填充后明文M的长度相同；128 bit长度的标签tag，128tag0,1。AEUR的每一轮都处理4个32 bit的数据块，每一轮 状 态 更 新 函 数 记 为Round(,)iiS Y，其 中4414243,iiiiiiiiiYYYYY，Y代表相关数据A和M等信息，按照算法不同阶段进行赋值。状态值集合iS是由16个32 bit的字构成的数据集合，记为0115,iiiiSSSS，算法的轮函数结构如图4所示。1)初始化 首先进行相关数据与明文的填充。本文使用PKCS5算法进行数据填充。PKCS7算法是目前常用加密算法都遵循的数据填充标准，PKCS5算法作为PKCS7算法的子集算法，在数据块大小blockSize上固定为128 bit，即数据始终会被切割为128 bit的数据块。然后计算需要填充的长度，由需要填充的字节数目来决定要填充的内容。此外，为了解决加解第 8 期 杨亚涛等：AEUR：基于 uBlock 轮函数的认证加密算法设计 173 密时对于数据填充的处理问题，当数据本身长度满足128n bit时，依据PKCS5的规则，在数据的尾部仍需要填充8个字节的内容，此时填充内容为0 x08。将k和N赋值到状态值中，并利用轮函数更新16轮状态值，再对相关数据进行初始化，如算法1所示。算法 1 AEUR算法初始化 输入 k，N，相关数据041(,)idAAAA RC1=(0 x31415824000000000000000000000000)RC2=(0 x53589793000000000000000000000000)输出 算法状态值01,iiiijSS SS 00000123,SSSSk；00004567,SSSSN；00008910111,RCS S SS；0000121314152,SSSSRC；for 0i to 16 Round(,0)iS end for for 0i to1d，16Round,iiSA 0123,iiiiiAAA AA end for 2)明文信息的处理 将明文信息填充后按32 bit分块，利用状态值与明文异或来生成密文，之后明文进行状态值更新，重复q1轮。具体算法过程如算法2所示。算法 2 AEUR算法明文信息处理 输入 明文M 输出 算法状态值16 d iS for 0i to 1q 4404812iiiiiiCMSSSS；414115913iiiiiiCMSSSS；4242261014iiiiiiCMSSSS；4343371115iiiiiiCMSSSS；16Round,d iiSM；4414243,iiiiiiiiiMMMMM end for 3)标签的生成 首先利用相关数据和消息长度adlen和msglen更新一轮状态值；然后迭代更新16轮；最后利用状态值生成标签tag。具体过程如算法3所示。算法 3 AEUR算法标签生成 输入 相关数据长度adlen，明文信息长度msglen，状态值16 q d iS 输出 标签值tag 1264,adlenM M；3464,msglenMM；16Round(,)q d iSM ；17128Round(,0)i q dS ；图 4 AEUR 算法的轮函数结构 174 通 信 学 报 第 44 卷 0481215913261014371115|iiiiiiiiiiiiiiiiTSSSSSSSSSSSSSSSS return 041,qCCC,tag 4.2 AEUR 解密认证过程 AEUR的解密认证算法输入为密钥k、初始向量N、相关数据A和密文C；输出为明文M或停止符，认证解密过程由初始化、密文信息处理和标签生成过程构成。解密认证过程的初始化、密文信息处理与加密认证过程的输入输出相同。最后生成状态16 dS。解密过程。利用状态16 dS和密文0(,CC 41)qC生成M，同时更新状态。具体算法如算法4所示。算法 4 AEUR算法密文信息处理 输入 状态值16 dS，密文C 输出 状态值16 d iS，明文信息M for 0i to 1q 4481240iiiiiiMCSSSS；414191351iiiiiiMCSSSS；4242101462iiiiiiMCSSSS；4343111573iiiiiiMCSSSS；16Round,d iiSM；4414243,iiiiiiiiiMMMMM end for 认证过程。在解密过程结束后可以得到状态值16 dqS，之后利用加密认证过程中的标签生成算法，得到标签tag，如果标签值tag与之前加密认证过程中生成的标签值tag相同，那么解密成功且通过认证，即解密验证算法执行成功，输出明文M；否则解密验证过程失败，输出停止符。4.3 基于通用结构R(t,s)的认证加密算法设计思路 R(t,s)结构是能够满足不同算法使用的通用型迭代结构，满足分组密码算法要求的混淆和扩散特性，且可以保障认证加密算法的安全性和正确性。采用这种结构生成的认证加密算法总体类似于大型序列密码算法。该结构通过并行操作可以大大提升运行效率，根据底层算法的安全性需求和运行特点，可以选择不同的置换P和底层轮函数个数，从而构造出满足安全性和实用性要求的结构，继而将其进行组合排列，满足算法的设计需求。5 正确性证明 加密认证和解密验证使用了相同的初始化、明/密文信息处理和标签生成过程，如算法5和算法6所示。算法 5 AEUR算法加密过程 输入 明文M 输出 算法状态值16 d iS for 0i to 1q 4404812iiiiiiCMSSSS；414115913iiiiiiCMSSSS；4242261014iiiiiiCMSSSS；4343371115iiiiiiCMSSSS；16Round(,)d iiSM；4414243,iiiiiiiiiMMMMM end for 算法 6 AEUR算法解密过程 输入 状态值16 dS，密文C 输出 状态值16 d iS，明文信息M for 0i to 1q 4481240iiiiiiMCSSSS；414191351iiiiiiMCSSSS；4242101462iiiiiiMCSSSS；4343111573iiiiiiMCSSSS；16Round(,)d iiSM；4414243,iiiiiiiiiMMMMM end for 由于算法的加解密与状态值紧密相关，如果在任意某一轮数时，算法在加解密过程中产生的状态值iS相同，则算法满足正确性。执行AEUR算法时，其加密与解密的初始化过程、相关数据处理过程完全一致，每一轮产生的状态值都相同，因此AEUR算法满足正确性。6 安全性分析 现有的可证明安全理论虽然可以对基于分组密码的认证加密模式进行安全性分析，但对于直接设计的认证加密算法，不能给出适合的安全假设。目前，直接设计的认证加密算法普遍使用针对密码算法的安全性分析方法22。为了让AEUR算法具备能够抵抗密钥恢复攻击和伪造攻击的能力，保证攻第 8 期 杨亚涛等：AEUR：基于 uBlock 轮函数的认证加密算法设计 175 击的复杂度大于2128，做出如下约束18。1)初始向量值（Nonce）的取值要随机，且不能复用，即每次使用认证加密算法之前都要更换随机初始向量值。2)在解密验证的过程中，明文信息对用户不可见，只有在验证成功后才会输出明文；如果验证失败，则输出停止符。3)加密时，相同密钥对相关数据和明文信息加密的最大数据长度不超过2128 bit。6.1 AEUR 算法安全性分析 1)线性攻击 线性攻击23是一种已知明文攻击，也就是攻击者能够获取当下使用密钥状态下的明密文对。在对明文、密文和密钥三者满足的某种线性关系的概率p进行研究后，得到一个统计特征，利用该特征能够将分组密码和随机置换区分开。对分组密码而言，期待找到一个线性区分器来恢复最后一轮密钥。采用MILP方法构建目标函数和约束条件来搜索其最小活跃S盒，设置活跃S盒的下界，从准确度考虑，将搜索过程中每一轮的S盒个数进行输出，结果如表6所示。在线性攻击的标准方法评估下，AEUR算法的10轮活跃S盒下界为71，大于安全性目标设定的66个。且AEUR算法在标签生成和初始化阶段均使用了16轮迭代，有足够的安全冗余，所以其具有抵抗线性攻击的能力。表 6 AEUR 算法在线性攻击条件下的活跃 S 盒个数 轮数 S 盒个数 2 8 3 16 4 26 5 31 6 37 7 48 8 52 9 60 10 71 2)滑动攻击 滑动攻击24是受相关密钥攻击的启发而提出的。当分组密码在迭代过程中出现一定的自相似性时，可以使用滑动攻击对算法进行分析。与线性或者差分攻击不同，迭代轮函数的性质和执行轮数对滑动攻击的影响很小，轮数对算法抵抗滑动攻击的能力几乎没有影响。在密码算法中，如果迭代函数可以被分解为若干小的轮函数，那么就可以利用这一缺点进行滑动攻击。为了避免滑动攻击，算法的轮函数，特别是迭代的轮函数应该避免在执行过程中形成周期而被分解，在综合考虑算法抵抗几种攻击方法的能力以及对运行效率的影响后，与文献18的分析相同，AEUR算法的轮函数并未生成周期，因此AEUR算法可以抵抗滑动攻击。3)猜测确定攻击 猜测确定攻击25的原理是对密码算法实现过程中的一些变量进行猜测，猜测的变量在轮函数中迭代可得到新的变量，利用得到的变量恢复出算法实现过程中相应的状态值。AEUR算法的扩散层来源于uBlock算法，其扩散层的二元域矩阵分支数为8，攻击者需要已知64 bit才能得到下一个字节变量的值。AEUR算法轮函数是基于状态值集合iS构造的，有16个32 bit的状态值。那么对于AEUR算法的猜测确定攻击，则需要以32 bit的状态值进行攻击，为了满足算法的安全性目标，攻击复杂度最高临界值被设定为2128，显然想通过4个变量来恢复其他的状态值并不现实，所以AEUR算法可以抵抗猜测确定攻击。4)状态恢复攻击 Pelican MAC攻击26主要利用小尺寸的内部状态来构造基于生日悖论的碰撞。AEGIS、ALE算法都具有较大的内部状态，在AEUR算法中，状态值iS的大小为1632=512 bit，足以抵抗生日攻击。当攻击者使用相同的密钥和随机数进行多次重复攻击时，可能会在标签生成过程中对状态值注入差分，特别是当标签的长度小于算法的密钥长度时，认证加密算法面对这种攻击会显得脆弱。在AEUR算法中，轮函数结构的安全性目标为抵抗内部碰撞攻击，因此针对状态恢复攻击是不现实的。在多次攻击之后，可能获得相对成功的伪造，但无法恢复整个状态值。因此AEUR算法可以抵抗状态恢复攻击。5)伪造攻击 伪造攻击是指攻击者伪造出通过验证的密文来进行攻击。R(4,4)在9轮迭代情况下的差分路径概率为2152，远超过设定的128 bit安全性复杂度目标，因此，该结构能够抵抗差分分析，且无可用差分路径。AEUR算法的结构与R(4,4)相同，且迭代轮数超过10轮，拥有绝对安全冗余，无法实现伪造。因此，AEUR可以抵抗伪造攻击。AEUR算法作为直接设计类认证加密算法，其176 通 信 学 报 第 44 卷 底层算法uBlock对差分分析和不可能差分分析等具有良好的抵抗性。R(t,s)结构可以抵抗差分分析和伪造攻击等，并以128 bit的复杂度为安全性目标，保障结构的安全性。因此可以认为AEUR算法对差分分析等方法也有足够的抵抗能力。6.2 安全性对比分析 为了进一步说明AEUR算法的安全性，选用近年来最有代表性的具有同类结构的AEGIS算法、SMAE算法和Pyjamask算法27作为对比对象。AEGIS算法4在拒绝初始向量重用的情况下，在标签生成过程中，恢复密钥攻击的速度要慢于穷举搜索，因此状态恢复攻击对于拒绝Nonce重用的AEGIS无法实施。在伪造攻击中，解密的明文若验证成功，当t为标签值tag的长度时，有2t的概率可以被攻击者破解。AEGIS的标签长度为128 bit，在恢复状态时至少需要2128次伪造尝试，由计算复杂性理论可知，这一数值在计算上是不可接受的。因此，AEGIS对状态恢复攻击和伪造攻击具有安全性。SMAE算法17就猜测确定攻击而言，因为其底层函数来源于SM4算法，SM4算法中线性变换L的分支数为5，即对于SMAE算法而言，要想通过猜测确定攻击来分析算法，至少需要得到32 bit的输出值，才能恢复新的字节值，同时考虑到算法的128 bit的计算安全性指标，超过332 bit的恢复状态攻击不可行，因此SMAE算法对于抵抗猜测确定攻击具有安全性。在线性攻击分析中，计算搜索线性掩码成立的最优偏差为292.43，区分攻击和明文恢复攻击的数据复杂度约为2184，因此SAME算法对于线性攻击具有安全性。AEUR算法对于多种攻击具有安全性，较SMAE17和AEGIS4更全面，对比细节如表7所示。表 7 AEUR 算法和其他算法的安全性对比 算法 线性 攻击 伪造 攻击 猜测 确定攻击 状态 恢复攻击 滑动 攻击