對(duì)認(rèn)證加密算法AES-OTR的偽造攻擊

鄭秀林 付伊鵬 宋海燕

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

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

對(duì)認(rèn)證加密算法AES-OTR的偽造攻擊

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

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

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

AES-OTR算法是CAESAR競(jìng)賽中的一個(gè)競(jìng)選算法，CAESAR競(jìng)賽是2014年在國(guó)際密碼協(xié)會(huì)IACR主辦下由日本發(fā)起面向全球的征集認(rèn)證加密算法的競(jìng)賽活動(dòng)。AES-OTR憑借自身獨(dú)特的優(yōu)點(diǎn)順利進(jìn)入了第三輪的篩選，該算法加密和認(rèn)證都是基于分組密碼AES。但是AES-OTR加密時(shí)各塊的相對(duì)獨(dú)立性以及簡(jiǎn)單的標(biāo)簽產(chǎn)生方法，使得存在有效的偽造攻擊方法。針對(duì)該算法的這些缺點(diǎn)，提出在已知明文條件下，當(dāng)關(guān)聯(lián)數(shù)據(jù)和公共消息數(shù)重用時(shí)對(duì)AES-OTR的偽造攻擊方法，同時(shí)證明了偽造方法的有效性，并且計(jì)算了偽造方法成功的概率。

AES-OTR算法 認(rèn)證加密 偽造攻擊 分組密碼

0 引 言

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

AES-OTR[6]算法是基于分組密碼AES[7]設(shè)計(jì)的認(rèn)證加密算法,該算法在密文產(chǎn)生階段用到了公共消息數(shù)N,標(biāo)簽產(chǎn)生階段用到了關(guān)聯(lián)數(shù)據(jù)A。

1 AES-OTR算法的描述

1.1 基本符號(hào)

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

1.2 輸入和輸出

Κae、Nae、Aae、Mae、Cae、Tae分別表示密鑰集合、公共消息數(shù)集合、關(guān)聯(lián)數(shù)據(jù)集合、明文集合、密文集合和標(biāo)簽集合，在這里，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

? 公共消息數(shù)N∈Νae

? 關(guān)聯(lián)數(shù)據(jù)A∈Αae

? 明文M∈Μae

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

解密算法需要下列序列：

? 密鑰K∈Κae

? 公共消息數(shù)N∈Νae

? 關(guān)聯(lián)數(shù)據(jù)A∈Αae

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

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

1.3 AES-OTR的加密和標(biāo)簽的產(chǎn)生

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

(1)

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

(2)

因?yàn)槭莾蓛煞纸M，所以分為m是奇數(shù)和偶數(shù)兩種情況，這兩種情況的不同之處是對(duì)最后一塊明文的處理不同，如圖2所示。加密過(guò)程用到L和δ，這兩個(gè)參數(shù)都是對(duì)公共消息數(shù)N進(jìn)行處理得到的，圖3是對(duì)關(guān)聯(lián)數(shù)據(jù)A的處理，由關(guān)聯(lián)數(shù)據(jù)得到TA，標(biāo)簽T的產(chǎn)生過(guò)程用到了TA。圖4中Σ的表達(dá)式與m的奇偶有關(guān)，當(dāng)m為偶數(shù)時(shí)：

(3)

L*=2l-1L⊕δ

(4)

當(dāng)m為奇數(shù)時(shí)：

(5)

L*=2l-1L

(6)

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

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

圖2 AES-OTR對(duì)最后一組明文的處理過(guò)程

圖3 由關(guān)聯(lián)數(shù)據(jù)A得到TA

圖4 標(biāo)簽的生成過(guò)程

1.4 AES-OTR的解密和驗(yàn)證

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

2 對(duì)AES-OTR的偽造攻擊

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

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

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

2.1.1 偽造方法介紹

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

其中m是奇數(shù)且對(duì)于1≤i≤m，|M[i]|=n，我們?cè)O(shè)M*和C*的分塊結(jié)果為：

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

1) 如果存在一個(gè)i∈{1,2,…,r}滿(mǎn)足如下式子：

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

(7)

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

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

(8)

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

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

(9)

當(dāng)1≤k

(10)

那么其解密后對(duì)應(yīng)的密文為：

當(dāng)1≤k

(11)

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

(12)

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

2) 如果存在兩個(gè)不等的數(shù)i,j∈{1,2,…,r}滿(mǎn)足：

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

(13)

通過(guò)式(2)得到：

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

(14)

對(duì)式(14)進(jìn)行變形得到：

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

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

(15)

通過(guò)式(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)

當(dāng)k?{2j-1,2j,m}時(shí)，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)

當(dāng)k?{2j,m}時(shí)，C*[k]=C[k]

(23)

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

3) 如果存在兩個(gè)不等的數(shù)i,j∈{1,2,…,r}滿(mǎn)足：

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

(24)

通過(guò)式(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)

當(dāng)k?{2j,2i}時(shí)，M*[k]=M[k]

(28)

其對(duì)應(yīng)的密文是：

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)

當(dāng)k?{2j,2i,2j-1,2i-1}時(shí)，C*[k]=C[k]

(33)

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

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

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

對(duì)于情況一，首先M*[m]的長(zhǎng)度不是n，由圖4我們知道標(biāo)簽的產(chǎn)生發(fā)生了變化，因?yàn)門(mén)A未變化，因此要想證明T′=T*(即T)，需要證明TE′=TE，由式(8)和式(9)得到pad(M*[m])=M[m]⊕δ,由TE的產(chǎn)生方法以及3L*未變化，可以得到TE*=TE，那么解密得到的標(biāo)簽T′=T即T′=T*。

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

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

2.1.3 計(jì)算偽造成功的概率

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

(34)

進(jìn)一步計(jì)算得P=r2·2-n。

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

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

2.2.1 偽造方法介紹

偽造算法F0：

第一步在加密過(guò)程中，首先對(duì)s+1對(duì)明文進(jìn)行分塊，如下所示：

?

以上s+1對(duì)明文對(duì)應(yīng)的密文分塊為：

?

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

第二步我們尋找滿(mǎn)足下面等式的明文塊，

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*，用公式表示即對(duì)于1≤q≤r：

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

(36)

對(duì)于2r

(37)

此時(shí)我們已經(jīng)構(gòu)造出了C*，標(biāo)簽為T(mén)*=T0。

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

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

首先計(jì)算C*解密后得到的明文的表達(dá)式,根據(jù)式(36)和式(37)，以及已知的明密文的對(duì)應(yīng)關(guān)系，我們可以得到M*的表達(dá)式，用公式表示即當(dāng)1≤q≤r時(shí)：

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

(38)

對(duì)于2r

(39)

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

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

(40)

(41)

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

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

(42)

根據(jù)式(35)得到：

Σ*⊕Σ0=0

(43)

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

2.2.3 計(jì)算偽造成功的概率

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

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

(44)

根據(jù)文獻(xiàn)[9]中的概率論知識(shí)，我們可以得到：

(45)

那么：

(46)

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

(47)

則式(46)可以變?yōu)椋?/p>

(48)

將常數(shù)項(xiàng)提到前邊，并且進(jìn)一步計(jì)算得到：

(49)

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

因?yàn)閟+1對(duì)明密文對(duì)中有s+1個(gè)標(biāo)簽可用，所以偽造成功的概率為s2(s+1)2r-n。

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

3 結(jié) 語(yǔ)

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

[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] 吳文玲.分組密碼的設(shè)計(jì)與分析[M].北京:清華大學(xué)出版社,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] 王志江.概率論與數(shù)理統(tǒng)計(jì)[M].北京:高等教育出版社,2011.

[10] 趙修坤.微積分[M].3版.北京:國(guó)防工業(yè)出版社,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。鄭秀林，教授，主研領(lǐng)域：分組密碼和序列密碼的設(shè)計(jì)與分析。付伊鵬，碩士生。宋海燕，碩士生。