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

楊文峰，胡予濮，高軍濤

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

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

楊文峰，胡予濮，高軍濤

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

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

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

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

在流密碼分析中，攻擊者常常會(huì)遇到以下兩種情形：一種情形是攻擊者無(wú)法通過(guò)公開(kāi)途徑獲得密碼算法，盡管文獻(xiàn)[4]指出流密碼的安全性不應(yīng)該依賴(lài)于密碼算法的保密性，而應(yīng)僅依賴(lài)于密鑰的保密性，但實(shí)際中使用的流密碼算法往往是不公開(kāi)的[1]。另一種情形是密碼算法使用的布爾函數(shù)是由密鑰控制的[5]。對(duì)于這兩種情形，攻擊者的任務(wù)是不但要恢復(fù)密鑰而且必須恢復(fù)布爾函數(shù)。密碼分析過(guò)程中，布爾函數(shù)的恢復(fù)往往都是利用統(tǒng)計(jì)方法求取其真值表。統(tǒng)計(jì)方法的致命弱點(diǎn)是所需數(shù)據(jù)量巨大，使得攻擊者往往因?yàn)閿?shù)據(jù)量有限而只能求得布爾函數(shù)的部分真值表。因此，如何通過(guò)布爾函數(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á)式和真值表之間存在著一一對(duì)應(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ù)的各種表示方法之間是相互等價(jià)的，只要知道了其中的一種表示方法就可以唯一確定其他的表示方法。

為了防止已知的各種攻擊方法，密碼學(xué)中使用的布爾函數(shù)必須滿(mǎn)足一定的密碼學(xué)指標(biāo)，其中主要有次數(shù)(代數(shù)次數(shù)和非線(xiàn)性次數(shù))、均衡性、相關(guān)免疫性、嚴(yán)格雪崩準(zhǔn)則和擴(kuò)散準(zhǔn)則等。已有的研究結(jié)果表明，布爾函數(shù)各項(xiàng)指標(biāo)之間是相互沖突、相互制約的，所以密碼設(shè)計(jì)者總是無(wú)法設(shè)計(jì)出各項(xiàng)指標(biāo)都能達(dá)到最優(yōu)的布爾函數(shù)。由于攻擊者是尋求利用布爾函數(shù)的最弱的一點(diǎn)采取攻擊，這就使得設(shè)計(jì)者設(shè)計(jì)布爾函數(shù)時(shí)不得不采取各項(xiàng)密碼學(xué)指標(biāo)折衷的思想。充分挖掘利用密碼學(xué)指標(biāo)之間的制約關(guān)系正是解決本文中問(wè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必須滿(mǎn)足d≤n?1?m，即布爾函數(shù)的相關(guān)階m越大，代數(shù)次數(shù)d就越小。當(dāng)設(shè)計(jì)者為了防止相關(guān)攻擊[9-10]而不得不提高布爾函數(shù)的相關(guān)免疫階和犧牲布爾函數(shù)的次數(shù)時(shí)，就為利用布爾函數(shù)的部分真值表還原整個(gè)布爾函數(shù)提供了有利條件。只要已知的部分真值表中包含了d(d≤n?1)次布爾函數(shù)的全部信息，應(yīng)用代數(shù)攻擊的思想首先求出該函數(shù)的代數(shù)表達(dá)式，然后把真值表中未知函數(shù)值的自變量代入代數(shù)正規(guī)型就可以補(bǔ)全其真值表。

2 攻擊方法

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

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

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

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

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

(1)Q

(2)Q

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

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

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

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

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

3 攻擊實(shí)例

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

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

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

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

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

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

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

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

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

4 結(jié) 束 語(yǔ)

流密碼的安全往往取決于其密鑰流生成器中布爾函數(shù)的設(shè)計(jì)質(zhì)量。在未知密碼算法或者由密鑰控制布爾函數(shù)的流密碼分析過(guò)程中，布爾函數(shù)的恢復(fù)是首先要解決的問(wèn)題。另外，密碼分析中的許多問(wèn)題都可以轉(zhuǎn)化為布爾函數(shù)的分析。當(dāng)攻擊者占有的數(shù)據(jù)有限時(shí)，只能求出部分真值表。本文利用布爾函數(shù)的次數(shù)和相關(guān)免疫階的制約關(guān)系提出了一種基于代數(shù)攻擊思想的布爾函數(shù)還原方法。當(dāng)已知的部分真值表包含所求布爾函數(shù)的全部信息時(shí)，該方法就可以唯一確定布爾函數(shù)。攻擊方法的計(jì)算復(fù)雜度低，實(shí)現(xiàn)簡(jiǎ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]汪小芬, 李勝?gòu)?qiáng), 肖國(guó)鎮(zhèn). 認(rèn)證群密鑰協(xié)商協(xié)議的安全性分析與改進(jìn)[J]. 電子科技大學(xué)學(xué)報(bào), 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

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

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