认证加密算法SCREAM及iSCREAM的新伪造攻击

田玉丹，韦永壮

（1.桂林电子科技大学广西信息科学实验中心，广西 桂林 541004；

2.桂林电子科技大学认知无线电与信息处理省部共建教育部重点实验，广西 桂林 541004；3.中国科学院信息工程研究所信息安全国家重点实验室，北京 100039）

认证加密算法SCREAM及iSCREAM的新伪造攻击

田玉丹1，韦永壮2，3

（1.桂林电子科技大学广西信息科学实验中心，广西 桂林 541004；

2.桂林电子科技大学认知无线电与信息处理省部共建教育部重点实验，广西 桂林 541004；3.中国科学院信息工程研究所信息安全国家重点实验室，北京 100039）

认证加密算法能同时提供信息的加解密及完整性检验两个功能，它已被广泛应用于各种网络安全系统中。最近伴随着欧洲CAESAR密码算法的征集活动，认证加密算法倍受业界关注。SCREAM算法凭借其新颖的设计理念和算法结构，已经顺利入围CAESAR竞选中的第二轮候选算法。而该算法是否存在新的安全性问题是目前的研究热点之一。基于SCREAM参数的变化特点，利用累加值碰撞的思想提出了一种新的伪造攻击。研究结果表明，新攻击成功的概率为1，所需的时间复杂度及数据复杂度均可忽略；此外该攻击同样适用于SCREAM的一种变体算法，即iSCREAM。与已有的攻击相比较，新攻击所需的复杂度更低，攻击范围更灵活有效。

SCREAM；iSCREAM；伪造攻击；CAESAR；认证

1　引言

认证加密算法可以同时实现信息的加解密和完整性检验两个功能，它已被广泛应用于各种网络安全系统中。2013年以来，伴随着CAESAR征集活动［1］，认证加密算法倍受广泛关注［2～5］。Vincent等基于可调认证加密模型所提出的SCREAM算法［6］具有新颖的设计理念和算法结构，并顺利入围CAESAR第二轮候选算法。该算法采用LS基本模型［7］及SPN基本加密模块，具有安全性高、加密速率快、抵抗侧信道攻击等优点。分组长度为128位，明文和相关数据长度分别小于（ n表示随机

b数N的字节长度）和个字节，N的长度范围在1到15个字节之间。SCREAM和iSCREAM的区别在于SPN型结构不同。目前该算法倍受关注，其主要分析结果如下。

Siang等［8］针对SCREAM和iSCREAM提出伪造攻击；成功伪造的概率是（设明文的最后分组为个0），时间复杂度和数据复杂度可以忽略不计。Gregor等［9］针对iSCREAM提出“依附S盒不变子空间”的攻击方法，通过寻找弱密钥恢复全部密钥。该攻击数据复杂度为个选择明文，时间复杂度为。文献［10］对SCREAM 和iSCREAM的基本结构进行分析，并归了算法中的TAE模型及SPN结构。

由上可知，文献［8］对明文要求高、攻击范围小、成功概率低；文献［9］是基于SPN结构的攻击，该攻击数据复杂度、时间复杂度都较高，且只能攻击iSCREAM算法。那么，针对SCREAM和iSCREAM能否找到一个高效的攻击，成为当前密码学者研究的热点之一。

本文根据SCREAM和iSCREAM的可变参数T的计数特点提出新伪造攻击。研究表明，新攻击可以删除明文的r-1个分组，使生成的标签tag不变。该攻击成功的概率为1，时间复杂度、数据复杂度可忽略不计。因此该攻击具有范围广、效率高等优点。

2　SCREAM和iSCREAM算法介绍

通过对可调认证加密模型［11］（TAE）改进得到算法SCREAM和iSCREAM。SCREAM和iSCREAM是128位加密算法，其基本模块E（ k）的SPN结构包括8位S盒和16位L盒。加密过程为其输入是明文P、128位密钥K、随机数N（建议使用12字节）和相关数据A，输出为密文C和标签tag。解密过程为输出为明文P和验证标签tag *（判断是否与tag匹配，若是则返回明文P，否则返回空）。

SCREAM和iSCREAM加密过程共分3个阶段，如图1所示，相关数据处理阶段、明文加密阶段、生成tag阶段。第一阶段，把相关数据A划分为128位的分组，第i个分组表示为可调分组加密器E（ k）对进行加密，然后将所有输出值进行异或，便得到这一步的主要输出值（表示为auth）。如果最后一个分组长度不足128位，用1和0填充，使得最后一个分组为128位（填充的数据表示为如果最后一个分组长度为128位，那么不需要填充，只是在加密过程中使用不同的。第二阶段，将明文P划分为128位的分组，用加密模块E（ k）对进行加密，输出密文表示为Ci。如果明文的最后一个分组长度不足128位，则对明文最后分组的位长加密，将输出值截取同样长度后与明文异或，得到密文，所以明文和密文长度是相同的。第三阶段，将所有明文分组（填充后的明文）进行异或得到校验和Σ，然后对校验和进行加密，将输出值与auth异或得到tag。

在TAE模型中，为了增强加密算法的安全性，在加密不同分组时采用不同的T值。一般情况下，T表示为c是明文分组计数器。具体情况如下。

相关数据处理阶段：

1）相关数据最后一个分组除外

2）相关数据最后一个分组为128位

3）相关数据最后一个分组不足128位

明文加密阶段：

1）明文最后一个分组除外

图1　SCREAM和iSCREAM的加密过程

2）明文最后一个分组为128位

3）明文最后一个分组不足128位

tag标签生成阶段：

1）明文最后一个分组为128位

2）明文最后一个分组不足128位

N和特定常数级联构成 T*、T∑，该常数取决于明文的最后分组否是128位。如果N相同且明文的最后分组长度相同，那么对应的 T*、T∑相同。

3　伪造攻击的基本思想

Brincat等在文献［12］中提出了一种攻击方法，即伪造攻击（forgery attack），这一攻击已广泛的应用到CAESAR算法［13，14］的攻击当中。本文给出了3种形式的伪造方式，其基本思想归纳为：假设攻击者已经知道某一对应关系，输入（明文1、公开变量1、相关数据1）与输出（密文1、认证标签1）有效对应。那么，如果能够找到另一输入（明文2、公开变量2、相关数据2）与输出（密文2、认证标签2）有效对应，而这一对应关系是不被密钥持有者所知晓的，那么就称这一过程为有效的伪造攻击。

4　对SCREAM和iSCREAM的删除明文伪造攻击（以SCREAM为例）

根据第1节对SCREAM的介绍，设明文长度为m个分组。在P0到Pm-2这m-1个明文加密过程中，可变参数是根据计数器c变化的；当加密Pm-1时，可变参数为常量或根据算法的这种特性，攻击过程如下。

步骤1对m个分组的明文P进行加密，加密过程如图2所示。设随机数为N，相关数据为A，输入明文为其中（共r-1个分组，其输出为（C， tag），其中

图2　m个分组明文的加密过程

步骤2保持随机数N、相关数据A与步骤1不变，伪造m-r+1个分组的明文P'=（与步骤1相比删除了明文中间连续的r-1个分组），如图3所示。那么，输出值为其中

伪造攻击正确性分析如下。

因为步骤1和步骤2这两次加密过程随机数N和相关数据A都相同，根据引理1可知，步骤1、步骤2中Tc'、T*'对应相同，因此两次加密过程具有相同的auth值（在图1和图2中将相关数据处理阶段省略，只假设该阶段输出值为auth）。步骤1中，加密m个分组的明文有所以即步骤1和步骤2得到的累加和相同。又因为步骤1和步骤2中N相同，且明文的最后分组都是Pm-1，根据引理1可知两次加密的T∑相同。由以上3个条件和tag的生成原理可知：tag'=tag，即两次加密得到的标签相同。

根据引理1可知两次加密对应的 Tc不变，P去掉Pm- r到Pm-2这r-1个连续的分组后得到明文P'，所以两次加密的前面m- r个明文的加密过程完全没有变，因此前r-1个输出密文不变。P和P'的最后一个分组都为Pm-1，根据引理1可知 T*不变，所以Pm-1的加密过程完全不变，因此Cm-1也不变。所以图3中输出密文为伪造成功的概率为1。

图3　个明文分组的加密过程

5　结果分析与对比

表1列出了SCREAM和iSCREAM的攻击结果。由表1可知，本文攻击对明文没有严格限制，成功概率为1，可以删除明文的r- 1个分组（2≤ r≤m），而文献［8］要求明文的最后分组为全0，伪造成功的概率为只能伪造明文的最后位（随着伪造位数 n的增大，成功概率指

1数倍减小）。文献［9］的时间复杂度、数据复杂度都远大于本文攻击，且只对iSCREAM算法有攻击性，并不能攻击SCREAM算法。因此本文提出的攻击更加实用有效。

表1　SCREAM和iSCREAM的攻击结果比较

6　结束语

认证加密是当前密码学者研究的热点和难点。本文基于认证加密算法SCREAM的参数特点，利用累加值碰撞的思想寻找出新的明文、密文对应关系，从而实现新伪造攻击。在新攻击过程中，经过一次加解密模块访问后，成功伪造的概率为1。与已有的攻击相比，新攻击所需的复杂度低、攻击范围大。该攻击同样适用于iSCREAM（SCREAM的变体算法）。

［1］CAESAR-competition for authenticated encryption：security，applicability and robustness［DB/OL］.http：//competitions.cr.yp.to/ caesar.html.

［2］NASOUR B，JAVAD A，MOHAMMAD R.A single query forgery on avalanchev1［J］.Cryptographic Competitions Mailing List，2014.

［3］GUY B.Forgery on stateless cmcc［DB/OL］.http：//eprint.iacr.org/ eprint-bin/search.pl.

［4］CHRISTOPH D，MARIA E，FLORIAN M，et al.Forgery and key recovery attacks on calico［DB/OL］.http：//ascon.iaik.tugraz.at/files/ analysis_calico.pdf.

［5］THOMAS F，GAËTAN L，VALENTIN S.Forgery and keyrecovery attacks on CAESAR candidate marble［DB/OL］.https：//www.researchgate.net/publication/278829118_Forgery_and_key-Recovery_ Attacks_on_CAESAR_Candidate_Marble.

［6］GROSSO V，LEURENT G，STANDAERT F，et al.SCREAM& iSCREAM side-channel resistant authenticated encryption with masking［DB/OL］.http：//competitions.cr.yp.to/roundl/screamvl.pdf.

［7］GROSSO V，LEURENT G，STANDAERT F，et al.LS-designs：bitsliceencryption for efficient masked software implementations［C］//Fast Software Encryption.Berlin：Springer，c2014：18-37.

［8］ SIANG M，LEI W.Practical forgery attacks on scream and iscream［DB/OL］.http：//www1.spms.ntu.edu.sg/～syllab/m/images/b/b3/ Forgery AttackonSCREAM.pdf.

［9］ GREGOR L，BRICE M，SONDRE R.A generic approach to invariant subspace attacks：cryptanalysis of robin，iscream and zorro［DB/OL］.http：//link.springer.com/chapter/10.1007%2F978-3-662-46800-511.

［10］ABED F，FORLER C，LUCKS S.General Overview of the First-Round CAESAR Candidates for Authenticated Ecryption［R］.2014.［11］LISKOV M，RIVEST R L，WAGNER D.Wagner.Tweakable block ciphers［J］.Journal of Cryptology，2011，24（3）：588-613.

［12］BRINCATK，MITCHELLCJ.NewCBC-MACforgery attacks［C］//Lecture Notes in Computer Science.c2010：3-14.

［13］陈杰，胡予濮，韦永壮.随机消息伪造攻击PMAC和TMAC-V［J］.计算机学报，2007，30（10）：1827-1832.CHENJ，HUY P，WEIY Z.Randommessageforgeryattack PMAC and TMAC-V［J］.ChineseJournalofComputers，2007，30（10）：1827-1832.

［14］晁仕德，张绍兰，田华，等.改进的PMAC及安全性分析［J］.计算机工程与应用，2009，45（21）：77-78.CHAO S D，ZHANG S L，TIAN H，et al.Modified PMAC and security analysis［J］.Computer Engineering and Applications，2009，45（21）：77-78.

New forgery attack on the authenticated cipher SCREAM and iSCREAM

TIAN Yu-dan1，WEI Yong-zhuang2，3

（1.Guangxi Experiment Center of Information Sciences，Guilin University of Electronic Technology，Guilin 541004，China；2.KeyLaboratoryofCognitiveRadioandInformationProcessing，MinistryofEducation，GuilinUniversityofElectronicTechnology，Guilin541004，China；3.State Key Laboratory of Information Security，Institute of Information Engineering，ChineseAcademy of Sciences，Beijing 100039，China）

Authentication encryption algorithms have been widely used in networks security system since these algorithms can efficiently provide both privacy and integrity measurement for data transmission.Recently，authentication encryption algorithms have received attentions extensively since the event of CAESAR cipher solicitation was developed.SCREAM had been selected as one of the second-round candidates in CAESAR competition because of its novel structure and design idea.Currently，the security issue of SCREAM becomes an interesting research topic.Based on the characteristic of SCREAM variable parameters，a new forgery attack was proposed by using the basic idea of the sum collision.In particular，this attack could also be used to iSCREAM algorithm.Different to the best known attacks，the new attack requires less time and data complexities.It is shown that this new attack is more flexible and effective.Furthermore，the success probability of the forgery will be one.

SCREAM，iSCREAM，forgery attack，CAESAR，authentication

The National Natural Science Foundation of China（No.61100185）

TP309.7

A

10.11959/j.issn.2096-109x.2016.00012

2015-09-08；

2015-11-20。通信作者：韦永壮，walker_wei@msn.com

国家自然科学基金资助项目（No.61100185）

田玉丹（1990-），女，山东菏泽人，桂林电子科技大学硕士生，主要研究方向为认证加密。

韦永壮（1976-），男，广西田阳人，博士，桂林电子科技大学教授，主要研究方向为信息安全。