對認證加密算法AES-OTR的偽造攻擊

鄭秀林 付伊鵬 宋海燕

1(北京電子科技學院 北京 100070)

2(西安電子科技大學 陜西 西安 710071)

對認證加密算法AES-OTR的偽造攻擊

鄭秀林1,2付伊鵬2宋海燕2

1(北京電子科技學院 北京 100070)

2(西安電子科技大學 陜西 西安 710071)

AES-OTR算法是CAESAR競賽中的一個競選算法，CAESAR競賽是2014年在國際密碼協會IACR主辦下由日本發起面向全球的征集認證加密算法的競賽活動。AES-OTR憑借自身獨特的優點順利進入了第三輪的篩選，該算法加密和認證都是基于分組密碼AES。但是AES-OTR加密時各塊的相對獨立性以及簡單的標簽產生方法，使得存在有效的偽造攻擊方法。針對該算法的這些缺點，提出在已知明文條件下，當關聯數據和公共消息數重用時對AES-OTR的偽造攻擊方法，同時證明了偽造方法的有效性，并且計算了偽造方法成功的概率。

AES-OTR算法 認證加密 偽造攻擊 分組密碼

0 引 言

我們知道保密性[1]和完整性[2]是信息安全的兩大核心目標，保密性是對抗敵手的被動攻擊，保證信息不泄露給未經授權的一方。完整性是對抗敵手的主動攻擊，防止信息被未授權的一方修改、偽造。認證加密算法能夠同時保證信息的機密性和完整性，是一種同時具有加密和認證兩種屬性的密碼算法。目前大量的信息在傳輸過程中不但需要保密，而且接收者收到信息后還需要對信息進行認證，保證信息在傳輸過程中的保密性、完整性和真實性。因此對于認證加密算法的設計和研究就顯得非常必要了，CAESAR競賽[3]共征集到 57個算法，要經過三輪篩選，預計到2017年12月底公布最終的勝選算法，目前正處于第三輪安全性評估階段。認證加密算法不同于之前的加密算法，其加密后的輸出不僅有密文C，還有與密文或明文有關的標簽T，在發送給接收方時，C和T要一起發送過去。當接收方收到信息后，分離出C和T，之后用解密算法對密文C進行解密，同時產生一個新的標簽T′ ，這個標簽與由C解密后得到的明文有關，因此如果密文C在傳輸過程中被人篡改，那么產生的T′和T是不一樣的，這時解密得到的密文是無效的，如果T′和T相等，那么解密得到的明文是有效的明文,文獻[4]的第17章對認證加密算法的定義及發展情況有詳細的描述。偽造攻擊[5]就是在改變密文的情況下，同時又做到不被接收方察覺，也就是能夠通過解密驗證，使得解密后的明文是有效的。

AES-OTR[6]算法是基于分組密碼AES[7]設計的認證加密算法,該算法在密文產生階段用到了公共消息數N,標簽產生階段用到了關聯數據A。

1 AES-OTR算法的描述

1.1 基本符號

如果沒有別的說明n一般取128，Ek代表的是AES加密函數，其中的密鑰為k，|k|∈{128,192,256}。對于X,Y∈{0,1}n，Y=Ek(X)表示明文X在密鑰k下，通過AES加密后的密文是Y。

1.2 輸入和輸出

Κae、Nae、Aae、Mae、Cae、Tae分別表示密鑰集合、公共消息數集合、關聯數據集合、明文集合、密文集合和標簽集合，在這里，Kae∈{0,1}|K|,Nae∈{0,1}|N|,Aae={0,1}8*,Mae=Cae={0,1}8*,Tae={0,1}τ其中τ∈{32,40,…,128}。

加密算法需要下列序列：

? 密鑰K∈Κae

? 公共消息數N∈Νae

? 關聯數據A∈Αae

? 明文M∈Μae

輸出序列為：密文(C,T)∈Cae×Tae

解密算法需要下列序列：

? 密鑰K∈Κae

? 公共消息數N∈Νae

? 關聯數據A∈Αae

? 密文(C,T)∈Cae×Tae

輸出序列為：明文M∈Μae或者為無效的信息記為⊥。

1.3 AES-OTR的加密和標簽的產生

C[2i-1]=Ek(2i-1L⊕M[2i-1])⊕M[2i]

(1)

C[2i]=EK(2i-1L⊕δ⊕C[2i-1])⊕M[2i-1]

(2)

因為是兩兩分組，所以分為m是奇數和偶數兩種情況，這兩種情況的不同之處是對最后一塊明文的處理不同，如圖2所示。加密過程用到L和δ，這兩個參數都是對公共消息數N進行處理得到的，圖3是對關聯數據A的處理，由關聯數據得到TA，標簽T的產生過程用到了TA。圖4中Σ的表達式與m的奇偶有關，當m為偶數時：

(3)

L*=2l-1L⊕δ

(4)

當m為奇數時：

(5)

L*=2l-1L

(6)

發送者將圖1、圖2和圖4得到的密文C和標簽T發送給接收方，其中C=C[1]‖C[2]‖…‖C[m]。

圖1 AES-OTR算法對明文(除去最后一組)的處理過程

圖2 AES-OTR對最后一組明文的處理過程

圖3 由關聯數據A得到TA

圖4 標簽的生成過程

1.4 AES-OTR的解密和驗證

當接收方收到(C,T)后，通過N、A、C和解密算法可以得到M和T′。如果T′=T，那么解密得到的明文M是有效的，如果T′≠T，那么得到的M是無效的。解密過程和加密過程非常類似，這里不再贅述，具體過程可以參考文獻[2]。

2 對AES-OTR的偽造攻擊

設我們手中有s+1對明密文，下面分別討論s=0和s>0這兩種情況下偽造成功的概率，當s=0時，也就是僅僅知道一對明密文，當s>0時，即知道多對明密文。

2.1 s=0時的偽造攻擊

設已知的明文為M，經加密后得到(C,T)，偽造的密文記為(C*,T*)，解密后的明文記為M*。

2.1.1 偽造方法介紹

首先對明文M和C進行分塊(在這里要求明文長度|M|必須是n的倍數,且為奇數倍),

其中m是奇數且對于1≤i≤m，|M[i]|=n，我們設M*和C*的分塊結果為：

其中m是奇數，最后一塊的長度不一定是n。設r=(m-1)/2，下面分三種情況進行討論：

1) 如果存在一個i∈{1,2,…,r}滿足如下式子：

C[2i-1]⊕M[2i]=C[2i]⊕M[2i-1]

(7)

通過式(1)和式(2)我們得到：

δ=M[2i-1]⊕C[2i-1]

(8)

如果我們選擇|M*[m]|

pad(M*[m])=M[m]⊕M[2i-1]⊕C[2i-1]

(9)

當1≤k

(10)

那么其解密后對應的密文為：

當1≤k

(11)

C*[m]=msb|M*|(C[m]⊕M[m])⊕M*[m]

(12)

因此我們選擇式(11)、式(12)所示的密文，標簽選擇T*=T，此時(C*,T*)是有效的。

2) 如果存在兩個不等的數i,j∈{1,2,…,r}滿足：

C[2i]⊕M[2i-1]=C[2j]⊕M[2j-1]

(13)

通過式(2)得到：

2i-1L⊕C[2i-1]=2j-1L⊕C[2j-1]

(14)

對式(14)進行變形得到：

2i-1L⊕M[2i-1]= 2j-1L⊕C[2j-1]⊕

M[2i-1]⊕C[2i-1]

(15)

通過式(1)和式(15)得到：

C[2i-1]⊕M[2i]=

Ek(2j-1L⊕C[2j-1]⊕M[2i-1]⊕C[2i-1])

(16)

如果我們選擇如下明文：

M*[2j-1]=C[2j-1]⊕M[2i-1]⊕C[2i-1]

(17)

M*[2j]=C[2i-1]⊕M[2i]⊕C[2j-1]

(18)

M*[m]=M[m]⊕M[2j]⊕C[2i-1]⊕

M[2i]⊕C[2j-1]

(19)

當k?{2j-1,2j,m}時，M*[k]=M[k]

(20)

由明文得到密文為：

C*[2j]=C[2j]⊕M[2j-1]⊕C[2j-1]⊕

M[2i-1]⊕C[2i-1]

(21)

C*[m]=C[m]⊕M[2j]⊕C[2i-1]⊕

M[2i]⊕C[2j-1]

(22)

當k?{2j,m}時，C*[k]=C[k]

(23)

因此我們選擇式(21)-式(23)所示的密文，標簽選擇T*=T，此時(C*,T*)是有效的。

3) 如果存在兩個不等的數i,j∈{1,2,…,r}滿足：

M[2i]⊕C[2i-1]=M[2j]⊕C[2j-1]

(24)

通過式(1)得到：

M[2i-1]⊕M[2j-1]=2i-1L⊕2j-1L

(25)

如果我們選擇如下明文：

M*[2j]=M[2i]⊕M[2i-1]⊕M[2j-1]

(26)

M*[2i]=M[2j]⊕M[2i-1]⊕M[2j-1]

(27)

當k?{2j,2i}時，M*[k]=M[k]

(28)

其對應的密文是：

C*[2j]=C[2i]⊕M[2i-1]⊕M[2j-1]

(29)

C*[2i]=C[2j]⊕M[2i-1]⊕M[2j-1]

(30)

C*[2i-1]=C[2j-1]⊕M[2i-1]⊕

M[2j-1]

(31)

C*[2j-1]=C[2i-1]⊕M[2i-1]⊕

M[2j-1]

(32)

當k?{2j,2i,2j-1,2i-1}時，C*[k]=C[k]

(33)

因此我們選擇式(29)-式(33)所示的密文，標簽選擇T*=T，此時(C*,T*)是有效的。

2.1.2 證明(C*,T*)的有效性

要想證明(C*,T*)的有效性，需要證明C*解密后得到的標簽T′和收到的標簽T*相等。

對于情況一，首先M*[m]的長度不是n，由圖4我們知道標簽的產生發生了變化，因為TA未變化，因此要想證明T′=T*(即T)，需要證明TE′=TE，由式(8)和式(9)得到pad(M*[m])=M[m]⊕δ,由TE的產生方法以及3L*未變化，可以得到TE*=TE，那么解密得到的標簽T′=T即T′=T*。

對于情況二，由式(18)和式(19)我們得到M*[2j]⊕M*[m]=M[2j]⊕M[m]，由此我們保證了Σ的值沒有變化，而3L*、δ和明文最后一塊的長度也沒變化，因此，保證了標簽值未變化，即T′=T，也就是T′=T*。

對于情況三，由式(26)和式(27)我們得到M*[2i]⊕M*[2j]=M[2i]⊕M[2j]，由此我們保證了Σ的值沒有變化，而3L*、δ也沒變化，因此保證了標簽值未變化，即T′=T，也就是T′=T*。

2.1.3 計算偽造成功的概率

計算成功的概率P，需要把式(7)、式(13)、式(24)成功的概率相加，設式(7)、式(13)、式(24)成功的概率分別為P1、P2、P3，則：

(34)

進一步計算得P=r2·2-n。

2.2 s>0時的偽造攻擊

假設我們的手中有s+1對明密文對可用，分別記為M0、M1、…、Ms，他們對應的密文和標簽分別記為(C0,T0)、(C1,T1)、…、(Cs,Ts)，我們的目標是偽造出一對有效的帶標簽的密文，不妨借用M0的標簽，偽造的密文記為(C*,T*)，其中T*=T0。

2.2.1 偽造方法介紹

偽造算法F0：

第一步在加密過程中，首先對s+1對明文進行分塊，如下所示：

?

以上s+1對明文對應的密文分塊為：

?

我們設m=min(m0,m1,…,ms)，r=「m/2?-1。

第二步我們尋找滿足下面等式的明文塊，

M0[k1]⊕M0[k2]⊕…⊕M0[ki]=

Mt1[k1]⊕Mt2[k2]⊕…⊕Mti[ki]

(35)

其中2≤i≤r，k1,k2,…,ki∈{2,4,…,2r}且k1

第三步找到一組(k1,k2,…,ki)和(t1,t2,…,ti)，那么我們偽造的密文C*是將C0中的C0[kj-1]和C0[kj]替換為Ctj[kj-1]和Ctj[kj]；這樣就得到C*，用公式表示即對于1≤q≤r：

C*[2q-1]‖C*[2q]=

(36)

對于2r

(37)

此時我們已經構造出了C*，標簽為T*=T0。

2.2.2 證明(C*,T*)的有效性

要證明(C*,T*)的有效性，根據前面介紹的AES-OTR解密驗證，我們需要證明C*解密后的得到的標簽T′滿足T′=T*(即T0)。

首先計算C*解密后得到的明文的表達式,根據式(36)和式(37)，以及已知的明密文的對應關系，我們可以得到M*的表達式，用公式表示即當1≤q≤r時：

M*[2q-1]‖M*[2q]=

(38)

對于2r

(39)

由圖4我們知道了標簽T由Σ、|M|、N和A決定，N和A沒變，根據式(38)和式(39)我們知道|M*|=|M0|，接下來只需要證明Σ*=Σ0即可。

根據AES-OTR的加密，我們得到Σ*和Σ0的計算公式(這里我們假設m0為偶數，奇數情況與此類似)。

(40)

(41)

Σ*⊕Σ0=Mt1[k1]⊕Mt2[k2]⊕…⊕Mti[ki]⊕

M0[k1]⊕M0[k2]⊕…⊕M0[ki]

(42)

根據式(35)得到：

Σ*⊕Σ0=0

(43)

即Σ*=Σ0，綜上(C*,T*)是有效的。

2.2.3 計算偽造成功的概率

下面我們偽造算法成功的概率，在這里我們假設已知的明文都是隨機且獨立[9]的。

設Pi表示式(35)成功的概率，那么偽造算法F0成功的概率為：

(44)

根據文獻[9]中的概率論知識，我們可以得到：

(45)

那么：

(46)

對于i≥2，下面不等式(47)一定成立：

(47)

則式(46)可以變為：

(48)

將常數項提到前邊，并且進一步計算得到：

(49)

當r較大時(如r>10)，r+1相比于2r可以忽略；我們知道2n(n一般取128)是一個非常大的數，因此根據文獻[10]中等價無窮小的知識，我們可以得到1-(1-1/2n)s2的等價無窮小為s2/2n。

因為s+1對明密文對中有s+1個標簽可用，所以偽造成功的概率為s2(s+1)2r-n。

明密文對各自也可獨立進行偽造，方法和第一種情況一樣，但是因為這個概率相比于s2(s+1)2r-n非常的小，并且還要求明文最后一塊必須是n的倍數且m必須是奇數，因此2.2.3節的計算忽略了這個概率。

3 結 語

本文針對AES-OTR 算法的特點，分別提出了僅僅知道一對明密文和多對明密文的情況下的偽造攻擊方法，并且分別證明了算法的有效性，計算了算法成功的概率，這對于AES-OTR算法的安全性分析有重要參考意義的。式(7)、式(13)、式(24)三個式子的編程查找是容易實現的，而式(35)的快速有效的編程查找并不容易，將作為下一步的研究目標。

[1] Lo A,Grotevant H,McRoy R.Privacy and Confidentiality in Adoption Research:Perspectives from the Minnesota/Texas Adoption Research Project[D].University of Massachusetts Amherst,2016.

[2] Sumra I A,Hasbullah H B,AbManan J B.Attacks on security goals (confidentiality,integrity,availability) in VANET:a survey[M]//Vehicular Ad-Hoc Networks for Smart Cities.Springer Singapore,2015:51-61.

[3] CAESAR-Competition for Authenticated Encryption:Security,Applicability,and Robustness(2014)[OL].http://competitions.cr.yp.to/Caesar.html.

[4] 吳文玲.分組密碼的設計與分析[M].北京:清華大學出版社,2009:371-391.

[5] Nandi M.Forging attacks on two authenticated encryption schemes COBRA and POET[C] //International Conference on the Theory and Application of Cryptology and Information Security.Springer Berlin Heidelberg,2014:126-140.

[6] Minematsu K.Parallelizable rate-1 authenticated encryption from pseudorandom functions[C] //Annual International Conference on the Theory and Applications of Cryptographic Techniques.Springer Berlin Heidelberg,2014:275-292.

[7] Daemen J,Rijmen V.The design of Rijndael:AES-the advanced encryption standard[M].Springer Science & Business Media,2013.

[8] Suzaki T,Minematsu K.Improving the generalized Feistel[C]//International Conference on FAST Software Encryption.Springer-Verlag,2010:19-39.

[9] 王志江.概率論與數理統計[M].北京:高等教育出版社,2011.

[10] 趙修坤.微積分[M].3版.北京:國防工業出版社,2012.

FORGINGATTACKSONAUTHENTICATEDENCRYPTIONALGORITHMAES-OTR

Zheng Xiulin1,2Fu Yipeng2Song Haiyan2

1(BeijingElectronicsScienceandTechnologyInstitute,Beijing100070,China)2(XidianUniversity,Xi’an710071,Shaanxi,China)

AES-OTR algorithm is a campaign of CAESAR competition, the competition is sponsored by the international cryptography Association IACR and launched by Japan in order to collect authentication and encryption algorithm to the whole world. AES-OTR has successfully entered the third round of screening by virtue of its unique advantages. Encryption and authentication of AES-OTR algorithm are all based on block cipher AES. But the relative independence of each block and label generation method is relatively simple make AES-OTR exists effective methods of forgery attack. For the disadvantages of this algorithm, this paper shows forgery attack on AES-OTR in the known plaintext conditions and association data and public message number are reused. At the same time, the validity of the methods is proved, and the probability of the success of the method is calculated.

AES-OTR algorithm Authentication and authorization Forgery attack Block cipher

TP309.7

A

10.3969/j.issn.1000-386x.2017.10.057

2016-12-22。鄭秀林，教授，主研領域：分組密碼和序列密碼的設計與分析。付伊鵬，碩士生。宋海燕，碩士生。