針對LBlock算法蹤跡驅(qū)動Cache攻擊S盒特性分析

于　茜,蔡紅柳，陳財森

(裝甲兵工程學(xué)院　a.信息工程系； b.科研部，北京　100072)

?

針對LBlock算法蹤跡驅(qū)動Cache攻擊S盒特性分析

于茜a,蔡紅柳a，陳財森b

(裝甲兵工程學(xué)院a.信息工程系； b.科研部，北京100072)

針對輕量級密碼LBlock算法的Cache計時研究，著重分析密碼算法中S盒的非線性結(jié)構(gòu)特征?；谄浣Y(jié)構(gòu)特征推導(dǎo)出S盒的真值表，求解得出S盒輸入輸出關(guān)系的代數(shù)表達(dá)式；再結(jié)合LBlock算法的加密過程和輪函數(shù)F的結(jié)構(gòu)，推導(dǎo)出每個輪運算的表達(dá)式以及S盒查找索引的代數(shù)表達(dá)式；結(jié)合蹤跡驅(qū)動Cache計時攻擊的攻擊原理與模型，總結(jié)得出針對LBlock算法Cache攻擊中密鑰分析的核心表達(dá)式，結(jié)果表明LBlock算法存在遭受Cache計時攻擊的可能性。

LBlock算法；Cache計時攻擊；代數(shù)表達(dá)式；S盒；特性分析

本文引用格式：于茜,蔡紅柳，陳財森.針對LBlock算法蹤跡驅(qū)動Cache攻擊S盒特性分析[J].兵器裝備工程學(xué)報，2016(8):146-150.

隨著信息安全的地位日益重要，輕量級密碼算法在RFID電子標(biāo)簽、無線傳感器網(wǎng)絡(luò)、移動智能終端等資源受限設(shè)備的應(yīng)用越來越廣，是目前密碼安全研究的一個熱點領(lǐng)域。LBlock算法[1]是吳文玲和張蕾2011年提出的一種基于32輪類Feistel結(jié)構(gòu)的輕量級分組密碼，采用與傳統(tǒng)分組密碼類似的迭代結(jié)構(gòu)，即將明文用簡單的輪函數(shù)在密鑰的作用下進(jìn)行多次迭代最終得到密文，輪密鑰則通過密鑰調(diào)度算法由主密鑰生成，其密鑰和分組長度分別為80和64比特。

輕量級密碼算法[2]具有處理數(shù)據(jù)規(guī)模小、數(shù)據(jù)吞吐量低、實現(xiàn)占用內(nèi)存空間小等特點，在保證安全性的前提下，為提高實現(xiàn)效率，目前主要采用利用現(xiàn)有算法結(jié)構(gòu)的健壯性和安全性改進(jìn)現(xiàn)有的密碼算法，如改善算法的布爾函數(shù)，使算法的S盒相同，以降低算法實現(xiàn)的資源需求等?；诜纸M密碼的迭代結(jié)構(gòu)特性，傳統(tǒng)的安全性分析方法主要有基于統(tǒng)計方法的線性分析[3]、差分分析[4]、立方攻擊[5]和基于解方程組的代數(shù)攻擊[6]等。近年來，隨著旁路攻擊在密碼分析領(lǐng)域的研究進(jìn)展，攻擊者可通過獲取密碼算法在執(zhí)行過程中泄露的功耗、電磁、時間等旁路信息，利用這些旁路信息與密鑰的相關(guān)性分析獲取密鑰，是密碼分析研究領(lǐng)域的熱點[7]。將旁路攻擊與傳統(tǒng)密碼分析方法相結(jié)合，提出了代數(shù)旁路攻擊、立方攻擊與側(cè)信道相結(jié)合的攻擊方法。Shamir等[8]提出的側(cè)信道立方攻擊，其思想是假設(shè)攻擊者通過側(cè)信道獲取密碼算法中間狀態(tài)的某個比特，將該比特信息與立方攻擊相結(jié)合從而獲取密鑰信息，2009年Yang等[9]對PRESENT算法進(jìn)行了側(cè)信道立方攻擊的驗證。自Kocher[10]和Kelsey[11]等人提出將高速存儲器Cache的行為信息作為旁路泄露信息的思想以來，Cache攻擊成為旁路攻擊的新熱點，其主要思想是通過獲取密碼算法在執(zhí)行過程中對Cache的訪問行為，以及Cache計時信息與密鑰信息的相關(guān)性分析獲取密鑰信息，對基于S盒查找的分組密碼算法構(gòu)成了安全性威脅，如DES、AES、ARIA算法，同時也可基于滑動窗口算法實現(xiàn)的RSA公鑰密碼算法進(jìn)行攻擊。

在Cache計時攻擊過程中，如何準(zhǔn)確獲取Cache訪問行為信息和S盒查找索引與子密鑰的相關(guān)性分析是密鑰分析的關(guān)鍵因素。本文在蹤跡驅(qū)動Cache計時攻擊原理的基礎(chǔ)上，結(jié)合LBlock算法實現(xiàn)過程的代數(shù)性質(zhì)分析，給出LBlock算法的非線性組件S盒的代數(shù)表達(dá)式，結(jié)合算法的加密過程和輪函數(shù)F的結(jié)果，推導(dǎo)出每個輪運算的表達(dá)式以及S盒查找索引的代數(shù)表達(dá)式，由輪子密鑰的代數(shù)表達(dá)式，給出通過Cache訪問信息與S盒查找索引推導(dǎo)出子密鑰信息的核心表達(dá)式，從理論上論證了LBlock存在遭受Cache計時攻擊的可能性。

1　LBlock密碼算法實現(xiàn)分析

1.1算法概述

LBlock算法的加密過程主要是一個32位的類Feistel結(jié)構(gòu)迭代。設(shè)M=X1‖X0表示64比特明文，其加密過程如下：

1) 對于i=2,3,…,33，執(zhí)行：

2) 輸出64比特密文C=X32‖X33。LBlock加密結(jié)構(gòu)如圖1所示。

圖1　LBlock加密結(jié)構(gòu)

其中，每輪加密運算的輪函數(shù)F及其涉及的混淆函數(shù)S和擴(kuò)散函數(shù)P定義如下。

1) 輪函數(shù)F：

2) 混淆函數(shù)S：

S:{0,1}32→{0,1}32

Y=Y7‖Y6‖Y5‖Y4‖Y3‖Y2‖Y1‖Y0→

Z=Z7‖Z6‖Z5‖Z4‖Z3‖Z2‖Z1‖Z0

Z7=s7(Y7),Z6=s6(Y6)

Z5=s5(Y5),Z4=s4(Y4)

Z3=s3(Y3),Z2=s2(Y2)

Z1=s1(Y1),Z0=s0(Y0)

混淆函數(shù)中S盒的具體變換規(guī)律如表1所示。

表1　LBlock的S盒

3) 擴(kuò)散函數(shù)P：

P:{0,1}32→{0,1}32

Z=Z7‖Z6‖Z5‖Z4‖Z3‖Z2‖Z1‖Z0→

U=U7‖U6‖U5‖U4‖U3‖U2‖U1‖U0

Z7=U6,Z6=U4,Z5=U7,Z4=U5

Z3=U2,Z2=U0,Z1=U3,Z0=U1

輪函數(shù)F的具體結(jié)構(gòu)如圖2所示。

圖2　LBlock輪函數(shù)F的結(jié)構(gòu)

根據(jù)LBlock輪函數(shù)F的結(jié)構(gòu)圖，對應(yīng)8個S盒，將每輪參與輪函數(shù)F的左32比特Xi按4比特一組，從左到右依次記為ai,7,ai,6,ai,5,ai,4,ai,3,ai,2,ai,1,ai,0；相應(yīng)地，輪密鑰Ki也按4比特一組，從左到右依次記為Ki,7,Ki,6,Ki,5,Ki,4,Ki,3,Ki,2,Ki,1,Ki,0。

假設(shè)第一輪右32比特X0為全0，那么以S7為例，則可知第一輪的查找索引為a1,7?K1,7；第二輪的查找索引為a2,7?K2,7。

由LBlock算法加密過程，每輪左32位的數(shù)學(xué)表達(dá)為

則有：

由輪函數(shù)F的結(jié)構(gòu)圖可知，第一輪S6盒的輸出對應(yīng)于第二輪S7盒的索引，即a2,7=S6(a1,6?K1,6)。

那么可得出，第二輪S7盒的查找索引為S6(a1,6?K1,6)?K2,7。

因此通過以上分析得出如下結(jié)論：

假設(shè)LBlock算法第一輪右32比特X0為全0，由算法加密結(jié)構(gòu)可得第一輪查找S7盒的索引為a1,7?K1,7；第二輪查找S7盒的索引為S6(a1,6?K1,6)?K2,7。

該結(jié)論也是通過獲取S盒索引值分析推導(dǎo)相關(guān)密鑰位的關(guān)鍵因素。

1.2子密鑰生成算法

LBlock算法的子密鑰生成，主要用于如何從80比特的主密鑰中依次生成32個32位的輪子密鑰。假設(shè)初始時80比特的主密鑰存儲于密鑰寄存器K中，記為

其中，k0表示最低位。

算法步驟具體如下：

1) 輸出K的最左邊32比特作為輪子密鑰K1；

2) 對于i=1,2,…,31，執(zhí)行：

a) K<<<29；

b) [k79k78k77k76]=s9[k79k78k77k76]，

[k75k74k73k72]=s8[k75k74k73k72]；

c) [k50k49k48k47]=[k50k49k48k47]?[i]2；

d) 輸出當(dāng)前最左邊32位最為輪子密鑰Ki+1。

利用同樣的方法依次生成各個輪子密鑰，用于輪計算。

2　LBlock算法中非線性S盒的特性分析

2.1S盒的真值表推導(dǎo)

LBlock算法的S盒輸入、輸出均為4位二進(jìn)制數(shù)。假設(shè)輸入X=x3x2x1x0，其中x3為最高位，x0為最低位，輸出Y=y3y2y1y0，其中y3為最高位，y0為最低位。根據(jù)表1中LBlockS盒的變換規(guī)律，以S0為例：當(dāng)輸入X(x3x2x1x0)=0000時，輸出Y(y3y2y1y0)=1110，依次可得S0的真值表，如表2所示。

表2　S0的真值表

由表2 S0的真值表可分別得到LBlock算法中S0盒4個對應(yīng)于x3x2x1x0(從0000到1111)的輸出y0，y1，y2，y3的真值表，如表3所示。

表3　LBlock S盒(S0)中輸出y0，y1，y2，y3的真值表

假設(shè)LBlock算法中S盒的輸出Y(y3y2y1y0)與輸入X(x3x2x1x0)的布爾函數(shù)關(guān)系為

yi=fi(x3,x2,x1,x0)

其中，i=0,1,2,3，以S0盒為例，根據(jù)4個輸出y0，y1，y2，y3的真值表求解其布爾函數(shù)表達(dá)式，以y0為例，真值表中共有8項為1，可表示成：

展開后得：

m0001=x3x2x1x0?x3x2x0?x3x1x0?x2x1x0?

x3x0?x2x0?x1x0?x0

同理可得：

m0010=x3x2x1x0?x3x2x1?x3x1x0?

x2x1x0?x3x1?x2x1?x1x0?x1

m0100=x3x2x1x0?x3x2x1?x3x2x0?

x2x1x0?x3x2?x2x1?x2x0?x2

m0111=x3x2x1x0?x2x1x0m1000=

x3x2x1x0?x3x2x1?x3x2x0?x3x1x0?

x3x2?x3x1?x3x0?x3

m1011=x3x2x1x0?x3x1x0

m1100=x3x2x1x0?x3x2x1?x3x2x0?x3x2

m1111=x3x2x1x0

全部相加并約去0項即可得到y(tǒng)0，同理可得其他3個輸出y1，y2，y3關(guān)于輸入的表達(dá)式。

即可得出如下結(jié)論：

設(shè)X=x3x2x1x0為S盒的輸入，Y=y3y2y1y0為S盒的輸出，利用LBlock算法中S0的真值表，可計算出：

其他S盒(S1到S9)的4個輸出的代數(shù)表達(dá)式都可用類似方法求得，這里不再贅述。

2.2輪子密鑰的代數(shù)表達(dá)式

根據(jù)上述章1.2中描述的子密鑰生成算法和章2.1中推導(dǎo)的S盒輸入輸出代數(shù)表達(dá)式可以得到LBlock算法的每一輪子密鑰的代數(shù)表達(dá)式。

設(shè)主密鑰

則第二輪子密鑰為

K2={1?k47?k49?k47k49?k48k49?k50,

k47?k48?k49?k50?k49k50,

1?k47?k47k49?k48k49?k50?k47k50?

k49k50?k47k49k50?k48k49k50,

1?k47k48?k47k49?k50?k48k50?k47k49k50,

1?k43?k43k45?k44k45?k43k46?k45k46k43k45k46?

k44k45k46?k43?k44?k43k44k45?k43k45?k44k46?

k45k46?k43k45k46,k43?k44?k45?k46?k45k46,

k43?k45?k43k45?k44k45?k46,k42,k41,k40,k39,

k38,k37,k36,k35,k34,k33,k32,k31,k30,k29,k28,

k27,k26,k25,k24,k23,k22,k21,k29,k19}

同理可得第三輪的子密鑰K3，以此類推。

3　基于S盒索引特性的蹤跡驅(qū)動Cache攻擊密鑰分析

3.1蹤跡驅(qū)動Cache攻擊原理與S盒索引特性

蹤跡驅(qū)動Cache 攻擊是一種非常有效的旁路分析技術(shù)[13]，其原理是：在執(zhí)行密碼算法的過程中，常常多次查表訪問同一個S盒，利用多次查表產(chǎn)生的Cache命中和失效情況推測密鑰。其中，查找所需元素在Cache中的情況稱為Cache命中，查找所需元素不在Cache中的情況稱之為Cache失效，此時處理器會把所需元素所在內(nèi)存塊的所有對應(yīng)元素加載到某一Cache行。

實驗中，先對Cache進(jìn)行清空，則第一次查表通常會發(fā)生Cache失效；第二次查表時，Cache可能產(chǎn)生Cache命中也可能產(chǎn)生Cache失效，若命中，說明所需元素一定在第一次查表后加載元素的Cache行中。而每次查表需要一個查表索引值，該索引值的高兩位對應(yīng)Cache行，低兩位對應(yīng)行內(nèi)地址，即兩次查表索引值的高兩位相等。

由此得出結(jié)論：

設(shè)Y為查找S盒的索引值，其高兩位表示為〈Y〉，若兩次查找同一S盒的索引值分別為Y1，Y2，且二次查找發(fā)生Cache命中，則有

3.2LBlock密鑰與S盒索引值相關(guān)性分析

通過構(gòu)造LBlock算法加密過程中的S盒查找命中，利用上述得出的3個結(jié)論理論上對LBlock密鑰與S盒索引值相關(guān)性進(jìn)行分析[14]。

假設(shè)第一輪右32比特X0為全0，隨機選擇第一輪加密的高四位明文ai,7和次高四位明文ai,6，使得第二輪查找S7發(fā)生Cache命中。則由節(jié)1.1與3.1得出的結(jié)論可推導(dǎo)出：

(1)

將明文比特和密鑰比特分別代入式(1)，可得：

此時S7索引的高兩位比特只與10位密鑰k79，k78，k75，k74，k73，k72，k50，k49，k48，k47有關(guān)，其中最高位只與9位密鑰k79，k75，k74，k73，k72，k50，k49，k48，k47有關(guān)，次高位只與9位密鑰k78，k75，k74，k73，k72，k50，k49，k48，k47有關(guān)。對此，選出發(fā)生命中的12組明文，由這12組等式可以確定唯一解，可以恢復(fù)與高兩位比特相關(guān)的10位密鑰。綜上可知，至多進(jìn)行12×29+12×29=12×210次判別運算可恢復(fù)上述10位密鑰k79，k78，k75，k74，k73，k72，k50，k49，k48，k47。

同理，分析第一輪第二輪S6盒查表索引的高兩位比特，可唯一確定8位密鑰，即k67，k66，k65，k64，k46，k45，k44，k43。

進(jìn)一步分析其他S盒查表索引的高兩位，最終可恢復(fù)49位密鑰，具體每次S盒查表索引的高兩位對應(yīng)密鑰位和密鑰個數(shù)如表4所示。

表4　第二輪命中時S盒查表索引的高兩位

如果每次選擇的明文的組數(shù)都比每次S盒索引所涉及的密鑰數(shù)多2，則從表4中易知此時共需12+10+8+6+10+5+8+6 = 65 個選擇明文，大約12 × 210+10 × 28+8 ×26+6×24+10×28+5×23+8×26+6×24≈214.18次判別操作。

因為LBlock 算法有32 輪，每一輪都有8個S盒參與運算，同時每一次判別操作至多有2 個S盒參與運算，所以1 次判別運算可視為2/(32×8)=1/128 次LBlock 加密運算。綜上所述，共需約27.18次LBlock 加密運算，可恢復(fù)表1中的49 bit密鑰。

同理，對S盒進(jìn)行第三輪第四輪分析，可獲得更多的相關(guān)密鑰位，如表5所示。

表5　第四輪命中時S盒查表索引的

同樣假設(shè)每次選擇的明文的組數(shù)都比每一次索引所涉及的密鑰數(shù)多2，則分析第3 輪只需5+8+4+6+6+4+4+4=41 個選擇明文，判別時間可忽略，最后剩余的6 bit 密鑰可以用窮舉的方法來得到，至多需要26次LBlock 運算。

綜上所述，整個攻擊一共需要106 個選擇明文，約27.18+26≈27.71次加密運算可恢復(fù)LBlock 的全部密鑰。

因此，LBlock算法存在Cache計時攻擊的可行性。

4　結(jié)論

本文通過深入分析LBlock算法的實現(xiàn)過程及算法函數(shù)結(jié)構(gòu)，依據(jù)蹤跡驅(qū)動Cache計時攻擊原理，針對LBlock算法的S盒特性展開研究，首先分析得出其非線性S盒的代數(shù)表達(dá)式，依據(jù)加密過程和輪函數(shù)F的結(jié)構(gòu)，推導(dǎo)出每個輪運算的表達(dá)式以及S盒查找索引的代數(shù)表達(dá)式；然后基于S盒索引特性分析，提出了針對LBlock算法Cache攻擊中密鑰分析的核心表達(dá)式，從而論證了LBlock算法Cache計時攻擊的可行性，為其他輕量級密碼算法的實現(xiàn)安全性分析提供有價值的參考借鑒。

[1]WU W L,ZHANG L.LBlock:A Lightweight Block Cipher[C]//Proceedings of the 9th International Conference on Applied Cryptography and Network Security.Berlin,Germany:Springer-Verlag,2011:327-344.

[2]吳文玲,范偉杰,張蕾.輕量級分組密碼研究進(jìn)展[J].中國密碼學(xué)發(fā)展報告,2010,140:159.

[3]MATSUI M.Linear cryptanalysis method for DES cipher[C]//Advances in Cryptology-EUROCRYPT’ 93.Springer Berlin Heidelberg,1994:386-397.

[4]BIHAM E,SHAMIR A.Differential cryptanalysis of the data encryption standard[C]//Advances in Cryptology-CRYPTO 1990,LNCS 537,1991: 2-21.

[5]DINUR I,SHAMIR A.Cube attacks on tweakable black box polynomials[C]//Advances.in Cryptology-EUROCRYPT 2009.Springer Berlin Heidelberg,2009:278-299.

[6]ALBRECHT M.Alorithmic algebraic techniques and their application to block cipher cryptanalysis[D].Royal Holloway:University of London,2010.

[7]郭世澤,王韜,趙新杰.密碼旁路分析原理與方法[M].北京:科學(xué)出版社,2014.

[8]LI Z Q,ZHANG B,YAO Y,et al.Cube Cryptanalysis of LBlock with Noisy Leakage[C]//Proceedings of the 15th International Conference on Information Security and Cryptology.Berlin,Germany:Springer-Verlag,2012:141-155.

[9]BOGDAOV A,KUNDSEN L R,LEANDER G,et al.PRESENT:An Ultra-lightweight Block Cipher[C]//Proceedings of the 9th International Workshop on Cryptographic Hardware and Embedded Systems.Berlin,Germany:Springer-Verlag,2007:450-466.

[10]KOCHER P.Timing attacks on implementations of Diffie-Hellman,RSA,DSS,and other systems[C]//Advances in Cryptology-CRYPTO 1996,LNCS 1109,1996:104-113.

[11]KELSEY J,SCHNEIER B,WAGNER D,et al.Side channel cryptanalysis of product ciphers[C]//Peoceeding of the 5th European Symposium on Research in Computer Security-ESORICS 1998,LNCS 1485,1998:97-110.

[12]溫巧燕,鈕心忻,楊義先.現(xiàn)代密碼學(xué)中的布爾函數(shù)[M].北京:科學(xué)出版社,2000.

[13]谷曉辰，丁文霞. 基于混沌Lorenz系統(tǒng)的S盒設(shè)計[J]．重慶理工大學(xué)學(xué)報(自然科學(xué))，2013(3)：97-103.

[14]朱嘉良,韋永壯.針對LBlock算法的蹤跡驅(qū)動Cache攻擊[J].計算機工程,2015,47(5):153-158.

[15]彭昌勇,祝躍飛,顧純祥,等.1～5輪LBlock的多項式表示及完全性分析[J].計算機工程,2012,38(9):155-157.

(責(zé)任編輯楊繼森)

Completeness Analysis onS-Box of Trace Driven Cache Timing Attack against LBlock Algorithm

YU Xia, CAI Hong-liua, CHEN Cai-senb

(a.Department of Information and Communication Engineering;b.Department of Science Research, Academy of Armored Forces Engineering, Beijing 100072, China)

Aiming at the study of the cache timing attack for lightweight block cipher called LBlock, we focused on the analysis of the nonlinear structure characteristics ofSbox in cryptographic algorithms. Firstly, we derived the truth-table ofSbox based on its structure feature to obtain the relation algebra expression between inputs and outputs ofSbox. Secondly, with reference of encryption process of the LBlock algorithm and the structure of round functionF, the operation expression of each round and the algebra expressions of look-up index forSbox were deduced. Finally, we summarized the core expression of the analysis of the key in the cache attack for LBlock algorithm on the basis of the principle and model of the trace-driven cache timing attack. The final conclusion shows that the LBlock algorithm has the possibility of the cache timing attack.

LBlock algorithm; Cache timing attack; algebra expression; S box; characteristic analysis

2016-02-17；

2016-04-10

于茜(1992—)，女，碩士研究生，主要從事網(wǎng)絡(luò)安全與對抗研究。

10.11809/scbgxb2016.08.033

format:YU Xi, CAI Hong-liu, CHEN Cai-sen.Completeness Analysis on S-Box of Trace Driven Cache Timing Attack against LBlock Algorithm[J].Journal of Ordnance Equipment Engineering,2016(8):146-150.

TP391

A

2096-2304(2016)08-0146-06

【信息科學(xué)與控制工程】