多输出前馈模型的代数攻击方法研究
|
摘要
代数攻击是目前密码学领域的研究热点之一。本文对多输出前馈模型的代数攻击进行了深入的研究,主要做出了以下几方面的工作:
1.对多输出布尔函数的零化函数进行了研究。给出了零化函数集合的代数结构,证明了多输出布尔函数的零化函数集合是布尔函数环的一个理想;分析了零化函数与分量函数组合的零化子之间的关系,证明了多输出函数在某点的零化函数集合与分量函数的某组合的零化子集合是相等的;对文献[19]的寻找布尔函数零化子的方法进行了分析,提出了两个寻找多输出函数的零化函数的算法。
2.对多输出布尔函数的代数免疫阶进行了研究。给出了多输出函数三种代数免疫阶之间的大小关系,证明了从零化函数角度定义的代数免疫阶与非线性代数免疫阶是相等的;给出了多输出函数的代数免疫阶与函数的平衡性和非线性性这两种密码学性质的相互关系;证明了,n进m出多输出函数的代数免疫阶的上界为|(n-1)/2|;分析了文献[35]中计算布尔函数代数免疫阶的算法,提出了计算多输出函数代数免疫阶的方法。
3.对前馈模型序列密码的代数攻击进行了研究。利用零化函数,给出对多输出前馈模型的代数攻击方法;利用不同时刻单输出前馈模型中布尔函数的输入状态的相关性,将布尔函数转化为多输出布尔函数进行研究,利用零化函数找到关于密钥的低次方程组,从而提出了对单输出前馈模型的改进代数攻击算法。该算法在一般情况下均优于文献[14]给出的攻击方法,并且在某些前馈模型中该算法优于快速代数攻击,最后通过实验对该结果进行了验证。对弱化的LILI-128算法,该算法的存储复杂度和计算复杂度均与快速代数攻击相同,而所需密钥流比特数却远远小于快速代数攻击。
Algebraic attack is one of the focuses in the cryptography nowadays. In this paper we will study the algebraic attack on stream ciphers with several outputs deeply, our contributions mainly include the following three parts:
1. We study the annihilator functions of multi-outputs Boolean function. We give the algebraic structure of the set of annihilator functions, prove that the set of annihilator functions of multi-outputs Boolean function is equal to the set of annihilator of combinatorial function of component functions; analyze the method of finding annihilator of Boolean function in [19], present two methods of finding annihilator functions of multi-outputs Boolean function.
2. We study the algebraic immunity of multi-outputs Boolean function. We show the relation of three algebraic immunity, prove that the algebraic immunity of annihilator functions is equal to the algebraic immunity of combinatorial function of component functions; show the relationship between algebraic immunity and other cryptographic properties, such as balance and nonlinearity; prove that the upper bound algebraic immunity of n-inputs m-outputs Boolean function is [(n-1)/2]; analyze the method of computing the algebraic immunity in [35], present a method of computing the algebraic immunity of multi-outputs function.
3. We study the algebraic attack on stream ciphers with linear feedback. We give the method of algebraic attack on stream ciphers with multi-outputs using the annihilator function; using the relativity between inputs of Boolean function in stream with linear feedback of different clock, convert Boolean function to multi-outputs Boolean function, and find low-degree functions about the key using annihilator functions, thereby gain the improved algebraic attack on stream ciphers with linear feedback. Finally, we analyze the computational complexity of our attack which is better than the algebraic attack in [14], and in some stream ciphers with linear feedback, our attack is better than fast algebraic attack, and test the result by computer simulations; the memory complexity and the computation complexity of our attack on simplified version of LILI-128 are equal to fast algebraic attack, but the date complexity is much lower.
1.对多输出布尔函数的零化函数进行了研究。给出了零化函数集合的代数结构,证明了多输出布尔函数的零化函数集合是布尔函数环的一个理想;分析了零化函数与分量函数组合的零化子之间的关系,证明了多输出函数在某点的零化函数集合与分量函数的某组合的零化子集合是相等的;对文献[19]的寻找布尔函数零化子的方法进行了分析,提出了两个寻找多输出函数的零化函数的算法。
2.对多输出布尔函数的代数免疫阶进行了研究。给出了多输出函数三种代数免疫阶之间的大小关系,证明了从零化函数角度定义的代数免疫阶与非线性代数免疫阶是相等的;给出了多输出函数的代数免疫阶与函数的平衡性和非线性性这两种密码学性质的相互关系;证明了,n进m出多输出函数的代数免疫阶的上界为|(n-1)/2|;分析了文献[35]中计算布尔函数代数免疫阶的算法,提出了计算多输出函数代数免疫阶的方法。
3.对前馈模型序列密码的代数攻击进行了研究。利用零化函数,给出对多输出前馈模型的代数攻击方法;利用不同时刻单输出前馈模型中布尔函数的输入状态的相关性,将布尔函数转化为多输出布尔函数进行研究,利用零化函数找到关于密钥的低次方程组,从而提出了对单输出前馈模型的改进代数攻击算法。该算法在一般情况下均优于文献[14]给出的攻击方法,并且在某些前馈模型中该算法优于快速代数攻击,最后通过实验对该结果进行了验证。对弱化的LILI-128算法,该算法的存储复杂度和计算复杂度均与快速代数攻击相同,而所需密钥流比特数却远远小于快速代数攻击。
Algebraic attack is one of the focuses in the cryptography nowadays. In this paper we will study the algebraic attack on stream ciphers with several outputs deeply, our contributions mainly include the following three parts:
1. We study the annihilator functions of multi-outputs Boolean function. We give the algebraic structure of the set of annihilator functions, prove that the set of annihilator functions of multi-outputs Boolean function is equal to the set of annihilator of combinatorial function of component functions; analyze the method of finding annihilator of Boolean function in [19], present two methods of finding annihilator functions of multi-outputs Boolean function.
2. We study the algebraic immunity of multi-outputs Boolean function. We show the relation of three algebraic immunity, prove that the algebraic immunity of annihilator functions is equal to the algebraic immunity of combinatorial function of component functions; show the relationship between algebraic immunity and other cryptographic properties, such as balance and nonlinearity; prove that the upper bound algebraic immunity of n-inputs m-outputs Boolean function is [(n-1)/2]; analyze the method of computing the algebraic immunity in [35], present a method of computing the algebraic immunity of multi-outputs function.
3. We study the algebraic attack on stream ciphers with linear feedback. We give the method of algebraic attack on stream ciphers with multi-outputs using the annihilator function; using the relativity between inputs of Boolean function in stream with linear feedback of different clock, convert Boolean function to multi-outputs Boolean function, and find low-degree functions about the key using annihilator functions, thereby gain the improved algebraic attack on stream ciphers with linear feedback. Finally, we analyze the computational complexity of our attack which is better than the algebraic attack in [14], and in some stream ciphers with linear feedback, our attack is better than fast algebraic attack, and test the result by computer simulations; the memory complexity and the computation complexity of our attack on simplified version of LILI-128 are equal to fast algebraic attack, but the date complexity is much lower.
引文
[1] N. Koblitz. Cryptanalysis of the HFE Public Key Cryptosystem [C]. Proceedings of Crypto'99, Spr,1999.
[2] N. Courtois. The security of Hidden Field Equation [C]. CTRSA 2001, LNCS 2020, Springer-Verlag, pp.266-281,2001.
[3] N. Courtois, A. Klimov, J. Patarin and A. Shamir. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations [C]. Advances in Cryptology- Eurocrypt 2000, LNCS 1807, pp.392-407, 2000.
[4] N. Courtois and J. Pieprzyk. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations [C].Asiacrypt 2002, LNCS 2501, Springer-Verlag, pp. 267-287, 2002.
[5] N. Courtois. How Fast can be Algebraic Attacks on Block Ciphers ? [EB]. Dagstuhl Seminar Proceedings 07021, Symmetric Cryptography, http://drops.dagstuhl.de/opus/volltexte/2007/1013. 2007.
[6] O. Dunkelman, N. Keller. Linear Cryptanalysis of CTC [EB]. Cryptology ePrint archive, Report 2006/250, 2006.
[7] N. Courtois, G. Bard. Algebraic Cryptanalysis of the Data Encryption Standard [EB]. Cryptology ePrint archive, Report 2006/168,2006.
[8] G Bard, N. Courtois, C. Jefferson. Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials over GF(2) via SAT- Solvers [EB]. Available from IACR eprint server, http://www.iacr.org/2007/024.2007.
[9] N. Een, N. Sorensson. An Extensible SAT Solver [C]. In Proc. SAr03, volume 2919 of LNCS. 2003
[10] N. Courtois, G Bard. Algebraic and Slide Attacks on Keeloq [EB]. Available from IACR eprint server,Cryptology ePrint archive, Report 2007/062, 2007
[11] N. S(?)rensson. Minisat SAT algorithm and applications [R]. nik@cs.chalmers.se, 2005.
[12] A. Bogdanov. Cryptanalysis of the KeeLoq block cipher [EB]. http://eprint.iacr.org/2007/055, 2007.
[13] F. Armkncht. A Linearization Attack on the Bluetooth Key Stream Generator [EB]. Available from IACR eprint server, Cryptology ePrint archive, Report 2002/191,2002.
[14] N.Courtois and W.Meier. Algebraic Attacks on Stream Ciphers with Linear Feedback(Extended version)[EB], available at http://www.Crvptosvstem.net/stream/. 2003.
[15] M. Juhani, O. Saarinen. A time-memory tradeoff attack against LILI-128 [C]. FSE2002, LNCS 2365,Springer, pp. 231-236, 2002
[16] N.Courtois. Fast Algebraic Attacks on Stream Ciphers with Linear Feedback [J]. In Advances in Cryptology-CRYPTO 2003,2003.
[17] F. Armknecht, M. Krause. Algebraic Attacks on Combiners with Memory [C]. In CRYPTO 2003, LNCS 2729, Springer-Verlag, pp. 162-175, 2003.
[18] N. Courtois, Algebraic attacks on combiners with memory and memory and several outputs [R].Technical Report 2003/125,2003.
[19] W. Meier, E. Pasalic, C.Carlet. Algebraic Attacks and Decomposition of Boolean Functions [J]. In Advances in Cryptology-EUROCRYPT 2004,LNCS 3027,Springer Verlag,pp.474-491,2004.
[20]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.
[21]F.Armknecht.Improving Fast Algebraic Attacks[J].Fast Software Encryption 2004,LNCS 3017,pp.65-82,Springer-Verlag,2003.
[22]P.Hawkes,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,Springer-Verlag,pp.390-406,2004.
[23]L.Batten.Algebraic Attacks over GF(q)[C].Indocrypt 2004,LNCS 3348,pp.84-91,2004.
[24]D.H.Lee,J.Kim,J.Hong,J.W.Han.D.Moon.Algebraic Attacks on Summation Generators[EB].Cryptology ePrint archive,Report 2003/229,2003.
[25]N.Courtois.Higher Order Correlation Attacks,XL Algorithm and Cryptoanalysis of Toyocrypt[J].In ICISC 2002,LNCS 2587,Springer-Verlag,pp.182-199,2002.
[26]张龙,吴文玲,温巧燕.流密码代数攻击的研究现状及其展望[J].通信学报,2006,27(1):91-98.
[27]A Iyad.Ajwa,L Z Jun,W Paul.Gr(o|¨)bner Bases Algorithm[R].2003 Department of Mathematics &Computer Science,2003.
[28]F.Armknecht.On the Existence of Low-degree Equations for Algebraic Attacks[R].Cryptology ePrint Archive,Report 2004/185,http://eprint.iacr.org/,2004.
[29]冯登国.密码分析学[M].清华大学出版社,2000.
[30]李世取,曾本胜等.密码学中的逻辑函数[M].中软出版社,2003.
[31]温巧燕,钮心忻,杨义先.现代密码学中布尔函数[M].科学出版社,2000.
[32]D.Dalai,K.Gupta,S.Maitra.Results on Algebraic Immunity for Cryptographically Significant Boolean Functions[J].In Indocrypt 2004,LNCS 3348,pp.92-106,Springer,2004.
[33]张文英,武传坤.密码学中布尔函数的零化子[J].电子学报,Vol.34,No.1,2006,pp.51-54,2006.
[34]聂灵沼,丁石孙.代数学引论[M].高等教育出版社,2000.
[35]F.Didier,J.Tillich.Computing the Algebraic Immunity Efficiently[J].FSE 2006,LNCS 4047,pp.359-374,2006.
[36]F.Armknecht,C.Carlet,P.Gaborit,S.K(u|¨)nzli.Efficient Computation of Algebraic Immunity for Algebraic and Fast Algebraic Attacks[C].In Proc.EUROCRYPT 2006(Lecture Notes in Computer Science),Springer-Verlag,LNCS 4004,pp.147-164,2006.
[37]F.Armknecht.M.Krause.Constructing Single-and Multi-output Boolean Functions with Maximal Algebraic Immunity.ICALP 2006,Part Ⅱ,LNCS 4052,pp.180-191,2006.
[38]D.Dalai,K.Gupta,S.Maitra.Cryptographically Significant Boolean functions:Construction and Analysis in Terms of Algebraic Immunity[J].In Fast Software Encryption 2005,LNCS 3557,Springer-Verlag,pp.98-111,2005.
[39]M.Lobanov.Tight Bound Between Nonlinearity and Algebraic Immunity[R].Cryptology ePrint Archive,Report 2005/441,2005.
[40]C.Carlet.A Lower Bound on the Higher Order Nonlinearity of Algebraic Immune Functions[R]. Cryptology ePrint Archive. Report 2005/469,2005.
[41] J. Golic. On the security of nonlinear filter generators. In Dieter Gollmann[C], FSE, LNCS 1039, pp.173-188,1996.
[42] S. Babbage. Cryptanalysis of LILI-128 [R]. NESSIE Public Report,http://www.cosic.esat.kuleuven.ac.be/nessie/reports. 2001.
[2] N. Courtois. The security of Hidden Field Equation [C]. CTRSA 2001, LNCS 2020, Springer-Verlag, pp.266-281,2001.
[3] N. Courtois, A. Klimov, J. Patarin and A. Shamir. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations [C]. Advances in Cryptology- Eurocrypt 2000, LNCS 1807, pp.392-407, 2000.
[4] N. Courtois and J. Pieprzyk. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations [C].Asiacrypt 2002, LNCS 2501, Springer-Verlag, pp. 267-287, 2002.
[5] N. Courtois. How Fast can be Algebraic Attacks on Block Ciphers ? [EB]. Dagstuhl Seminar Proceedings 07021, Symmetric Cryptography, http://drops.dagstuhl.de/opus/volltexte/2007/1013. 2007.
[6] O. Dunkelman, N. Keller. Linear Cryptanalysis of CTC [EB]. Cryptology ePrint archive, Report 2006/250, 2006.
[7] N. Courtois, G. Bard. Algebraic Cryptanalysis of the Data Encryption Standard [EB]. Cryptology ePrint archive, Report 2006/168,2006.
[8] G Bard, N. Courtois, C. Jefferson. Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials over GF(2) via SAT- Solvers [EB]. Available from IACR eprint server, http://www.iacr.org/2007/024.2007.
[9] N. Een, N. Sorensson. An Extensible SAT Solver [C]. In Proc. SAr03, volume 2919 of LNCS. 2003
[10] N. Courtois, G Bard. Algebraic and Slide Attacks on Keeloq [EB]. Available from IACR eprint server,Cryptology ePrint archive, Report 2007/062, 2007
[11] N. S(?)rensson. Minisat SAT algorithm and applications [R]. nik@cs.chalmers.se, 2005.
[12] A. Bogdanov. Cryptanalysis of the KeeLoq block cipher [EB]. http://eprint.iacr.org/2007/055, 2007.
[13] F. Armkncht. A Linearization Attack on the Bluetooth Key Stream Generator [EB]. Available from IACR eprint server, Cryptology ePrint archive, Report 2002/191,2002.
[14] N.Courtois and W.Meier. Algebraic Attacks on Stream Ciphers with Linear Feedback(Extended version)[EB], available at http://www.Crvptosvstem.net/stream/. 2003.
[15] M. Juhani, O. Saarinen. A time-memory tradeoff attack against LILI-128 [C]. FSE2002, LNCS 2365,Springer, pp. 231-236, 2002
[16] N.Courtois. Fast Algebraic Attacks on Stream Ciphers with Linear Feedback [J]. In Advances in Cryptology-CRYPTO 2003,2003.
[17] F. Armknecht, M. Krause. Algebraic Attacks on Combiners with Memory [C]. In CRYPTO 2003, LNCS 2729, Springer-Verlag, pp. 162-175, 2003.
[18] N. Courtois, Algebraic attacks on combiners with memory and memory and several outputs [R].Technical Report 2003/125,2003.
[19] W. Meier, E. Pasalic, C.Carlet. Algebraic Attacks and Decomposition of Boolean Functions [J]. In Advances in Cryptology-EUROCRYPT 2004,LNCS 3027,Springer Verlag,pp.474-491,2004.
[20]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.
[21]F.Armknecht.Improving Fast Algebraic Attacks[J].Fast Software Encryption 2004,LNCS 3017,pp.65-82,Springer-Verlag,2003.
[22]P.Hawkes,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,Springer-Verlag,pp.390-406,2004.
[23]L.Batten.Algebraic Attacks over GF(q)[C].Indocrypt 2004,LNCS 3348,pp.84-91,2004.
[24]D.H.Lee,J.Kim,J.Hong,J.W.Han.D.Moon.Algebraic Attacks on Summation Generators[EB].Cryptology ePrint archive,Report 2003/229,2003.
[25]N.Courtois.Higher Order Correlation Attacks,XL Algorithm and Cryptoanalysis of Toyocrypt[J].In ICISC 2002,LNCS 2587,Springer-Verlag,pp.182-199,2002.
[26]张龙,吴文玲,温巧燕.流密码代数攻击的研究现状及其展望[J].通信学报,2006,27(1):91-98.
[27]A Iyad.Ajwa,L Z Jun,W Paul.Gr(o|¨)bner Bases Algorithm[R].2003 Department of Mathematics &Computer Science,2003.
[28]F.Armknecht.On the Existence of Low-degree Equations for Algebraic Attacks[R].Cryptology ePrint Archive,Report 2004/185,http://eprint.iacr.org/,2004.
[29]冯登国.密码分析学[M].清华大学出版社,2000.
[30]李世取,曾本胜等.密码学中的逻辑函数[M].中软出版社,2003.
[31]温巧燕,钮心忻,杨义先.现代密码学中布尔函数[M].科学出版社,2000.
[32]D.Dalai,K.Gupta,S.Maitra.Results on Algebraic Immunity for Cryptographically Significant Boolean Functions[J].In Indocrypt 2004,LNCS 3348,pp.92-106,Springer,2004.
[33]张文英,武传坤.密码学中布尔函数的零化子[J].电子学报,Vol.34,No.1,2006,pp.51-54,2006.
[34]聂灵沼,丁石孙.代数学引论[M].高等教育出版社,2000.
[35]F.Didier,J.Tillich.Computing the Algebraic Immunity Efficiently[J].FSE 2006,LNCS 4047,pp.359-374,2006.
[36]F.Armknecht,C.Carlet,P.Gaborit,S.K(u|¨)nzli.Efficient Computation of Algebraic Immunity for Algebraic and Fast Algebraic Attacks[C].In Proc.EUROCRYPT 2006(Lecture Notes in Computer Science),Springer-Verlag,LNCS 4004,pp.147-164,2006.
[37]F.Armknecht.M.Krause.Constructing Single-and Multi-output Boolean Functions with Maximal Algebraic Immunity.ICALP 2006,Part Ⅱ,LNCS 4052,pp.180-191,2006.
[38]D.Dalai,K.Gupta,S.Maitra.Cryptographically Significant Boolean functions:Construction and Analysis in Terms of Algebraic Immunity[J].In Fast Software Encryption 2005,LNCS 3557,Springer-Verlag,pp.98-111,2005.
[39]M.Lobanov.Tight Bound Between Nonlinearity and Algebraic Immunity[R].Cryptology ePrint Archive,Report 2005/441,2005.
[40]C.Carlet.A Lower Bound on the Higher Order Nonlinearity of Algebraic Immune Functions[R]. Cryptology ePrint Archive. Report 2005/469,2005.
[41] J. Golic. On the security of nonlinear filter generators. In Dieter Gollmann[C], FSE, LNCS 1039, pp.173-188,1996.
[42] S. Babbage. Cryptanalysis of LILI-128 [R]. NESSIE Public Report,http://www.cosic.esat.kuleuven.ac.be/nessie/reports. 2001.