◆夏红星 郑庆华

（深圳华威世纪科技股份有限公司 广东 518029）

认证加密算法的发展与研究

◆夏红星 郑庆华

（深圳华威世纪科技股份有限公司 广东 518029）

认证加密是一种可以防止消息被篡改、删除的有效方法，主要技术有密码分析、身份识别、消息确认等，已经被广泛应用于各种信息安全领域。认证加密算法能同时具有机密性、完整性、抗抵赖性等功能。其中，加解密可以对信息进行明密文变换，使信息以密文的形式进行通信，保证信息的机密性；认证可以判定数据是否被伪造、篡改或损坏。本文主要介绍认证加密的基础知识以及认证加密算法的基本分析方法。

认证加密；分组密码；流密码；CAESAR

0 引言

随着计算机通信网络的发展以及社会信息化的深入，尤其是电子商务的普及，信息安全成为当前重要的研究热点之一。密码学初期主要应用于军事、政治等特殊领域，如今已经普及到社会的各个方面，如通信、自动化、电子等多个科学领域，成为实现安全必不可少的手段。

密码学的研究具有悠久的发展史，可以被归纳为以下几个阶段：

第一阶段：密码学成为一门学科。古代到19世纪末，人们用简单的机械实现加解密，被称为古典密码体制。直到20世纪50年代末，人们采用稍微复杂的机械设备进行加解密，被称为近代密码体制。1949年，Shannon写了文章《保密系统的信息理论》，首次在密码学中引入信息论的概念，并对密码技术用数学的方法进行了理论分析、证明，数学成为密码学不可分割的一部分。1976年，Diffie出版了《密码学的新方向》，提出在公钥加密体制中，将加密算法与加密密钥进行公开，同时根据需要也可以公开[1]，从此，密码学进入快速发展的阶段。

第二阶段：密码学快速发展阶段。1977年，NBS发布DES算法，并成为数据加密的标准。1978年，麻省理工学院的Rivest等人提出公钥密码体制RSA[2]。90年代初，为了完善DES[3]，欧洲密码会提出了加密算法IDEA，该算法作为DES的候选算法得到了广泛应用，从此人们可以选择性的使用DES或IDEA。

第三阶段：密码学算法征集阶段。1997年，美国国家标准与技术研究院（NIST）进行了公开征集AES（Advanced Encryption Standard）的活动，最终，比利时学者Daemen和Rijmen设计的分组密码Rijndael[4]成为新的数据加密标准。2004年，欧洲启动了eSTREAM工程[5]来征集流密码加密算法，最终确定了8个候选算法，从此流密码的成为密码学的又一分支。而在对哈希函数的研究中，中国密码学者王小云对SHA-1和MD5的攻击[6]受到了广泛关注。2007年，NIST开启了对SHA-3的征集活动，最终宣布Keccak[7]算法为散列函数SHA-3的推荐算法。2013年，NIST启动了CAESAR（Competition for Authenticated Encryption：Security，Applicability and Robustness）密码计划[8]，最终获胜者将于2017年进行公示。

1 认证加密算法概述

随着消息认证码和Hash函数的发展，人们开始将消息认证码和加解密算法相结合，提出认证加密的概念[9]。2013年以来，欧洲CAESAR密码算法的征集活动，极大地促进了认证加密算法的发展，涌现了众多优秀的认证加密方案。

1.1 认证加密算法简介

将消息认证和信息加解密相结合来同时保证信息的完整性和安全性，这样的算法就称作认证加密算法。1974年，首次提出消息认证码MAC（Message Authentication Codes）的概念，实现了对信息起源的可靠性验证。消息认证码由与密钥相关的单向公开函数产生的固定长度认证符，不同的密钥产生不同的认证符，通过该认证符可以判定接收到的数据是否有效。

信息的传递不仅需要确认信息的真实性，还要保证信息是保密的，即同时实现信息的完整性和机密性。具体解释如下：

（1）机密性，编码明文信息，使得只有某一些人能够识别内部信息，其他人无法识别。编码前的信息称为明文，编码后的信息为密文。发送者发送密文给接收者，接收者接收到密文后若要进行阅读，那么接收者应该与发送者共同分享密钥，这样才能对收到的密文进行解密，从而获得明文信息。

（2）完整性保证信息是真正来自发送方的数据，而不是在传输过程中被篡改的数据。假设发送方A向接收方B一次性发送明文消息M和验证码MAC，当B收到消息后继续做一次同样的验证码生成运算，并将得到的结果与A发送过来的验证码进行比较，通过这种方式可以判断此次传输的明文信息M有没有被篡改，以此来确认信息的完整性。

一个典型的认证加密算法[10]共有四个典型的编程接口，具体如下：

（1）加密阶段：

输入：明文M、密钥K、随机数N、相关数据AD、初始状态S。随机数的重复使用会导致安全性的降低，因此尽量保证初始向量的唯一性。

输出：密文C和认证标签tag。

（2）解密阶段：

输入：初始状态、密文、随机数、相关数据、密钥。

输出：如果输出的认证标签和加密阶段认证标签相同，则返回明文，否则返回空。

1.2 认证加密算法的基本构造方法

认证加密可以同时提供机密性（加密）和完整性（认证）两种功能，将加密模块与认证模块相融合可以得到认证加密算法，如图1所示。其中，认证过程可分为两个步骤，tag算法和tag认证。接收者用明文、tag、密钥来验证tag的正确性。认证结果将决定该明文有效或者无效。

图1 认证加密算法的基本组成

1.2.1 机密性模块

机密性模块是将明文加密生成密文的基本模块，这些模块一般是基本的分组密码算法和流密码算法。

（1）分组加密算法。分组加密算法是一个n位置换，自AES提出以来，对AES的安全性分析成为密码学者不断追求的目标，很多认证加密算法是基于AES设计而成的。近期出现了一系列叫做AES-NI的高级加密标准指令，该系列指令先是得到Intel CPU支持，之后又得到了AMD CPU支持。AES-NI 共分为六个指令，四个是针对AES轮函数设计的，其余两个是针对AES密钥扩展而设计的。这些指令很大程度上提高了AES的软件执行能力，因此AES可以进行高效的加解密处理。此外，基于AES构造的认证方案还有ACS-1[11]，ALE，Marvin和AEGIS。尽管以上方案都没能证明其具有抵抗选择明文、密文攻击的能力，但根据AES的特殊属性可以直接推断其具有抵御某些攻击的能力，例如线性攻击、差分攻击。

（2）流密码。流密码是一个对称伪随机序列生成器：输入固定长度的密钥，输出可变长度的密钥流。在现代流密码设计中，包含非线性反馈移位寄存器（NFSR）的序列生成器最为流行，著名的流密码算法Trivium[12]和Grain[13]都用到了此类序列生成器。图2描述了两种密钥流生成器的结构。

图2 两种密钥流生成器的结构[14]

根据人们对认证加密算法的不同需要，逐步形成了一些认证加密模型，目前最多的是基于分组密码构造的认证加密方案。2013年以前，就已经提出了很多构建消息认证的基本模型，部分模型已得到标准化，例如OCB，GCM，CCM，SIV[15]，但是几乎所有的这些模型都有一个缺点，很难抵抗生日攻击。2013年征集活动中，出现的认证加密模型有CFB、CTR、ECB、EME、iFeed、JHAE、LEX、OFB、OTR、PFB、PPAE、SIV、TAE、XEX[16]等。

1.2.2 完整性模块

完整性模块是用来产生固定认证符的函数，产生这种模块的函数有很多种，其中最常用的有消息认证码MAC和Hash函数。

（1）消息认证模型是认证加密算法的重要组成部分。最初提出的消息认证模式是串行操作的MAC，后来又出现了可并行操作的PMAC，以及由PMAC衍生出的很多消息认证模型，如UMAC、HMAC、CBC-MAC、CBCR、iPMAC、PAE等。这些模型都有自己特有的优势，甚至在某些方面是不可替代的。

（2）散列函数。散列函数是一个双射长度固定的字符串。在SHA-3 征集活动中置换受到了广泛关注，CAESAR 征集活动中很多算法都是在散列函数的基础上设计产生的，目前最著名的置换是GOST 28147-89[17]，其输入长度是可变的，输出为固定长度。2013年，俄罗斯联邦授权使用了GOST R 34.11- 2012[18]算法，这一算法有效弥补了早期哈希标准GOST R 34.11- 94[19]的缺点。而美国国家标准与技术研究院推选具有海绵哈希结构的KECCAK作为未来SHA-3的新标准。如图3所示，海绵置换结构以一种直接的方法实现信息认证功能，其具有性能好，效率高等优点，尤其适用于资源有限的条件下。

图3 海绵结构的简易模型[20]

2 认证加密算法分析

认证加密算法的分析思路一般分为两种：一、不对基本模块内部进行探究，只对认证加密算法的整体结构进行分析，寻找不同输入产生的可预测性的输出；二、将认证加密算法看作普通的加密算法，使用密码学常用的分析手段进行分析。

2.1 经典的认证加密算法分析方法

以下列举了五种主要的攻击方法：

（1）生日碰撞[21]

生日碰撞。具体过程可解释为：利用生日现象，查找Hash值的冲突部分，通过伪造报文的手段，对身份验证的报文进行攻击的模式。生日碰撞取决于消息摘要的长度（Hash值的长度），这意味着该攻击要求消息摘要必须足够长。

（2）伪造攻击[22]

2001年，Brincat等人提出伪造攻击方法，其基本思想可归纳为：假设攻击者已经知道某一对应关系，输入（明文1、公开变量1、相关数据1）与输出（密文1、认证标签1）有效对应。那么，如果能够找到另一输入（明文2、公开变量2、相关数据2）与输出（密文2、认证标签2）有效对应，而新的对应关系是在已知对应关系的基础上没有增加新的未知变量，那么我们就称这一伪造攻击有效。常用的三种基本形式有：MAC猜测、验证伪造、尾0伪造。

（3）差分攻击[23]

1980年，Biham 等人首次提出了差分攻击的分析方法，并且将这一分析方法应用到大量分组密码算法上。差分攻击属于选择明文攻击，其基本思想为：给定多组数据不完全相同的明文和密文，对各组进行异或（或相减加），得到数据差分；攻击者通过对输入输出对应的差分进行统计，寻找差分规律，根据这种差分规律判断某一明密文是经哪一算法加密的。同样通过在输入端注入差分，可以找到某些内部状态碰撞，再结合一些其他方法可以实现密钥恢复攻击或者伪造攻击。该攻击方法可以应用于很多认证加密算法，例如PAES、poet、JAMBU等。

（4）选择明文攻击（CPA）和选择密文攻击（CCA）[24]

攻击者对加密模块访问时自己选择明文，通过加密模块得到相应的密文。通过多次访问加密模块，可以将模块的某些信息暴露出来，例如密钥、内部状态等。通过猜测某些内部状态，建立大量输入输出表达式，结合代数攻击或者其他的数学方法就可以实现密钥的恢复。选择密文攻击与选择明文攻击类似，可以通过选择密文进行加密算法访问得到对应的明文，从而获得算法的某些信息，此类攻击已经广泛应用在认证加密算法的攻击中。

（5）滑动攻击

1999年，Biryukov等人[25]首次提出了滑动攻击的思想。滑动攻击最先应用于分组密码的分析，分组密码一般轮数比较高，而滑动攻击的攻击效果一般不随轮数的变化而变化。2008年Priemuth等人将滑动攻击应用于流密码算法Trivium。由于大多数认证加密算法是基于流密码和分组密码设计的，因此该类攻击同样适用于认证加密算法。

2.2 几种典型的认证加密算法的最新研究进展

随着CAESAR征集活动的研究进展，部分认证加密算法已经被攻破或退出竞赛，同样有些算法经过分析整理后更加完善，因此具有较强的抗攻击能力。

下面将列举若干种典型的认证加密算法的最新攻击结果。

（1）PAE算法

PAE是基于并行消息认证码PMAC提出的另一并行消息认证码。其具有平行的结构模型，采用面向字的混淆参数，因此具有较快的运行速度。2015年，Debrup等人针对PAE的认证性进行攻击[26]，首先，对PAE的认证性攻击，攻击结果表明，成功实现伪造攻击的概率为0.5，共使用2次加解密模块访问；其次，对PAE的安全性攻击，提出了两对明密文对，通过验证认证标签和输出密文的关系，可以将PAE和随机的加密算法区分开来。

（2）Keccak

2012年，NIST宣布了Keccak体制作为新的SHA-3 Hash函数标准。2014年，Dong等人[27]对7-轮 Keccak-224，8-轮Keccak-256/384和9-轮Keccak-512进行了原像攻击，证明了随着轮数的增加攻击复杂度也显著增加，当到达9-轮的时候，复杂度接近暴力攻击。

（3）国密SM3

2010年，中国国家密码管理局将王小云等人设计的SM3杂凑算法作为中国商用密码杂凑算法新标准，从此开启了用SM3算法代替早期使用的MD5算法新的时代。SM3算法本质是将不同长度的明文映射成为固定长度的密文，并且这种映射是单向映射。在2011 年的 ICISC国际会议上，Zou等人针对SM3算法提出攻击，该攻击可以通过减少轮数进行攻击[28]。

（4）Marble算法[29]

Marble算法可以应用在不同的环境下，例如加密模块采用AES-GCM算法，并声明该算法具有128位的安全性。2015年，Thomas等人对Marble进行分析[30]，结果表明，该算法的相关数据阶段和明文加密阶段没有明显的界限，可以将相关数据与明文进行相互转化，从而实现内部状态的碰撞。为了使得认证标签相同，攻击者筛选了明文，实现数据伪造，并恢复出全部密钥。

（5）JAMBU算法

JAMBU算法共有3n位的内部状态，但是只有其中的2n位状态需要通过加密模块更新。2015年Thomos 等人对该算法进行分析[31]，分析过程：将同一明文分别和不同随机数组合进行加密模块访问，产生内部状态差分；利用这些差分结构恢复内部状态；然后将该算法和其它算法区分开来，即实现区分攻击，并且可以伪造部分密文（该密文在攻击过程没有使用过）。

（6）FASER128

FASER认证加密体系包括两种加密算法：FASER128和FASER256，FASER不需要外加其它加密算法，且具有平行的软件加密过程。随后，FENG等人针对FASER128提出了实时密钥恢复攻击[32]。攻击步骤：①通过代数分析得到输出密钥流和移位寄存器状态之间的线性关系，从而得到很多组关于初始状态的代数方程组，通过数学运算恢复初始状态。②由上一步已知初始寄存器状态，经过初始化得到实时移位寄存器状态，然后对寄存器状态进行猜测，通过初始化逆运算可以得到密钥的可能值，通过验证便可筛选出真正的密钥。

（7）祖冲之序列密码算法

该算法是中国科学院等自主设计的流密码算法，已成为下一代移动通讯4G网络中的国际标准，包括祖冲之算法（ZUC）、加密算法（128-EEA3）和完整性算法（128-EIA3）三个部分。2014年，Cheng等人整合了祖冲之流密码系统与虫洞映射的优点提出了一种高效混浊加密算法，并成功运用于图像加密领域。

3 CAESAR征集活动的研究进展

CAESAR活动共征集了57个候选算法，从候选算法的结果来看，构造认证加密算法的方法有很多，有些算法基于分组加密算法（AES），有些基于流密码，有些基于Hash函数或海绵结构。对算法的总结如表1所示。

表1 认证加密算法的最新研究进展

POET 弱密钥攻击，针对POET-G伪造攻击SCREAM 伪造攻击，弱密钥攻击，密钥恢复攻击Silver 伪造攻击，密钥恢复攻击

4 总结

在当今信息社会高速发展的时代，认证加密算法起着关键的作用，尤其是在信息安全中来保障各种信息的机密性、真实性和完整性。本文主要对认证加密算法的分析方法进行简单的介绍，总结了目前对CASAER征集算法的研究方法。这些方法包括密码分析常用的方法，例如代数攻击或差分攻击，也包括主要针对认证加密算法的伪造攻击。最后，本文归纳总结了认证加密算法的最新进展。

[1]张秀洁．抵抗密钥泄露密码技术研究[D]．电子科技大学，2014．

[2]Khatarkar S，Kamble R．A survey and performance anal ysis of various RSA based encryption techniques [J]．Internation al journal of computer applications，2015．

[3]Hora A，Sahayam N．Implementation of efficient proba bilistic symmetric key encryption method [J]．Asian journal of current engineering and maths，2015．

[4]Supriya D V，Niranjan M R．Realization of AES encry ption and decryption based on null convention logic [J]，2015．

[5]https：//www．ecrypt．eu．org/stream/．

[6]Wang X，Yu H，Wang W．et al．Cryptanalysis on hma c/nmac-md5 and md5-mac [M]．Advances in cryptology EU ROCRYPT 2009．Springer berlin heidel berg，2009．

[7]Bertoni G，Daemen J，Peeters M，et al．The keccak s ha-3 submission [J]．Submission to NIST（round 3），2011．

[8]CAESAR call for submissions，2014[EB/OL]．http：//c ompetitions．cr．yp．to/caesar submissions．html．

[9]Naito Y．Full PRF-secure message authentication code based on tweakable block cipher [M]．Provable security．Springe r international publishing，2015．

[10]Sarkar P．Pseudo-random functions and parallelizable modes of operations of a block cipher [J]．Information theory，ieee transactions on，2010．

[11]An J，Bellare M．Does encryption with redundancy pr ovide authenticity．advances in cryptology EUROCRYPT 200 1 Proceedings，lecture notes in computer science，vol．2045，s pringer-verlag，b．pfitzmann，ed，2001．

[12]Ye D，Wang P，Hu L，et al．PAES v1：parallelizable authenticated encryption schemes based on AES round functi on [J]．CAESAR first round submission，competitions．Cr．yp．to/r ound1/paesv1．pdf，2014．

[13]Cannière D．Trivium：a stream cipher construction ins pired by block cipher design principles [M]．Information securit y．Springer berlin heidel berg，2006．

[14]Hell M．Johansson T．Meier W．Grain：a stream cipher for constrained environments [J]．International journal of wireles s and mobile computing，2007．

[15]Ye D,Wang P,Hu L,et al．Parallelizable authenticate-d encryption schemes based on AES round function[J]，2014．

[16]Abed F,Forler C,Lucks S．General overview of the aut henticated schemes for the first round of the CAESAR comp etition[R]．Cryptology eprint archive：report 2014/792．[2] CAE SAR submissions，second-round candidates．Available：http：// competitions．cr．yp．to/caesar submissions．Html．

[17]Bjorstad T．Cryptanalysis of grain using time/memory/ data tradeoffs [J]，2013．

[18]Kazymyrov O,Kazymyrova V．GOST R 34．11．2012 [J]．

[19]Popov V,Kurepkin I,Leontiev S．Additional cryptograp hic algorithms for use with GOST 28147-89，GOST R 34．1 0-94，GOST R 34．10-2001，and GOST R 34．11-94 algori thms[J]．Draft popov cryptopro-cpalgs-03．txt，2006．

[20]池相会．基于拟群的Hash函数以及消息认证码安全性研究[D]．宁波大学，2012．

[21]陈杰，胡予濮，韦永壮．随机消息伪造攻击PMAC和T MAC-V[J]．计算机学报，2007．

[22]李玮，谷大武．基于密钥编排故障的 SMS4 算法的差分故障分析[J]．通信学报，2008．

[23]鲁力，胡磊．基于 Weil 对的多接收者公钥加密方案[J]．软件学报，2008．

[24]Biryukov A,Wagner D．Slide attacks[C]．Fast software e ncryption．Springer berlin heidel berg，1999．

[25]Chakraborty D,Nandi M．Attacks on the authenticated encryption mode of operation PAE [J]．Ieee trans．inf．theory（t o appear）．Doi，2014．

[26]Chang D，Kumar A，Morawiecki P，et al．1st and 2 nd preimage attacks on 7，8 and 9 rounds of keccak-224，2 56，384，512[J]．

[27]Zou J，Wu W，Wu S，et al．Preimage attacks on ste p-reduced SM3 hash function．LNCS，2011，vol．7259：pp．375 -390，springer．

[28]Fuhr T，Leurent G，Suder V．Forgery and key-recov ery attacks on CAESAR candidate marble [J]，2015．

[29]Dunkelman O，Keller N，Shamir A．Slidex attacks on th e even-mansour encryption scheme [J]．Journal of cryptology，2015．

[30]Peyrin T，Sim S M，Wang L，et al．Cryptanalysis of JAMBU[C]．Fast software encryption．Springer berlin heidel ber g，2015．

[31]Feng X，Zhang F．A realtime key recovery attack on the authenticated cipher faser128．Cryptology ePrint Archive，R eport 2014/258（2014）．http：//eprint．iacr．org/．

[32]Cheng H，Huang C，Ding Q，et al．An Efficient Ima ge Encryption Scheme Based on ZUC Stream Cipher and C haotic Logistic Map[M]// Intelligent Data analysis and its App lications，Volume II．Springer International Publishing，2014．

支撑：深圳市技术创新计划技术攻关项目（项目编号：深科技创新[2015]293号）。