對認證加密算法Pyjamask的偽造攻擊*

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

(1.中國人民武裝警察部隊工程大學密碼工程學院，陜西 西安 710086;2.中國人民武裝警察部隊網絡與信息安全重點實驗室，陜西 西安 710086)

1 引言

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

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

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

2 Pyjamask算法描述

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

2.1 相關數據處理

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

(1)

式(2)為最后分組長度為r比特和不足r比特時auth的值計算方式：

(2)

Figure 1 Processing processes of related data

2.2 明文加密

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

Pad=EK(O*)

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

(3)

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

Figure 2 Encryption process of Pyjamask

2.3 tag生成

標簽tag生成部分(見圖2)是利用前2部分得到的auth和sum來生成最后的tag值，具體計算過程如式(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$等參數的計算方法是通過有限域dbl運算產生的，式(4)和式(5)分別表示明文未填充和經過填充時tag值的計算過程。調整參數Oi的計算過程相對獨立，通過式(6)和式(7)計算產生：

(6)

Oi=Oi-1⊕Lntz(i)

(7)

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

(8)

3 Pyjamask算法的偽造攻擊

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

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

Step1分別對明文分組Mi進行加密，加密過程如圖2所示。設公共消息為N，相關數據為A，輸入明文為M，其中存在分組Mm-r⊕Mm-r+1⊕…⊕Mm-3⊕Mm-2=0(共r-1個分組，2≤r≤m)，輸出密文C=C1‖C2‖…‖Cm-1‖Cm和標簽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個明文分組),加密過程如圖3所示。輸出值為(C′,tag′)，其中C′=C1‖C2‖…‖Cm-r-1‖C*。

Figure 3 Encryption process of m-r plaintext group

偽造攻擊的有效性分析：在2次加密過程中使用相同相關數據A的條件下，如圖1中對相關數據處理時的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存在以下關系：

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

Mm-1⊕Mm=∑M′

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

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

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

3.2.1s=0時的偽造攻擊

當s=0時，攻擊者只掌握1組明文M=M1‖M2‖…‖Mm-1‖Mm。通過引入差分對構造1組明文M′=M1‖…‖M′j‖…‖M′k‖…‖Mm-1‖Mm分組(在分組M′j和M′k中引入差分對)，如圖4所示，加密后產生的新標簽與使用原始明文加密得到的標簽一致，驗證通過。

Figure 4 Encryption process with differential pair

攻擊過程如下所示：

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

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

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

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

3.2.2 s>0時的偽造攻擊

Table 1 Comparison of analysis results of Pyjamask

4 結果對比與分析

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

5 結束語

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