摘要
2003年法国密码学专家N.Courtois提出代数攻击以来,代数攻击被广泛用于分析各类密码算法,密码算法中布尔函数的代数免疫性能已成为判断布尔函数密码学性能好坏的一个重要准则。
目前,代数攻击最成功的实例是针对序列密码Toyocrypt和LILI-128的攻击。文献利用这两个密码算法中非线性函数各自存在的低次零化子,建立了关于输入、输出和密钥的低次方程组,成功破译了这两个算法。通过分析我们发现,这两个算法所使用的非线性函数的补函数也存在低次零化子,且数量与原函数的低次零化子数量相同,利用这一点,我们可建立两倍于文献的代数方程,使得代数攻击破译这两个算法所需明密文对的数量减少了一半。
对安全性基于非线性布尔函数的密码算法,找出其非线性布尔函数的低次零化子是利用代数攻击方法破译这类密码算法成效的关键。本文利用布尔函数支撑点逻辑相邻关系和函数代数次数的联系,给出了一种计算布尔函数低次零化子的新方法——卡诺图法,并分析了卡诺图法和目前几个有代表性的计算布尔函数零化子算法的区别和联系。
布尔函数的代数免疫阶是体现布尔函数抗代数攻击能力强弱的重要指标。本文分析了两个布尔函数相加生成新函数的代数免疫阶的变化情况,还给出了布尔函数通过非线性级联组合生成新函数的代数免疫阶变化结果。同时,文章还对这两种函数组合方式在均衡布尔函数其它密码学性质上的作用进行了分析。另外,文章还分析了布尔函数代数免疫阶与布尔函数汉明重量、非线性度、相关免疫阶等密码学性质之间的相互关系。
最大代数免疫阶布尔函数是一类抗代数攻击最有效的布尔函数。文章证明了最大代数免疫阶平衡布尔函数本身及其补函数都存在代数次数为代数免疫阶的零化子。文章还对一种最大代数免疫阶布尔函数——择多函数进行了分析,研究了这种函数的平衡性、对称性、Walsh循环谱、自相关性、非线性度以及相关免疫阶等密码学性质。文章还介绍了三种已有的构造最大代数免疫阶布尔函数的方法,重点分析了这三种构造函数的一些其它密码学性质。
Since algebraic attack method was proposed by Gallo cryptographist N.Courtois in 2003, it had been extensively used to analyze various cryptogram algorithms. The algebraic immune capability of Boolean function in cryptogram algorithm has already become an important criteria to judge the cryptographic capability of Boolean function.
At present, the most successful examples of using algebraic attack on cryptogram algorithms are the attacks on stream ciphers Toyocrypt and LILI-128. Paper [4] has successfully broken out the two algorithms by building up some low-degree equations concerning inputs, outputs and keywords, using the low-degree annihilators of the nonlinear Boolean functions in the two algorithms. The same amount of low-degree annihilators are also found in the complementary functions of the nonlinear functions in the two algorithms. Consequently, double equations as paper[4] can be built up to reduce half the quantity of pairs of plain-ciphertext used to attack the two algorithms.
To break out the cryptogram algorithms whose parameter of safety lies on the nonlinearity Boolean function using algebraic attack, what is the most important factor of attack efficiency is to find out the low-degree annihilators of the nonlinear Boolean functions. Making a good use of the relation between the logic border elements in the support set and the algebraic degree of the Boolean function, we got a new method to work out the low-degree annihilators of the Boolean function, called Karnargh Graphics Method. Its dissimilarity and affiliation to some typical methods used currently are expounded in the paper.
The algebraic immunity (AI) of Boolean function is the significant index for Boolean function's capacity to resist algebraic attack. This thesis gives the change of the AI of new function, when it is combined by two Boolean functions adding mutually, and the change of the AI of new function, when it is combined by some Boolean functions concatenating together. Meanwhile, we analyze how the two function-combining modes work on proportioning the other cryptographic properties. In addition, this paper shows the relationship between AI and other cryptographic properties, such as Hamming Weight, nonlinearity, correlation immunity etc.
Boolean function with maximum AI is one of the most effective Boolean functions to resist algebraic attack. This paper proves that the annihilators with algebraic degree at AI exist both in the balance Boolean function with maximum AI and its complementary function. We have also talked about a sort of Boolean function with maximum AI called select-more function, and studied its balance, symmetry, Walsh transform, self-correlation, nonlinearity and correlation immunity etc. Three methods of construction of Boolean function with maximum AI are mentioned in this paper, and some other cryptographic properties of the three construction functions are unfolded as emphases.
引文
[1]N.Courtois and W.Meier.Algebraic Attacks on Stream Ciphers with Linear Feedback[J].In Advances in Cryptology-EUROCRYPT 2003,volume LNCS 2656,pages 346-359.Springer-Verlag,2003.
[2]胡予濮,张玉清,肖国镇.对称密码学[M].北京:机械工业出版社,2002.
[3]李世取,曾本胜等.密码学中的逻辑函数[M].北京:中软出版社,2003.
[4]N.Courtois and W.Meier.Algebraic Attacks on Stream Ciphers with Linear Feedback(Extended version)[EB/OL],available at http://www.Cryptosystem.net/stream/,2003.
[5]AdiShamir.Stream Ciphers:Dead orAlive?[R].In Asiacrypt2004,78.
[6]Neal Koblitz.Cryptanalysis of the HFE Public Key Cryptosystem[C].Proceedings ofCrypto'99,Spr,1999.
[7]N.Courtois and J.Pieprzyk.Cryptanalysis of Block Ciphers with Overdefined Systems of Equations[J].Asiacrypt2002,LNCS2501,Springer-Verlag,pp.267-287,2002.
[8]N.Courtois.Fast Algebraic Attacks on Stream Ciphers with Linear Feedback[J].In Advances in Cryptology-CRYPTO 2003,2003.
[9]W.Meier,E.Pasalic and C.Carlet.Algebraic Attacks and Decomposition of Boolean Functions[J].In Advances in Cryptology-EUROCRYPT 2004,number 3027 in Lecture Notes in Computer Science,pages 474-491,SpringerVerlag,2004.
[10]N.Courtois,A.Klimov,J.Patarin and A.Shamir.Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations.Advances in Cryptology-Eurocrypt 2000 1807,392-407,2000.
[11]张文英,武传坤.密码学中布尔函数的零化子[J].电子学报,Vol.34,No.1,2006,pp.51-54,2006.
[12]Frederic Didier and Jean-Pierre Tillich.Computing the Algebraic Immunity Efficiently[J].FSE 2006,LNCS 4047,pp.359-374,2006.
[13]F.Armknecht.On the Existence of Low-degree Equations for Algebraic Attacks[R].Cryptology ePrint Archive,Report2004/185,http://eprint.iacr.org/,2004.
[14]阎石.数字电子技术基础(第四版)[M].北京:高等教育出版社,1997.
[15]罗卫华,李超,周海银.布尔函数的代数免疫性研究[J].计算机工程与应用,2007,43(8),pp59-61.
[16]A.Canteaut.Invited talk:Open Problems Related to Algebraic Attacks on Stream Ciphers[R].In Proceedings of the 2005 International Workshop on Coding and Cryptography(WCC 2005),Bergen,Norway,To appear in LNCS,2005.
[17]D.K..Dalai,K.C.Gupta and S.Maitra.Results on Algebraic Immunity for Cryptographically Significant Boolean Functions[J].In Indocrypt 2004,LNCS 3348,pp.92-106,Springer,2004.
[18]E.Pasalic.On Boolean Functions with Maximum Algebraic Immunity[R].Cryptology ePrint Archive:Report 2005/437,2005.
[19]D.K..Dalai,K.C.Gupta and S.Maitra.Cryptographically Significant Boolean functions:Construction and Analysis in Terms of Algebraic Immunity[J].In Fast Software Encryption 2005,volume LNCS 3557,pages 98-111,Springer-Verlag,2005.
[20]C.Carlet,D.K.Dalai,K.C.Gupta and S.Maitra.Algebraic Immunity for Cryptographically Significant Boolean Functions:Analysis and Construction[J].IEEE Transactions on Information Theory,VOL.52,NO.7,pages3105-3120,July2006.
[21]D.K.Dalai,S.Maitra and S.Sarkar.Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity[J].Cryptology ePrint Archive,http://eprint.iacr.org/,No.2005/229,15July,2005.To be published in Designs,Codes and Cryptography.
[22]M.Lobanov.Tight Bound Between Nonlinearity and Algebraic Immunity[R].Cryptology ePrint Archive,Report2005/441,http://eprint.iacr.org/,2005.
[23]C.Carlet.A Lower Bound on the Higher Order Nonlinearity of Algebraic Immune Functions[R].CryptologyePrintArchive,http://eprint.iacr.org/,Report2005/469,2005.
[24]Qu L J,Feng G Z and Li C.On the Boolean Functions with Maximum Possible Algebraic Immunity:Construction and A Lower Bound of the Count[EB/OL].http://eprint.iacr.org/20051449,2005.
[25]A.Braeken and B.Preneel.On the Algebraic Immunity of Symmetric Boolean Functions[C].Accepted at Indocrypt,2005.
[26]P.Sarkar and S.Maitra.Construction of Nonlinear Boolean Functions with Important Cryptographic Properties[J].In EUROCRYPT 2000,number 1807 in Lecture Notes in Computer Science,pages 485-506,Springer Verlag,May2000.
[27]何良生.一类具有最高代数免疫阶的布尔函数[J].计算机学报,Vol.29,No.9,PP.1579-1583,Sept.2006.
[28]C.Carlet.Improving the Algebraic Immunity of Resilient and Nonlinear Functions and Constructing Bent Functions[EB].IACRePrint server,http://eprint.iacr.org/2004/276/,2004.
[29]F.Armknecht,C.Carlet,EGaborit,S.K(u|¨)nzli,W.Meier and O.Ruatta.Efficient Computation of Algebraic Immunity for Algebraic and Fast Algebraic Attacks[C].In Proc.EUROCRYPT 2006(Lecture Notes in Computer Science),Berlin,Germany,Springer-Verlag,vol.4004,pp.147-164,2006.
[30]F.Armknecht.Improving Fast Algebraic Attacks[J].Fast Software Encryption 2004,LNCS 3017,pp.65-82,Springer-Verlag,2003.
[31]Faugere J C,Joux A.Algebraic Cryptanalysis of Hidden Field Equation(HFE) Cryptosystems Using Grobner Bases[J].Cryptology-CRYPTO'2003,Lecture Notes in Computer Science 2729,Berlin,Springer-Verlag,pp.44-66,2003.
[32]N.Courtois and Bard G V.Algebraic Cryptanalysis of the Data Encryption Standard[EB/OL].http://www.eprint.iacr.org/2006/168,2006.
[33]C.Carlet.A Method of Construction of Balanced Functions with Optimum Algebraic Immunity[EB/OL].Available at http://eprint.iac.rg/2006/149,April,16,2006.
[34]Y.Nawazl,GuangGong and K.C.Gupta.Upper Bounds on Algebraic Immunity of Power Functions[J].FSE2006,LNCS4047,pp.375-389,2006.
[35]张莉.代数攻击的若干问题研究[D].西安:西安电子科技大学硕士学位论文,2005.
[36]陈杰.对流密码中代数攻击的研究[D].西安:西安电子科技大学硕士学位论文,2005.
[37]Na Li and Wen-Feng Qi.Symmetric Boolean Functions Depending on an Odd Number of Variables with Maximum Algebraic Immunity[J].IEEE Transactions on Information Theory,Vol.52,No.5,May 2006.
[38] A.Botev. On Algebraic Immunity of some Recursively Given Sequence of Correlation Immune Functions[C]. In Proceedings of XV International Workshop on Synthesis and Complexity of Control Systems (in Russian), Novosibirsk, Oct.18-23, pp.8-12, 2004.
[39] C.Carlet. A Larger Class of Cryptographic Boolean Functions Via a Study of the Maiorana-McFarland Construction[J]. In Advances in Cryptology—CRYPTO 2002 (Lecture Notes in Computer Science),Berlin, Germany, Springer-Verlag, vol.2442, pp.549-564, 2002.
[40] D.K.Dalai, K.C.Gupta and S.Maitra. Notion of Algebraic Immunity and Its Evaluation Related to Fast Algebraic Attacks[C]. In Proc. 2nd Int, Workshop on Boolean Functions: Cryptography and Applications(BFCA 2006), Rouen, France, Mar.2006 [Online]. Available: eprint.iacr.org
[41] E.Pasalic, S.Maitra, T.Johansson and P.Sarkar. New Constructions of Resilient and Correlation Immune Boolean Functions Achieving Upper Bounds on Nonlinearity. In Workshop on Coding and Cryptography—WCC 2001 (Electronic Notes in Discrete Mathematics), Amsterdam, The Netherlands:Elsevier Science, 2001, vol.6.
[42] J.-C. Faugere and G. Ars. An Algebraic Cryptanalysis of Nonlinear Filter Generators Using Grobner Bases[J]. In Rapport de Recherche INRIA, volume 4739, 2003.
[43] An Braeken, Joseph Lano and Bart Preneel. Evaluating the Resistance of Stream Ciphers with Linear Feedback Against Fast Algebraic Attacks[J]. ACISP 2006, LNCS 4058, pp.40-51, 2006.
[44] P.Hawkes and G.Rose. Rewriting variables: The Complexity of Fast Algebraic Attacks on Stream Ciphers[J]. In M. Franklin, editor, Crypto 2004, volume 3152 of Lecture Notes in Computer Science,pages 390-406, Springer-Verlag, 2004.
[45] D.K.Dalai and S.Maitra. Reducing the Number of Homogeneous Linear Equations in Finding Annihilators[C]. to appears in SETA 2006, 2006.
[46] C.Carlet. On the Secondary Constructions of Resilient and Bent Functions[C]. Proceedings of the 2003 Workshop on Coding, Cryptography and Combinatorics, BirkHauser Verlag, 2004.
[47] N.Courtois. How Fast can be Algebraic Attacks on Block Ciphers? [C]. Dagstuhl Seminar Proceedings 07021, Symmetric Cryptography, http://drops.dagstuhl.de/opus/volltexte/2007/1013, 2007.
[48] N.Courtois and J.Patarin. About the XL Algorithm over GF(2)[C]. In Topics in Cryptology-CT-RSA 2003: The Cryptographers' Track at the RSA Conference 2003, volume 2612 of Lecture Notes in Computer Science, pages pp.141 -157, Springer Verlag Heidelberg, 2003.
[49] C.Carlet . On Bent and Highly Nonlinear Balanced/Resilient Functions and Their Algebraic Immunities[J]. In AAECC2006, number 3857 in Lecture Notes in Computer Science, pages 1-28,Springer Verlag, 2006.
[50] S.Maitra and P.Sarkar. Maximum Nonlinearity of Symmetric Boolean Functions on Odd Number of Variables[J]. IEEE Transactions on Information Theory, 48(9): 2626-2630, September 2002.
[51] S.Maitra. Boolean Functions with Important Cryptographic Properties[C]. PhD The-sis, Indian Statistical Institute, 2000.
[52] C.Carlet and P.Gaborit. On the Construction of Balanced Boolean Functions with a Good Algebraic Immunity[J]. in Proc.BFCA (1st Workshop on Boolean Functions: Cryptography and Applications),Rouen, France, Mar.2005, pp.1-14, 2005.
[53] N.Courtois. Higher Order Correlation Attacks, XL Algorithm and Cryptoanalysis of Toyocrypt[J]. In ICISC 2002, volume LNCS 2587, pages 182-199, Springer-Verlag, 2002.
[54] A.Botev. On Algebraic Immunity of New Constructions of Filters with High Nonlinearity[C]. In Proceedings of VI international conference on Discrete models in the theory of control systems,Moscow, December 7-11, 2004, pages 227-230 (in Russian).