歐海文 王湘南 李艷俊 雷亞超

1(北京電子科技學(xué)院信息安全系 北京 100070)2(西安電子科技大學(xué)通信工程學(xué)院 陜西 西安 710071)

0 引 言

ARIA算法[1]由韓國學(xué)者設(shè)計，從開始的ARIA 0.8版、ARIA 1.0版和ARIA 1.2版，確定最終版本為1.2版。ARIA算法是分組長度為128 bit的SPN型的分組密碼[2]，密鑰長度支持：128 bit、192 bit和256 bit，迭代輪數(shù)分別為12、14、16輪[3]。采用了與AES算法[4]相似的結(jié)構(gòu)，很多AES算法的分析方法也適用于ARIA，結(jié)合ARIA算法的研究，實現(xiàn)了對ARIA算法的不可能差分攻擊。

不可能差分分析是由Knudsen和Biham分別獨立提出[5-6]。與差分不同，不可能差分分析的理念是憑借概率為0的差分特征，將那些會導(dǎo)致概率為0的差分出現(xiàn)的候選密鑰去除，因為若使用正確的密鑰來對明文進行加密，不可能得到這樣的密文差分特征[3]。篩除這些候選密鑰值，剩下的就是正確的密鑰值。

1 ARIA算法

1.1 ARIA算法介紹

ARIA是分組長度為128 bit的SPN型密碼，ARIA每一輪由3個部件構(gòu)成：

1) 輪密鑰加(RKA)。由每一輪的輸入狀態(tài)和輪密鑰ki兩者之間按字節(jié)進行異或構(gòu)成，而輪密鑰ki是由密鑰擴展算法得到的。

SLo=S1S2S1-1S2-1S1S2S1-1S2-1S1S2S1-1S2-1S1S2S1-1S2-1

SLe=S1-1S2-1S1S2S1-1S2-1S1S2S1-1S2-1S1S2S1-1S2-1S1S2

SLo、SLe分別在單數(shù)輪中用和在雙數(shù)輪中用。

y0=x3⊕x4⊕x6⊕x8⊕x9⊕x13⊕x14y1=x2⊕x5⊕x7⊕x8⊕x9⊕x12⊕x15y2=x1⊕x4⊕x6⊕x10⊕x11⊕x12⊕x15y3=x0⊕x5⊕x7⊕x10⊕x11⊕x13⊕x14y4=x0⊕x2⊕x5⊕x8⊕x11⊕x14⊕x15y5=x1⊕x3⊕x4⊕x9⊕x10⊕x14⊕x15y6=x0⊕x2⊕x7⊕x9⊕x10⊕x12⊕x13y7=x1⊕x3⊕x6⊕x8⊕x11⊕x12⊕x13y8=x0⊕x1⊕x4⊕x7⊕x10⊕x13⊕x15y9=x0⊕x1⊕x5⊕x6⊕x11⊕x12⊕x14y10=x2⊕x3⊕x5⊕x6⊕x8⊕x13⊕x15y11=x2⊕x3⊕x4⊕x7⊕x9⊕x12⊕x14y12=x1⊕x2⊕x6⊕x7⊕x9⊕x11⊕x12y13=x0⊕x3⊕x6⊕x7⊕x8⊕x10⊕x13y14=x0⊕x3⊕x4⊕x5⊕x9⊕x11⊕x14y15=x1⊕x2⊕x4⊕x5⊕x8⊕x10⊕x15

1.2 符號說明

本文使用的符號及標(biāo)注如表1所示。

表1 使用的符號及標(biāo)注

續(xù)表1

2 對7輪ARIA-256的不可能差分分析

在Yu Sasaki和Yosuke Todo給出的4輪不可能差分區(qū)分器上添加2輪前置路徑、1輪后置路徑，得到7輪不可能差分路徑。

2.1 ARIA算法的2個性質(zhì)

性質(zhì)1如圖1所示，存在一差分對，在字節(jié)(1,4)處差分值非0，其余字節(jié)處差分值為0，4輪變換后，ΔX4的差分特征不會是如下式子：

(h⊕g,0,0,0,h⊕g,h,h,0,0,h,0,0,0,g,0,g)

這一不可能差分性質(zhì)可用下式表示：

(0,a,0,0,a,0,0,0,0,0,0,0,0,0,0,0)→/

(h⊕g,0,0,0,h⊕g,h,h,0,0,h,0,0,0,g,0,g)

式中：a、h和g為任意非零值。

圖1 ARIA算法的4輪不可能差分

證明：首先從前兩輪正推。

明文對的輸入狀態(tài)滿足(0,a,0,0,a,0,0,0,0,0,0,0,0,0,0,0),經(jīng)過第一輪RKA運算后，由于RKA運算不改變差分，所以差分沒有發(fā)生改變，經(jīng)過第一輪SL運算，差分特征為：

(0,b1,0,0,b4,0,0,0,0,0,0,0,0,0,0,0)

其中:b1和b4為非0字節(jié)。經(jīng)過第一輪DL運算，差分特征為：

(b4,0,b1⊕b4,0,0,b1⊕b4,0,b1,b1⊕b4,b1,0,b4,b1,0,b4,b1⊕b4)

再進行RKA運算和SL運算，差分特征為：

(c0,0,c2,0,0,c5,0,c7,c8,c9,0,c11,c12,0,c14,c15)

然后進行第二輪的DL運算，差分特征為：

(d0,d1,d2,d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15)

其中:d10=d15=c2⊕c5⊕c8⊕c15。

再推導(dǎo)(h⊕g,0,0,0,h⊕g,h,h,0,0,h,0,0,0,g,0,g)經(jīng)過兩輪逆變換。經(jīng)過1次DL-1運算，差分特征為：

(h,g,0,0,0,0,0,h⊕g,0,h⊕g,0,g,0,0,0,0)

經(jīng)過SL-1、RKA-1運算，差分特征為：

(e0,e1,0,0,0,0,0,e7,0,e9,0,e11,0,0,0,0)

再進行1次DL-1運算，差分特征為：

(e9,e7⊕e9,e1⊕e11,e0⊕e7⊕e11,e0⊕e11,e1⊕e9,e0⊕e7⊕e9,e1⊕e11,e0⊕e1⊕e7,e0⊕e1⊕e11,0,e7⊕e9,e1⊕e7⊕e9⊕e11,e0⊕e7,e0⊕e9⊕e11,e1)

其中:e0、e1、e7、e9、e11為非0值。

最后經(jīng)過SL-1運算和RKA-1運算，差分特征為：

p0=p5=n9+n14

(1)

p2=p7=n11+n12

(2)

p8=p13=n0+n7

(3)

p3⊕p6⊕p9⊕p11⊕p12⊕p14=0

(4)

p0⊕p1⊕p2⊕p4⊕p8=0

(5)

同理，式(2)和式(3)都成立。

又有：

p0=n9+n14p1=n7+n9+n12p2=n11+n12p3=n0+n7+n11+n14p4=n0+n11+n14p6=n0+n7+n9+n12p8=n0+n7p9=n0+n11+n12+n14p11=n7+n9+n12+n14p12=n7+n9+n11+n12p14=n0+n9+n11+n14

所以，式(4)和式(5)成立。

p=248/272=2-24

證畢。

2.2 7輪ARIA的不可能差分攻擊過程

上述7輪不可能差分路徑如圖2所示。其中ARIA算法的最后一輪的擴散層由密鑰加替換。在分析時間復(fù)雜度時采用了密鑰恢復(fù)的“early-abort”(早夭)技術(shù)[7]。

圖2 7輪ARIA的不可能差分路徑

攻擊過程如下：

步驟2取2N個上述結(jié)構(gòu)，選取密文對中在(1,2,3,7,8,10,11,12,14)這9個字節(jié)處差分為0，剩余密文對有2N+223×2-8×(16-7)=2N+151個。

步驟3猜測密鑰k8的7 B(k8,0,k8,4,k8,5,k8,6,k8,9,k8,13,k8,15)，假設(shè)步驟2中保留下來的密文對為(C,C′)。在計算復(fù)雜度時，只需要計算7 B的值的復(fù)雜度。

步驟3.1猜測密鑰(k8,5,k8,6,k8,9)，計算：

步驟3.2猜測密鑰(k8,13,k8,15)，計算：

步驟3.3猜測密鑰(k8,0,k8,4)，計算：

步驟4猜測密鑰k1的14個字節(jié)，并結(jié)合性質(zhì)2分析，使保留下來的密文對相應(yīng)的明文對為(P,P′)。計算復(fù)雜度時，因為只有密鑰加和擴散層操作，所以進行每一次運算就相當(dāng)于2/3的1輪運算。

步驟4.1猜測密鑰(k1,0,k1,5)，計算：

步驟4.2猜測密鑰(k1,2,k1,7)，計算：

步驟4.3猜測密鑰(k1,8,k1,13)，計算：

步驟4.4猜測密鑰(k1,3,k1,6,k1,9,k1,11,k1,12,k1,14)，計算：

步驟4.5猜測密鑰(k1,1,k1,4)，計算：

步驟5猜測密鑰(k2,0,k2,7,k2,9,k2,11,k2,12,k2,14)，計算：

所以總的攻擊時間復(fù)雜度為：

(3×2164+2173+2180+1/3×2158+1/3×2166+1/3×2174+2214+1/3×2222+1/3×2216+15×2205)×1/7≈2217

綜上所述，7輪的攻擊復(fù)雜度為2112數(shù)據(jù)復(fù)雜度和大約2217次7輪加密運算。

3 8輪ARIA算法的不可能差分分析

在4輪不可能差分區(qū)分器上添加了2輪前置路徑和2輪后置路徑，形成8輪ARIA算法的不可能差分路徑，如圖3所示。

圖3 8輪ARIA的不可能差分路徑

3.1 ARIA算法的另一性質(zhì)

t2⊕t5⊕t12=0

(6)

t1⊕t11⊕t15=0

(7)

t4⊕t10⊕t13=0

(8)

t5⊕t6⊕t8=0

(9)

t0⊕t7⊕t11=0

(10)

t3⊕t9⊕t15=0

(11)

t4⊕t5⊕t14=0

(12)

證明同性質(zhì)2類似，這里省略。

3.2 8輪ARIA的不可能差分攻擊過程

8輪不可能差分分析路徑中，ARIA算法的最后一輪的擴散層由密鑰加替換。

攻擊過程如下：

步驟2取2N個上述結(jié)構(gòu)，這樣明文對有2223×2N=2N+223對。

步驟3猜測密鑰字節(jié)(k9,0,k9,1,k9,2,k9,3,k9,4,k9,5,k9,6,k9,7,k9,8,k9,9,k9,10,k9,11,k9,12,k9,13,k9,14,k9,15)對步驟2中留下來的任意密文對(C,C′)，分別進行以下計算：

步驟4猜測k8的16 B，并利用性質(zhì)3進行分析。在步驟4中計算復(fù)雜度時，因為只有RKA和SL這兩種操作，我們把每次操作可當(dāng)作2/3的1輪操作。

步驟4.1猜測(k8,2,k8,5,k8,12)，并計算：

選擇滿足t2⊕t5⊕t12=0的密文對，剩余2N+103×2-8=2N+95個密文對。這一步驟需要232×2×2182×224×3/16×2/3=2236次1輪加密運算。

步驟4.2猜測(k8,1,k8,11,k8,15)，并計算：

選擇滿足t1⊕t11⊕t15=0的密文對，剩余2N+95×2-8=2N+87個密文對。這一步驟需要232×2×224×2174×224×3/16×2/3=2255次1輪加密運算。

步驟4.3猜測(k8,4,k8,10,k8,13)，并計算：

選擇滿足t4⊕t10⊕t13=0的密文對，剩余2N+87×2-8=2N+79個密文對。這一步驟需要232×2×248×2166×224×3/16×2/3=2268次1輪加密運算。

步驟4.4猜測(k8,6,k8,8)，并計算：

選擇滿足t5⊕t6⊕t8=0的密文對，剩余2N+79×2-8=2N+71個密文對。這一步驟需要232×2×272×2158×216×2/16×2/3=1/3×2277次1輪加密運算。

步驟4.5猜測(k8,0,k8,7)，并計算：

選擇滿足t0⊕t7⊕t11=0的密文對，剩余2N+71×2-8=2N+63個密文對。這一步驟需要232×2×288×2150×216×2/16×2/3=1/3×2285次1輪加密運算。

步驟4.6猜測(k8,3,k8,9)，并計算：

選擇滿足t3⊕t9⊕t15=0的密文對，剩余2N+63×2-8=2N+55個密文對。這一步驟需要232×2×2104×2142×216×2/16×2/3=1/3×2293次1輪加密運算。

步驟4.7猜測(k8,14)，并計算：

選擇滿足t4⊕t5⊕t14=0的密文對，剩余2N+55×2-8=2N+47個密文對。這一步驟需要232×2×2120×2134×28×1/16×2/3=1/3×2292次1輪加密運算。

步驟5猜測密鑰k1的14 B，并結(jié)合性質(zhì)2進行分析，使對應(yīng)的明文對為(P,P′)。在步驟5中，只有RKA和SL這兩種操作，我們把每次操作可認(rèn)為是2/3的1輪操作。

步驟5.1猜測(k1,0,k1,5)，計算：

步驟5.2猜測密鑰(k1,2,k1,7)，計算：

步驟5.3猜測密鑰(k1,8,k1,13)，計算：

步驟5.4猜測密鑰(k1,3,k1,6,k1,9,k1,11,k1,12,k1,14)，計算：

步驟5.5猜測密鑰(k1,1,k1,4)，計算：

步驟6猜測密鑰(k2,0,k2,7,k2,9,k2,11,k2,12,k2,14)，計算：

總的攻擊時間復(fù)雜度為：

(15×2319+2236+2255+2268+1/3×2277+1/3×2285+1/3×2293+1/3×2292+1/3×2287+1/3×2157+1/3×2165+1/3×2173+2213+1/3×2221+1/3×2215+15×2204)×1/8≈2319

綜上所述，8輪的攻擊復(fù)雜度為2191數(shù)據(jù)復(fù)雜度和大約2319次8輪加密運算。

4 改進的不可能差分分析

本文還改進了文獻[12]的7輪分析和8輪分析，使用的4輪不可能差分如圖4所示。

圖4 四輪不可能差分

c0=c13=b6⊕b8

(13)

c3=c14=b5⊕b11

(14)

c5=c8=b1⊕b15

(15)

c2⊕c4⊕c7⊕c9⊕c10⊕c15=0

(16)

c0⊕c1⊕c3⊕c5⊕c12=0

(17)

證明同性質(zhì)2類似，這里省略。

性質(zhì)2中符號具體代表含義詳見參考文獻[12]，這里不再贅述。

對于7輪攻擊，結(jié)合性質(zhì)4，進行密鑰恢復(fù)，需要的攻擊復(fù)雜度為：2112+2N=2112+7=2119數(shù)據(jù)復(fù)雜度和大約2216次7輪加密運算。

對于8輪分析，使用性質(zhì)4的同時，將步驟4.1的DL操作，放到步驟4的最后一步，需要數(shù)據(jù)復(fù)雜度2112+295=2112+95=2207和大約2327次8輪加密運算，進一步減少了時間復(fù)雜度。

5 結(jié) 語

本文在Yu Sasaki和Yosuke Todo給出的4輪不可能差分的基礎(chǔ)上，依據(jù)ARIA算法的結(jié)構(gòu)特征，添加了2輪前置路徑和1輪后置路徑，實現(xiàn)了7輪ARIA算法的不可能差分分析。此路徑下，7輪分析共需要數(shù)據(jù)復(fù)雜度為2112和時間復(fù)雜度為2217次7輪加密運算。實現(xiàn)了ARIA算法的8輪不可能差分分析，在4輪不可能差分上添加了2輪前置路徑和2輪后置路徑。在該路徑下，8輪分析共需要時間復(fù)雜度為2191和大約2319次8輪加密運算。最后還改進了文獻[12]的分析結(jié)果，與原結(jié)果相比較，降低了時間復(fù)雜度。不同算法的不可能差分對比結(jié)果如表2所示。

表2 ARIA算法的不可能差分總結(jié)

未來研究的重點在于尋找新的不可能差分區(qū)分器，再嘗試用不同的密鑰恢復(fù)技術(shù)來降低8輪ARIA

算法不可能差分分析的復(fù)雜度，使得其時間復(fù)雜度低于窮舉搜索的攻擊復(fù)雜度。