楊文峰，胡予濮，高軍濤

(西安電子科技大學(xué)計算機(jī)網(wǎng)絡(luò)與信息安全教育部重點(diǎn)實(shí)驗(yàn)室 西安 710071)

布爾函數(shù)的代數(shù)攻擊

楊文峰，胡予濮，高軍濤

(西安電子科技大學(xué)計算機(jī)網(wǎng)絡(luò)與信息安全教育部重點(diǎn)實(shí)驗(yàn)室 西安 710071)

基于代數(shù)攻擊，提出了一種已知部分真值表還原整個布爾函數(shù)的方法。對于n元d次布爾函數(shù), 該方法的空間復(fù)雜度和數(shù)據(jù)復(fù)雜度均為O(N)，計算復(fù)雜度為O(N3)，其中。由復(fù)雜度可知，所求密碼函數(shù)的代數(shù)次數(shù)越低，該方法的有效性越高。攻擊方法表明密碼設(shè)計中應(yīng)該謹(jǐn)慎使用代數(shù)次數(shù)較低的布爾函數(shù)。

代數(shù)方法; 布爾函數(shù); 密碼分析; 密碼學(xué)

作為許多流密碼的核心部件，布爾函數(shù)的設(shè)計和分析一直是密碼學(xué)中極為活躍的研究領(lǐng)域。在密碼算法設(shè)計中，設(shè)計者通過構(gòu)造滿足各種密碼學(xué)指標(biāo)的布爾函數(shù)以增加密碼的強(qiáng)度。而在密碼分析中，攻擊者往往通過尋找并利用布爾函數(shù)的設(shè)計漏洞和弱點(diǎn)實(shí)現(xiàn)對密碼算法的攻擊。密碼設(shè)計者和攻擊者這種堅持不懈的攻防爭斗正是密碼學(xué)發(fā)展的源動力所在[1-3]。各種密碼攻擊方法的不斷出現(xiàn)迫使布爾函數(shù)的設(shè)計必須滿足多方面的指標(biāo)，而各種指標(biāo)之間的相互制約關(guān)系往往又為攻擊者尋找新的攻擊方法提供了機(jī)會。本文提出的攻擊方法就是一個基于該攻擊思想的實(shí)例。

在流密碼分析中，攻擊者常常會遇到以下兩種情形：一種情形是攻擊者無法通過公開途徑獲得密碼算法，盡管文獻(xiàn)[4]指出流密碼的安全性不應(yīng)該依賴于密碼算法的保密性，而應(yīng)僅依賴于密鑰的保密性，但實(shí)際中使用的流密碼算法往往是不公開的[1]。另一種情形是密碼算法使用的布爾函數(shù)是由密鑰控制的[5]。對于這兩種情形，攻擊者的任務(wù)是不但要恢復(fù)密鑰而且必須恢復(fù)布爾函數(shù)。密碼分析過程中，布爾函數(shù)的恢復(fù)往往都是利用統(tǒng)計方法求取其真值表。統(tǒng)計方法的致命弱點(diǎn)是所需數(shù)據(jù)量巨大，使得攻擊者往往因?yàn)閿?shù)據(jù)量有限而只能求得布爾函數(shù)的部分真值表。因此，如何通過布爾函數(shù)的已知部分特性恢復(fù)出完整的布爾函數(shù)具有現(xiàn)實(shí)的應(yīng)用背景。代數(shù)攻擊思想[6-7]和布爾函數(shù)指標(biāo)之間的內(nèi)在制約關(guān)系為本文提供了一種基于部分真值表的布爾函數(shù)還原方法。只要布爾函數(shù)真值表的已知部分包含了確定該函數(shù)的所需的全部或者接近全部信息量，本文的攻擊方法可以唯一確定該函數(shù)的代數(shù)表達(dá)式。布爾函數(shù)的代數(shù)表達(dá)式和真值表之間存在著一一對應(yīng)關(guān)系，求出代數(shù)表達(dá)式就等于確定了所求的布爾函數(shù)。

1 密碼學(xué)中的布爾函數(shù)

首先給出布爾函數(shù)的定義和兩種表示方法，然后討論布爾函數(shù)的相關(guān)密碼學(xué)指標(biāo)，最后闡述本文的攻擊思路。

布爾函數(shù)主要有真值表表示、小項(xiàng)表示、多項(xiàng)式表示和Walsh譜表示4種表示方法。本文只考慮真值表表示和多項(xiàng)式表示。

多項(xiàng)式表示法則是指任意n元布爾函數(shù)f(x)都可用其代數(shù)表達(dá)式表示為：

布爾函數(shù)的各種表示方法之間是相互等價的，只要知道了其中的一種表示方法就可以唯一確定其他的表示方法。

為了防止已知的各種攻擊方法，密碼學(xué)中使用的布爾函數(shù)必須滿足一定的密碼學(xué)指標(biāo)，其中主要有次數(shù)(代數(shù)次數(shù)和非線性次數(shù))、均衡性、相關(guān)免疫性、嚴(yán)格雪崩準(zhǔn)則和擴(kuò)散準(zhǔn)則等。已有的研究結(jié)果表明，布爾函數(shù)各項(xiàng)指標(biāo)之間是相互沖突、相互制約的，所以密碼設(shè)計者總是無法設(shè)計出各項(xiàng)指標(biāo)都能達(dá)到最優(yōu)的布爾函數(shù)。由于攻擊者是尋求利用布爾函數(shù)的最弱的一點(diǎn)采取攻擊，這就使得設(shè)計者設(shè)計布爾函數(shù)時不得不采取各項(xiàng)密碼學(xué)指標(biāo)折衷的思想。充分挖掘利用密碼學(xué)指標(biāo)之間的制約關(guān)系正是解決本文中問題的基本思路。

n元均衡布爾函數(shù)f(x)的代數(shù)次數(shù)d和相關(guān)免疫階m就存在著嚴(yán)格的制約關(guān)系，即如下定理。

定理 1[8]若n元d次布爾函數(shù)f(x)，x∈GF(2)n是m階相關(guān)免疫的，則d+m≤n；若更設(shè)f(x)是均衡的，且1≤m≤n?2，則d+m≤n?1。

由上述定理可以看出，布爾函數(shù)的代數(shù)次數(shù)d必須滿足d≤n?1?m，即布爾函數(shù)的相關(guān)階m越大，代數(shù)次數(shù)d就越小。當(dāng)設(shè)計者為了防止相關(guān)攻擊[9-10]而不得不提高布爾函數(shù)的相關(guān)免疫階和犧牲布爾函數(shù)的次數(shù)時，就為利用布爾函數(shù)的部分真值表還原整個布爾函數(shù)提供了有利條件。只要已知的部分真值表中包含了d(d≤n?1)次布爾函數(shù)的全部信息，應(yīng)用代數(shù)攻擊的思想首先求出該函數(shù)的代數(shù)表達(dá)式，然后把真值表中未知函數(shù)值的自變量代入代數(shù)正規(guī)型就可以補(bǔ)全其真值表。

2 攻擊方法

代數(shù)攻擊[6]是一種密碼分析方法，常用于對流密碼、分組密碼及HFE公鑰密碼系統(tǒng)的安全性分析。代數(shù)攻擊方法的步驟為：(1)通過分析利用密碼算法的代數(shù)結(jié)構(gòu)，把密碼算法的安全性(密鑰恢復(fù))規(guī)約為一個次數(shù)盡可能低的超定多元方程組的求解問題；(2)求解步驟(1)中的多元高次方程組，代數(shù)攻擊的復(fù)雜度主要取決于多元方程組的求解復(fù)雜度，現(xiàn)有的求解方法主要有Linearization、Relinearization、XL、Gr?bner Base等；(3)如果步驟(2)中順利求出了多元方程組的解，結(jié)合步驟(1)中分析的密碼算法的代數(shù)特征，密碼算法的安全性就無法保證。

從上述代數(shù)攻擊的基本思想可以看出，所謂的代數(shù)攻擊實(shí)際上就是一個利用密碼系統(tǒng)的代數(shù)結(jié)構(gòu)建立方程組進(jìn)而求解的過程。本文的攻擊方法就是利用布爾函數(shù)的部分真值表和代數(shù)表達(dá)式建立一個(線性)方程組，然后求解方程組得到代數(shù)表達(dá)式的系數(shù)。主要分為以下3個步驟。

如果根據(jù)真值表的已知部分和上述代數(shù)表達(dá)式能夠確定出多項(xiàng)式的系數(shù)a0、a1、…、an?d+1…n，就求出了布爾函數(shù)。

2)建立多元線性方程組，根據(jù)真值表中已知的函數(shù)值，把對應(yīng)的自變量和函數(shù)值分別代入步驟1)的布爾函數(shù)的代數(shù)表達(dá)式，得到一個包含M個線性方程的多元線性方程組。

3)求解線性方程組，利用Gauss消元法對步驟2)中得到的線性方程組進(jìn)行化簡求解。假設(shè)方程組中含有Q個線性無關(guān)的方程，求解的結(jié)果有4種情況。

(1)Q

(2)Q

(3)Q=N。說明該布爾函數(shù)的代數(shù)次數(shù)正好為d并且真值表中包含所求布爾函數(shù)的信息量足夠唯一確定布爾函數(shù)。

(4)Q>N。說明所求布爾函數(shù)的代數(shù)次數(shù)大于d，利用已在的真值表無法確定該布爾函數(shù)。

該攻擊方法實(shí)現(xiàn)簡單，計算復(fù)雜度低，有利于工程實(shí)現(xiàn)。攻擊方法的主要計算就是用Gauss消元法求解一個線性方程組，其計算復(fù)雜度就是Gauss消元法的計算復(fù)雜度，即O(N3)。對于n元d次布爾函數(shù)來說由于方程組中未知元的系數(shù)是由1、x1、x2、…、xn、x1x2、…、xn?1xn、…、xn?d+1xn?d+2…xn組成的，輸入變量的相互糾纏使得方程組中的線性無關(guān)的方程個數(shù)不能精確計算，也就無法給出唯一確定布爾函數(shù)的M的精確估計。但可以利用布爾函數(shù)的理論給出M的上下界。由攻擊方法易知M的下界就是N。

定理 2[8]任意兩個不同的次數(shù)小于等于d的n元布爾函數(shù)的漢明距離至少為2n?d。

由上述定理可知M的上界就是2n?d。

3 攻擊實(shí)例

舉例說明攻擊方法的有效性。假設(shè)已知8元布爾函數(shù)的部分真值表如下(自變量按照 x8,x7,x6,x5,x4,x3,x2,x1的字典序排列)：

得到d=4。由此可以確定如果該布爾函數(shù)的代數(shù)次數(shù)d≤4，通過本文的攻擊方法就可基本求出函數(shù)的代數(shù)表達(dá)式；如果d>4，本攻擊方法無效。假設(shè)所求布爾函數(shù)的代數(shù)表達(dá)式為：

攻擊的目的就是求出上述代數(shù)正規(guī)型中的所有系數(shù)a0、a1、a2、…、a8、a12、…、a78、…、a5678。

根據(jù)攻擊方法中的步驟(2)，把真值表中有函數(shù)值的x和f(x)代入上述代數(shù)表達(dá)式，得到一個包含163個線性方程的線性方程組。

接下來實(shí)施攻擊方法中的步驟(3)，利用Gauss消元法化簡上述方程組后，獲得的方程組的秩為162，該方程組有一個自由變量a5678，這屬于攻擊方法中的第二種情形。通過窮舉自由變量a5678得到兩個布爾函數(shù)的代數(shù)表達(dá)式分別為：

從已知的真值表所能提供的信息量看，應(yīng)用本文的攻擊方法無法確定所求布爾函數(shù)的代數(shù)表達(dá)式是f1(x)還是f2(x)。但是結(jié)合其他信息，例如流密碼的簡潔性原則或者密碼學(xué)中布爾函數(shù)設(shè)計的經(jīng)驗(yàn)，不難看出：

其中邏輯函數(shù)φ(x6,x7,x8)的真值表如表1所示。

表1 邏輯函數(shù)φ(x6,x7,x8)的真值表

這就是著名的Maiorana-McFarland函數(shù)[11-12]。由此可以得出，f1(x)即為所求的布爾函數(shù)。當(dāng)然，這只是對所攻擊的布爾函數(shù)一種判斷方法，最終正確與否還要結(jié)合密碼攻擊的實(shí)踐進(jìn)行判斷。

4 結(jié) 束 語

流密碼的安全往往取決于其密鑰流生成器中布爾函數(shù)的設(shè)計質(zhì)量。在未知密碼算法或者由密鑰控制布爾函數(shù)的流密碼分析過程中，布爾函數(shù)的恢復(fù)是首先要解決的問題。另外，密碼分析中的許多問題都可以轉(zhuǎn)化為布爾函數(shù)的分析。當(dāng)攻擊者占有的數(shù)據(jù)有限時，只能求出部分真值表。本文利用布爾函數(shù)的次數(shù)和相關(guān)免疫階的制約關(guān)系提出了一種基于代數(shù)攻擊思想的布爾函數(shù)還原方法。當(dāng)已知的部分真值表包含所求布爾函數(shù)的全部信息時，該方法就可以唯一確定布爾函數(shù)。攻擊方法的計算復(fù)雜度低，實(shí)現(xiàn)簡單。但該攻擊方法的復(fù)雜度與布爾函數(shù)階的關(guān)系、小項(xiàng)數(shù)及其分布的關(guān)系等如何給定嚴(yán)格的界限，還有待進(jìn)一步研究。

[1]KAHN D. The codebreakers: the story of secret writing[M].New York: Macmillan, 1967.

[2]汪小芬, 李勝強(qiáng), 肖國鎮(zhèn). 認(rèn)證群密鑰協(xié)商協(xié)議的安全性分析與改進(jìn)[J]. 電子科技大學(xué)學(xué)報, 2009, 38(1): 51-54.

WANG Xiao-fen, LI Sheng-qiang, XIAO Guo-zhen.Analysis and improvement of an authenticated group key agreement protocol[J]. Journal of University of Electronic Science and Technology of China, 2009, 38(1): 51-54.

[3]ZHANG J L, WANG Y M. Efficient membership revocation in ACJT group signature[J]. Journal of University of Electronic Science and Technology of China, 2008, 6(1): 39-42.

[4]SCHNEIER B. Applied cryptography second edition:protocols, algorithms, and source code in C[M]. [S.l.]: John Wiley & Sons, 1996.

[5]GOLI? J D, MORGARI G. On the resynchronization attack[C]//Proceedings of FSE’03, LNCS 2887. Berlin:Springer-Verlag, 2003: 100-110.

[6]COURTOIS N T, MEIER W. Algebraic attacks on stream ciphers with linear feedback[C]//Proceedings of Eurocrypt’03, LNCS 2656. Berlin: Springer-Verlag, 2003: 345-359.

[7]COURTOIS N T. Fast algebraic attacks on stream ciphers with linear feedback[C]//Proceedings of Crypt’03, LNCS 2729. Berlin: Springer-Verlag, 2003: 176-194.

[8]CLARLET C. Boolean functions for cryptography and error correcting codes[DB/OL]. [2009-9-10]. http://www-rocq.inria.fr /secret/Claude.Carlet/chap-fcts-Bool.pdf.

[9]SIEGENTHALER T. Decrypting a class of stream ciphers using ciphertext only[J]. IEEE Transactions on computers,1985, 34(1): 81-85.

[10]MEIER W, STAFFELBACH O. Fast correlation attacks on stream ciphers[C]//Proceedings of Euro-crypt’88, LNCS 330. Berlin: Springer-Verlag, 1988: 301-314.

[11]GUPTA K C, SARKAR P. Efficient representation and software implementation of resilient Maiorana-McFarland S-boxes[C]//Proceedings of WISA’04, LNCS 3325. Berlin:Springer-Verlag, 2004: 317-331.

[12]CLARLET C. A larger class of cryptographic Boolean functions via a study of the Maiorana-McFarland construction[C]//Proceedings of Crypt’02, LNCS 2442.Berlin: Springer-Verlag, 2002: 549-564.

編 輯 稅 紅

Algebraic Attack on Boolean Functions

YANG Wen-feng, HU Yu-pu, and GAO Jun-tao

(Key Laboratory of Computer Networks and Information Security Ministry of Education, Xidian University Xi'an 710071)

Based on algebraic attack, a new reconstruction method of Boolean functions from the partial truth table is proposed. For the Boolean function with n variables and the degree of d, the proposed method requires O(N)values in the truth table, and the computational complexity is O(N3), and the memory complexity is O(N), whereFrom the above complexity, the lower the degree of the Boolean function is，the more efficient the method is. The proposed attack shows the designer of stream cipher should use Boolean functions with low degree carefully.

algebraic approach; Boolean function; cryptanalysis; cryptology

TN918.1

A

10.3969/j.issn.1001-0548.2010.06.006

2009- 04- 10;

2009- 07- 08

國家自然科學(xué)基金(60833008，60803149)；國家973計劃(2007CB311201)

楊文峰(1971- )，男，博士生，副教授，主要從事密碼學(xué)方面的研究.