賀水喻，魏悅川,2，潘 峰,2，暢利鵬

(1.中國人民武裝警察部隊(duì)工程大學(xué)密碼工程學(xué)院，陜西 西安 710086;2.中國人民武裝警察部隊(duì)網(wǎng)絡(luò)與信息安全重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710086)

1 引言

在信息傳輸過程中，信息的機(jī)密性[1]和完整性[2]是保證其安全的2大重要目標(biāo)。機(jī)密性保證信息不被泄露，是抵抗對(duì)手被動(dòng)攻擊的一種特性；完整性則防止信息被修改、被篡改，是抵抗對(duì)手主動(dòng)攻擊的一種特性。認(rèn)證加密AE(Authenticated Encryption)算法[3]，指能夠同時(shí)實(shí)現(xiàn)消息保密性和完整性的密碼算法，并做到同時(shí)滿足加密和認(rèn)證功能。在資源受限的環(huán)境中，在輕量化和降低資源消耗的同時(shí)，對(duì)實(shí)現(xiàn)數(shù)據(jù)加密和完整性認(rèn)證功能的密碼保護(hù)的需求急劇增長(zhǎng)。意識(shí)到這一問題，由美國標(biāo)準(zhǔn)技術(shù)研究所NIST(National Institute of Standards and Technology)發(fā)起了密碼競(jìng)賽。到目前為止，正在進(jìn)行輕量級(jí)密碼LWC(LightWeight Cryptography)標(biāo)準(zhǔn)化[4]。

Pyjamask算法[5]是NIST在全球范圍內(nèi)征集的后量子時(shí)代輕量級(jí)密碼算法之一，入選了LWC競(jìng)賽第2輪。該算法設(shè)計(jì)的目的為在有效抵抗側(cè)信道攻擊的同時(shí)，以其簡(jiǎn)單的結(jié)構(gòu)、較少的非線性門數(shù)量和適用于并行運(yùn)算的通用位片結(jié)構(gòu)來大大提高算法效率。目前，關(guān)于該算法的安全性分析相對(duì)較少，許澤雨[6]給出了Pyjamask-128的自動(dòng)化分析結(jié)果,包括Pyjamask-128的5輪差分分析、6輪飛來飛去(Boomerang)分析和4輪線性分析;Tian等人[7]通過積分攻擊得到了Pyjamask-96的11輪區(qū)分器;劉亞等人[8]對(duì)Pyjamask進(jìn)行了不可能差分分析，結(jié)果顯示該算法有很好的抗不可能差分性質(zhì)。前人從面向位的微觀角度對(duì)該算法進(jìn)行了相關(guān)分析，而相對(duì)于原始的操作模式，本文發(fā)現(xiàn)可以從結(jié)構(gòu)性質(zhì)上進(jìn)行明文偽造，依概率達(dá)到偽造成功的效果。

偽造攻擊[9]的基本思想是通過偽造不同的明文或密文分組從而產(chǎn)生與合法密文解密相同的認(rèn)證標(biāo)簽，達(dá)到通過認(rèn)證的目的。對(duì)于合法密文而言，該操作破壞了密文的完整性。本文對(duì)Pyjamask算法的結(jié)構(gòu)進(jìn)行分析時(shí)發(fā)現(xiàn)，該算法與入圍CAESAR(Competition for Authenticated Encryption: Security, Applicability and Robustness)競(jìng)賽[10]第2輪的SCREAM算法[11]結(jié)構(gòu)十分相似。結(jié)合田玉丹等人[12]對(duì)SCREAM算法利用累加值碰撞的思想提出的新偽造攻擊方法，本文實(shí)現(xiàn)了對(duì)Pyjamask算法的刪除明文偽造。在保持明文的異或值sum不變的情況下，本文通過選擇明文[13]進(jìn)行偽造，且成功通過了驗(yàn)證，從而達(dá)到對(duì)Pyjamask算法的選擇明文偽造攻擊。

2 Pyjamask算法描述

Pyjamask算法的基本模塊采用了SPN(Substitution-Permutation Network)結(jié)構(gòu)，算法包含2種分組長(zhǎng)度：96比特和128比特,分別對(duì)應(yīng)Pyjamask-96和Pyjamask-128。加密過程為(C,tag)=EK(N,A,M)，K表示密鑰，輸入可變長(zhǎng)的明文M、可變長(zhǎng)的相關(guān)數(shù)據(jù)A和定長(zhǎng)的公共消息N，輸出密文C和標(biāo)簽tag。解密過程為M=DK(N,A,C,tag)，輸出對(duì)應(yīng)明文M和驗(yàn)證標(biāo)簽tag*(判斷tag=tag*是否成立，若相等則返回明文M，否則返回空)。Pyjamask算法的加密過程共分為相關(guān)數(shù)據(jù)處理、明文加密和tag生成3個(gè)部分。

2.1 相關(guān)數(shù)據(jù)處理

Si=Si-1⊕EK(Ai⊕Oi)

(1)

式(2)為最后分組長(zhǎng)度為r比特和不足r比特時(shí)auth的值計(jì)算方式：

(2)

Figure 1 Processing processes of related data

2.2 明文加密

明文加密部分的輸入為密鑰K、公共消息N、相關(guān)數(shù)據(jù)A和明文M，輸出為密文C及產(chǎn)生的中間值sum,如圖2所示。與相關(guān)數(shù)據(jù)處理幾乎一致，將明文M分成m組，即M=M1‖M2‖…‖Mm。但是，在通過加密模塊EK前后都與Oi進(jìn)行異或得到密文C，即C=C1‖C2‖…‖Cm。若最后明文分組長(zhǎng)度不足r比特，生成密文的方式如式(3)所示：

Pad=EK(O*)

C*=M*⊕Pad[1…|M*|]

(3)

其中，Pad表示計(jì)算的中間量,Pad[1…|M*|]取Pad的后半段與M*運(yùn)算。sum值的計(jì)算方式為sum=M1⊕M2⊕…⊕Mm，相應(yīng)地，當(dāng)明文最后一個(gè)分組長(zhǎng)度不足r比特時(shí)：sum*=summ-1⊕(M*‖1‖0127-|M*|)。

Figure 2 Encryption process of Pyjamask

2.3 tag生成

標(biāo)簽tag生成部分(見圖2)是利用前2部分得到的auth和sum來生成最后的tag值，具體計(jì)算過程如式(4)和式(5)所示：

auth=HASH(K,A),

O$=Om⊕L$,

tag=EK(summ⊕O$)⊕HASH(K,A)

(4)

O$=O*⊕L$,

tag=EK(sum*⊕O$)⊕HASH(K,A)

(5)

其中，O$等參數(shù)的計(jì)算方法是通過有限域dbl運(yùn)算產(chǎn)生的，式(4)和式(5)分別表示明文未填充和經(jīng)過填充時(shí)tag值的計(jì)算過程。調(diào)整參數(shù)Oi的計(jì)算過程相對(duì)獨(dú)立，通過式(6)和式(7)計(jì)算產(chǎn)生：

(6)

Oi=Oi-1⊕Lntz(i)

(7)

其中，ntz(x)函數(shù)表示將x轉(zhuǎn)化為二進(jìn)制后，用所包含0的個(gè)數(shù)代替x;dbl(x)表示使用有限域字段中倍加操作，具體如式(8)所示：

(8)

3 Pyjamask算法的偽造攻擊

3.1 Pyjamask算法的刪除明文偽造攻擊

由第2節(jié)對(duì)Pyjamask算法的介紹可知，可將明文劃分為m個(gè)分組，即M=M1‖M2‖…‖Mm-1‖Mm(本文默認(rèn)最后一個(gè)明文分組是經(jīng)過填充的)，在加密明文的過程中對(duì)應(yīng)分組使用參數(shù)Om，第m分組使用O*。根據(jù)該特性可以進(jìn)行如下過程的攻擊:

Step1分別對(duì)明文分組Mi進(jìn)行加密，加密過程如圖2所示。設(shè)公共消息為N，相關(guān)數(shù)據(jù)為A，輸入明文為M，其中存在分組Mm-r⊕Mm-r+1⊕…⊕Mm-3⊕Mm-2=0(共r-1個(gè)分組，2≤r≤m)，輸出密文C=C1‖C2‖…‖Cm-1‖Cm和標(biāo)簽tag。

Step2保持Step 1中的N和A不變，偽造m-r組明文M′=M1‖M2‖…‖Mm-r-1‖Mm-r(其中Mm-r+1⊕Mm-r+2⊕…⊕Mm-1⊕Mm=0，故刪去這r個(gè)明文分組),加密過程如圖3所示。輸出值為(C′,tag′)，其中C′=C1‖C2‖…‖Cm-r-1‖C*。

Figure 3 Encryption process of m-r plaintext group

偽造攻擊的有效性分析：在2次加密過程中使用相同相關(guān)數(shù)據(jù)A的條件下，如圖1中對(duì)相關(guān)數(shù)據(jù)處理時(shí)的auth值是相同的。Step 1中加密明文M=M1‖M2‖…‖Mm-r-1‖Mm-r‖…‖Mm-2‖Mm-1‖Mm有Mm-r+1⊕Mm-r+2⊕…⊕Mm-1⊕Mm=0，因此2次加密的sum存在以下關(guān)系：

∑M=∑M′⊕Mm-r+1⊕Mm-r+2⊕…⊕

Mm-1⊕Mm=∑M′

即Step 1和Step 2加密過程得到的累加值sum是相同的。又因?yàn)?次保持加密過程中的公共消息N相同，且最后一個(gè)明文分組都是Mm,由文獻(xiàn)[6]知，加密過程中使用的參數(shù)O$僅與最后一個(gè)明文分組加密使用的參數(shù)Om相關(guān)，并且各參數(shù)與對(duì)應(yīng)的明文分組相對(duì)獨(dú)立。根據(jù)以上3個(gè)條件和tag的生成方式可知：tag′=tag，即2次加密得到的認(rèn)證標(biāo)簽相同，驗(yàn)證通過。根據(jù)圖3的加密過程，攻擊者可以成功獲得加密的密文，實(shí)現(xiàn)信息偽造，并且成功的概率為1。

3.2 Pyjamask算法的選擇明文偽造攻擊

針對(duì)Pyjamask算法類OBC(Operational Cipher Block)模式的結(jié)構(gòu)特性，攻擊者又可以通過在明文中引入差分對(duì)Δ⊕Δ′=0，使得2次加密時(shí)偽造的明文分組與原始明文分組計(jì)算所得的sum值相等，達(dá)到了高概率地引入差分對(duì)偽造攻擊的目的。攻擊者可以利用s+1組明文，即分別使用1組或多組明文進(jìn)行加密。根據(jù)明文分組異或得到sum這一特性，則2次加密可以產(chǎn)生相同的認(rèn)證標(biāo)簽，即tag′=tag，并且通過驗(yàn)證達(dá)到成功偽造的效果。

3.2.1s=0時(shí)的偽造攻擊

當(dāng)s=0時(shí)，攻擊者只掌握1組明文M=M1‖M2‖…‖Mm-1‖Mm。通過引入差分對(duì)構(gòu)造1組明文M′=M1‖…‖M′j‖…‖M′k‖…‖Mm-1‖Mm分組(在分組M′j和M′k中引入差分對(duì))，如圖4所示，加密后產(chǎn)生的新標(biāo)簽與使用原始明文加密得到的標(biāo)簽一致，驗(yàn)證通過。

Figure 4 Encryption process with differential pair

攻擊過程如下所示：

Step1選定公共消息N和相關(guān)數(shù)據(jù)A進(jìn)行處理，對(duì)已知的明文分組M=M1‖M2‖…‖Mm-1‖Mm進(jìn)行加密操作，得到中間值auth和明文的異或和sum，輸出(C,tag)。

Step2保持Step 1中的N和A不變。攻擊者通過給已知的明文M=M1‖M2‖…‖Mm-1‖Mm分組中注入差分對(duì)得到新的明文分組M′=M1‖…‖M′j‖…‖M′k‖…‖Mm-1‖Mm(1≤j

有效性分析：相關(guān)數(shù)據(jù)A依然保持不變，2次處理得到的auth值相同。在s=0時(shí)，引入差分對(duì)Δ⊕Δ′=0，偽造的明文中除M′j和M′k外，其它分組與已知明文M=M1‖M2‖…‖Mm-1‖Mm保持相同，加密過程得到的sum值相等，即:

因此，2組明文加密產(chǎn)生的認(rèn)證標(biāo)簽tag一致，偽造后的明文加密后得到密文C′=C1‖…‖C′j‖…‖C′k‖…‖Cm-1‖Cm，得證以概率1成功偽造。

3.2.2 s>0時(shí)的偽造攻擊

Table 1 Comparison of analysis results of Pyjamask

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

在實(shí)際操作過程中(如圖3和圖4所示)，攻擊者可以選用刪除明文和引入差分對(duì)實(shí)施偽造，并且偽造成功的概率為1，消耗的時(shí)間和數(shù)據(jù)復(fù)雜度為2，較為高效。通過累加遍歷多組明文,得到包含差分對(duì)的明文分組，以此進(jìn)行偽造時(shí)消耗的數(shù)據(jù)量較大，但成功偽造的概率仍然為1。表1列出了Pyjamask算法的現(xiàn)有分析結(jié)果，文獻(xiàn)中的分析方法所對(duì)應(yīng)的時(shí)間復(fù)雜度和數(shù)據(jù)復(fù)雜度均較高，因此本文提出的攻擊方法更加實(shí)用有效。

5 結(jié)束語

認(rèn)證加密算法的方案設(shè)計(jì)與安全性分析是當(dāng)前密碼學(xué)方向的研究重點(diǎn)及難點(diǎn)。本文基于Pyjamask算法的結(jié)構(gòu)和參數(shù)特點(diǎn)，提出了2種偽造方案，通過構(gòu)造明文，產(chǎn)生局部碰撞的方式，找到了與原始明密文產(chǎn)生相同tag的明密文對(duì)應(yīng)關(guān)系，成功實(shí)現(xiàn)了認(rèn)證標(biāo)簽的偽造。對(duì)于刪除明文的偽造，成功的概率為1，攻擊的時(shí)間復(fù)雜度和數(shù)據(jù)復(fù)雜度可以忽略不記，操作方式更加簡(jiǎn)便有效。對(duì)于選擇明文的偽造，當(dāng)攻擊者知道1組分組時(shí)，通過引入差分對(duì)，加密時(shí)產(chǎn)生碰撞，此時(shí)偽造成功的概率仍然為1，適用性良好；當(dāng)已知s+1組明文時(shí)，攻擊者通過已知的明文信息，獲取可產(chǎn)生碰撞的明文分組，并且將獲得的可碰撞明文分組引入預(yù)留的1組明文當(dāng)中，產(chǎn)生偽造，成功的概率也為1。本文在實(shí)際操作的過程中發(fā)現(xiàn)，相對(duì)于前2次攻擊，通過遍歷獲取可碰撞分組對(duì)數(shù)據(jù)的要求較高。