第5 章　认证加密算法 5.1 概述 5.1.1 认证加密算法一般性设计原理 认证加密算法是能够同时保护数据机密性、完整性以及进行数据源认证的对称密码算 法。早期的认证加密算法多采用组合方式设计,主要的组合方式有先加密后认证(Encryptthen- MAC,EtM)、先认证后加密(MAC-then-Encrypt,MtE)和加密并认证(Encrypt-and- MAC,E&M)。这3种构造方式的优势在于通用性,适用于常见的加密算法和认证算法,但 其没有令人信服的安全性[383,384]。Bellare等人分析了3种组合认证加密方案(EtM、MtE、 E&M)的安全性,并正式提出了认证加密(AuthenticatedEncryption,AE)的概念[385]。带 有关联数据的认证加密(AuthenticatedEncryptionwithAssociatedData,AEAD)[386]是认 证加密的一种扩展,在为明文数据提供机密性和完整性双重保护的同时,为关联数据提供完 整性保护。AEAD的加密算法以密钥K 、临时值N 、关联数据A 和明文M 为输入,输出密 文C 和标签T ;解密算法以密钥K 、临时值N 、关联数据A 、密文C 和标签T 为输入,输出 明文M 或者符号⊥(意味着完整性验证没有通过)。AEAD 的典型应用是各种网络协议, 协议报头等信息仅需要完整性保护而不需要机密性保护。 目前的认证加密算法基本上都是AEAD,可以归为两类,一类是分组密码工作模式,另 一类是直接设计的认证加密算法。分组密码工作模式类的认证加密算法又称分组密码认证 加密工作模式,此类认证加密算法以黑盒方式调用分组密码,优点是可以方便地替换底层分 组密码,比较典型的算法有OCB、GCM、CCM、EAX等[387-389]。这方面的研究始于十几年前 NIST对AES征集认证加密工作模式。国际标准化组织和NIST 都颁布了相关标准,收录 了OCB2.0、KeyWrap、CCM、EAX、Encrypt-then-MAC、GCM 共6种认证加密模式[390],这 6种模式包含了不同的设计理念和对应用需求的考量,是目前具有代表性和影响力的认证 加密算法。 分组密码认证加密工作模式一般分为One-pass和Two-pass两类。Two-pass的算法 需要对明文进行两次处理,比如CCM;One-pass的算法只需要对每个明文分组进行一次处 理,比如OCB。OCB是最经典的分组密码认证加密工作模式,其设计理念影响了许多认证 加密算法。OCB经历了OCB1、OCB2和OCB3多个版本,在掩码生成方式等方面不断优 化,在安全性证明方面不断改进。如果底层可调分组密码是理想的,则OCB3是具有完美保 密性的依赖临时值的认证加密算法[391]。 可调分组密码是一个函数E ~ :{0,1}k ×{0,1}w ×{0,1}n →{0,1}n ,对于任意的密钥K ∈{0,1}k 和调柄W ∈{0,1}w ,E ~ (K ,W ,·)是{0,1}n 上的一个置换,通常记为E ~ K (W ,·) 或者E~W K 。可调分组密码是一族分组密码,利用公开参数调柄实现分组密码可变性。和一 轻量级密码学 般的分组密码相比,可调分组密码多了一个调柄输入,调柄是不需要保密的公开值,意味着 即使对手控制了调柄,可调分组密码仍然保持安全性。类似伪随机置换和强伪随机置换,文 献[392]定义了伪随机可调置换和强伪随机可调置换以及安全可调分组密码和强安全可调 分组密码。 一些分组密码的密钥扩展算法比较复杂,更改密钥需要执行密钥扩展算法。调柄的作 用主要是为分组密码提供可变性,因此,可调分组密码应该具有更改调柄比更新密钥代价小 的属性。基于分组密码E,有如下两种构造可调分组密码的通用方法,分别称作XE 、XEX 框架: ~ (1)EK ( W , M )=EK ( W ..EK ( M ))。 ~ (2)Eh ( W , M )EK ( W ))..h( W )。 假设 E 是安全分组密码,则第一种方法构造的可调分组密码是安全的;进一步假定 h 是 ε-即,、yz 都有Ph (x)..h(= K ,= M ..h( AXU2 泛杂凑函数( 对于所有满足x≠ y 的 x 、rh(y)z)≤ ε 成立), 则第二种方法可以构造强安全的可调分组密码。第一种构造方法更改调柄很容易,但是需要 调用两次分组密码;第二种构造方法只需调用一次分组密码,比第一种构造方法更有效。 可调分组密码的引入使得设计认证加密算法更容易,证明更简洁,可调分组密码已经成 为认证加密算法的一种底层模块。TAE是一个基于可调分组密码的认证加密工作模式, OCB可以看成TAE的一个实例,其中的可调分组密码可以看成是在XEX框架下利用分组 密码构造的。利用XEX框架构造的可调分组密码不是理想的,仅提供生日攻击安全性,因 此OCB仅提供生日界安全。当临时值 N 重用时,OCB不安全,因此OCB是依赖临时值的 认证加密算法。与OCB不同,SIV是抵抗临时值重用的认证加密算法[393]。SIV基于一个 加密方案 E 和一个伪随机函数F,首先计算标签 T =F(K1, N ‖ M ),然后计算密文C= E(K2,T, M ),标签 T 作为加密的临时值使用。SIV是Two-pas 的认证加密算法,而且需 要两个密钥。RFC5297给出SIV的一个实例,其中,加密方案 E 采用AES-CTR,伪随机函 数 F 采用CMAC-AES 。 直接设计的认证加密算法是从底层模块直接设计的,而且分组密码不再是底层模块的 唯一选择,基于伪随机置换、伪随机函数、压缩函数等构建的认证加密算法被陆续提出,其中 基于置换的AEAD结构多来源于海绵结构。海绵结构采用固定置换作为底层模块,以先吸 收再榨取的方式处理消息,是目前杂凑函数设计中备受青睐的一种结构。Bertoni等人将海 绵结构中的吸收与榨取阶段结合,形成边吸收边榨取的Duplex结构[394]。如图5-1所示, 图5- 1 Duplex结构 第 5 章　认证加密算法 x结构由初始化()和迭代(组成。其中, P 是固定长度的置换;d是 消息的填充方式; r 和 c 是两个参数,分别称为比率和容量;输出 Z 可用作加密的密钥流或 认证的标签。 Duplex结构可以用于处理各种长度的密钥、关联数据、消息等,具有极强的灵活性。底 层固定置换无须进行逆向调用,具有较好的实现性能。基于Duplex结构,Bertoni等人提出 了认证加密算法的MonkeyDuplex结构[395],如图5-2所示。MonkeyDuplex结构相对于 Duplex结构的差异在于:密钥吸入的状态由外部状态扩展到整个状态;增强初始化过程, 对吸入密钥的状态进行一次置换;降低duplexing模块中置换的迭代轮数。MonkeyDuplex 结构可以使用不同的底层模块。如果采用迭代型置换,初始化和末尾置换的迭代轮数通常 大于duplexing模块的迭代轮数。如果密钥长度为 k 比特,置换状态为 b 比特,容量为 c 比 特,标签为 t 比特, nelx结构的安全界量级如下:机密性为mn{c,完 Dupleinit.duplexing) Pa in{k 则 , MokyDupeib/2,k}, 整性为mc/2,t}[396]。 图5- 2 MonkeyDuplex结构 Chakraborti等人在Duplex结构上增加了一个简单的变换ρ,得到一种变体———Betle 结构。变换 ρ 作用在数据吸收和榨取阶段,使得释放的密文和反馈到状态的值不同。 Duplex类结构的密钥嵌入方式有多种形式,但一般都是在初始化和末尾部分添加密钥,底 层置换是公开的。还有一些算法的底层置换是带密钥的置换,安全证明中不存在对底层模 块的询问,仅考虑整个状态的碰撞,可用更小的内部状态提供相同的安全性。当底层置换公 开时,考虑到每个密钥处理的数据量,为了抵抗基于碰撞的状态恢复攻击,内部状态必须足 够大。对于内嵌密钥的设备,使用带密钥的底层置换更易于设计轻量级认证加密算法。 5..认证加密算法研究进展 12 认证加密算法发展迅速,各种新型算法百花齐放,虽然可以粗略地分为基于置换/分组 密码/流密码的直接设计类以及黑盒调用分组密码的认证加密工作模式,但有些算法兼具多 类的特点。认证加密算法是功能复合的算法,不同设计在保护机密性和完整性方面有不同 的侧重。此外,认证加密算法的应用场景繁杂多样,由此产生了各种设计和评估指标,比如 在线加密、多层次的健壮性、增量标签、并行计算、密文保长、不需要底层模块逆运算、较低的 实现代价等。 CAESAR竞赛和NIST的轻量级密码标准化项目征集了100多个认证加密算法,集中 体现了认证加密算法的研究进展和设计趋势:更加注重具体应用需求,努力提高算法的健 轻量级密码学 壮性,尽量避免因算法实现或使用不当而导致的安全漏洞。分组密码、流密码和杂凑函数等 对称密码设计理论在认证加密算法中得到了充分融合,许多候选算法以加密算法和认证算 法作为基本单元或者借鉴其设计理念。CAESAR竞赛的全称是“Competitionfor AuthenticatedEncryption:Security,Applicability,andRobustnes”,旨在选拔安全、高效 的认证加密算法,推动认证加密算法设计与分析的发展[397,398]。CAESAR竞赛要求候选认 证加密算法应满足两个条件:一是具有广泛的兼容性;二是优于AES-GCM 。 2014年3月,CAESAR竞赛公布了征集的57个算法,随后有9个算法因安全缺陷宣布 退出竞赛。在进入第一轮评估的48个候选算法中,将AES等密码算法作为整体调用的认 证加密工作模式有18个:++AE 、AES-CMCC 、AES-COPA 、AES-CPFB 、AES-JAMBU 、 AES-OTR 、AVALANCHE 、CBA 、CLOC 、ELmD 、Enchilada、HS1-SIV 、iFed 、Julius、OCB 、 POET 、SHELL和SILC 。其中,ELmD和SHELL为了提高性能,部分模块采用缩减轮 AES 。考虑到AES指令集对算法软件性能的影响,大部分算法是基于AES的;Enchilada 和HS1-SIV采用黑盒调用ChaCha流密码的方法。直接设计的候选算法有29个。有些算 法采用了多种设计理念,对它们的分类比较困难而且观点各异。 基于算法的典型设计理念,本书尝试将它们归为如下几类。第一类是基于分组密码的 认证加密算法,包含11个算法:AEGIS 、AEZ 、Deoxys、Joltik、KIASU 、LAC 、PAEQ 、 SCREAM 、Silver、Tiaoxin和YAES 。第二类是基于置换(杂凑函数)的认证加密算法,包含 12 个算法:Artemia、Ascon、ICEPOLE 、Ketje、Keyak、Minalpher、NORX 、OMD 、 PRIMATEs、Pr.st、π-Cipher和STRIBOB 。第三类是基于流密码的认证加密算法,包含6 个算法:ACORN 、MORUS 、Raviyoyla、Sablier、TriviA-ck和Whesht。此外,还有设计理 念比较特殊的POLAWIS算法。 基于分组密码的11个候选算法按模块分类,有8个算法直接使用了AES轮函数,其他 3个算法采用了分组密码的设计理念。这11个算法按整体框架分为3类:AEZ 、Deoxys、 KIASU 、Joltik和SCREAM利用了可调分组密码的理念;PAEQ 、Silver和YAES采用分组 密码构造大置换并进一步设计认证加密算法的思路,本质上这一类设计和基于置换的设计 是相通的,只是置换的设计和分析评估采用了分组密码的理念;AEGIS 、Tiaoxin和LAC采 用流密码框架,此类算法的明文参与状态更新,而且状态更新函数比较简单,所以一般要求 临时值 N 不能重用,而且接收方在解密验证阶段需要先认证再输出密文。 2015年7月,CAESAR竞赛公布了进入第二轮评估的29个候选算法。基于分组密码 的认证加密算法有7个:AEZ 、Deoxys、Joltik、SCREAM 、AEGIS 、Tiaoxin和PAEQ 。从实 现性能方面考虑,AES指令是现阶段设计认证加密算法绕不开的点。从设计趋势看,基于 可调分组密码设计认证加密算法的思路值得关注。基于置换的认证加密算法有10个,其中 Ascon、ICEPOLE 、Ketje、Keyak、NORX 、PRIMATEs、π-Cipher和STRIBOB都采用了 Sponge类结构,Minalpher采用了工作模式类的结构,OMD采用了MD结构。从底层置换 分类,Ascon、ICEPOLE 、Ketje和Keyak采用了SHA3,PRIMATEs采用了AES类设计思 想,NORX和π-Cipher采用ARX类的底层置换,另外有两个算法分别使用了GOST和 SHA512的模块。 2016年8月,CAESAR竞赛公布了进入第三轮评估的15个候选算法。2018年3月, CAESAR竞赛公布了获胜算法:ACORN 、AEGIS 、Ascon、COLM 、Deoxys-Ⅱ、MORUS和 第 5 章　认证加密算法 OCB 。2019年,史丹萍等人发现了MORUS的安全问题[399],随后MORUS被撤出。 2013年,美国NIST启动了一个轻量级密码项目,调研NIST现有密码算法标准在资源 受限环境中的适应性以及对轻量级密码算法标准的需求[400]。2017年4月,NIST发布了轻 量级密码标准化的流程。首先考虑认证加密算法,一类是面向硬件的带关联数据的认证加 密算法,另一类是兼顾软硬件性能的带关联数据的认证加密算法和杂凑函数。2018年8 月,NIST发布公告正式启动轻量级密码的征集、评估和标准化工作,旨在推出系列轻量级 密码算法,用于现有NIST密码标准不适用的资源受限环境。2019年4月,NIST公布了征 集到的56个候选算法,8月宣布了进入第二轮的32个候选算法,包含11个工作模式类的 认证加密算法、17个基于置换的认证加密算法、两个基于分组密码的认证加密算法以及两 个基于流密码的认证加密算法。 11个工作模式类候选算法包括COMET 、ESTATE 、ForkAE 、GIFT-COFB 、HyENA 、 LOTUS-AEAD&LOCUS-AEAD 、mixFed 、Romulus、SAEAES 、SKINNY-AEAD 和 SUNDAE-GIFT 。从整体框架分类,ESTATE和SUNDAE-GIFT是Two-pas 的算法,其 余9个都是One-pas 的算法。ESTATE 、ForkAE 、LOTUS-AEAD&LOCUS-AEAD 、 Romulus和SKINNY-AEAD采用了可调分组密码的设计理念。SKINNY-AEAD和 LOCUS采用了OCB类模式。按采用的分组密码分类,COFB 、HyENA 、LOTUSAEAD&LOCUS 、SUNDAE-GIFT和ESTATE采用了GIFT分组密码,ForkAE 、Romulus 和SKINNY-AEAD采用了SKINNY分组密码,mixFed 、ESTATE和SAEAES采用了 AES-128分组密码。 rephanml 17个基于置换的候选算法为ACE 、ASCON 、DyGASCON 、Elt、Gii、ISAP 、 KNOT 、ORANGE 、Oribatida、PHOTON-Betle、SPARKLE(SCHWAEMMandESCH )、 SPIX 、SpC、ok、utraen2.oa除Elphn oSpoSbena0、WAGE和Xodyk。从整体结构分类, eat 采用先加密后认证的方式之外,其余16个算法都采用了Duplex结构及其变体。从底层置 换分类,可将这17个候选算法分为3类:6个算法采用了杂凑函数的设计理念,主要参考的 杂凑函数是SHA3和PHOTON,其中,i、ISAP 、0和Xk的底层 GimlSubteranean2.oodya 置换类似SHA3,ORANGE和PHOTON-Betle采用了PHOTON256;9个算法的底层置 换采用了分组密码设计理念,其中,ACE 、Oribatida、SPIX和SpoC采用或借鉴了SIMON 或Simeck分组密码,ASCON 、DryGASCON 、KNOT和Spook采用了比特切片技术, SPARKLE采用了ARX类底层置换;WAGE的底层置换采用了流密码的设计思想。 两个基于分组密码的候选算法是Pyjamask和Saturnin。Pyjamask采用了OCB类模 式,专门设计了底层分组密码Pyjamask-96和Pyjamask-128 。Saturnin结合CTR模式和 MAC算法,采用先加密后认证的方式,底层分组密码Saturnin的设计借鉴了3DAES算 法。两个基于流密码的候选算法是Grain-128AEAD和TinyJAMBU 。Grain-128AEAD基 于流密码Grain-128,采用基于泛杂凑函数的MAC 。TinyJAMBU的整体框架类似Duplex 结构,基于带密钥的置换,其中置换的设计采用了NFSR 。 可证明安全性是衡量工作模式类认证加密算法的重要指标。可证明安全是在一定的安 全假设下,针对确定的攻击者能力,证明相应的安全目标。常用的安全假设包括伪随机置 换、伪随机函数、不可预测函数和理想密码。刻画攻击者能力和手段通常需考虑密码算法运 行的环境,目前存在多种对攻击者能力和手段的刻画。分组密码认证加密工作模式的可证 200 轻量级密码学 明安全通常不限制攻击者的计算能力,但是限制攻击者向随机预言机查询的次数、查询消息 的总长度等。结合不同的安全假设和攻击者能力,形式化定义了多种安全模型:选择明文 攻击下的不可区分性(-选择密文攻击下的不可区分性(-明文完整性 INDCPA )、INDCCA )、 (PTXT )、密文完整性(等。如果一个认证加密算法能够同时达到INT INT-INT-CTXT) CTXT 和IND-CPA,则认为该认证加密算法是安全的。随着临时值与关联数据等概念的加 入,相应的使用唯一值与带关联数据的认证加密算法的安全性定义陆续被提出。同时,针对 认证加密算法的一些新性质与功能,也提出了一些特殊的安全模型,比如抵抗临时值重用的 认证加密算法、依赖临时值的认证加密算法、超越生日界的认证加密算法、在线认证加密 RUP 安全的认证加密算法等[401-403]。 由于轻量级分组密码的分组长度比较短,考虑到量子计算安全性,超越生日界安全成为 一些密码算法设计的指标。对于认证加密算法而言,结合TAE 模式和超越生日界安全的 可调分组密码,可以很自然地设计超越生日界安全的认证加密算法,比如CAESAR 竞赛的 获胜算法Deoxs-Ⅱ和SKINNY-AEAD 等。问题是如何设计高效的超越生日界安全的可 y[200], 调分组密码。TWEAKEY 是一种可调分组密码的设计框架将密钥和调柄看成调柄密 钥(tweakey), 设计调柄密钥扩展算法以替换分组密码的密钥扩展算法。利用TWEAKEY 框架的可调分组密码没有理论安全性证明,只能评估其对差分分析、线性分析等分析方法的 安全性。王磊等通过两次调用底层分组密码,构造了达到全安全性的可调分组密码[404]。 对于直接设计的认证加密算法,已有的可证明安全理论显示出局限性。由于没有合理 化的安全假设,因此不能从可证明安全角度论证其安全性,只能评估其对各种分析方法的安 全性,差分分析、线性分析、碰撞攻击、相关密钥攻击、故障攻击等都被用来分析认证加密算 法的安全性[405-407]。直接设计的认证加密算法种类多、效率高,是未来发展的趋势,但是安 全性基础不够坚固,安全性分析方法与评估技术有待深入研究。 5.分组密码认证加密工作模式 2 在本节中,主要使用如下符号与记号: A 关联数据。 M 明文。 N 临时值。 K 密钥。 C 密文。 E 分组密码加密算法。 D 分组密码解密算法。 E ~ 可调分组密码的加密算法。 m M 划分后的分组个数。 n 分组密码的分组长度。 t 标签的比特长度。 S 状态。 T 标签。 第5 章　认证加密算法2 01 0i 由i 个0构成的比特串。 1i 由i 个1构成的比特串。 10* 由1个1和若干0构成的比特串,在常见的填充形式X10* 中,星号代表 n-|X|-1,即将任意的比特串X (|X|