ARIA 算法的一個(gè)新不可能差分路徑及相應(yīng)攻擊

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

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

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

1 引言

ARIA 算法[1]由韓國研究人員設(shè)計(jì), 從開始的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 算法的研究, 實(shí)現(xiàn)了對(duì)ARIA 算法的不可能差分攻擊.

不可能差分分析是由Knudsen 和Biham 分別獨(dú)立提出[5,6]. 與差分不同, 不可能差分分析的理念是憑借概率為0 的差分特征, 將那些會(huì)導(dǎo)致概率為0 的差分出現(xiàn)的候選密鑰去除, 因?yàn)槿羰褂谜_的密鑰來對(duì)明文進(jìn)行加密, 不可能得到這樣的密文差分特征[3]. 篩除這些候選密鑰值, 剩下的就是正確的密鑰值.

2 ARIA 算法

2.1 ARIA 算法介紹

ARIA 是分組長度為128 比特的SPN 型分組密碼, ARIA 每一輪由3 個(gè)部件構(gòu)成:

(1) 輪密鑰加(Round Key Addition, RKA). 由每一輪的輸入狀態(tài)和輪密鑰ki兩者之間進(jìn)行異或構(gòu)成, 而輪密鑰ki是由密鑰擴(kuò)展算法得到的.

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

(3) 擴(kuò)散層(Diffusion Layer, DL). 擴(kuò)散層是一個(gè)將16 B 輸入(x0,x1,··· ,x15) 映射為16 B 輸出(y0,y1,··· ,y15) 的線性函數(shù):(F82)16→(F82)16, 其中:

2.2 符號(hào)說明

3 對(duì)7 輪ARIA-256 的不可能差分分析

本文是對(duì)7 輪ARIA 算法的不可能差分分析, 首先構(gòu)造了新的4 輪不可能差分區(qū)分器, 然后在區(qū)分器上構(gòu)造2 輪前置路徑和1 輪后置路徑, 得到7 輪不可能差分路徑.

3.1 ARIA 算法的2 個(gè)性質(zhì)

命題1 如圖1 所示, 存在一明文對(duì), 在字節(jié)(4,10) 處差分值非0, 其余字節(jié)處差分值為0, 4 輪變換后, 密文對(duì)差分特征?X4不會(huì)是如下形式: (f,0,0,0,f,0,f,f,0,f,0,f,0,0,f,f). 這一不可能差分性質(zhì)

符號(hào) 說明 符號(hào) 說明第i 個(gè)輸出C密文 mS P 明文 mo i第i 個(gè)SL 輸出P′ 16 字節(jié)明文的第i 字節(jié) mi,j mi 的第j 字節(jié)C′ 16 字節(jié)密文的第i 字節(jié) ki,j 第i 個(gè)子密鑰ki 的第j 字節(jié)mI i i第i 個(gè)輸入 B Byte (字節(jié))

可用下式表示:

其中a 和f 為任意非零值.

證明: 首先從前兩輪正推.

明文對(duì)的輸入狀態(tài)滿足 (0,0,0,0,a,0,0,0,0,0,a,0,0,0,0,0), 明文對(duì)經(jīng)過第一輪的 RKA 運(yùn)算后, 由于 RKA 運(yùn)算不改變差分, 所以差分沒有發(fā)生改變, 經(jīng)過第一輪 SL 運(yùn)算, 差分特征變?yōu)?(0,0,0,0,b4,0,0,0,0,0,b10,0,0,0,0,0). 其中, b4和b10為非0 字節(jié).

經(jīng)過第一輪DL 運(yùn)算,差分特征為: (b4,0,b4⊕b10,b10,0,b4⊕b10,b10,0,b4⊕b10,0,0,b4,0,b10,b4,b4⊕b10). 再進(jìn)行RKA 運(yùn)算和SL 運(yùn)算, 差分特征為:(c0,0,c2,c3,0,c5,c6,0,c8,0,0,c11,0,c13,c14,c15).

然后進(jìn)行第二輪的DL 運(yùn)算,差分特征為:(d0,d1,d2,d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13,d14,d15).其中有d1=d15=c2⊕c5⊕c8⊕c15.

再推導(dǎo)(f,0,0,0,f,0,f,f,0,f,0,f,0,0,f,f) 經(jīng)過兩輪逆變換的過程.

經(jīng)過1 次DL?1變換, 差分特征為:(0,f,0,0,0,0,f,0,0,0,0,0,0,f,f,0).

經(jīng)過1 次SL?1、RKA?1運(yùn)算, 差分特征為:(0,e1,0,0,0,0,e6,0,0,0,0,0,0,e13,e14,0).

再進(jìn)行1 次DL?1運(yùn)算,差分特征為:(e6⊕e13⊕e14,0,e1⊕e6,e13⊕e14,e14,e1⊕e14,e13,e1⊕e6⊕e13,e1⊕e13,e1⊕e6⊕e14,e6⊕e13,e14,e1⊕e6,e6⊕e13,e14,e1).

其中, e1,e6,e13,e14為非0 值.

最后經(jīng)過SL?1運(yùn)算和RKA?1運(yùn)算,差分特征為:(d?0,d?1,d?2,d?3,d?4,d?5,d?6,d?7,d?8,d?9,d?10,d?11,d?12,d?13,d?14,d?15). 其中d?15?=0, 這是因?yàn)镾L?1(d?15)=e1?=0.

而與d?1?=d?15矛盾, 故是不可能差分路徑.

推論1 如圖2 所示, 使ms1通過擴(kuò)散層變換至mo1時(shí), 當(dāng)ms1差分滿足以下五個(gè)等式時(shí), mo1在10B(1,2,4,5,7,8,9,10,12,15) 處差分為零的概率為2?24, 而在隨機(jī)的情況下, 此概率為2?80, 這五個(gè)等式分別為:

證明: 定義一個(gè)在字節(jié)(1,2,4,5,7,8,9,10,12,15) 處取值相等, 其余字節(jié)差分不為0 的明文空間結(jié)構(gòu),在輸出mo1處,如果存在這樣一個(gè)結(jié)構(gòu),通過DL?1操作后,可以得到p2=n6+n11和p12=n6+n11,不管n6和n11為何值, 式(1)以概率1 成立.

圖1 ARIA 算法的4 輪不可能差分分器Figure 1 4-round impossible difference divider of ARIA algorithm

圖2 7 輪ARIA 的不可能差分分析路徑Figure 2 Impossible differential analysis path of ARIA in 7-rounds

同理, 式(2)和式(3)都成立. 又有

所以, 易證式(4)和式(5)成立.

DL 是線性變換, 在mo1處有248個(gè), 故滿足以上五個(gè)等式的?mo1的概率為p=248/272=2?24.

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

本文在3.1 節(jié)已證明的4 輪不可能差分區(qū)分器上構(gòu)造2 輪前置路徑和1 輪后置路徑, 得到7 輪不可能差分路徑, 如圖2 所示. 其中ARIA 算法的最后一輪沒有擴(kuò)散層, 而是密鑰加.

攻擊過程如下:

步驟1. 定義一個(gè)在字節(jié)(1,15) 處差分為0, 在其余字節(jié)(0,2,3,4,5,6,7,8,9,10,11,12,13,14) 處取遍0–255 的明文空間結(jié)構(gòu), 這樣的空間中含有28×(16?2)= 2112個(gè)明文. 每個(gè)結(jié)構(gòu)中明文對(duì)共有2112×2112×1/2=2223個(gè).

步驟2. 取2N個(gè)上述結(jié)構(gòu), 選取密文對(duì)中在(1,2,3,5,8,10,12,13) 這8 個(gè)字節(jié)處差分為0, 密文對(duì)有2N+223×2?8×(16?8)=2N+159個(gè).

步驟3. 猜測(cè)密鑰k8的8B (k8,0,k8,4,k8,6,k8,7,k8,9,k8,11,k8,14,k8,15), 假設(shè)步驟二中保留下來的密文對(duì)為(C,C′), 分別進(jìn)行計(jì)算:

選擇滿足?ms7,0= ?ms7,4= ?ms7,6= ?ms7,7= ?ms7,9= ?ms7,11= ?ms7,14= ?ms7,15的密文對(duì), 還剩余密文對(duì)2N+159×2?56=2N+103個(gè).

步驟4. 猜測(cè)密鑰k1的14 個(gè)字節(jié), 并結(jié)合推論1 進(jìn)行分析, 使保留下來的密文對(duì)相應(yīng)的明文對(duì)為(P,P′).

步驟4.1. 猜測(cè)密鑰(k1,2,k1,12), 計(jì)算:

選擇滿足?ms1,2=?ms1,12的明文對(duì), 剩余2N+103×2?8=2N+95個(gè)明文對(duì).

步驟4.2. 猜測(cè)密鑰(k1,5,k1,11), 計(jì)算:

選擇滿足?ms1,5=?ms1,11的明文對(duì), 還剩余2N+95×2?8=2N+87個(gè)明文對(duì).步驟4.3. 猜測(cè)密鑰(k1,6,k1,8), 計(jì)算:

選擇滿足?ms1,6=?ms1,8的明文對(duì), 還剩余2N+87×2?8=2N+79個(gè)明文對(duì).

步驟4.4. 猜測(cè)密鑰(k1,0,k1,3,k1,7,k1,9,k1,13,k1,14), 計(jì)算:

選擇在字節(jié)(0,3,7,9,13,14) 處差分滿足?ms1,0⊕?ms1,3⊕?ms1,7⊕?ms1,9⊕?ms1,13⊕?ms1,14=0 相應(yīng)的明文對(duì), 還剩余2N+79×2?8=2N+71個(gè)明文對(duì).

步驟4.5. 猜測(cè)密鑰(k1,4,k1,10), 計(jì)算:

選擇滿足?ms1,2⊕?ms1,4⊕?ms1,5⊕?ms1,6⊕?ms1,10=0 相應(yīng)的明文對(duì),此時(shí)還剩余2N+71×2?8=2N+63個(gè)明文對(duì).

步驟4.6. 對(duì)于步驟4.1–4.5 中的?ms1, 計(jì)算經(jīng)過擴(kuò)散層后的差分即?mo1= DL(?ms1), 選擇?mo1在字節(jié)(1,2,4,5,7,8,9,10,12,15) 處差分為0 的明文對(duì), 結(jié)合推論1, 還剩余2N+63×2?24= 2N+39個(gè)明文對(duì).

步驟5. 猜測(cè)密鑰(k2,0,k2,3,k2,6,k2,11,k2,13,k2,14), 計(jì)算:

選擇滿足?ms2,0= ?ms2,3= ?ms2,6= ?ms2,11= ?ms2,13= ?ms2,14且不為0 的明文對(duì), 由于是0 概率差分, 上述所猜測(cè)的密鑰字節(jié)均為錯(cuò)誤的, 是需要排除掉的密鑰. 通過分析2N+39個(gè)明文對(duì), 還剩余248×(1 ?2?40)2N+39個(gè)錯(cuò)誤值, 令248×(1 ?2?40)2N+39<1, 得到N =7.

3.3 復(fù)雜度分析

下面在分析時(shí)間復(fù)雜度時(shí)應(yīng)用了“early-abort” 技術(shù)[7].

步驟3 中只需要計(jì)算8 B 的值, 所以這一步驟需要2×(2166×216+2158×224+ 2150×232+2142×240+2134×248+2126×256+2118×264)×8/16=7×2182次1 輪加密運(yùn)算.

在步驟4 中, 只有RKA 和DL 這兩種操作, 所以進(jìn)行每一次運(yùn)算相當(dāng)于2/3 的1 輪運(yùn)算. 所以步驟4 中:

步驟4.1 需要232×2×2110×216×2/16×2/3=1/3×2157次1 輪加密.

步驟4.2 需要232×2×216×2102×216×2/16×2/3=1/3×2165次1 輪加密.

步驟4.3 需要232×2×232×294×216×2/16×2/3=1/3×2173次1 輪加密.

步驟4.4 需要232×2×248×286×248×6/16×2/3=2213次1 輪加密.

步驟4.5 需要232×2×296×278×216×2/16×2/3=1/3×2221次1 輪加密.

步驟4.6 只有DL 操作, 需要232×2×2112×270×1/3=1/3×2215次1 輪加密.

步驟5 需要232×2×2112×(246×216+238×224+230×232+222×240+214×248)×6/16 =15×2204次1 輪加密.

所以總的時(shí)間復(fù)雜度:(7×2182+1/3×2157+1/3×2165+1/3×2173+2213+1/3×2221+1/3×2215+15×2204)×1/7 ≈2216.

綜合而言, 7 輪的攻擊復(fù)雜度為: 2112+N=2112+7=2119數(shù)據(jù)復(fù)雜度和大約2216次7 輪加密運(yùn)算.

4 總結(jié)

本文提出了一個(gè)新的4 輪不可能差分路徑, 根據(jù)ARIA 算法的結(jié)構(gòu)特征, 第3 節(jié)中, 在4 輪不可能差分區(qū)分器上構(gòu)造了2 輪前置路徑和1 輪后置路徑, 實(shí)現(xiàn)了7 輪ARIA 算法的不可能差分分析. 此路徑下,7 輪不可能差分分析共需要2119選擇明文和大約2216次7 輪加密運(yùn)算. 與表2 相比, 減少了時(shí)間復(fù)雜度.

算法 輪數(shù) 時(shí)間復(fù)雜度 數(shù)據(jù)復(fù)雜度 來源ARIA-128 6r 2112 2121 文獻(xiàn)[8]296 2120 文獻(xiàn)[9]ARIA-256 7r 2238 2125 文獻(xiàn)[10]2219 2120 文獻(xiàn)[11]2218 2119 文獻(xiàn)[12]2216 2119 本文3.2 8r 2346 2207 文獻(xiàn)[12]

在以后的研究中, 希望能夠?qū)ふ业叫碌牟豢赡懿罘致窂? 嘗試用不同的密鑰恢復(fù)技術(shù)來降低7 輪ARIA 算法不可能差分分析的復(fù)雜度, 再進(jìn)行8 輪不可能差分分析, 重點(diǎn)在于降低8 輪不可能差分分析的復(fù)雜度, 使得其時(shí)間復(fù)雜度、數(shù)據(jù)復(fù)雜度低于窮搜的攻擊復(fù)雜度.