認證加密算法SCREAM及iSCREAM的新偽造攻擊

田玉丹，韋永壯

（1.桂林電子科技大學廣西信息科學實驗中心，廣西 桂林 541004；

2.桂林電子科技大學認知無線電與信息處理省部共建教育部重點實驗，廣西 桂林 541004；3.中國科學院信息工程研究所信息安全國家重點實驗室，北京 100039）

認證加密算法SCREAM及iSCREAM的新偽造攻擊

田玉丹1，韋永壯2，3

（1.桂林電子科技大學廣西信息科學實驗中心，廣西 桂林 541004；

2.桂林電子科技大學認知無線電與信息處理省部共建教育部重點實驗，廣西 桂林 541004；3.中國科學院信息工程研究所信息安全國家重點實驗室，北京 100039）

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

SCREAM；iSCREAM；偽造攻擊；CAESAR；認證

1　引言

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

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

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

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

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

2　SCREAM和iSCREAM算法介紹

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

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

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

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

1）相關數(shù)據(jù)最后一個分組除外

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

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

明文加密階段：

1）明文最后一個分組除外

圖1　SCREAM和iSCREAM的加密過程

2）明文最后一個分組為128位

3）明文最后一個分組不足128位

tag標簽生成階段：

1）明文最后一個分組為128位

2）明文最后一個分組不足128位

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

3　偽造攻擊的基本思想

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

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

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

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

圖2　m個分組明文的加密過程

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

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

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

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

圖3　個明文分組的加密過程

5　結果分析與對比

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

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

表1　SCREAM和iSCREAM的攻擊結果比較

6　結束語

認證加密是當前密碼學者研究的熱點和難點。本文基于認證加密算法SCREAM的參數(shù)特點，利用累加值碰撞的思想尋找出新的明文、密文對應關系，從而實現(xiàn)新偽造攻擊。在新攻擊過程中，經(jīng)過一次加解密模塊訪問后，成功偽造的概率為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，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］陳杰，胡予濮，韋永壯.隨機消息偽造攻擊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-），男，廣西田陽人，博士，桂林電子科技大學教授，主要研究方向為信息安全。