田玉丹，韋永壯

（1.桂林電子科技大學(xué)廣西信息科學(xué)實(shí)驗(yàn)中心，廣西 桂林 541004；

2.桂林電子科技大學(xué)認(rèn)知無(wú)線電與信息處理省部共建教育部重點(diǎn)實(shí)驗(yàn)，廣西 桂林 541004；3.中國(guó)科學(xué)院信息工程研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100039）

認(rèn)證加密算法SCREAM及iSCREAM的新偽造攻擊

田玉丹1，韋永壯2，3

（1.桂林電子科技大學(xué)廣西信息科學(xué)實(shí)驗(yàn)中心，廣西 桂林 541004；

2.桂林電子科技大學(xué)認(rèn)知無(wú)線電與信息處理省部共建教育部重點(diǎn)實(shí)驗(yàn)，廣西 桂林 541004；3.中國(guó)科學(xué)院信息工程研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100039）

認(rèn)證加密算法能同時(shí)提供信息的加解密及完整性檢驗(yàn)兩個(gè)功能，它已被廣泛應(yīng)用于各種網(wǎng)絡(luò)安全系統(tǒng)中。最近伴隨著歐洲CAESAR密碼算法的征集活動(dòng)，認(rèn)證加密算法倍受業(yè)界關(guān)注。SCREAM算法憑借其新穎的設(shè)計(jì)理念和算法結(jié)構(gòu)，已經(jīng)順利入圍CAESAR競(jìng)選中的第二輪候選算法。而該算法是否存在新的安全性問(wèn)題是目前的研究熱點(diǎn)之一?；赟CREAM參數(shù)的變化特點(diǎn)，利用累加值碰撞的思想提出了一種新的偽造攻擊。研究結(jié)果表明，新攻擊成功的概率為1，所需的時(shí)間復(fù)雜度及數(shù)據(jù)復(fù)雜度均可忽略；此外該攻擊同樣適用于SCREAM的一種變體算法，即iSCREAM。與已有的攻擊相比較，新攻擊所需的復(fù)雜度更低，攻擊范圍更靈活有效。

SCREAM；iSCREAM；偽造攻擊；CAESAR；認(rèn)證

1　引言

認(rèn)證加密算法可以同時(shí)實(shí)現(xiàn)信息的加解密和完整性檢驗(yàn)兩個(gè)功能，它已被廣泛應(yīng)用于各種網(wǎng)絡(luò)安全系統(tǒng)中。2013年以來(lái)，伴隨著CAESAR征集活動(dòng)［1］，認(rèn)證加密算法倍受廣泛關(guān)注［2～5］。Vincent等基于可調(diào)認(rèn)證加密模型所提出的SCREAM算法［6］具有新穎的設(shè)計(jì)理念和算法結(jié)構(gòu)，并順利入圍CAESAR第二輪候選算法。該算法采用LS基本模型［7］及SPN基本加密模塊，具有安全性高、加密速率快、抵抗側(cè)信道攻擊等優(yōu)點(diǎn)。分組長(zhǎng)度為128位，明文和相關(guān)數(shù)據(jù)長(zhǎng)度分別小于（ n表示隨機(jī)

b數(shù)N的字節(jié)長(zhǎng)度）和個(gè)字節(jié)，N的長(zhǎng)度范圍在1到15個(gè)字節(jié)之間。SCREAM和iSCREAM的區(qū)別在于SPN型結(jié)構(gòu)不同。目前該算法倍受關(guān)注，其主要分析結(jié)果如下。

Siang等［8］針對(duì)SCREAM和iSCREAM提出偽造攻擊；成功偽造的概率是（設(shè)明文的最后分組為個(gè)0），時(shí)間復(fù)雜度和數(shù)據(jù)復(fù)雜度可以忽略不計(jì)。Gregor等［9］針對(duì)iSCREAM提出“依附S盒不變子空間”的攻擊方法，通過(guò)尋找弱密鑰恢復(fù)全部密鑰。該攻擊數(shù)據(jù)復(fù)雜度為個(gè)選擇明文，時(shí)間復(fù)雜度為。文獻(xiàn)［10］對(duì)SCREAM 和iSCREAM的基本結(jié)構(gòu)進(jìn)行分析，并歸了算法中的TAE模型及SPN結(jié)構(gòu)。

由上可知，文獻(xiàn)［8］對(duì)明文要求高、攻擊范圍小、成功概率低；文獻(xiàn)［9］是基于SPN結(jié)構(gòu)的攻擊，該攻擊數(shù)據(jù)復(fù)雜度、時(shí)間復(fù)雜度都較高，且只能攻擊iSCREAM算法。那么，針對(duì)SCREAM和iSCREAM能否找到一個(gè)高效的攻擊，成為當(dāng)前密碼學(xué)者研究的熱點(diǎn)之一。

本文根據(jù)SCREAM和iSCREAM的可變參數(shù)T的計(jì)數(shù)特點(diǎn)提出新偽造攻擊。研究表明，新攻擊可以刪除明文的r-1個(gè)分組，使生成的標(biāo)簽tag不變。該攻擊成功的概率為1，時(shí)間復(fù)雜度、數(shù)據(jù)復(fù)雜度可忽略不計(jì)。因此該攻擊具有范圍廣、效率高等優(yōu)點(diǎn)。

2　SCREAM和iSCREAM算法介紹

通過(guò)對(duì)可調(diào)認(rèn)證加密模型［11］（TAE）改進(jìn)得到算法SCREAM和iSCREAM。SCREAM和iSCREAM是128位加密算法，其基本模塊E（ k）的SPN結(jié)構(gòu)包括8位S盒和16位L盒。加密過(guò)程為其輸入是明文P、128位密鑰K、隨機(jī)數(shù)N（建議使用12字節(jié)）和相關(guān)數(shù)據(jù)A，輸出為密文C和標(biāo)簽tag。解密過(guò)程為輸出為明文P和驗(yàn)證標(biāo)簽tag *（判斷是否與tag匹配，若是則返回明文P，否則返回空）。

SCREAM和iSCREAM加密過(guò)程共分3個(gè)階段，如圖1所示，相關(guān)數(shù)據(jù)處理階段、明文加密階段、生成tag階段。第一階段，把相關(guān)數(shù)據(jù)A劃分為128位的分組，第i個(gè)分組表示為可調(diào)分組加密器E（ k）對(duì)進(jìn)行加密，然后將所有輸出值進(jìn)行異或，便得到這一步的主要輸出值（表示為auth）。如果最后一個(gè)分組長(zhǎng)度不足128位，用1和0填充，使得最后一個(gè)分組為128位（填充的數(shù)據(jù)表示為如果最后一個(gè)分組長(zhǎng)度為128位，那么不需要填充，只是在加密過(guò)程中使用不同的。第二階段，將明文P劃分為128位的分組，用加密模塊E（ k）對(duì)進(jìn)行加密，輸出密文表示為Ci。如果明文的最后一個(gè)分組長(zhǎng)度不足128位，則對(duì)明文最后分組的位長(zhǎng)加密，將輸出值截取同樣長(zhǎng)度后與明文異或，得到密文，所以明文和密文長(zhǎng)度是相同的。第三階段，將所有明文分組（填充后的明文）進(jìn)行異或得到校驗(yàn)和Σ，然后對(duì)校驗(yàn)和進(jìn)行加密，將輸出值與auth異或得到tag。

在TAE模型中，為了增強(qiáng)加密算法的安全性，在加密不同分組時(shí)采用不同的T值。一般情況下，T表示為c是明文分組計(jì)數(shù)器。具體情況如下。

相關(guān)數(shù)據(jù)處理階段：

1）相關(guān)數(shù)據(jù)最后一個(gè)分組除外

2）相關(guān)數(shù)據(jù)最后一個(gè)分組為128位

3）相關(guān)數(shù)據(jù)最后一個(gè)分組不足128位

明文加密階段：

1）明文最后一個(gè)分組除外

圖1　SCREAM和iSCREAM的加密過(guò)程

2）明文最后一個(gè)分組為128位

3）明文最后一個(gè)分組不足128位

tag標(biāo)簽生成階段：

1）明文最后一個(gè)分組為128位

2）明文最后一個(gè)分組不足128位

N和特定常數(shù)級(jí)聯(lián)構(gòu)成 T*、T∑，該常數(shù)取決于明文的最后分組否是128位。如果N相同且明文的最后分組長(zhǎng)度相同，那么對(duì)應(yīng)的 T*、T∑相同。

3　偽造攻擊的基本思想

Brincat等在文獻(xiàn)［12］中提出了一種攻擊方法，即偽造攻擊（forgery attack），這一攻擊已廣泛的應(yīng)用到CAESAR算法［13，14］的攻擊當(dāng)中。本文給出了3種形式的偽造方式，其基本思想歸納為：假設(shè)攻擊者已經(jīng)知道某一對(duì)應(yīng)關(guān)系，輸入（明文1、公開變量1、相關(guān)數(shù)據(jù)1）與輸出（密文1、認(rèn)證標(biāo)簽1）有效對(duì)應(yīng)。那么，如果能夠找到另一輸入（明文2、公開變量2、相關(guān)數(shù)據(jù)2）與輸出（密文2、認(rèn)證標(biāo)簽2）有效對(duì)應(yīng)，而這一對(duì)應(yīng)關(guān)系是不被密鑰持有者所知曉的，那么就稱這一過(guò)程為有效的偽造攻擊。

4　對(duì)SCREAM和iSCREAM的刪除明文偽造攻擊（以SCREAM為例）

根據(jù)第1節(jié)對(duì)SCREAM的介紹，設(shè)明文長(zhǎng)度為m個(gè)分組。在P0到Pm-2這m-1個(gè)明文加密過(guò)程中，可變參數(shù)是根據(jù)計(jì)數(shù)器c變化的；當(dāng)加密Pm-1時(shí)，可變參數(shù)為常量或根據(jù)算法的這種特性，攻擊過(guò)程如下。

步驟1對(duì)m個(gè)分組的明文P進(jìn)行加密，加密過(guò)程如圖2所示。設(shè)隨機(jī)數(shù)為N，相關(guān)數(shù)據(jù)為A，輸入明文為其中（共r-1個(gè)分組，其輸出為（C， tag），其中

圖2　m個(gè)分組明文的加密過(guò)程

步驟2保持隨機(jī)數(shù)N、相關(guān)數(shù)據(jù)A與步驟1不變，偽造m-r+1個(gè)分組的明文P'=（與步驟1相比刪除了明文中間連續(xù)的r-1個(gè)分組），如圖3所示。那么，輸出值為其中

偽造攻擊正確性分析如下。

因?yàn)椴襟E1和步驟2這兩次加密過(guò)程隨機(jī)數(shù)N和相關(guān)數(shù)據(jù)A都相同，根據(jù)引理1可知，步驟1、步驟2中Tc'、T*'對(duì)應(yīng)相同，因此兩次加密過(guò)程具有相同的auth值（在圖1和圖2中將相關(guān)數(shù)據(jù)處理階段省略，只假設(shè)該階段輸出值為auth）。步驟1中，加密m個(gè)分組的明文有所以即步驟1和步驟2得到的累加和相同。又因?yàn)椴襟E1和步驟2中N相同，且明文的最后分組都是Pm-1，根據(jù)引理1可知兩次加密的T∑相同。由以上3個(gè)條件和tag的生成原理可知：tag'=tag，即兩次加密得到的標(biāo)簽相同。

根據(jù)引理1可知兩次加密對(duì)應(yīng)的 Tc不變，P去掉Pm- r到Pm-2這r-1個(gè)連續(xù)的分組后得到明文P'，所以兩次加密的前面m- r個(gè)明文的加密過(guò)程完全沒(méi)有變，因此前r-1個(gè)輸出密文不變。P和P'的最后一個(gè)分組都為Pm-1，根據(jù)引理1可知 T*不變，所以Pm-1的加密過(guò)程完全不變，因此Cm-1也不變。所以圖3中輸出密文為偽造成功的概率為1。

圖3　個(gè)明文分組的加密過(guò)程

5　結(jié)果分析與對(duì)比

表1列出了SCREAM和iSCREAM的攻擊結(jié)果。由表1可知，本文攻擊對(duì)明文沒(méi)有嚴(yán)格限制，成功概率為1，可以刪除明文的r- 1個(gè)分組（2≤ r≤m），而文獻(xiàn)［8］要求明文的最后分組為全0，偽造成功的概率為只能偽造明文的最后位（隨著偽造位數(shù) n的增大，成功概率指

1數(shù)倍減?。Ｎ墨I(xiàn)［9］的時(shí)間復(fù)雜度、數(shù)據(jù)復(fù)雜度都遠(yuǎn)大于本文攻擊，且只對(duì)iSCREAM算法有攻擊性，并不能攻擊SCREAM算法。因此本文提出的攻擊更加實(shí)用有效。

表1　SCREAM和iSCREAM的攻擊結(jié)果比較

6　結(jié)束語(yǔ)

認(rèn)證加密是當(dāng)前密碼學(xué)者研究的熱點(diǎn)和難點(diǎn)。本文基于認(rèn)證加密算法SCREAM的參數(shù)特點(diǎn)，利用累加值碰撞的思想尋找出新的明文、密文對(duì)應(yīng)關(guān)系，從而實(shí)現(xiàn)新偽造攻擊。在新攻擊過(guò)程中，經(jīng)過(guò)一次加解密模塊訪問(wèn)后，成功偽造的概率為1。與已有的攻擊相比，新攻擊所需的復(fù)雜度低、攻擊范圍大。該攻擊同樣適用于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，F(xiàn)LORIAN 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，F(xiàn)ORLER 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］陳杰，胡予濮，韋永壯.隨機(jī)消息偽造攻擊PMAC和TMAC-V［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30（10）：1827-1832.CHENJ，HUY P，WEIY Z.Randommessageforgeryattack PMAC and TMAC-V［J］.ChineseJournalofComputers，2007，30（10）：1827-1832.

［14］晁仕德，張紹蘭，田華，等.改進(jìn)的PMAC及安全性分析［J］.計(jì)算機(jī)工程與應(yīng)用，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

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61100185）

田玉丹（1990-），女，山東菏澤人，桂林電子科技大學(xué)碩士生，主要研究方向?yàn)檎J(rèn)證加密。

韋永壯（1976-），男，廣西田陽(yáng)人，博士，桂林電子科技大學(xué)教授，主要研究方向?yàn)樾畔踩?/p>