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

于　茜,蔡紅柳，陳財森

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

?

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

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

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

針對輕量級密碼LBlock算法的Cache計時研究，著重分析密碼算法中S盒的非線性結構特征。基于其結構特征推導出S盒的真值表，求解得出S盒輸入輸出關系的代數表達式；再結合LBlock算法的加密過程和輪函數F的結構，推導出每個輪運算的表達式以及S盒查找索引的代數表達式；結合蹤跡驅動Cache計時攻擊的攻擊原理與模型，總結得出針對LBlock算法Cache攻擊中密鑰分析的核心表達式，結果表明LBlock算法存在遭受Cache計時攻擊的可能性。

LBlock算法；Cache計時攻擊；代數表達式；S盒；特性分析

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

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

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

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

1　LBlock密碼算法實現分析

1.1算法概述

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

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

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

圖1　LBlock加密結構

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

1) 輪函數F：

2) 混淆函數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)

混淆函數中S盒的具體變換規律如表1所示。

表1　LBlock的S盒

3) 擴散函數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

輪函數F的具體結構如圖2所示。

圖2　LBlock輪函數F的結構

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

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

由LBlock算法加密過程，每輪左32位的數學表達為

則有：

由輪函數F的結構圖可知，第一輪S6盒的輸出對應于第二輪S7盒的索引，即a2,7=S6(a1,6?K1,6)。

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

因此通過以上分析得出如下結論：

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

該結論也是通過獲取S盒索引值分析推導相關密鑰位的關鍵因素。

1.2子密鑰生成算法

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

其中，k0表示最低位。

算法步驟具體如下：

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

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

a) K<<<29；

b) [k79k78k77k76]=s9[k79k78k77k76]，

[k75k74k73k72]=s8[k75k74k73k72]；

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

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

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

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

2.1S盒的真值表推導

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

表2　S0的真值表

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

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

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

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

其中，i=0,1,2,3，以S0盒為例，根據4個輸出y0，y1，y2，y3的真值表求解其布爾函數表達式，以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項即可得到y0，同理可得其他3個輸出y1，y2，y3關于輸入的表達式。

即可得出如下結論：

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

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

2.2輪子密鑰的代數表達式

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

設主密鑰

則第二輪子密鑰為

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盒索引特性的蹤跡驅動Cache攻擊密鑰分析

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

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

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

由此得出結論：

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

3.2LBlock密鑰與S盒索引值相關性分析

通過構造LBlock算法加密過程中的S盒查找命中，利用上述得出的3個結論理論上對LBlock密鑰與S盒索引值相關性進行分析[14]。

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

(1)

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

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

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

進一步分析其他S盒查表索引的高兩位，最終可恢復49位密鑰，具體每次S盒查表索引的高兩位對應密鑰位和密鑰個數如表4所示。

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

如果每次選擇的明文的組數都比每次S盒索引所涉及的密鑰數多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 加密運算，可恢復表1中的49 bit密鑰。

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

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

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

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

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

4　結論

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

[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].中國密碼學發展報告,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].北京:科學出版社,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]溫巧燕,鈕心忻,楊義先.現代密碼學中的布爾函數[M].北京:科學出版社,2000.

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

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

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

(責任編輯楊繼森)

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—)，女，碩士研究生，主要從事網絡安全與對抗研究。

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

【信息科學與控制工程】